3n+1問題（問題１００）
http://acm.uva.es/p/v1/100.htmlを昨夜はずっと解いてました。問題を簡単に書くと、次のようになります。
整数nが与えられます。次に、計算ルールとして、nが偶数のときはnを２で割り、奇数のときはnを3倍して１を足します。これを、nが１になるまで続けます。そして、nが１になるのに必要なこの計算の合計回数をnの寿命とします。で、問題は、整数iとjが与えられたとき、iとjの間の数の中で最大の寿命を求めよというものです。
プログラムとしては、非常にシンプルに書けます。寿命を求める関数をcycleとすると、問題は次のようなプログラムになります。（とりあえず、C言語で書いてみる）
int solve( int i, int j )
{
int max = 0;
for( int n=i; n<=j; n++ )
if( cycle(n) > max )
max = cycle(n);
return max;
}
また、寿命を求める関数cycleは次にようになります。
int cycle( int n )
{
int c=1;
while( n !- 1 ){
if( n%2 -- 1 ) n = 3*n+1;
else n = n / 2;
c = c + 1;
}
return c;
}
しかし、それでは面白くないし、いちいち再計算をしなければならないため、実行時間が大きくなってしまう。実行結果をテーブルにキャッシングしておくという手があるけど、それでは小手先の改良に過ぎない。
もっと根本的な改良はないかと言うことで、ダイナミックプログラミングの要素を取り入れることにした。すなわち、n=1から始める幅優先探査であらかじめテーブルを作成してしまおうということです。
このプロセスは次のようになります。
count = 1;
An = {1};
Live[n] : the table of cycle(n);
while( size of An > 0 ){
forall n ∈ An
Live[n] = count;
if( n*2 <= MAX )
add n*2 to An';
if( (n-1)%3==0 && (n-1)/3%2!=0 && (n-1)/3>1 )
add (n-1)/3 to An';
An = An';
count = count + 1;
}
かなり適当な言語になってしまいましたけど、こんな感じです。これは、計算ルールの適用で、nになる数字は、n*2と、(n-1)/3になります。ですから、A1={1}からはじめて、A2={2}, A3={4}, A4={8}, A5={16}, A6={32,5}, A7={64,10}, A8={128,21,3}...と続けていくことで、テーブルを作ってしまおうというやつです。
もしここで、求めなければならない最大の整数をｎ、可能性のある最大寿命がｋであったとします。このとき、最初の解き方で必要な計算オーダーはknとなります（たぶん）。次に、改良した解き方の計算オーダーは、ｎになります（かなり自信がない）。ですから、改良した方が圧倒的に速くなるはずです。
さて、これでサンプルとして与えられている入力に対して、出力は正しい結果を返しました。そこで、オンラインジャッジ！！をしてもらいました。
結果は、不合格。
何がいけないんだろうと、いろいろテストをしてみました。そしたら、恐ろしいバグ！？を発見してしまいました。そのバグとは、nの最大値の見積もりでした。
私は、nの最大値は、調べたい数字の３倍ぐらい取っておけば良いと考えていました。すなわち、iとjの間の全ての整数の寿命を調べるためには、nの最大値はmax(i,j)*3ぐらいと想定してプログラムを書いていました。なぜこのような最大値の想定が必要かというと、今回考えた幅優先探査によるアルゴリズムは、最大値の制限を設けないと、永遠にAnの探索を行ってしまいます。ですから、最大値MAXを与えることで、新たにAn'を作るときに最大値MAXを超える数値は登録しないようにすることで、収束させることをもくろみました。また、このアルゴリズムを利用すると、最大値MAXまでのすべての表を生成することはできません。特にMAXに近づくにつれて、寿命が求められていない数字が多くなります。ですから、ある程度の数までぎっしり詰まったテーブルを生成するには、MAXを大きく取る必要があります。
で、問題文によると、iとjの最大値は1,000,000です。これは、２０ビットほどで表現できる数です。さて、ではこの最大値までぎっしり詰まったテーブルを求めるために、MAXはいくつにすればよいでしょうか。
それで、MAXに対する、テーブルの隙間ができる数を、実験して求めました。
10 4
100 15
1000 27
10000 255
100000 703
1000000 1819
10000000 9663
で、ぜんぜんたらねえ！！これ以上MAXを大きくすると、メモリが足らなくて終了してしまう！！
ということで、ちとこれより対策を考える。とりあえず、２乗までは必要なさそうなので、MAXが32ビットに収まってくれると良いんだけど。。。
