#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]--;
}
}
}
}
回溯递归相关笔记
剪枝函数:约束函数和限界函数 n个数中取r个数
#include <stdio.h>
#include <string.h>
#define MAX 100
static int n = 10, r = 5;
static int used[MAX] = {0}; //标记是否使用
static int p[MAX]; //输出的排列
static int a[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; //当前数组
int count=0;
void permute(int pos);
int main()
{
permute(0);
printf("%d",count);
return 0;
}
void permute(int pos)
{
//pos==r排列形成并输出
if (pos == r)
{
for (int i = 0; i < r; i++)
printf("%d", p[i]);
printf("\n");
count++;
return;
}
//已经选了pos个数
//否则匹配第pos+1个数,对应p数组位置pos;
for (int i = 0; i <n; i++)
{
//这里用used数组进行剪枝 这里是约束函数剪去的重复使用一个数组位置的可能结果(即保证这r个数没有从n中重复取用)
//那么pos也可以算是限界函数,限制结果必须是r个数字的组合
if (used[i] == 0)
{
used[i]++;
p[pos] = a[i];
permute(pos+1); //递归 下一个数 直到pos+1-> pos==r输出一个排列
//递归后在pos到r后输出排列,同时需要将当前使用a的数对应的used数组归位
used[i]--;
}
}
}
无相同元素排列重排列 如1221中(1,2)1,2 (1,3)1,2算作同一排列 1.去重后进行排列 2.对上面函数进行修改
n个数中取r个数 不考虑顺序 无重组合
#include <stdio.h>
#include <string.h>
#define MAX 100
static int n = 10, r = 5;
static int used[MAX] = {0}; //标记是否使用
static int C[MAX]; //输出的排列
static int a[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; //当前数组
int count = 0;
void combine(int pos, int h);
int main()
{
combine(0, 0);
printf("%d", count);
return 0;
}
void combine(int pos, int h)
{
if (pos == r)
{
for (int i = 0; i < r; i++)
printf("%d", C[i]);
printf("\n");
count++;
return;
}
//调整后续取数的遍历范围,顺序取数,开始位置依次后移
//例如长10取5 当前pos==0时,从0- 5(5=10-5+pos)都是pos==0时可取值
for (int i = h; i <= n - r + pos; i++)
if (used[i] == 0)
{
C[pos] = a[i];
used[i]++;
combine(pos + 1, i + 1);
used[i]--;
}
}
剪枝
● 如何剪枝：使用used数组还是begin变量？都是用来剪重复数字的枝，着这两个有什么区别呢？
used数组：
■ 一个boolean数组，用来标记nums中对应元素是否已经使用过。
■ 用于全排列问题中，对于这一类问题，我们是考虑数字顺序的，即[1,2,3]和[3,2,1]是两个不同的排列。它剪去的其实是当前层数以上的祖先节点，比如当我们第一位取了2时，2、3位只能取1和3，不能再取1了。
begin变量
■ 一个int类型，在递归时根据题意来决定下一层函数的选择列表中元素的起始位置，如果可重复即为begin，不可重复为begin+1
■ 用于组合问题中，对于这一类问题，我们是考虑数字顺序的，即[1,2,3]和[3,2,1]是两个相同的组合。它相对于used数组，剪去了更多的枝，这也就是我们都知道的排列的个数比组合个数多。因为它是控制每层对选择列表的起始位置，所以它不仅剪去了当前节点的祖先节点，还剪去了当祖先节点的左兄弟，这就是begin在起作用。(对应排列中就是这个h head变量也即bigin位置在限制)
● begin
○ 剪父节点和父节点的兄弟节点，排在它前面的元素都被剪掉
● used
○ 剪父节点和兄弟节点
● 重复节点两者都可
● 剪枝前需要考虑是否要对nums进行排序，剪重复节点是必须要进行排序的。
总结:两层
● 确定总的DFS深度,每个深度上进行剪枝和遍历,
● 在每个深度上确定分叉数,对每个子节点进行剪枝和遍历
如火车进站,火车序列已知,深度为火车数量n,每个深度上分叉为进站和出站两个
如全排列,数组已知,用used剪枝,深度为数组元素数量n,每个深度上有n个分叉(即取用n个元素中的一个),用used剪枝
递归后要还原操作回溯到前一深度状态
京公网安备 11010502036488号