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

24小时热门版块排行榜    

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

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的回帖

智能机器人

Robot (super robot)

我们都爱小木虫

找到一些相关的精华帖子，希望有用哦~

科研从小木虫开始，人人为我，我为人人

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的回帖

libralibra

至尊木虫 (著名写手)

骠骑将军
★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
jjdg(金币+2): 辛苦了 2011-05-21 00:51:59
微尘、梦想(程序强帖+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

结果
CODE:
% Elapsed time is 13.644453 seconds.
% ans =
%       837799
赞一下(3人) 回复此楼
matlab/VB/python/c++/Java写程序请发QQ邮件:790404545@qq.com
6楼2011-05-20 21:23:11
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

holmescn

金虫 (正式写手)
微尘、梦想(程序强帖+1): 2011-05-21 19:19:52
matlab果然是不给力啊，Fortran版的只要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

结果同libralibra同学。不过恐怖的是，中间项居然会大于40亿啊。32位整数都保存不了了。最后总共有525项。这东西用Mathematica的NestList展开会是什么样？

现在的计算机速度太快了，以至于我们都不想去找一个更好的解法了，不过，这东西的解空间应该还能减小，我看到2到3000以内都还是单调上涨的呢。
赞一下(2人) 回复此楼
7楼2011-05-21 13:40:36
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
相关版块跳转 我要订阅楼主 holmescn 的主题更新
41/1返回列表
普通表情 龙 兔 虎 猫 高级回复 (可上传附件)
信息提示
关闭
请填处理意见
关闭