坑爹的奥数——枚举
发布时间
阅读量：
阅读量
一、问题引入
在数学课堂上，
小明遇到了一道令人挑战的奥数题。
请在两个方框内填入相同的数字以使等式成立。
不用分析了，直接show代码：
forint19)
if1036528308256)
printf("%d"//答案为4这就是最简单的枚举算法。
枚举算法的基本思想是：有序地去尝试每一种可能。
二、问题拓展
现在小明又遇到一个稍微复杂一点的奥数题，【】【】【】+【】【】【】=【】【】【】，将数字1~9分别填入9个【】中，每个数字智能使用一次使得等式成立。
分析：根据枚举思想我们只需要枚举每一位上所有可能的数就好了。
int0;
for19//第1个数的百位for19//第1个数的十位for19//第1个数的个位for19//第2个数的百位for19//第2个数的十位for19//第2个数的个位for19//第3个数的百位for19//第3个数的十位for19//第3个数的个位 //接下来要判断每一位上的数互不相等 ifi
i
i
i
i
i
i
i
100101001010010i)
{
total;
printf("%d%d%d+%d%d%d=%d%d%d\n",a,b,c,d,e,f,g,h,i);
}
}
printf("total=%d"2//这是关键return0
特别注意：由于173加286等于459与其交换顺序相加结果为相同数值的情况属于同一组合，在输出时我们需要将total的值除以二。
三、代码优化
上述代码中的if语句显得过于复杂难以想象会遇到如此复杂的判断逻辑
所以我们用一个book数组来解决互不相等的问题：
int10010//这里用a[1]-a[9]来代替刚才的a~ifor11191)
for2292)
for3393)
for4494)
for5595)
for6696)
for7797)
for8898)
for9999)
{
for19//初始化数组0;
for19//如果某个数出现过就标记一下1;
sum0;
for19)
sum//统计供出现了多少个不同的数 if9110021034100510671008109])
{
total;
printf("%d%d%d+%d%d%d=%d%d%d\n"123456789]);
}
}
printf("total=%d"2);
return0在代码实现中，为了便于标记哪些数出现过，在原有循环变量a至i的基础上引入了一维数组代替它们。随后初始化了一个名为'book'的数组，并将其所有元素设值为0；随后每当某个数字出现时就将其对应位置设值为1；这样一来我们便无需关心具体的变量名称了——只需关注'book'数组中到底有多少个元素被置为了1即可。当书包数组中恰好有9个元素被置位1时，则表示所有从1到9的数字都恰好出现了一次
四、篇外：dfs求解
int10100;
voidint//step表示现在站在第几个盒子面前{
int i;
if10)
{
if110021034100510671008109])
{
/*如果满足要求，可行解+1，并打印这个解*/
total;
printf("%d%d%d+%d%d%d=%d%d%d\n"123456789]);
}
return//返回之前的一步（最近调用的地方） }
/*站在第step个盒子面前，按照1、2、3...n的顺序一一尝试*/for19)
{
if0)
{
a[step]i;
book[i]1;
dfs(step1);
book[i]0;
}
}
return;
}
int main()
{
dfs(1);
printf("total=%d"2);
return0;
}奥数算式求解-dfs
全部评论 (0)
还没有任何评论哟~