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

[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)

#! 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:

好算法，接近最优了。