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

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

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

北京石油化工學(xué)院2026年研究生招生接收調(diào)劑公告

返回列表

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

holmescn

金蟲 (正式寫手)

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

[交流] Euler 工程第14題：找最長(zhǎng)的數(shù)列已有6人參與

周末了，放個(gè)題出來玩玩：

定義一個(gè)正整數(shù)數(shù)列，其迭代公式為：
n = n/2 (當(dāng)n為偶數(shù))
n = 3n+1 (當(dāng)n為奇數(shù))

比如從n=13開始，計(jì)算這個(gè)數(shù)列得：
13 ->40->20->10->5->16->8->4->1
這個(gè)數(shù)列一共有10項(xiàng)。
這個(gè)數(shù)列是不是總收斂到1還是個(gè)沒有解決的問題（稱為Collatz Problem)
不過，我們并不是要解這個(gè)難題，而是要求在小于1百萬的所有起始數(shù)中，哪個(gè)數(shù)能產(chǎn)生最長(zhǎng)的數(shù)列。

這里要注意的是，數(shù)列中間的項(xiàng)是可以大于1百萬的，要看提最后數(shù)列終止到1時(shí)候的長(zhǎng)度。

PS：這東西不能用歸納法證出來嗎？
PS2：注意1分鐘原則啊。不過，大于1分鐘的程序也可以發(fā)上來，這樣才有的交流。

Here we go!

回復(fù)此樓

» 猜你喜歡

085600 286分材料求調(diào)劑已經(jīng)有3人回復(fù)
275求調(diào)劑已經(jīng)有10人回復(fù)
286求調(diào)劑已經(jīng)有6人回復(fù)
083000學(xué)碩274求調(diào)劑已經(jīng)有5人回復(fù)
【求調(diào)劑】085601材料工程專碩 | 總分272 | 已經(jīng)有5人回復(fù)
275求調(diào)劑已經(jīng)有13人回復(fù)
0856，材料與化工321分求調(diào)劑已經(jīng)有8人回復(fù)
085701環(huán)境工程，267求調(diào)劑已經(jīng)有12人回復(fù)
320分，材料與化工專業(yè)，求調(diào)劑已經(jīng)有7人回復(fù)
085701環(huán)境工程求調(diào)劑已經(jīng)有8人回復(fù)

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

Euler 工程第四十四題已經(jīng)有4人回復(fù)
Euler 工程第四十二題: 三角詞已經(jīng)有4人回復(fù)
Euler 工程第四十一題已經(jīng)有5人回復(fù)
Euler 工程第三十八題已經(jīng)有9人回復(fù)
Euler 工程第三十七題已經(jīng)有6人回復(fù)
Euler 工程第三十六題：已經(jīng)有18人回復(fù)
Euler 工程第三十五題：循環(huán)質(zhì)數(shù) 已經(jīng)有16人回復(fù)
Euler 工程第三十二題：pandigital 數(shù) 已經(jīng)有3人回復(fù)
Euler 工程第三十一題: 換零錢已經(jīng)有10人回復(fù)
Euler 工程第三十題已經(jīng)有12人回復(fù)
Euler 工程第廿九題：有多少不同的項(xiàng)? 已經(jīng)有30人回復(fù)
Euler 工程第廿八題：旋轉(zhuǎn)矩陣對(duì)角線的和已經(jīng)有6人回復(fù)
Euler 工程第廿七題：系數(shù)的積已經(jīng)有15人回復(fù)
Euler 工程第廿六題：最長(zhǎng)的循環(huán)節(jié) 已經(jīng)有9人回復(fù)
Euler 工程第廿五題：Fibonacci 數(shù)列第一個(gè)包含1000個(gè)數(shù)字的項(xiàng) 已經(jīng)有3人回復(fù)
Euler 工程第廿四題：全排列的第100萬項(xiàng) 已經(jīng)有19人回復(fù)
Euler 工程第廿三題：已經(jīng)有16人回復(fù)
Euler 工程第廿二題: 姓的總分已經(jīng)有13人回復(fù)
Euler 工程第廿題：100! 的各項(xiàng)和已經(jīng)有5人回復(fù)
Euler 工程第十九題：每月第一天是周日的天數(shù) 已經(jīng)有4人回復(fù)
Euler 工程第十八題：三角陣上最大的和已經(jīng)有12人回復(fù)
Euler 工程第十六題：2的1000次方的各項(xiàng)和已經(jīng)有14人回復(fù)
Euler 工程第十一題：相鄰元素乘積最大已經(jīng)有10人回復(fù)
Euler 工程第三題：尋找600851475143的最大質(zhì)因子已經(jīng)有18人回復(fù)

