Problem 14
14問目。コラッツ数列(?)で100万以内の数字で最も数列が長くなるものを求める。
普通に解くと1分強かかってしまったので、すべての数列の長さを記録しておき、
数字が記録していた数になったら、記録した数にそれまでの回数を加算するという
ことにしました。つまり 10だと初めに 2で割ると5になるから、2で割った 1回に
5の場合の数列の長さを足すということ。これで8秒ほどで解けました。
#!/usr/bin/perl use strict; use warnings; my %collatz; my ($max, $max_index) = p14(1000000); print "max is ", $max, " max index is ", $max_index, "\n"; sub p14 { my ($limit) = @_; my ($max, $max_index) = (0, 0); for my $i(1..$limit){ my $count = count_collatz_number($i); ($max, $max_index) = ($count, $i) if $max < $count; $i++; } return ($max, $max_index); } sub count_collatz_number { my ($num) = @_; my $count = 0; my $num_copy = $num; while ($num != 1) { if( exists $collatz{$num} ){ $collatz{$num_copy} = $count + $collatz{$num}; return $collatz{$num_copy}; } $num = ($num % 2) ? (3 * $num + 1) : ($num / 2); $count++; } $collatz{$num_copy} = $count + 1; return $count + 1; }