利用C程序枚举完全破解王柳数字谜题

2009-04-05 • 技术文章

题目是这样的:下面的竖式中,每个不同的字母代表一个数字(0-9)且它们互异,求出所有可能的结果。

1
2
3
4
5
a b c
d a f g g
+ e g h a
---------
i j g g f

使用C程序如下代码执行,显示所有结果后提示“Problem Solved”:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<stdio.h>
int main()
{ int a,b,c,d,e,f,g,h,i,j,use[10]={0},jin1;
for(c=0;c<10;c++)
{ use[c]=1;
    for(g=0;g<10;g++)
     if(use[g]==0)
     { use[g]=1;
       for(a=0;a<10;a++)
       { use[a]=1;
         jin1=(c+g+a)/10;
         f=(c+g+a)%10;
         if(use[f]==0)
         { use[f]=1;
           for(b=0;b<10;b++)
            if(use[b]==0)
            { use[b]=1;
              if(b+jin1>0&&b+jin1<=10)
              { h=10-b-jin1;
                if(use[h]==0)
                { use[h]=1;
                  f=10-1-a;
                  if(use[f]==0)
                  { use[f]=1;
                    for(e=0;e<10;e++)
                     if(use[e]==0)
                     { use[e]=1;
                       j=a+e+1-10;
                       if(j>=0&&use[j]==0)
                       { use[j]=1;
                         for(d=0;d<9;d++)
                          if(use[d]==0&&use[d+1]==0)
                           printf("    %d %d %d
%d %d %d %d %d
+ %d %d %d %d
---------
%d %d %d %d %d
 
",a,b,c,d,a,f,g,g,e,g,h,a,i,j,g,g,f);
                       } }}}}}}}}} 
printf("Problem solved.");
getch();
}

运行结果是,无输出(只输出了Problem Solved)。使用Visual Basic 6.0程序计算,经过计算机4个小时的计算还是无解。

对于如此纷繁复杂的程序,首先应该从较浅层的循环出发,进行输出当前变量操作,以查看是否枚举完毕。像这类问题,往往是由于逻辑问题,而导致枚举过程没有进行完就退出了。

首先检测末位的枚举情况,在下面的代码中加入输出。f=(c+g+a)%10;printf("%d %d %d %d

",c,g,a,f);if(use[f]==0)

输出如下:

1
2
3
4
5
6
7
8
9
10
11
0 1 0 1
0 1 1 2
0 1 2 3
0 1 3 4
0 1 4 5
0 1 5 6
0 1 6 7
0 1 7 8
0 1 8 9
0 1 9 0
Problem solved.

我们不由得疑问:为什么c的取值只有0这个很小的数,而没有更大的枚举?原因一定是在中间时枚举中断了。观察有无控制枚举中断的return,break,continue,发现不存在,于是断定是use数组的问题:忘记归零。

修改后,删除输出语句,发现输出中的某个数很大,一定是输出了地址,或者忘记赋值。发现正是i的位置,原因是d+1事实上并没有赋值为i,于是将i替换为d+1。

输出很多,发现了两个问题:大量重复;末位和不正确。

明明是末位和求了出来,为什么输出时被改变了?一定是内层循环中有修改f之处。果然,f=10-1-a;if(use[f]==0) use[f]=1;便是对f的重新处理。遇到这种情况,不能简单的将后面的语句删除,而要思考出现重复的原因:没有考虑到f在式中出现了两次,重复枚举。注意到a和f都是第一次枚举出来的,于是a+f=9成为枚举的一个约束条件。

删除上面的语句和有关恢复语句use[f]=0;,修改逻辑结构。加入f=(c+g+a)%10;if(a+f==9) if(use[f]==0)判断,成为约束条件。再次运行,不再出现末位和不正确的情况,但仍然出现了重复,例如

1
2
3
4
5
7 8 9
5 7 2 6 6
+ 3 6 0 7
---------
6 1 6 6 2

一组解中i和g重复。下面检查没有进行重复剪枝的问题。for(a=0;a<10;a++) if(use[a]==0) {use[a]=1;中原来没有对a的重复性进行判断。

经过调试,我们得到这样的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<stdio.h>
int main()
{ int a,b,c,d,e,f,g,h,i,j,use[10]={0},jin1;
for(c=0;c<10;c++)
{ use[c]=1;
    for(g=0;g<10;g++)
     if(use[g]==0)
     { use[g]=1;
       for(a=0;a<10;a++)
       if(use[a]==0)
       { use[a]=1;
         jin1=(c+g+a)/10;
         f=(c+g+a)%10;
         if(a+f==9)
         if(use[f]==0)
         { use[f]=1;
           for(b=0;b<10;b++)
            if(use[b]==0)
            { use[b]=1;
              if(b+jin1>0&&b+jin1<=10)
              { h=10-b-jin1;
                if(use[h]==0)
                { use[h]=1;
                    for(e=0;e<10;e++)
                     if(use[e]==0)
                     { use[e]=1;
                       j=a+e+1-10;
                       if(j>=0&&use[j]==0)
                       { use[j]=1;
                         for(d=0;d<9;d++)
                          if(use[d]==0&&use[d+1]==0)
                           printf("    %d %d %d
%d %d %d %d %d
+ %d %d %d %d
---------
%d %d %d %d %d
 
",a,b,c,d,a,f,g,g,e,g,h,a,d+1,j,g,g,f);
                         use[j]=0;
                       }
                       use[e]=0;   
                  }
                  use[h]=0;
                }
              }
              use[b]=0;
            }
            use[f]=0;
         }
         use[a]=0;
       }
       use[g]=0;
     }
     use[c]=0;
} 
printf("Problem solved.");
getch();
}

输出为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
6 0 2
7 6 3 5 5
+ 4 5 9 6
------------
8 1 5 5 3
    6 9 2
7 6 3 5 5
+ 4 5 0 6
------------
8 1 5 5 3
    6 0 5
7 6 3 2 2
+ 4 2 9 6
------------
8 1 2 2 3
    6 9 5
7 6 3 2 2
+ 4 2 0 6
------------
8 1 2 2 3
    7 0 6
4 7 2 9 9
+ 3 9 8 7
------------
5 1 9 9 2
    7 8 6
4 7 2 9 9
+ 3 9 0 7
------------
5 1 9 9 2
    7 0 9
4 7 2 6 6
+ 3 6 8 7
------------
5 1 6 6 2
    7 8 9
4 7 2 6 6
+ 3 6 0 7
------------
5 1 6 6 2
Problem solved.

共计8组解。

通过这个问题的解决过程,我们体验了一个较为复杂的枚举问题的调试过程。也许读者看起来这些错误都很“幼稚”,但在我们编程的过程中,正是这种“幼稚”的错误一再降低着我们的AC率。因此我们一方面要在写程序时更加小心,另一方面要学会一定的调试技巧,尽可能在短时间内调试成功。

今日的续声——读余先生《遥远的绝响》

2009-01-10 • 个人情感

《遥远的绝响》的作者是余秋雨先生,他被定位为“文化名人”,读毕《遥远的绝响》才觉得这个定位甚为恰当。

这篇文章中的故事情节我不想述及,语言、技法自然精当。但我想余先生之所以是文化名人,那么他的写作目的不仅仅是故事,更核心但隐秘的应该是对中华文化的发扬光大呀!

余先生的睿智之目看到了当前中华最大的危险——文化危机。中国经济腾飞,然而文化却日趋势弱。中科院报告指出当前70%以上的人价值观存在问题,而心理学理论指出价值观决定人之举止,故糟糕的价值观阻抑了社会的文明进步,使得社会极不和谐。还有一点便是中国人的自信力,有鲁迅先生的《中国人失掉自信力了吗》一文在,我不敢妄加怀疑;然而,凡是某物,很多人一听说是美国货,便认为必定比国产的好。我不愿多写,畏惧引发内心的激愤。但我想提醒大家——

当前,务必提高民族自信力和自信心,重拾文明的贝壳,重绘文化的蓝图,则国可兴。

我想,余秋雨先生写作像本文一样一系列文章的目的也就在于——利用影响力传播文明,欲以遥远的绝响激发今日的续声。

昔事重拾——肖桥的冬

2009-01-01 • 个人情感

29日上午,蔡老师把我们几个参加奥赛培训的同学送到师大生命科学系后便回了沧州,他已有一年没回去了。而我呢,离开沧州已五年余了,却还不曾有机会回家看看。

骑行于飒飒秋风间,心浮丝丝凉意,忆起老家的冬来。秋脖子亦不很长,故无所顾恋,唯独肖桥的冬让人回味。

肖桥的冬是冷的,不像城市里冬天也这么暖和。早晨,被窝里是最暖和舒服的,窗户玻璃上嵌着一层冰花,晶莹美丽,但美里却透着寒意,似乎要封冻整个世界,于是让人更不情愿爬起来。

好不容易挪出被窝,便有一种往家北麦地里走一圈的冲动。田间小道没有章法地交错相通,地面上还有一层冰碴儿没来得及融化,踩上去发出清脆的断裂声,这来自大自然的音乐是这个蔚蓝星球上最高雅的艺术。冬小麦露出点点芽绿,是灰黄土地间最鲜明的色彩,饱藏着生命的玄机。

雪是冬日里不可缺少的东西。一旦下雪,村里小学是最热闹的,这里的雪通常不扫,孩子们玩着各种各样的游戏,笑声能传出很远。

野兔们也怕冷,藏到被大雪覆盖的棒秸垛里暖和着,却总是被喜欢猎兔的村民逮个正着,成了冬日的桌上美食。

太阳出来了,屋顶的积雪融化,从檐边往下流,流到一半又冻住,形成一列列冰挂。阳光照射下,折射出缕缕光芒,形成地面上跃动着的斑点。

冬日农闲,妇女们凑到一起打麻将或是闲谈家常,男人们聚到一户畅谈军事政治,打发冬闲时光。虽非一家人,但情感浓厚,胜似一家。

立足寂寞都市,思念远方的冬,因为那里的景色,更因为那里的人心。如果我可以主宰一切,我愿降低城市的气温去温暖淡漠的人心。

一封未发出的倡议书——王雪柏《团结·责任·有我们在》

2008-05-30 • 个人情感

牵挂,心灵的颤动。

只因为你我共生在华夏的土地上,共同聆听圣人的经典,共流炎黄的血脉,我们叫兄弟姐妹。

就在几天前,你我都还在课桌前认真读书,准备上课。就在那时,零八年五月十二日十四时二十八分——一个让无数学子泪眼回望的时刻,一切都改变了!

一声巨响,让天府之国为之震动,让神州苍生为之悲歌。

我的同胞们哪,我的同学们。突如其来的灾祸瞬间而至,也许压倒了你们中的许多人,一栋栋教学楼的坍塌也许让一间间教室中的学生再也没能站起来,再也没能看到那熟悉的课本,那些祖国亲人们关切的目光。你们和我们一样啊!拥有最美丽的年华,最阳光的少年时代,而今天,想握住你那曾经充满活力的双手,凝望你们曾经闪着青春的双眸,却似乎,永远,永远……

同是炎黄子孙,同是中国人!我们失去的是一位位兄弟姐妹,苍天斩断的是我们的手足之情啊!

五月,原本不该有的阴霾笼罩着我们,是死亡的洗礼敲醒了我们原本稚气未脱的头脑。生命,难道真的如此脆弱?如果我们在四川,瞬间,也许在无意识中,便什么都不再拥有了!灾难, 死亡告诉我们生命该有的光亮。 残酷的现实向我们昭示着:中国少年,你要自强!

兄弟们,姐妹们,一路走好,亲人们为你们虔诚地祈祷!

还有那么多受灾的兄弟啊,也许你失去了你的书本,也许你失去了学校,也许你失去了所有的家人,也许你的心灵在无比黑暗中经受着悲伤和迷茫。地震的伤痛落在了你们同样稚嫩的肩膀上,也深深留在了你们的心灵中。肢体的伤痛残缺,家园的毁灭,心中梦想的渺茫,也许会折断你们这些天使飞翔的翅膀!但我要告诉你们,告诉你们,我们和你们一同经受这心灵的考验,我们都在磨难中学会坚强。灾难让我们变得成熟,让我们学会抚平创伤,即使双膝挂满伤痕,即使双眼泪雨盈眶,我们都会靠自己的双腿重新站起,把少年人的责任,扛在肩上!

汶川的雨还在下吗?你的脸颊依旧挂满泪花吗?雨,总会过去;天,又总会晴朗。书本,可以再找;学校,可以重建。但我们还要告诉你们,你们失去家园,没有失去亲人;你们会痛苦,但永远不会绝望,有我们与你们血脉相连!来,靠上我们的胸膛,让我们分担痛苦,分享希望,有我们在,中国未来还要由我们共同担当。

同胞们,你们知道吗?你们受灾后的几分钟,千里之外,我们的教学楼也随之摇晃。震痛足以绵延千里,共同的惊恐也让我们的心紧紧相连。失学的同胞们,我们虽身处两地,但心却在一起,我们永远站在你的身旁,因为我们都是中国未来的太阳。

因此,我庄严地向校领导建议,也向所有同学倡议:献出我们每个人的力量,虽然力量似乎微弱,但我希望我们每个班可以团结起来,承担一位灾区同龄人的高中学费,为兄弟姐妹们尽自已的一份力量。我们毕业了,还可以号召更多的同学继续帮助他们,用我们的双手创造我们共同的阳光。

团结起来,凝聚大家的力量,承担我们的责任,让世界知道:中国的少年胸怀天下,明天的中华必将傲立于世界东方;因为少年进步则国进步,少年强则国强!

执笔:王雪柏

高一17班

2008.5.24