1樓 2011-05-20 16:41:24

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

huycwork

金蟲 (著名寫手)

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

★ ★ ★ ★
小木蟲(金幣+0.5):給個(gè)紅包，謝謝回帖
余澤成(金幣+3, 程序強(qiáng)帖+1): 辛苦了！ 2011-05-20 21:02:20

昨天寫好這個(gè)了，C++版本的是醬紫：

CODE:

#include 

enum {BUFSZ = 1000000};

size_t eular14(size_t bufsz = 1000000){

        size_t buf[BUFSZ+1];

        size_t max = 1, c, r;

        long long n;

        buf[1] = 1;

        for(int i = 2; i < BUFSZ + 1; ++i){

                n = i;

                c ^= c;

                while(1){

                        if(n < BUFSZ && buf[n])

                                break;

                        ++c;

                        if(n % 2){

                                n = 3*n + 1;

                        }else

                                n = n/2;

                }

                buf[i] = buf[n] + c;

                if(buf[i] > max){

                        max = buf[i];

                        r = i;

                }

        }

        return r;

}

int main(void){

        std::cout<
}

贊一下(2人)

回復(fù)此樓

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

2樓2011-05-20 17:05:54

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

wangww2011

木蟲 (著名寫手)

程序強(qiáng)帖: 13
應(yīng)助: 11 (小學(xué)生)
金幣: 4023.1
散金: 2709
紅花: 18
沙發(fā): 1
帖子: 1915
在線: 1537.1小時(shí)
蟲號(hào): 772953
注冊(cè): 2009-05-17
性別: GG
專業(yè): 凝聚態(tài)物性 II ：電子結(jié)構(gòu)

★ ★
小木蟲(金幣+0.5):給個(gè)紅包，謝謝回帖
余澤成(金幣+1): 說到！ 2011-05-20 21:02:42
微塵、夢(mèng)想(程序強(qiáng)帖+1): 很好，歡迎常來！ 2011-05-21 19:18:45

給個(gè)迭代算法吧，0.05s 先看結(jié)果：

CODE:

max=837799  count=525

elapsed time=0.050000 seconds.

代碼為

CODE:

#include 

#include 

#include 

#define TIMERSTART clock_t start_time,stop_time;double elapsed_time;start_time = clock();

#define TIMERSTOP stop_time = clock();elapsed_time=(double)(stop_time-start_time)/CLOCKS_PER_SEC;printf("elapsed time=%f seconds.\n",elapsed_time);

#define N 1000001

static int count[N];

int euler14(long long n){

  int result;

  if(n0){

    return count[n];

  }

  if(n%2) {

    n=3*n+1;

  }else {

    n=n/2;

  }

  result=euler14(n);

  if(n
    count[n]=result;

  } 

  return result+1;

}

int main(void){

  int i=0;

  int max_count,max;

  TIMERSTART;

  count[1]=1;

  max_count=0;

  for(i=N-1;i>1;i--){

    if(count[i]==0){

       count[i]=euler14(i);

    }

    if(count[i]>max_count){

      max_count=count[i];

      max=i;

    }

  }

  printf("max=%d  count=%d\n",max,max_count);

  TIMERSTOP;

  return 0;

}

[ Last edited by wangww2011 on 2011-5-21 at 14:14 ]

贊一下(3人)

回復(fù)此樓

3樓2011-05-20 17:53:37

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

huycwork

金蟲 (著名寫手)

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

★ ★ ★ ★
小木蟲(金幣+0.5):給個(gè)紅包，謝謝回帖
余澤成(金幣+3): 鼓勵(lì)交流！ 2011-05-20 21:03:01

這個(gè)用歸納法證明是證明不出來的
前提條件可以選2->1
但是后面無法作出歸納假設(shè)：就算你假設(shè)an -> ak，歸納的下一步驟就是a(n+1)沒法推導(dǎo)a(k+1)，你看代碼就知道了，你無法知道中間產(chǎn)生的鏈條有多長(zhǎng)，實(shí)際原因是無法知道中間經(jīng)過的元素有哪些，當(dāng)然也就無法歸納證明。

贊一下(2人)

回復(fù)此樓

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

4樓2011-05-20 18:03:01

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

微塵、夢(mèng)想

木蟲 (知名作家)

程序強(qiáng)帖: 6
應(yīng)助: 2 (幼兒園)
貴賓: 0.353
金幣: 4757.9
散金: 3089
紅花: 31
沙發(fā): 247
帖子: 8788
在線: 1125小時(shí)
蟲號(hào): 1203290
注冊(cè): 2011-02-14
專業(yè): 制造系統(tǒng)與自動(dòng)化

