应《网络安全法》要求，自2017年10月1日起，未进行实名认证将不得使用互联网跟帖服务。为保障您的帐号能够正常使用，请尽快对帐号进行手机号验证，感谢您的理解与支持！

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 计算模拟区 » 程序语言 » 其它 » Euler 工程 第14题：找最长的数列
51/1返回列表
查看: 3076  |  回复: 9
只看楼主 @他人 存档 新回复提醒 (忽略) 收藏    在APP中查看
本帖产生 4 个 程序强帖 ，点击这里进行查看
当前只显示满足指定条件的回帖，点击这里查看本话题的所有回帖

holmescn

金虫 (正式写手)

[交流] 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!
回复此楼

» 猜你喜欢

» 本主题相关价值贴推荐，对您同样有帮助:
1楼 2011-05-20 16:41:24
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

holmescn

金虫 (正式写手)
★
余泽成(金币+1): 谢谢参与交流！ 2011-05-22 11:53:05
引用回帖:
Originally posted by wmc_1979 at 2011-05-21 20:04:41:
我计算出是     837799
项数  524

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

当n=1的时候，就退出循环了，所以认为最后计数的时候没有数1
赞一下(1人) 回复此楼
9楼2011-05-22 09:08:54
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
查看全部 10 个回答

huycwork

金虫 (著名写手)
★ ★ ★ ★
小木虫(金币+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< }
赞一下(2人) 回复此楼
漩涡的中心有一块空地，空空的。
2楼2011-05-20 17:05:54
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

wangww2011

木虫 (著名写手)
★ ★
小木虫(金币+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的回帖

huycwork

金虫 (著名写手)
★ ★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
余泽成(金币+3): 鼓励交流！ 2011-05-20 21:03:01
这个用归纳法证明是证明不出来的
前提条件可以选2->1
但是后面无法作出归纳假设：就算你假设an -> ak，归纳的下一步骤就是a(n+1)没法推导a(k+1)，你看代码就知道了，你无法知道中间产生的链条有多长，实际原因是无法知道中间经过的元素有哪些，当然也就无法归纳证明。
赞一下(2人) 回复此楼
漩涡的中心有一块空地，空空的。
4楼2011-05-20 18:03:01
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
查看全部 10 个回答
普通表情 龙 兔 虎 猫 高级回复 (可上传附件)
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[基金申请] 什么时候开奖？ +4 CrisMessi 2026-08-18 4/200 2026-08-19 00:53 by gatelove
[基金申请] 咱们一起用铁证分析2026国家社科基金中标与否 +7 启萌科技 2026-08-12 27/1350 2026-08-18 21:44 by Noways
[教师之家] 为什么余额宝的年化利率越来越低？主要原因有哪些？ +3 瞬息宇宙 2026-08-15 3/150 2026-08-18 21:40 by xiaohuixin
[基金申请] 2027广东省杰青 +3 奶牛小黑 2026-08-15 9/450 2026-08-18 20:09 by 奶牛小黑
[基金申请] 朋友圈看到的 +4 wangzilk 2026-08-18 5/250 2026-08-18 19:25 by wangzilk
[基金申请] 明天放榜？ +5 Shxjjxjkx 2026-08-18 5/250 2026-08-18 18:14 by -大大大大大-
[基金申请] 时间戳变了，能看出什么问题？ +8 基诺咪客 2026-08-17 11/550 2026-08-18 17:13 by 悠然熊猫
[基金申请] 重要消息，中午系统在维护 +9 yuleib84 2026-08-18 10/500 2026-08-18 16:52 by archvillain
[论文投稿] 投稿咨询 +4 wwm09 2026-08-17 6/300 2026-08-18 15:36 by wwm09
[基金申请] 今天维护系统维护 祝所有人 高中 +8 gjjjzhong 2026-08-18 9/450 2026-08-18 13:01 by 家与远方
[基金申请] 哪位老哥知道今年的国自然具体哪一天放榜？ +13 Ldrop2023 2026-08-13 16/800 2026-08-18 12:25 by 淀粉搬运工
[基金申请] 快农历七夕节了，轻松一下，男人悄悄话，女施主请不要进来。 +4 Tide man 2026-08-14 5/250 2026-08-18 11:35 by Tide man
[基金申请] 感觉是下周放榜了 +6 angus9576 2026-08-17 11/550 2026-08-17 23:57 by angus9576
[基金申请] filecode=后面第一个是大写字母 +8 wangze12014 2026-08-14 10/500 2026-08-17 17:05 by xter9665
[基金申请] 今天系统多次维护，明天很可能放榜！ +8 zju2000 2026-08-16 9/450 2026-08-17 12:20 by lmz0216
[精细化工] 招聘 金属平磨液，抛光液研发工程师 +3 小天0311 2026-08-14 3/150 2026-08-16 07:31 by H9PLUS
[基金申请] 各位道友，我要去昆明玩几天，回来见。 +7 Tide man 2026-08-14 8/400 2026-08-15 01:11 by arzu_hma
[基金申请] 不应该看fileCode +7 且听虎啸 2026-08-12 9/450 2026-08-13 14:27 by flydreamws
[基金申请] Filecode 又变了，巨变 +3 WH3796 2026-08-12 4/200 2026-08-13 14:13 by 小木虫6752397
[基金申请] 结合人工智能，周易传统文化，filecode打分制来了，3分以上希望很大。 +3 Tide man 2026-08-12 4/200 2026-08-13 08:35 by ZJTJZ
信息提示
关闭
请填处理意见
关闭