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;
}

京公网安备 11010502036488号