3n+1問題
30分プログラム、その54。
http://acm.uva.es/p/v1/100.html via http://www.agusa.i.is.nagoya-u.ac.jp/person/mzp/hiki/?exercise。
- もし現在の値が1なら、終了する
- もし現在の値が偶数なら、半分にする
- もし現在の値が奇数なら、3倍して1を足す
という操作を与えられた数値に対して繰り返す。例えば10が与えられた場合には、
10 5 16 8 4 2 1となる。どんな入力に対しても、最終的には1になると思われる。この問題では、初期値が1になるまでの系列の長さを求める。この例の場合には、系列の長さはもちろん7である。
プログラムへの入力として大小2つの整数が与えられる。この2つの数値の間にある全ての数に対して1になるまでの系列の長さを求め、その最大値を出力するようなプログラムを書け。
サンプル入力:
1 10 100 200 201 210 900 1000
出力:
20 125 89 174
use strict; use warnings; use List::Util qw(max); sub get_length($){ my $val = shift; my $length = 1; until($val== 1){ if($val % 2 == 0){ # even $val /= 2; }else{ # odd $val = $val*3+1; } $length++; } return $length; } while(<>){ my ($a,$b) = split ' '; my $max=0; for($a..$b){ my $i = get_length($_); $max = $i if $i > $max; } print $max,"\n"; }