4.10　数字哑谜和回文

    人越大越聪明还是越大越笨？最近笔者看了一些小学低年级的“奥数”题目，把脑袋拍痛了，还做不出来，真想列几个二元一次方程，把解求出来——不过小学低年级还没有学方程，所以这个不算；笔者也想干脆写个程序，用蛮力搜索的方法，把答案找出来算了，不过这个肯定也不是正确的解法。看来我们“大人”依赖于“方程”、“程序”太多了，脑子变得不灵活了。

    下面的问题，可以用小学三年级的方法解决，也可以用初中列方程式的办法解决，还可以用大学的高级编程语言解决。读者有没有兴趣尝试和比较一下各种解法？

    1．神奇的9位数。能不能找出符合如下条件的9位数：

    这个数包括了1～9这9个数字。

    这个9位数的前n位都能被n整除，若这个数表示为abcdefghi，则ab可以被2整除，abc可以被3整除……abcdefghi可以被9整除。

    2．有这样一个乘法算式：人过大佛寺*我＝寺佛大过人

    这里面每一字都代表着一个数字，并且不同的字代表的数字不同，你能把这些数字都找出来么？

    分析与解法

    【问题1的解法一】

    假设这个9位数是abcdefghi，根据题目要求，每个字符对应一个1～9之间的数。习惯于写程序的人，可以用嵌套的循环（对a，b，…，i进行循环，遍历各种可能的组合）来搜索正确的解。

    这样的搜索，效率必然很低，因此可以考虑使用剪枝来优化性能。剪枝的概念，跟走迷宫避开死胡同差不多。如果把搜索比作遍历一棵树，那么剪枝就是将树中的一些不能到达解的枝条“剪”掉，以提高算法的性能。

    比如在循环到b等于奇数时，由于ab必须被2整除，因此奇数已经不满足条件了，那就可以不用搜索b等于奇数的所有9位数，而直接对b加1。剪枝后程序的效率应该会有大幅度地提高。

    【问题1的解法二】

    我们还可以试一试用逻辑推理的办法求解这个问题，假设每个字符目前都可以对应1～9之间的任何数字：

    alt

    我们把“整除”的条件列出来，见下：

    a被1整除，任何数都能满足这个条件。a可以是1..9中的任何数。

    ab被2整除

    b等于2　4　6　8

    abc被3整除

    （a＋b＋c）被3整除

    abcd被4整除

    d等于2　4　6　8

    cd被4整除

    abcde被5整除

    e等于5

    abcdef被6整除

    f等于2　4　6　8

    （a＋b＋c＋d＝e＋f）被3整除

    abcdefg被7整除

    abcd－efg能被7整除（考虑到7能整除1001）

    abcdefgh被8整除

    h等于2　4　6　8

    fgh能被8整除

    abcdefghi被9整除

    （a＋b＋c＋d＋e＋f＋g＋h＋i）被9整除，肯定成立

    根据上述的充要条件，可以将各个字母取值范围缩小为：

    alt

    我们还有下面的条件没有用上：

    （a＋b＋c）被3整除

    cd被4整除

    （d＋e＋f）被3整除

    abcd－efg能被7整除（考虑到7能整除1001）

    fgh能被8整除

    由于“（d＋e＋f）被3整除”，并且e＝5，所以d＋f必须是3k＋1的形式，才能保证整除性。因此我们有下面4种可能：

    （d＝2，f＝8），（d＝4，f＝6），（d＝6，f＝4），（d＝8，f＝2）

    又由于cd被4整除，cd＝12，16，32，36，72，76，92，96。我们得到：d＝2或6，对应地，f等于8或4。

    看其他条件：

    fgh能被8整除

    fgh＝816，832，872，896，416，432，472，496

    f＝8时，d＝2，故h不能等于2，

    f＝4时，d＝6，故h不能等于6

    fgh＝816，896，432，472

    进一步简化的结果，我们得到：

    alt

    尚未使用的条件有：

    “（a＋b＋c）被3整除”

    “abcd－efg能被7整除”（考虑到7能整除1001）

    这样，我们可以推断出：

    cd＝12，16，32，36，72，76，92，96

    df＝28，64

    fgh＝816，896，432，472

    b＝4或8

    b＝4，ac＝17，71

    b＝8，ac＝13，31，19，91，37，73，79，97

    h＝6或2

    h＝6，g＝1or9，gi＝93

    h＝2，g＝3or7，gi＝31，37，73，79

    bdfh＝4286或8642

    bdfh＝4286时，

    ac＝17，71

    gi＝93

    acgi＝1793，7193

    bdfh＝8642时，

    ac＝13，31，19，91，37，73，79，97

    gi＝31，37，73，79

    acgi＝1379，3179，1937，1973，9137，9173，7931，9731

    剩下10个组合，需要使用“abcd－efg能被7整除”判别。

    最后得到的解是：381654729。经历这样的过程得到了答案，会不会比写程序更快呢？

    【问题2的解法】

    人过大佛寺，寺佛大过人。

    真是有趣的回文。我们尝试用“大人”的办法来解决。

    代码清单4-4

    alt

    像这样变量太多，可能的解也不少的情况，用程序去处理可能会比较快。但是对于一些有提示的问题，用小学学到的数学知识，加上简单的推理，就可以完成。如果这道题目简化为：

    人过大佛寺*4＝寺佛大过人

    也许你在纸上写写画画5分钟就可以搞定。

    而同样的5分钟时间，刚够你启动电脑，登录用户，打开最新最强有力的编程集成环境（例如Visual Studio 2008 IDE），运用“项目向导（Project Wizard）”，回答了若干问题后，得到了一个空的C++控制台项目。

    我们太依赖电脑，也许正因为我们懒得思考。

    扩展问题

    【问题1】

    上面的“人过大佛寺*我＝寺佛大过人”等式，这种带有“回文”特性的对称的美，让人愉悦。“回文”在中国传统文学中有不少有趣的故事。苏东坡写过一首回文诗：

    潮随暗浪雪山倾，远浦渔舟钓月明。

    桥对寺门松径小，槛当泉眼石波清。

    迢迢绿树江天晓，霭霭红霞晚日晴。

    遥望四边云接水，碧峰千点数鸥轻。

    这首诗，顺着读下来，读者仿佛看到了从月夜景色到江天破晓的画面。而反过来读，就变成了：

    轻鸥数点千峰碧，水接云边四望遥。

    晴日晚霞红霭霭，晓天江树绿迢迢。

    清波石眼泉当槛，小径松门寺对桥。

    明月钓舟渔浦远，倾山雪浪暗随潮。

    仿佛是一幅从黎明晓日，到渔舟唱晚的画卷。

    回文修辞在英语中也有，比如，“Able was I ere I saw Elba”，这句话形式上对称了，但意境上似乎不能和上面提到的中文回文同日而语。

    与回文诗对应的回文数，也有着严格的对称美，不论是从左向右顺读，还是从右向左倒读，结果都是一样的，例如：323、4554都是回文数。

    在两位数中，回文数有11，22，33，…，99；在三位数中，有111，121，131，…，222，…。那么，N位回文数的个数总共有多少呢？数字回文难言意境，但是也许可以在数量上取胜？⑥

    【问题2】

    这本书的作者全部是男士，但事实上微软公司里有不少优秀的女员工和女实习生。她们不仅是“半边天”，而且往往发挥着“一个顶俩”的作用。下面一道题目就是作者们献给女员工的：

    （he）2＝she

    “他”的平方等于“她”，读者们能把h、e、s，代表的数字找出来么？

    问题2的推广：大家一般都“假定”（assume）我们说的数字是十进制，很多创意都被一些“假定”给限制住了。如果不是十进制，那么我们上面的各个等式还有解么？试试看，也许解法更精彩。