版塊導(dǎo)航: 正在加載中...

登錄注冊

應(yīng)《網(wǎng)絡(luò)安全法》要求，自2017年10月1日起，未進(jìn)行實(shí)名認(rèn)證將不得使用互聯(lián)網(wǎng)跟帖服務(wù)。為保障您的帳號能夠正常使用，請盡快對帳號進(jìn)行手機(jī)號驗(yàn)證，感謝您的理解與支持！

24小時(shí)熱門版塊排行榜

返回列表

本帖產(chǎn)生 1 個(gè) 程序強(qiáng)帖，點(diǎn)擊這里進(jìn)行查看

holmescn

金蟲 (正式寫手)

程序強(qiáng)帖: 37
應(yīng)助: 1 (幼兒園)
金幣: 1918.8
散金: 275
紅花: 1
帖子: 699
在線: 102.6小時(shí)
蟲號: 913482
注冊: 2009-11-26
性別: GG
專業(yè): 凝聚態(tài)物性 II ：電子結(jié)構(gòu)

[交流] Euler 工程第廿六題：最長的循環(huán)節(jié) 已有4人參與

鑒于剛才發(fā)的那了Fibonacci數(shù)列的題太無聊，可能用C寫大數(shù)加法也不會(huì)太慢，所以再發(fā)一個(gè)吧，這個(gè)有點(diǎn)意思了。

分子為1的分?jǐn)?shù)可以寫成一個(gè)有限小數(shù)或者無限循環(huán)小數(shù)。比如分母從2到10的分?jǐn)?shù)就寫為：

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......�？梢娖溲h(huán)節(jié)為1個(gè)數(shù)字。而1/7則有6個(gè)數(shù)字的循環(huán)節(jié)。

那么，分母小于1000的所有分子為1的分?jǐn)?shù)中，誰的循環(huán)節(jié)最長呢？

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

回復(fù)此樓

» 猜你喜歡

281求調(diào)劑（0805）已經(jīng)有9人回復(fù)
293求調(diào)劑已經(jīng)有14人回復(fù)
0703化學(xué)336分求調(diào)劑已經(jīng)有6人回復(fù)
304求調(diào)劑已經(jīng)有9人回復(fù)
環(huán)境領(lǐng)域全國重點(diǎn)實(shí)驗(yàn)室招收博士1-2名已經(jīng)有3人回復(fù)
材料專碩306英一數(shù)二已經(jīng)有10人回復(fù)
301求調(diào)劑已經(jīng)有6人回復(fù)
一志愿天津大學(xué)化學(xué)工藝專業(yè)（081702）315分求調(diào)劑已經(jīng)有7人回復(fù)
302求調(diào)劑已經(jīng)有6人回復(fù)
26博士申請已經(jīng)有3人回復(fù)

» 本主題相關(guān)商家推薦: (我也要在這里推廣)

» 本主題相關(guān)價(jià)值貼推薦，對您同樣有幫助:

Project Euler 50 歐拉工程 50 題已經(jīng)有12人回復(fù)
Project Euler 48 歐拉工程 48 題已經(jīng)有30人回復(fù)
Project Euler 45 歐拉工程 45 題已經(jīng)有7人回復(fù)
Euler 工程第廿九題：有多少不同的項(xiàng)? 已經(jīng)有30人回復(fù)
Euler 工程第廿四題：全排列的第100萬項(xiàng) 已經(jīng)有19人回復(fù)
Euler 工程第十六題：2的1000次方的各項(xiàng)和已經(jīng)有14人回復(fù)
Euler 工程第十五題：從左上角到右下角有多少條路？已經(jīng)有5人回復(fù)
Euler 工程第14題：找最長的數(shù)列已經(jīng)有9人回復(fù)
Euler Project Q13 歐拉工程第十三題已經(jīng)有20人回復(fù)
Euler Project Q12 歐拉工程第十二題已經(jīng)有23人回復(fù)
Euler 工程第十一題：相鄰元素乘積最大已經(jīng)有10人回復(fù)
Euler Project Q7. 歐拉工程第七題已經(jīng)有14人回復(fù)
Euler 工程第六題：平方和與和的平方差多少？已經(jīng)有5人回復(fù)
Euler 工程第三題：尋找600851475143的最大質(zhì)因子已經(jīng)有18人回復(fù)
Euler 工程第二題：Fibonacci數(shù)列中小于4百萬的偶數(shù)的和已經(jīng)有8人回復(fù)

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

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

libralibra

