holmescn

金蟲 (正式寫手)

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

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

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

分子為1的分數(shù)可以寫成一個有限小數(shù)或者無限循環(huán)小數(shù)。比如分母從2到10的分數(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......。可見其循環(huán)節(jié)為1個數(shù)字。而1/7則有6個數(shù)字的循環(huán)節(jié)。

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

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

回復(fù)此樓

» 猜你喜歡

求調(diào)劑一志愿海大，0703化學(xué)學(xué)碩304分，有大創(chuàng)項目，四級已過已經(jīng)有9人回復(fù)
289材料與化工（085600）B區(qū)求調(diào)劑已經(jīng)有4人回復(fù)
一志愿武理材料工程348求調(diào)劑已經(jīng)有6人回復(fù)
08工科 320總分求調(diào)劑已經(jīng)有11人回復(fù)
一志愿華中農(nóng)業(yè)071010，總分320求調(diào)劑已經(jīng)有6人回復(fù)
323求調(diào)劑已經(jīng)有5人回復(fù)
284求調(diào)劑已經(jīng)有5人回復(fù)
317求調(diào)劑已經(jīng)有16人回復(fù)
287求調(diào)劑已經(jīng)有9人回復(fù)
求調(diào)劑已經(jīng)有6人回復(fù)

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

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

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 工程第廿九題：有多少不同的項? 已經(jīng)有30人回復(fù)
Euler 工程第廿四題：全排列的第100萬項已經(jīng)有19人回復(fù)
Euler 工程第十六題：2的1000次方的各項和已經(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的回帖

huycwork

金蟲 (著名寫手)

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

★ ★ ★ ★
小木蟲(金幣+0.5):給個紅包，謝謝回帖
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的回帖

查看全部 10 個回答

libralibra

至尊木蟲 (著名寫手)

驃騎將軍

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

★ ★ ★ ★ ★
小木蟲(金幣+0.5):給個紅包，謝謝回帖
jjdg(金幣+3): 辛苦了 2011-06-11 22:44:31
dubo(金幣+1): 歡迎常來程序語言版討論 2011-06-11 22:44:43
余澤成(程序強帖+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 = []

    # 計算余數(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 # 補0

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

        while rem
            rem_list.append(rem)

            rem *= 10

        # 計算下一個余數(shù)

        rem %= n

    # 循環(huán)結(jié)束時,如果余數(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的回帖

libralibra

至尊木蟲 (著名寫手)

驃騎將軍

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

★ ★ ★
小木蟲(金幣+0.5):給個紅包，謝謝回帖
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ù)的時候,好像講過a/b的循環(huán)節(jié)計算方法
需要化簡后分解質(zhì)因數(shù)的,然后怎么判斷999..9整除的個數(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

金蟲 (著名寫手)

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

★ ★ ★
小木蟲(金幣+0.5):給個紅包，謝謝回帖
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ù)的時候,好像講過a/b的循環(huán)節(jié)計算方法
需要化簡后分解質(zhì)因數(shù)的,然后怎么判斷999..9整除的個數(shù)的,
記不大清了

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

我原先也分析過篩數(shù)算法來著，得出了兩個規(guī)則：
1.某個生成循環(huán)節(jié)的數(shù)針對不同的確定數(shù)長度是一致的，比如3的循環(huán)節(jié)只有1個，那任何確定的數(shù)對3做除法都只能產(chǎn)生1個循環(huán)節(jié)，如，0.13/3，0.17/3都只有一個循環(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個(1/27=0.(037))，對于3*7的循環(huán)節(jié)，則是6個，其中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的回帖

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

[考研] 323求調(diào)劑 +5	洼小桶 2026-03-18	5/250	2026-03-22 17:38 by luoyongfeng
[考研] 284求調(diào)劑 +5	Zhao anqi 2026-03-22	5/250	2026-03-22 17:38 by barlinike
[考研] 308求調(diào)劑 +3	墨墨漠 2026-03-21	3/150	2026-03-22 16:54 by i_cooler
[考研] 生物學(xué)071000 329分求調(diào)劑 +5	我愛生物生物愛?/a> 2026-03-17	5/250	2026-03-22 16:42 by tcx007
[考研] 354求調(diào)劑 +7	Tyoumou 2026-03-18	10/500	2026-03-22 11:11 by 人來盛
[考研] 286分人工智能專業(yè)請求調(diào)劑愿意跨考！ +4	lemonzzn 2026-03-17	8/400	2026-03-21 22:49 by lemonzzn
[考研] 初試 317 +7	半拉月丙 2026-03-20	7/350	2026-03-21 22:26 by peike
[考研] 一志愿南大，0703化學(xué)，分數(shù)336，求調(diào)劑 +3	收到VS 2026-03-21	3/150	2026-03-21 18:42 by 學(xué)員8dgXkO
[考研] 【考研調(diào)劑】化學(xué)專業(yè) 281分，一志愿四川大學(xué)，誠心求調(diào)劑 +11	吃吃吃才有意義 2026-03-19	11/550	2026-03-21 18:23 by 學(xué)員8dgXkO
[考研] 278求調(diào)劑 +9	煙火先于春 2026-03-17	9/450	2026-03-21 17:47 by 學(xué)員8dgXkO
[考研] 313求調(diào)劑 +4	肆叁貳壹22 2026-03-19	4/200	2026-03-21 17:33 by ColorlessPI
[考研] 材料工程（專）一志愿985 初試335求調(diào)劑 +3	hiloiy 2026-03-17	4/200	2026-03-21 03:04 by JourneyLucky
[考研] 307求調(diào)劑 +10	冷笙123 2026-03-17	10/500	2026-03-21 01:54 by JourneyLucky
[考研] 一志愿西北大學(xué) ，070300化學(xué)學(xué)碩，總分287，雙非一本，求調(diào)劑。 +3	晨昏線與星海 2026-03-18	3/150	2026-03-21 00:46 by JourneyLucky
[考研] 北科281學(xué)碩材料求調(diào)劑 +5	tcxiaoxx 2026-03-20	5/250	2026-03-20 21:35 by laoshidan
[考研] 工科材料085601 279求調(diào)劑 +7	困于星晨 2026-03-17	9/450	2026-03-20 17:38 by 無懈可擊111
[考研] 085601材料工程專碩求調(diào)劑 +10	慕寒mio 2026-03-16	10/500	2026-03-19 15:26 by 丁丁*
[考研] 085600材料與化工求調(diào)劑 +6	緒幸與子 2026-03-17	6/300	2026-03-19 13:27 by houyaoxu
[考研] 材料工程專碩調(diào)劑 +5	204818@lcx 2026-03-17	6/300	2026-03-18 22:55 by 204818@lcx
[考研] 0703化學(xué)調(diào)劑 +3	妮妮ninicgb 2026-03-17	3/150	2026-03-18 10:29 by macy2011