18 十月, 2006
小学生的算法
问题：寻找这样的自然数，把这个数个位上的数字挪到最前面去，例如 123 变成 312，12345变成51234。但是还要求得到的“新数”要是原来数的两倍。
即求数a1a2...an-1an，使得ana1a2...an-2an-1=2*(a1a2...an-1an)
1）借助电脑的穷尽法：
就是死算，从12开始，对每一个自然数进行测试，看看是否满足条件
2）死算的改进法1：
不难得出如下公式：19*（a1a2...an-1)=an*(10n-1-2)，19是质数，问题演变为先求n，满足10n-2-2可以被19整除，然后再遍历。
3）运用费马小定理：
参考“也说说算法的力量”。这是纯靠数论来做题了，和计算机没有关系了。估计不少人看到这个“费马定理”都会觉得眼熟，可是，如果不搞竞赛，不搞数学，能够自觉运用的天才恐怕没几个。原文中的证明还是有一点小小纰漏，它没有证明不存n小于18。逻辑错误在此处：“t的最小值为1。 所以，求解结果是：n最小值为19-t=18”。t最小，19-t是最大值才对。
4）小学5年级学生的算法：
据说这道题是1986那年出给5年级小学生做的。很多人纳闷，小学生怎么会做这么高深的题目？其实，小学生用的是最最直观最最基础的方法：乘法规则。
首先，很直观的，1<an<=9。
我们先假设an=2。
an*2的个位数字==an-1，所以an-1=4；
an-1*2的个位数字==an-2，-> an-2=8；
an-2*2的个位数字==an-3， -> an-3=6，因为2*8=16，大于10，需要向上一位进1；
an-3*2+1（进位）的个位数字==an-4， -> an-4=3，进位；
an-4*2+1（进位）的个位数字==an-5， -> an-5=7；
...
依照这个方法，一直做到乘法得出的个位数字是2（等于an），并且没有进位为止。
得出的结果：105263157894736842
（幸好，满足条件的数字是存在的，否则，小学生要无穷无尽地计算下去了^^）
同样地，依次就an等于3..9重复上述过程，可以得出其它数字。
从以上的计算方法，我们还可以得出一个结论，这样得到的数字，是满足条件的最小数字。如果，你想寻找更大的数字，只要继续进行基本的乘法，直到再一次得到的an。
其它直观结论还有，如果数字K=a1a2...an-1an满足题目的要求，那么，KK（a1a2...an-1ana1a2...an-1an）也满足条件，并且是所有比K大的，末尾数字和K相同的满足条件的自然数中最小的一个。
15 十月, 2006
道德谴责只需要口水，不需要体力。自觉占据道德高位不好，轻视任何一座山峰更不好。
与爱山者共勉