至尊木蟲 (著名寫手)

驃騎將軍

程序強(qiáng)帖: 40
應(yīng)助: 817 (博后)
金幣: 12914.1
紅花: 64
帖子: 2238
在線: 287.3小時(shí)
蟲號: 696514
注冊: 2009-02-05
專業(yè): 計(jì)算機(jī)軟件

★ ★ ★ ★ ★
小木蟲(金幣+0.5):給個(gè)紅包，謝謝回帖
jjdg(金幣+3): 辛苦了 2011-06-11 22:44:31
dubo(金幣+1): 歡迎常來程序語言版討論 2011-06-11 22:44:43
余澤成(程序強(qiáng)帖+1): 2011-06-15 21:03:07

模擬除法,python代碼

CODE:

#! usr/bin/env python

from mytictoc import tic, toc

# 返回1/n的循環(huán)節(jié)長度

def findCircleLen(n):

    rem = 1

    # 循環(huán)節(jié)前面的0,不影響結(jié)果

    while rem
        rem *= 10

    # 保存余數(shù)的list

    rem_list = []

    # 計(jì)算余數(shù)

    rem %= n

    # 做除法,循環(huán)直到: a)余數(shù)為0; b)以前出現(xiàn)過的余數(shù)再次出現(xiàn)

    while rem!=0 and rem not in rem_list:

        rem_list.append(rem) # 添加當(dāng)前余數(shù)到余數(shù)列表

        rem *= 10 # 補(bǔ)0

        # 一直補(bǔ)到可以接著做除法,保存補(bǔ)零后的結(jié)果到列表

        while rem
            rem_list.append(rem)

            rem *= 10

        # 計(jì)算下一個(gè)余數(shù)

        rem %= n

    # 循環(huán)結(jié)束時(shí),如果余數(shù)為0,說明整除,循環(huán)節(jié)長度返回0

    if rem==0:

        return 0

    # 返回循環(huán)節(jié)長度

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

結(jié)果:

CODE:

 983

Elapsed time: 0.52579169 seconds

[ Last edited by libralibra on 2011-6-11 at 15:17 ]

贊一下(4人)

回復(fù)此樓

matlab/VB/python/c++/Java寫程序請發(fā)QQ郵件:790404545@qq.com

2樓2011-06-11 15:15:59

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

huycwork

金蟲 (著名寫手)

程序強(qiáng)帖: 22
應(yīng)助: 0 (幼兒園)
金幣: 953
散金: 663
紅花: 8
沙發(fā): 13
帖子: 1080
在線: 264.1小時(shí)
蟲號: 1257243
注冊: 2011-04-06
專業(yè): 金融學(xué)

★ ★ ★ ★
小木蟲(金幣+0.5):給個(gè)紅包，謝謝回帖
jjdg(金幣+1): 感謝參與 2011-06-11 22:44:11
jjdg(金幣+1): 感謝參與 2011-06-11 22:44:19
dubo(金幣+1): 歡迎常來程序語言版討論 2011-06-11 22:44:51

引用回帖:

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

from mytictoc import tic, toc

# 返回1/n的循環(huán)節(jié)長度
def findCircleLen(n):
rem = 1
# 循環(huán)節(jié)前面的0,不影響結(jié)果
while rem<n:
...

好算法，接近最優(yōu)了。

贊一下(4人)

回復(fù)此樓

漩渦的中心有一塊空地，空空的。

3樓2011-06-11 18:56:05

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

libralibra

至尊木蟲 (著名寫手)

驃騎將軍

程序強(qiáng)帖: 40
應(yīng)助: 817 (博后)
金幣: 12914.1
紅花: 64
帖子: 2238
在線: 287.3小時(shí)
蟲號: 696514
注冊: 2009-02-05
專業(yè): 計(jì)算機(jī)軟件

★ ★ ★
小木蟲(金幣+0.5):給個(gè)紅包，謝謝回帖
jjdg(金幣+1): 感謝參與 2011-06-11 22:44:03
dubo(金幣+1): 歡迎常來程序語言版討論 2011-06-11 22:44:57

引用回帖:

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

好算法，接近最優(yōu)了。

不過我記得小學(xué)奧數(shù)的時(shí)候,好像講過a/b的循環(huán)節(jié)計(jì)算方法
需要化簡后分解質(zhì)因數(shù)的,然后怎么判斷999..9整除的個(gè)數(shù)的,
記不大清了

贊一下(3人)

回復(fù)此樓