★ ★
小木蟲(金幣+0.5):給個(gè)紅包，謝謝回帖
余澤成(金幣+1): 鼓勵(lì)交流！ 2011-05-20 21:03:21

這不是著名的3x+1問題嗎？以前寫過這個(gè)程序，也試著證過這道題，看著挺簡(jiǎn)單，要真證起來，才發(fā)現(xiàn)根本不可能，否則它也不是世界難題了……

贊一下(2人)

回復(fù)此樓

任風(fēng)云變幻，我笑對(duì)人生！

5樓2011-05-20 18:27:20

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

libralibra

至尊木蟲 (著名寫手)

驃騎將軍

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

★ ★ ★
小木蟲(金幣+0.5):給個(gè)紅包，謝謝回帖
jjdg(金幣+2): 辛苦了 2011-05-21 00:51:59
微塵、夢(mèng)想(程序強(qiáng)帖+1): 2011-05-21 19:19:39

matlab的,13s多哦

CODE:

 %% Which starting number, under one million, produces the longest chain?

%   n = n/2 (even); n = 3*n+1 (odd) till n==1

% like starting from 13, we generate the following sequence (contains 10 terms)

%  13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

function result = euler14()

tic;

n = 0;

len = 0;

big = 0;

result = 0;

for i=1:1e6

    n = i;

    len = 0;

    while n~=1

        if mod(n,2)==0

            n = n/2;

        else

            n = n*3+1;

        end

        len = len+1;

    end

    len = len+1; % n==1

    if len>big

        big = len;

        result = i;

    end

end

toc;

end

結(jié)果

CODE:

 % Elapsed time is 13.644453 seconds.

% ans =

%       837799

贊一下(3人)

回復(fù)此樓

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

6樓2011-05-20 21:23:11

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

holmescn

金蟲 (正式寫手)

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

微塵、夢(mèng)想(程序強(qiáng)帖+1): 2011-05-21 19:19:52

matlab果然是不給力啊，F(xiàn)ortran版的只要0.75s

CODE:

Program euler14

    Implicit None

    Integer :: maxLen = 0, l

    Integer(8) :: n

    Integer :: start, maxStart

    Real :: t1, t2

    Call CPU_Time(t1)

    Do start = 2, 1000000

        n = start

        l = 0

        Do While (n .gt. 1) 

            If(mod(n, 2) .eq. 0) Then

                n = n / 2

            Else

                n = 3*n + 1

            EndIf

            l = l + 1

        EndDo

        l = l + 1

        If(l .gt. maxLen) Then

            maxLen = l

            maxStart = start

        EndIf

    EndDo

    Call CPU_Time(t2)

    Print *, "Result:", maxStart, maxLen, t2-t1

End Program euler14

結(jié)果同libralibra同學(xué)。不過恐怖的是，中間項(xiàng)居然會(huì)大于40億啊。32位整數(shù)都保存不了了。最后總共有525項(xiàng)。這東西用Mathematica的NestList展開會(huì)是什么樣？

現(xiàn)在的計(jì)算機(jī)速度太快了，以至于我們都不想去找一個(gè)更好的解法了，不過，這東西的解空間應(yīng)該還能減小，我看到2到3000以內(nèi)都還是單調(diào)上漲的呢。

贊一下(2人)

回復(fù)此樓

7樓2011-05-21 13:40:36

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

wmc_1979

金蟲 (小有名氣)

應(yīng)助: 4 (幼兒園)
金幣: 1232.8
散金: 30
帖子: 128
在線: 110.9小時(shí)
蟲號(hào): 1243434
注冊(cè): 2011-03-24
專業(yè): 運(yùn)籌學(xué)

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

我計(jì)算出是 837799
項(xiàng)數(shù) 524

[ Last edited by wmc_1979 on 2011-5-21 at 20:38 ]

贊一下(1人)

回復(fù)此樓

8樓2011-05-21 20:04:41

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

holmescn

金蟲 (正式寫手)

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

★
余澤成(金幣+1): 謝謝參與交流！ 2011-05-22 11:53:05

引用回帖:

Originally posted by wmc_1979 at 2011-05-21 20:04:41:
我計(jì)算出是 837799
項(xiàng)數(shù) 524

[ Last edited by wmc_1979 on 2011-5-21 at 20:38 ]

當(dāng)n=1的時(shí)候，就退出循環(huán)了，所以認(rèn)為最后計(jì)數(shù)的時(shí)候沒有數(shù)1

贊一下(1人)

回復(fù)此樓

9樓2011-05-22 09:08:54

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

chyanog

