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!

回复此楼

» 猜你喜欢

北京211副教授，35岁，想重新出发，去国外做博后，怎么样？已经有5人回复
论文终于录用啦！满足毕业条件了已经有25人回复
2026年机械制造与材料应用国际会议（ICMMMA 2026）已经有3人回复
自荐读博已经有3人回复
求助:我三月中下旬出站，青基依托单位怎么办？已经有5人回复
不自信的我已经有5人回复
磺酰氟产物，毕不了业了！已经有4人回复
投稿Elsevier的杂志（返修），总是在选择OA和subscription界面被踢皮球已经有8人回复

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

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