Euler Project Problem 14 with Ruby
看题
The following iterative sequence is defined for the set of positive integers:
n 
n/2 (n is even)
n 3n + 1 (n is odd)
Using the rule above and starting with 13, we generate the following sequence:
13 40 20 10 5 16 8 4 2 1
40 20 10 5 16 8 4 2 1It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.
Which starting number, under one million, produces the longest chain?
NOTE: Once the chain starts the terms are allowed to go above one million.
Ruby 代码 这个速度还算可以了 4秒之内出结果
#!/d/ruby192/bin/ruby
#coding:utf-8
# get the next num of the chain
def next_num(num)
if num.even?
num/2
else
num*3+1
end
end
$cache = Hash.new(0)
def get_len(num)
if $cache.include?(num)
res = $cache[num]
else
res = get_len(next_num(num))+1
$cache[num] = res
end
res
end
$cache[1] = 1
$cache[2] = 2
$cache[4] = 3
$max,$most = 1,1
# from 1 to 1 million, so that the $cache may be used the most
(1...1_000_000).each do |num|
if $max < get_len(num)
$max = get_len(num)
$most = num
end
end
puts $most,$max
Jul 27, 2011 03:21:59 AM
不斷調用函數挺耗時間的。不知 Ruby 的全局變量調用會不會比局部變量調用更耗時。
其實不使用緩存區的話，用 C 寫的最簡單的代碼（就那個獲取下一個數的函數改成循環），我這一般的機子只需要 1 秒左右就找到了。
10 000 000 以內的話就要六七秒左右，10億以內的就要 25 分鐘。
只要上限一大，就很難緩沖過來的了，緩沖區不夠用。
Jul 27, 2011 09:51:18 AM
@λ: 这里使用 Ruby 的全局变量不是必须的，从 0 => 1 000 000 的循环方向是怕深度递归调用导致栈溢出，其实我也不知道 Ruby 的递归有没有层数限制。 Ruby 我也是刚学不久。
Jul 27, 2011 10:04:15 AM
@tisyang: 看棧有多大了……10億以內的，最長的鏈不超過1000項，再加上你緩存了，我估計最多也只可能用到 300 層的棧，我也用 Perl 的 hash 來試試看好了。
遞歸就更慢了……你這樣用hash表做緩存，算10億內的要用多長時間？
Jul 27, 2011 10:44:01 AM
@λ:
1，000，000 的计算
Jul 27, 2011 11:13:22 AM
這是 Collatz 猜想，Collatz 樹的樹枝太分散了……剛才算 10 億內的差點內存爆掉，算原題的要 10 秒。（用 Perl ）。還是不優化，不緩存，直接算快多了。
Aug 17, 2022 08:47:09 PM
The question paper for the next class 12 final examinations in 2023 has been announced by the Bihar School Examination Board in Patna. Since then, the following pupils have been waiting for the entrance card. Later, the board will release the Important Question Papers; in the meanwhile, applicants can obtain the BSEB 12th Exam New Model Paper 2023, BSEB 12th Sample Question Paper 2023, or BSEB 12th Exam Guess Paper 2023 from the official website or from the URL that we have provided below. BSEB Intermediate Model Paper 2023 In the month of February 2023, the board will administer tests to all candidates who are enrolled in Bihar. Bihar Board also offers following the conclusion of the final examination and after results.
Mar 10, 2023 02:21:26 AM
Glad to chat your blog, I seem to be forward to more reliable articles and I think we all wish to thank so many good articles, blog to share with us. clenbuterol for sale
Apr 24, 2023 11:55:55 PM
I curious more interest in some of them hope you will give more information on this topics in your next articles. Crocodile Dundee Paul Hogan vest
Jun 25, 2023 02:21:42 AM
I am always searching online for articles that can help me. There is obviously a lot to know about this. I think you made some good points in Features also. Keep working, great job ! 다낭 밤문화
Jun 25, 2023 04:52:02 AM
I’m excited to uncover this page. I need to to thank you for ones time for this particularly fantastic read !! I definitely really liked every part of it and i also have you saved to fav to look at new information in your site. خلیج فارس
Jul 10, 2023 06:25:48 AM
We are tied directly into the sate’s renewal database which allows us to process your request almost instantly QUIETUM PLUS
Jul 23, 2023 05:36:09 AM
I have express a few of the articles on your website now, and I really like your style of blogging. I added it to my favorite’s blog site list and will be checking back soon… 41215663
Jul 24, 2023 10:59:03 PM
I found Hubwit as a transparent s ite, a social hub which is a conglomerate of Buyers and Sellers who are ready to offer online digital consultancy at decent cost.
Jan 25, 2024 10:56:37 PM
Pavzi.com is a startup by passionate webmasters and bloggers who have a passion for providing engaging content that is accurate, interesting, and worthy to read. pavzi.com We are more like a web community where you can find different information, resources, and topics on day-to-day incidents or news. We provide you with the finest web content on every topic possible with the help of the editorial and content team.