matlab/VB/python/c++/Java寫程序請發(fā)QQ郵件:790404545@qq.com

4樓2011-06-11 20:04:23

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

huycwork

金蟲 (著名寫手)

程序強(qiáng)帖: 22
應(yīng)助: 0 (幼兒園)
金幣: 953
散金: 663
紅花: 8
沙發(fā): 13
帖子: 1080
在線: 264.1小時(shí)
蟲號: 1257243
注冊: 2011-04-06
專業(yè): 金融學(xué)

★ ★ ★
小木蟲(金幣+0.5):給個(gè)紅包，謝謝回帖
jjdg(金幣+1): 感謝參與 2011-06-11 22:43:55
dubo(金幣+1): 歡迎常來程序語言版討論 2011-06-11 22:45:03

引用回帖:

Originally posted by libralibra at 2011-06-11 20:04:23:
不過我記得小學(xué)奧數(shù)的時(shí)候,好像講過a/b的循環(huán)節(jié)計(jì)算方法
需要化簡后分解質(zhì)因數(shù)的,然后怎么判斷999..9整除的個(gè)數(shù)的,
記不大清了

這個(gè)也有通項(xiàng)公式？這就跟那個(gè)斐波那契數(shù)一樣的必須先算前面才能知道后面那個(gè)數(shù)啊，每個(gè)余數(shù)都恰好只計(jì)算了一次，這種計(jì)算方法而言，已經(jīng)是最優(yōu)解法了。除非存在某種直接導(dǎo)出長度的方法。

我原先也分析過篩數(shù)算法來著，得出了兩個(gè)規(guī)則：
1.某個(gè)生成循環(huán)節(jié)的數(shù)針對不同的確定數(shù)長度是一致的，比如3的循環(huán)節(jié)只有1個(gè)，那任何確定的數(shù)對3做除法都只能產(chǎn)生1個(gè)循環(huán)節(jié)，如，0.13/3，0.17/3都只有一個(gè)循環(huán)節(jié)
2.對于符合規(guī)則1的數(shù)的積都可能產(chǎn)生更長的循環(huán)節(jié)，如3的循環(huán)節(jié)是1(1/3=0.(3))，3*3的循環(huán)節(jié)還是1(1/9=0.(1))，但是3*9的循環(huán)節(jié)就有3個(gè)(1/27=0.(037))，對于3*7的循環(huán)節(jié)，則是6個(gè)，其中1/7=0.(142857)，1/21=0.(047619)。

但是后來一想就傻了，篩了還不如沒篩，原先是O(n)的算法，篩數(shù)算法卻要O(n*n)，得不償失。

贊一下(3人)

回復(fù)此樓

漩渦的中心有一塊空地，空空的。

5樓2011-06-11 21:16:29

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

libralibra

至尊木蟲 (著名寫手)

驃騎將軍

程序強(qiáng)帖: 40
應(yīng)助: 817 (博后)
金幣: 12914.1
紅花: 64
帖子: 2238
在線: 287.3小時(shí)
蟲號: 696514
注冊: 2009-02-05
專業(yè): 計(jì)算機(jī)軟件

★ ★ ★
小木蟲(金幣+0.5):給個(gè)紅包，謝謝回帖
jjdg(金幣+1): 感謝參與 2011-06-11 22:43:47
dubo(金幣+1): 歡迎常來程序語言版討論 2011-06-11 22:45:09

引用回帖:

Originally posted by huycwork at 2011-06-11 21:16:29:
這個(gè)也有通項(xiàng)公式？這就跟那個(gè)斐波那契數(shù)一樣的必須先算前面才能知道后面那個(gè)數(shù)啊，每個(gè)余數(shù)都恰好只計(jì)算了一次，這種計(jì)算方法而言，已經(jīng)是最優(yōu)解法了。除非存在某種直接導(dǎo)出長度的方法。

我原先也分析過篩 ...

我記得奧數(shù)的時(shí)候用筆算很簡單,想用程序?qū)崿F(xiàn),還不如模擬豎式除法好理解.

搜了下,這有個(gè)比較詳細(xì)的講解
http://hi.baidu.com/piaoshi111/b ... 857caccd1166a6.html

贊一下(3人)

回復(fù)此樓

matlab/VB/python/c++/Java寫程序請發(fā)QQ郵件:790404545@qq.com

6樓2011-06-11 22:02:07

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

huycwork

金蟲 (著名寫手)

