24小时热门版块排行榜

返回列表

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

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

holmescn

金虫 (正式写手)

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

[交流] Euler 工程第14题：找最长的数列已有6人参与

周末了，放个题出来玩玩：

定义一个正整数数列，其迭代公式为：
n = n/2 (当n为偶数)
n = 3n+1 (当n为奇数)

比如从n=13开始，计算这个数列得：
13 ->40->20->10->5->16->8->4->1
这个数列一共有10项。
这个数列是不是总收敛到1还是个没有解决的问题（称为Collatz Problem)
不过，我们并不是要解这个难题，而是要求在小于1百万的所有起始数中，哪个数能产生最长的数列。

这里要注意的是，数列中间的项是可以大于1百万的，要看提最后数列终止到1时候的长度。

PS：这东西不能用归纳法证出来吗？
PS2：注意1分钟原则啊。不过，大于1分钟的程序也可以发上来，这样才有的交流。

Here we go!

回复此楼

» 猜你喜欢

上海工程技术大学【激光智能制造】课题组招收硕士已经有6人回复
带资进组求博导收留已经有11人回复
自荐读博已经有5人回复
求个博导看看已经有16人回复
上海工程技术大学张培磊教授团队招收博士生已经有4人回复
求助院士们，这个如何合成呀已经有4人回复
临港实验室与上科大联培博士招生1名已经有9人回复
写了一篇“相变储能技术在冷库中应用”的论文，论文内容以实验为主，投什么期刊合适？已经有6人回复
最近几年招的学生写论文不引自己组发的文章已经有11人回复
中科院杭州医学所招收博士生一名（生物分析化学、药物递送）已经有3人回复

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

Euler 工程第四十四题已经有4人回复
Euler 工程第四十二题: 三角词已经有4人回复
Euler 工程第四十一题已经有5人回复
Euler 工程第三十八题已经有9人回复
Euler 工程第三十七题已经有6人回复
Euler 工程第三十六题：已经有18人回复
Euler 工程第三十五题：循环质数已经有16人回复
Euler 工程第三十二题：pandigital 数已经有3人回复
Euler 工程第三十一题: 换零钱已经有10人回复
Euler 工程第三十题已经有12人回复
Euler 工程第廿九题：有多少不同的项? 已经有30人回复
Euler 工程第廿八题：旋转矩阵对角线的和已经有6人回复
Euler 工程第廿七题：系数的积已经有15人回复
Euler 工程第廿六题：最长的循环节已经有9人回复
Euler 工程第廿五题：Fibonacci 数列第一个包含1000个数字的项已经有3人回复
Euler 工程第廿四题：全排列的第100万项已经有19人回复
Euler 工程第廿三题：已经有16人回复
Euler 工程第廿二题: 姓的总分已经有13人回复
Euler 工程第廿题：100! 的各项和已经有5人回复
Euler 工程第十九题：每月第一天是周日的天数已经有4人回复
Euler 工程第十八题：三角阵上最大的和已经有12人回复
Euler 工程第十六题：2的1000次方的各项和已经有14人回复
Euler 工程第十一题：相邻元素乘积最大已经有10人回复
Euler 工程第三题：寻找600851475143的最大质因子已经有18人回复

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

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

wangww2011

木虫 (著名写手)

程序强帖: 13
应助: 11 (小学生)
金币: 4023.1
散金: 2709
红花: 18
沙发: 1
帖子: 1915
在线: 1537.1小时
虫号: 772953
注册: 2009-05-17
性别: GG
专业: 凝聚态物性 II ：电子结构

★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
余泽成(金币+1): 说到！ 2011-05-20 21:02:42
微尘、梦想(程序强帖+1): 很好，欢迎常来！ 2011-05-21 19:18:45

给个迭代算法吧，0.05s 先看结果：

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

回复此楼

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

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

查看全部 10 个回答

huycwork

金虫 (著名写手)

程序强帖: 22
应助: 0 (幼儿园)
金币: 953
散金: 663
红花: 8
沙发: 13
帖子: 1080
在线: 264.1小时
虫号: 1257243
注册: 2011-04-06
专业: 金融学

★ ★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
余泽成(金币+3, 程序强帖+1): 辛苦了！ 2011-05-20 21:02:20

昨天写好这个了，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<
}