金蟲 (小有名氣)

程序強(qiáng)帖: 1
應(yīng)助: 12 (小學(xué)生)
金幣: 808.1
紅花: 5
帖子: 85
在線: 52.8小時(shí)
蟲號(hào): 1540955
注冊(cè): 2011-12-17
性別: GG
專業(yè): 計(jì)算數(shù)學(xué)與科學(xué)工程計(jì)算

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

Mathematica和中的遞歸可以很方便的“記憶化”，很簡(jiǎn)潔但還是沒有編譯后的循環(huán)快：

CODE:

c@1 = 1; c@n_ := c@n = 1 + If[EvenQ@n, c[n/2], c[3 n + 1]]; 

Ordering[c /@ Range@1*^6, -1] // AbsoluteTiming

cf = Compile[{{n0, _Integer}},

   Block[{n = N@n0},

    Catch@Do[If[n == 1, Throw@i];

      n = If[FractionalPart[n/2] == 0, n/2, 3*n + 1],

      {i, 1*^8}]

    ], RuntimeAttributes -> Listable,

   CompilationTarget -> "C", RuntimeOptions -> "Speed"

   ];

Ordering[cf@Range@1*^6, -1] // AbsoluteTiming

贊一下

回復(fù)此樓

10樓2013-10-05 01:49:15

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

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

返回列表

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

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

[考研] 【求調(diào)劑】085601材料工程專碩 \| 總分272 \| +5	腳滑的守法公民 2026-03-27	5/250	2026-03-27 22:50 by lcl13500..
[考研] 070300求調(diào)劑306分 +3	26要上岸 2026-03-27	3/150	2026-03-27 17:57 by arrow8852
[考研] 352分化工與材料 +3	海納百川Ly 2026-03-27	3/150	2026-03-27 17:18 by 楊楊楊紫
[考研] 085602 化工專碩 338分求調(diào)劑 +8	路癡小琪 2026-03-27	8/400	2026-03-27 16:50 by lenovolsw
[考研] 292求調(diào)劑 +13	鵝鵝鵝額額額額?/a> 2026-03-25	14/700	2026-03-27 15:40 by caszguilin
[考研] 考研化學(xué)308分求調(diào)劑 +10	你好明天你好 2026-03-23	12/600	2026-03-27 14:43 by shangxh
[考研] 0703化學(xué)/290求調(diào)劑/本科經(jīng)歷豐富/工科也可 +7	丹青奶蓋 2026-03-26	8/400	2026-03-27 11:24 by 丹青奶蓋
[考研] 調(diào)劑 +3	李嘉圖·S·路 2026-03-27	3/150	2026-03-27 11:19 by wangjy2002
[考研] 316求調(diào)劑 +5	江辭666 2026-03-26	5/250	2026-03-27 08:08 by hypershenger
[考研] 081200-11408-276學(xué)碩求調(diào)劑 +3	崔wj 2026-03-26	3/150	2026-03-27 07:58 by chemisry
[考研] 349求調(diào)劑 +5	杰斯塔里斯 2026-03-21	5/250	2026-03-27 00:31 by wxiongid
[考研] 286求調(diào)劑 +13	Faune 2026-03-21	13/650	2026-03-26 19:52 by peike
[考研] 297求調(diào)劑 +6	田洪有 2026-03-26	6/300	2026-03-26 15:55 by 不吃魚的貓
[考研] 網(wǎng)絡(luò)空間安全0839招調(diào)劑 +4	w320357296 2026-03-25	6/300	2026-03-25 17:59 by 255671
[考研] 285求調(diào)劑 +3	AZMK 2026-03-24	3/150	2026-03-25 12:23 by userper
[考研] 化工專碩求調(diào)劑 +3	question挽風(fēng) 2026-03-24	3/150	2026-03-24 18:48 by jhhcooi
[考研] 306求0703調(diào)劑一志愿華中師范 +10	紙魚ly 2026-03-21	11/550	2026-03-24 17:22 by qingfeng258
[考研] 085404電子信息284分求調(diào)劑 +4	13659058978 2026-03-24	4/200	2026-03-24 12:15 by syl20081243
[考研] 335求調(diào)劑 +4	yuyu宇 2026-03-23	5/250	2026-03-23 23:49 by Txy@872106
[考研] 生物學(xué)調(diào)劑 +5	Surekei 2026-03-21	5/250	2026-03-22 14:39 by tcx007

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

[交流] Euler 工程 第14題：找最長(zhǎng)的數(shù)列 已有6人參與

» 猜你喜歡

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

[交流] Euler 工程第14題：找最長(zhǎng)的數(shù)列已有6人參與

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