程序強(qiáng)帖: 22
應(yīng)助: 0 (幼兒園)
金幣: 953
散金: 663
紅花: 8
沙發(fā): 13
帖子: 1080
在線: 264.1小時(shí)
蟲號: 1257243
注冊: 2011-04-06
專業(yè): 金融學(xué)

★ ★ ★
小木蟲(金幣+0.5):給個(gè)紅包，謝謝回帖
jjdg(金幣+1): 感謝參與 2011-06-11 22:43:35
dubo(金幣+1): 歡迎常來程序語言版討論 2011-06-11 22:45:17

引用回帖:

Originally posted by libralibra at 2011-06-11 22:02:07:
我記得奧數(shù)的時(shí)候用筆算很簡單,想用程序?qū)崿F(xiàn),還不如模擬豎式除法好理解.

搜了下,這有個(gè)比較詳細(xì)的講解
http://hi.baidu.com/piaoshi111/b ... 857caccd1166a6.html

高手果然得從娃娃抓起哈~

剛才看了下那個(gè)我就突然想起來高中學(xué)數(shù)列的時(shí)候也講過用等比數(shù)列轉(zhuǎn)換循環(huán)小數(shù)的，0.333...=0.3+0.03+0.003+...這樣。如果把這題也換一下，所有的循環(huán)節(jié)都可以改成等差數(shù)列的形式，然后逆推，應(yīng)該也是一種方案。

我說高考的數(shù)列和排列組合咋這么難，敢情是天才班的內(nèi)部資料外泄了。

贊一下(3人)

回復(fù)此樓

漩渦的中心有一塊空地，空空的。

7樓2011-06-11 22:24:28

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

tieer

木蟲 (正式寫手)

程序強(qiáng)帖: 4
應(yīng)助: 48 (小學(xué)生)
金幣: 1528.2
散金: 565
紅花: 26
帖子: 551
在線: 739.7小時(shí)
蟲號: 761880
注冊: 2009-05-02
專業(yè): 高分子材料結(jié)構(gòu)與性能

★ ★
小木蟲(金幣+0.5):給個(gè)紅包，謝謝回帖
jjdg(金幣+1): 歡迎來程序版交流 2011-06-15 00:13:30

是不是應(yīng)該要找1000里最大的素?cái)?shù)，然后計(jì)算循環(huán)節(jié)長度就可以了啊

贊一下(2人)

回復(fù)此樓

思考，讓這個(gè)世界更有趣。

8樓2011-06-14 21:34:39

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

libralibra

至尊木蟲 (著名寫手)

驃騎將軍

程序強(qiáng)帖: 40
應(yīng)助: 817 (博后)
金幣: 12914.1
紅花: 64
帖子: 2238
在線: 287.3小時(shí)
蟲號: 696514
注冊: 2009-02-05
專業(yè): 計(jì)算機(jī)軟件

★
小木蟲(金幣+0.5):給個(gè)紅包，謝謝回帖

引用回帖:

Originally posted by tieer at 2011-06-14 21:34:39:
是不是應(yīng)該要找1000里最大的素?cái)?shù)，然后計(jì)算循環(huán)節(jié)長度就可以了啊

1000內(nèi)最大素?cái)?shù)是997

贊一下(1人)

回復(fù)此樓

matlab/VB/python/c++/Java寫程序請發(fā)QQ郵件:790404545@qq.com

9樓2011-06-15 00:14:51

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

qinghuoly

木蟲 (正式寫手)

程序強(qiáng)帖: 1
應(yīng)助: 140 (高中生)
金幣: 4753.1
紅花: 10
帖子: 885
在線: 918.1小時(shí)
蟲號: 966225
注冊: 2010-03-09
性別: GG
專業(yè): 金屬有機(jī)化學(xué)

★ ★ ★
小木蟲(金幣+0.5):給個(gè)紅包，謝謝回帖
xzhdty(金幣+2): 歡迎到程序語言來 2011-06-27 10:03:40

循環(huán)小數(shù)1/d的循環(huán)節(jié)c長度為n；f為d因式分解后移除2和5的因子的乘積。則999...9（n個(gè)9）恰好能整除f。
n即為循環(huán)節(jié)長度。

例如
1/7=0.(142857)
1/12=0.08(3) 此時(shí)d為12，因式分解為 2 2 3；移除兩個(gè)2，得到f＝3 ; 999999/7=142857
1/420=0.00(238095) 此時(shí)d為420，因式分解為 2 2 3 5 7；移除兩個(gè)2，一個(gè)5; 得到f＝21 ; 999999/21=47619

循環(huán)節(jié)為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)

