乍听之下,不无道理;仔细揣摩,胡说八道

0%

今天上百度贴吧的ProjectEuler吧时发现大家在讨论第26题的一个解法的原理[求值]求解释原理,然后话题很快又从对解法的原理的解释转移到了对性能的攀比之中——这也是人之常情啦,哪个做PE题目的人不希望自己的方法是尽量快的呢^_^看了一下吧主的解法的运行时间,发现居然不是毫秒级别的,顿时对自己以前的解法需要运行多久心生好奇,于是在已经打开的SLIME中加载了以前的源文件,一运行,发现相当地快,速度上是吧主给出解法的快一百倍,连我自己都吓了一跳,不过还是掩盖不了自己内心的欢喜。

我的思路

我不知道吧主是怎么做的,他在贴吧里面没有给出代码,不过我倒是可以给一下我的解法的链接第26题。刚翻出来看的时候我自己也看蒙了,完全不知道自己当初究竟是怎样的思路的,也不知道自己当初是在怎样的情况下想出这样的代码的。不过再仔细看了一会儿之后,总算有点明白是什么意思了。这其中的做法,还得从小学的时候学习除法来说起……

哦,不好意思,说太远了,没必要追溯到小学那里去,不过思路本身可能确实就是小学的除法,只不过是找了一下其中的规律,然后用计算机代替了手动计算而已。考虑一个简单的情况,例如一除以二,要怎么计算呢?嗯,因为1比2要小,所以计算结果应该是个小数,所以商必然有0.(零以及小数点),然后在1后面添一个0,再继续计算。这时候我们知道了2×5=10,所以在商的部分再添上一个5,就得到了余数为0的情况。因为余数为0,所以我们知道2是可以整除1的,所以计算就到此结束了,因此1/2=0.5。

上面的例子是可以整除的情况,因此在小数点后面并没有循环的部分,所以循环部分的长度理所当然的就是0。那如果是一除以六呢?计算方法是一样的,因为1比6小,所以商添上0.,而给1添上一个0得到10,而10除以6的商为1余数为4。接下来给4添上一个0得到40,再进行40除以6的计算过程。最后得到的结果是一个无限循环小数,按照第26题的写法就是0.1(6)。不过且慢,这里有个地方值得注意,那就是对于得到余数为4的情况,我们为其添上了一个0再继续进行计算,这个步骤和一开始为1添上0再进行计算难道有什么本质的差别吗?

显然没有啊!而且计算40除以6的结果是6.(6),如果直接把这个计算1除以6时的第一步得到的商进行拼接,就得到了0.1(6)啊。也就是说,小学的时候学到的手动进行除法计算的方法,实际上可以分解成一个递归的算法。具体如何分解不是这里的讨论重点,这里的重点在于怎样从递归的过程中发现可以得到循环部分的长度的方法。

余数的奥秘

如果在手动计算的过程中,遇到了某个曾经在余数的位置上出现过的数,那么还有必要继续计算下去吗?显然没有,40除以6得到的第一个余数是4,而这个余数比6小(事实上我们都知道,所有的余数都比除数要小),就需要先将其乘上10再继续计算下去。结果显而易见,一乘上10,就又得到了一开始的40了,这样的话要是继续计算下去,那么结果一定是在重复前面的那些动作,并且永无休止。结论就是,当你遇到了一个余数是之前出现的数的时候,计算就不需要继续下去了,此时根据历史积累的信息,就可以知道循环部分的长度是多少。这也就是我的代码中第一个函数cycle-length的内部辅助函数rec的作用。

rec接收三个参数,第一个参数就是被除数,第二个数是除数,第三个数是这一次计算得到的商在原来的小数部分上是位于哪一个位置上的一个整数。对于每一个出现过的被除数,都将它们记录在了一个内部的哈希表中(为了查找速度的尽可能快),如果一个被除数已经被计算过了,那么就直接取出它所对应的商所在的位置,然后用现在的商所在的位置减掉前者,就知道了循环部分的长度了;如果没有出现过,那么就计算出这一次计算的余数,如果余数为0,意味着除数可以整除被除数,所以没有循环部分可言,长度为0;如果不能整除,那么这个余数的10倍就是新的被除数(因为余数必定小于除数,所以要乘以10直到大于除数为止),位置计数器加上1,重新进行递归。