[交流] Euler 工程 第廿六题：最长的循环节已有4人参与

#! usr/bin/env python

from mytictoc import tic, toc

# 返回1/n的循环节长度
def findCircleLen(n):
    rem = 1
    # 循环节前面的0,不影响结果
    while rem         rem *= 10

    # 保存余数的list
    rem_list = []
   
    # 计算余数
    rem %= n

    # 做除法,循环直到: a)余数为0; b)以前出现过的余数再次出现
    while rem!=0 and rem not in rem_list:

        rem_list.append(rem) # 添加当前余数到余数列表
        
        rem *= 10 # 补0

        # 一直补到可以接着做除法,保存补零后的结果到列表
        while rem             rem_list.append(rem)
            rem *= 10

        # 计算下一个余数
        rem %= n

    # 循环结束时,如果余数为0,说明整除,循环节长度返回0
    if rem==0:
        return 0

    # 返回循环节长度
    else:
        return len(rem_list)

def euler26():
    tic()
    s = [findCircleLen(x) for x in xrange(2,1000)]
    print 2+s.index(max(s))
    toc()

if __name__=='__main__':
    euler26()

983
Elapsed time: 0.52579169 seconds

Originally posted by libralibra at 2011-06-11 15:15:59:
模拟除法,python代码
[code]#! usr/bin/env python

from mytictoc import tic, toc

# 返回1/n的循环节长度
def findCircleLen(n):
    rem = 1
    # 循环节前面的0,不影响结果
    while rem<n:
...

Originally posted by huycwork at 2011-06-11 18:56:05:

好算法，接近最优了。

Originally posted by libralibra at 2011-06-11 20:04:23:
不过我记得小学奥数的时候,好像讲过a/b的循环节计算方法
需要化简后分解质因数的,然后怎么判断999..9整除的个数的,
记不大清了

Originally posted by huycwork at 2011-06-11 21:16:29:
这个也有通项公式？这就跟那个斐波那契数一样的必须先算前面才能知道后面那个数啊，每个余数都恰好只计算了一次，这种计算方法而言，已经是最优解法了。除非存在某种直接导出长度的方法。

我原先也分析过筛 ...

Originally posted by libralibra at 2011-06-11 22:02:07:
我记得奥数的时候用笔算很简单,想用程序实现,还不如模拟竖式除法好理解.

搜了下,这有个比较详细的讲解
http://hi.baidu.com/piaoshi111/b ... 857caccd1166a6.html

Originally posted by tieer at 2011-06-14 21:34:39:
是不是应该要找1000里最大的素数，然后计算循环节长度就可以了啊

[define [ans26]

  [define N 1000]
  [define M [string->number [string-append "1" [make-string 30 #\0]]]]
  [define [recur n d]
    ;get the recurring cycle length of n/d
    [define [r counter x deno]
      [if [= 0 [remainder x deno]]
          counter
          [r [add1 counter]
             [+ 9 [* 10 x]]
             deno]]]
    [let* [[c [denominator
               [/ M
                  [denominator [/ n d]]]]]
           [o [add1 [order-of-magnitude c]]]
           ]
      [if [= c 1]
          0
          [r o
             [string->number
              [string-append
                     [make-string o #\9]]]
             c]]]]
  [define [c num max len]
    [if [= num N]
        [list max len]
        [if [>= len [recur 1 num]]
            [c [+ 1 num] max len]
            [c [+ 1 num] num [recur 1 num]]]]]
  [c 3 2 1]]

> [time [ans26]]
cpu time: 531 real time: 547 gc time: 126
'(983 982)