耗時(shí)547 ms。答案為983，循環(huán)節(jié)長為982

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

贊一下(2人)

回復(fù)此樓

天地為帳，日月為燈，風(fēng)雷為號角，云虹為旗令，山川為陣圖，草木為兵卒。運(yùn)陰陽五行為謀，策古今興替為略。

10樓2011-06-27 07:20:36

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

相關(guān)版塊跳轉(zhuǎn) 我要訂閱樓主 holmescn 的主題更新

返回列表

普通表情龍兔虎貓高級回復(fù) (可上傳附件)

最具人氣熱帖推薦 [查看全部]		作者	回/看	最后發(fā)表

[考研] 344求調(diào)劑 +4	knight344 2026-03-16	4/200	2026-03-17 17:27 by ruiyingmiao
[考研] 290求調(diào)劑 +3	p asserby. 2026-03-15	4/200	2026-03-17 16:35 by wangkm
[考研] 工科材料085601 279求調(diào)劑 +3	困于星晨 2026-03-17	3/150	2026-03-17 14:08 by ms629
[考研] 材料與化工專碩調(diào)劑 +5	heming3743 2026-03-16	5/250	2026-03-17 14:03 by 勇敢太監(jiān)王公公
[考研] 285化工學(xué)碩求調(diào)劑（081700） +9	柴郡貓_ 2026-03-12	9/450	2026-03-17 10:18 by Sammy2
[考研] 東南大學(xué)364求調(diào)劑 +5	JasonYuiui 2026-03-15	5/250	2026-03-16 21:28 by 木瓜膏
[考研] 一志愿211 0703方向310分求調(diào)劑 +3	努力奮斗112 2026-03-15	3/150	2026-03-16 16:44 by houyaoxu
[考研] 070300化學(xué)學(xué)碩求調(diào)劑 +6	太想進(jìn)步了0608 2026-03-16	6/300	2026-03-16 16:13 by kykm678
[考研] 085600調(diào)劑 +5	漾漾123sun 2026-03-12	6/300	2026-03-16 15:58 by 漾漾123sun
[考研] 0703 物理化學(xué)調(diào)劑 +3	我可以上岸的對?/a> 2026-03-13	5/250	2026-03-16 10:50 by 我可以上岸的對?/a>
[考研] 0703化學(xué)調(diào)劑 290分有科研經(jīng)歷，論文在投 +7	膩膩gk 2026-03-14	7/350	2026-03-16 10:12 by houyaoxu
[考研] 080500，材料學(xué)碩302分求調(diào)劑學(xué)校 +4	初識可樂 2026-03-14	5/250	2026-03-14 21:08 by peike
[考研] 材料與化工 323 英一+數(shù)二+物化，一志愿：哈工大本人本科雙一流 +4	自由的_飛翔 2026-03-13	5/250	2026-03-14 19:39 by hmn_wj
[考研] 266求調(diào)劑 +4	學(xué)員97LZgn 2026-03-13	4/200	2026-03-14 08:37 by zhukairuo
[考研] 材料工程調(diào)劑 +9	咪咪空空 2026-03-12	9/450	2026-03-13 22:05 by 星空星月
[考研] ［0860］321分求調(diào)劑，ab區(qū)皆可 +4	寶貴熱 2026-03-13	4/200	2026-03-13 22:01 by 星空星月
[考研] 0703化學(xué)一志愿211 總分320求調(diào)劑 +5	瑪卡巴卡啊哈 2026-03-11	5/250	2026-03-13 21:40 by JourneyLucky
[考研] 【考研調(diào)劑求收留】 +3	Ceciilia 2026-03-11	3/150	2026-03-13 20:18 by JourneyLucky
[考研] 081200-11408-276學(xué)碩求調(diào)劑 +3	崔wj 2026-03-12	4/200	2026-03-12 19:33 by 求調(diào)劑zz
[考博] 2026年博士申請 +3	QwQwQW10 2026-03-11	3/150	2026-03-12 17:58 by gxch43

24小時(shí)熱門版塊排行榜

[交流] Euler 工程 第廿六題：最長的循環(huán)節(jié) 已有4人參與

» 猜你喜歡

» 本主題相關(guān)商家推薦: (我也要在這里推廣)

» 本主題相關(guān)價(jià)值貼推薦，對您同樣有幫助:

[交流] Euler 工程第廿六題：最長的循環(huán)節(jié) 已有4人參與

» 本主題相關(guān)價(jià)值貼推薦，對您同樣有幫助: