dfs算法
#include<stdio.h> #include<string.h> char str[10][10] = { 0 }; int a[10] = { 0 }; int b[10] = { 0 }; int v[10] = { 0 }; int his[10] = { 0 }; char syms[10] = { 0 }; int flag2 = 0; int dfs1(int i, int sum) { if (i == 3) { if (sum == 24) { return 1; } else { return 0; } } int ti = i + 1; if (ti <= 3 && ti >= 0 && his[ti] == 0) { his[ti] = 1; if (dfs1(ti, sum + b[ti]) == 1) { syms[ti] = '+'; return 1; } else { his[ti] = 0; } } if (ti <= 3 && ti >= 0 && his[ti] == 0) { his[ti] = 1; if (dfs1(ti, sum - b[ti]) == 1) { syms[ti] = '-'; return 1; } else { his[ti] = 0; } } if (ti <= 3 && ti >= 0 && his[ti] == 0) { his[ti] = 1; if (dfs1(ti, sum * b[ti]) == 1) { syms[ti] = '*'; return 1; } else { his[ti] = 0; } } if (ti <= 3 && ti >= 0 && his[ti] == 0) { his[ti] = 1; if (dfs1(ti, sum / b[ti]) == 1) { syms[ti] = '/'; return 1; } else { his[ti] = 0; } } return 0; } void dfs2(int i)//i表示树层 { if (i >= 4) { his[0] = 1; if (dfs1(0, b[0]) == 1) { flag2 = 1; for (int m = 0; m < 4; m++) { if (b[m] > 1 && b[m] <= 9) { str[m][0] = b[m] + '0'; } if (b[m] == 10) { strcpy(str[m], "10"); } if (b[m] == 1) { str[m][0] = 'A'; } if (b[m] == 11) { str[m][0] = 'J'; } if (b[m] == 12) { str[m][0] = 'Q'; } if (b[m] == 13) { str[m][0] = 'K'; } } printf("%s%c%s%c%s%c%s", str[0], syms[1], str[1], syms[2], str[2], syms[3], str[3]); } return; } for (int k = 0; k < 4; k++)//k表示树枝 { if (a[k] == a[k - 1] && v[k - 1] == 1 && k > 1) { continue; } if (v[k] == 0) { v[k] = 1; b[i] = a[k]; dfs2(i + 1); v[k] = 0; } } } int main(void) { int flag = 0; for (int i = 0; i < 4; i++) { scanf("%s", str[i]); if (strlen(str[i]) > 2) { flag = 1; printf("ERROR"); } if (str[i][0] >= '2' && str[i][0] <= '9') { a[i] = str[i][0] - '0'; } if (strcmp(str[i], "10") == 0) { a[i] = 10; } if (str[i][0] == 'A') { a[i] = 1; } if (str[i][0] == 'J') { a[i] = 11; } if (str[i][0] == 'Q') { a[i] = 12; } if (str[i][0] == 'K') { a[i] = 13; } }//输入完毕 //求全排列 if (flag == 0) { //先排序 for (int i = 0; i < 4; i++) { for (int j = 0; j < 4 - 1 - i; j++) { if (a[j] > a[j + 1]) { int temp; temp = a[j + 1]; a[j + 1] = a[j]; a[j] = temp; } } }//排序完毕 //printf("%d %d %d %d",a[0],a[1],a[2],a[3]); dfs2(0);//全排列 if (flag2 == 0) { printf("NONE"); } } return 0; }