版块导航: 正在加载中...

登录注册

应《网络安全法》要求，自2017年10月1日起，未进行实名认证将不得使用互联网跟帖服务。为保障您的帐号能够正常使用，请尽快对帐号进行手机号验证，感谢您的理解与支持！

24小时热门版块排行榜

返回列表

本帖产生 1 个程序强帖，点击这里进行查看

当前只显示满足指定条件的回帖，点击这里查看本话题的所有回帖

holmescn

金虫 (正式写手)

程序强帖: 37
应助: 1 (幼儿园)
金币: 1918.8
散金: 275
红花: 1
帖子: 699
在线: 102.6小时
虫号: 913482
注册: 2009-11-26
性别: GG
专业: 凝聚态物性 II ：电子结构

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

鉴于刚才发的那了Fibonacci数列的题太无聊，可能用C写大数加法也不会太慢，所以再发一个吧，这个有点意思了。

分子为1的分数可以写成一个有限小数或者无限循环小数。比如分母从2到10的分数就写为：

1/2 = 0.5
1/3 = 0.(3)
1/4 = 0.25
1/5 = 0.2
1/6 = 0.1(6)
1/7 = 0.(142857)
1/8 = 0.125
1/9 = 0.(1)
1/10 = 0.1

这里, 0.1(6) 表示0.1666666......。可见其循环节为1个数字。而1/7则有6个数字的循环节。

那么，分母小于1000的所有分子为1的分数中，谁的循环节最长呢？

[ Last edited by holmescn on 2011-6-11 at 10:09 ]

回复此楼

» 猜你喜欢

请问有评职称，把科研教学业绩算分排序的高校吗已经有6人回复
2025冷门绝学什么时候出结果已经有6人回复
Bioresource Technology期刊，第一次返修的时候被退回好几次了已经有7人回复
真诚求助：手里的省社科项目结项要求主持人一篇中文核心，有什么渠道能发核心吗已经有8人回复
寻求一种能扛住强氧化性腐蚀性的容器密封件已经有5人回复
请问哪里可以有青B申请的本子可以借鉴一下。已经有4人回复
请问下大家为什么这个铃木偶联几乎不反应呢已经有5人回复
天津工业大学郑柳春团队欢迎化学化工、高分子化学或有机合成方向的博士生和硕士生加入已经有4人回复
康复大学泰山学者周祺惠团队招收博士研究生已经有6人回复
AI论文写作工具：是科研加速器还是学术作弊器？已经有3人回复

» 本主题相关商家推荐: (我也要在这里推广)

» 本主题相关价值贴推荐，对您同样有帮助:

Project Euler 50 欧拉工程 50 题已经有12人回复
Project Euler 48 欧拉工程 48 题已经有30人回复
Project Euler 45 欧拉工程 45 题已经有7人回复
Euler 工程第廿九题：有多少不同的项? 已经有30人回复
Euler 工程第廿四题：全排列的第100万项已经有19人回复
Euler 工程第十六题：2的1000次方的各项和已经有14人回复
Euler 工程第十五题：从左上角到右下角有多少条路？已经有5人回复
Euler 工程第14题：找最长的数列已经有9人回复
Euler Project Q13 欧拉工程第十三题已经有20人回复
Euler Project Q12 欧拉工程第十二题已经有23人回复
Euler 工程第十一题：相邻元素乘积最大已经有10人回复
Euler Project Q7. 欧拉工程第七题已经有14人回复
Euler 工程第六题：平方和与和的平方差多少？已经有5人回复
Euler 工程第三题：寻找600851475143的最大质因子已经有18人回复
Euler 工程第二题：Fibonacci数列中小于4百万的偶数的和已经有8人回复

1楼2011-06-11 10:08:35

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

qinghuoly

木虫 (正式写手)

程序强帖: 1
应助: 140 (高中生)
金币: 4753.1
红花: 10
帖子: 885
在线: 918.1小时
虫号: 966225
注册: 2010-03-09
性别: GG
专业: 金属有机化学

★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
xzhdty(金币+2): 欢迎到程序语言来 2011-06-27 10:03:40

循环小数1/d的循环节c长度为n；f为d因式分解后移除2和5的因子的乘积。则999...9（n个9）恰好能整除f。
n即为循环节长度。

例如
1/7=0.(142857)
1/12=0.08(3) 此时d为12，因式分解为 2 2 3；移除两个2，得到f＝3 ; 999999/7=142857
1/420=0.00(238095) 此时d为420，因式分解为 2 2 3 5 7；移除两个2，一个5; 得到f＝21 ; 999999/21=47619

循环节为142857

scheme语言解法：

CODE:

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

CODE:

> [time [ans26]]

cpu time: 531 real time: 547 gc time: 126

'(983 982)

耗时547 ms。答案为983，循环节长为982

[ Last edited by qinghuoly on 2011-6-27 at 22:52 ]

赞一下(2人)