24点运算

C 解法, 执行用时: 2ms, 内存消耗: 320KB, 提交时间: 2022-02-08

#include <stdio.h>
#include <string.h>
//将读入字符转换为数字存储,判断是否有王
//DFS回溯遍历,剪枝函数 约束 used 限界 pos
//确定总的DFS深度 pos 4  每个深度上的分叉数+-*/,pos==0一定是+;
//用cal 记录数组和符号;
//将数组转化为字符串输出


int cal_num[4];
char cal_signal[4];
int flag;
int used[4] = {0};
void compute(int num[], int res, int pos);
int main()
{
  char card[10];
  int num[4];
  int joker_exist = 0;
  int i;
  for (i = 0; i < 4; i++)
  {
    scanf("%s", card);
    if (strstr(card, "joker") != NULL || strstr(card, "JOKER") != NULL)
      joker_exist = 1;
    else if (strstr(card, "10") != NULL)
      num[i] = 10;
    else if (card[0] == 'J')
      num[i] = 11;
    else if (card[0] == 'Q')
      num[i] = 12;
    else if (card[0] == 'K')
      num[i] = 13;
    else if (card[0] == 'A')
      num[i] = 1;
    else if (card[0] >= '0' && card[0] <= '9')
      num[i] = card[0] - '0';
  }

  int res = 0;
  int pos = 0;
  compute(num, res, pos);
  
  if (joker_exist == 1)
  {
    printf("ERROR\n");
  }
  else if (flag == 0)
  {
    printf("NONE\n");
  }
  else if (flag == 1)
  {
    //cal_num
    char res_card[4] = {'\0'};
    for (int i = 0; i < 4; i++)
    {
      switch (cal_num[i])
      {
      case 11:
        res_card[i] = 'J';
        break;
      case 12:
        res_card[i] = 'Q';
        break;
      case 13:
        res_card[i] = 'K';
        break;
      case 1:
        res_card[i] = 'A';
        break;
      default:
        res_card[i] = cal_num[i] + '0';
        break;
      }
    }
    printf("%c", res_card[0]);
    for (int i = 1; i < 4; i++)
    {
      printf("%c%c", cal_signal[i], res_card[i]);
    }
  }

  return 0;
}

//pos 计算到哪一个数 0 -3
void compute(int num[], int res, int pos)
{
  if (pos == 4)
  {
    if (res == 24)
      flag = 1;
    else
      flag = 0;
    return;
  }

  for (int i = 0; i < 4; i++)
  {
    if (used[i] == 0)
    {
      if (pos == 0)
      {
        used[i]++;
        res += num[i];
        cal_num[pos] = num[i];
        compute(num, res, pos + 1);
        if (flag == 1)
          break;
        res -= num[i];
        used[i]--;
      }
      else
      {
        used[i]++;
        res += num[i];
        cal_num[pos] = num[i];
        cal_signal[pos] = '+';
        compute(num, res, pos + 1);
        if (flag == 1)
          break;
        res -= num[i];
        used[i]--;

        used[i]++;
        res -= num[i];
        cal_num[pos] = num[i];
        cal_signal[pos] = '-';
        compute(num, res, pos + 1);
        if (flag == 1)
          break;
        res += num[i];
        used[i]--;

        used[i]++;
        res *= num[i];
        cal_num[pos] = num[i];
        cal_signal[pos] = '*';
        compute(num, res, pos + 1);
        if (flag == 1)
          break;
        res /= num[i];
        used[i]--;

        used[i]++;
        int temp = res;
        res /= num[i];
        cal_num[pos] = num[i];
        cal_signal[pos] = '/';
        compute(num, res, pos + 1);
        if (flag == 1)
          break;
        res = temp;
        used[i]--;
      }
    }
  }
}

C 解法, 执行用时: 2ms, 内存消耗: 332KB, 提交时间: 2022-02-09

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char face[14][2]={"0","A","2","3","4","5","6","7","8","9","10","J","Q","K"};
char sign[3];
char signal[4]={'+','-','*','/'};
int n=0;
char cal(int a[4]){
    float out;
    int i,j,k,m;
    for(i=0;i<4;i++){
        sign[0]=i;
        for(j=0;j<4;j++){
            sign[1]=j;
            for(k=0;k<4;k++){
                sign[2]=k;
                out=a[0];
                for(m=0;m<3;m++){
                    if(sign[m]==2)
                        out*=a[m+1];
                    else if(sign[m]==3)
                        out/=a[m+1];
                    else if(sign[m]==1)
                        out-=a[m+1];
                    else
                        out+=a[m+1];
                }
                if(out-24<0.01&&out-24>-0.01){
                    printf("%s%c%s%c%s%c%s\n",face[a[0]],signal[sign[0]],face[a[1]],signal[sign[1]],face[a[2]],signal[sign[2]],face[a[3]]);
                    return 1;
                }
            }
        }
    }
    return 0;
}

void swap(int *a,int *b){
    int m;
    m=*a;
    *a=*b;
    *b=m;
}

int find_24(int a[],int k,int m){
    int i;
    if(k>m){
        if(cal(a))
            return 1;
        n++;
    }else{
        for(i=k;i<=m;i++){
            swap(&a[k],&a[i]);
            if(find_24(a,k+1,m))
                return 1;
            swap(&a[k],&a[i]);
        }
    }
    return 0;
}

int main(){
    int card[100];
    card['A'-'1']=1;
    card[1]=2;card[2]=3;card[3]=4;card[4]=5;
    card[5]=6;card[6]=7;card[7]=8;card[8]=9;
    card['1'-'1']=10;
    card['J'-'1']=11;card['Q'-'1']=12;card['K'-'1']=13;
    char A[6],B[6],C[6],D[6];
    while(scanf("%s %s %s %s",A,B,C,D)!=EOF){
        int a[4];
        if(strlen(A)>2||strlen(B)>2||strlen(C)>2||strlen(D)>2)
            printf("ERROR\n");
        else{
            a[0]=card[A[0]-'1'];
            a[1]=card[B[0]-'1'];
            a[2]=card[C[0]-'1'];
            a[3]=card[D[0]-'1'];
            char flag[4]={0};
            if(find_24(a,0,3));
            else{
                printf("NONE\n");
            }
        }
    }
    return 0;
}

详情