「プロジェクトオイラー問１４」の編集履歴（バックアップ）一覧はこちら

「プロジェクトオイラー問１４」(2014/02/13 (木) 14:32:23) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2014

Problem 14 「最長のコラッツ数列」 †
正の整数に以下の式で繰り返し生成する数列を定義する.

n → n/2 (n が偶数)

n → 3n + 1 (n が奇数)

13からはじめるとこの数列は以下のようになる.

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

13から1まで10個の項になる. この数列はどのような数字からはじめても最終的には 1 になると考えられているが, まだそのことは証明されていない(コラッツ問題)
さて, 100万未満の数字の中でどの数字からはじめれば最長の数列を生成するか.
注意: 数列の途中で100万以上になってもよい


解法
とりあえず計算するだけです。
計算途中ある数字になったらそのあとの結果は一意です
例えば
3　16　8　4 2 1
2ならあと１回で１
4ならあと２回で１
8ならあと３回で１
16ならあと４回で１です。
これを２分木でメモ化しておきます。


32　16ときたら
16はメモにあるので4回+32までの１回と計算すれば少しだけ計算量を減らせます。
C++ならこのメモは配列になりますがPrologでは配列がないので、２分木で実装し、また効率の問題から２５万以下までの数をメモしておきました。


 limit(250000):-!.
 f(N,N1):-N mod 2=:=0,!,N1 is N//2.
 f(N,N1):-!,N1 is 3*N+1.
 
 max(A,B,A):-A>B,!.
 max(_,B,B):-!.
 
 
 
 createBTree(LNum,RNum,nil):-
 	LNum+1=:=RNum,
 	!.
 
 createBTree(LNum,RNum,[-1,LTree,RTree]):-
 	MNum is (LNum+RNum)//2,
 	createBTree(LNum,MNum,LTree),
 	createBTree(MNum,RNum,RTree).
 
 
 searchBTree(SearchNum,[NodeNum,_,_],LNum,RNum,NodeNum):-
 	MNum is (LNum+RNum)//2,
 	SearchNum=:=MNum,
 	!.
 
 searchBTree(SearchNum,[_,Left,_],LNum,RNum,Result):-
 	MNum is (LNum+RNum)//2,
 	SearchNum<MNum,
 	!,
 	searchBTree(SearchNum,Left,LNum,MNum,Result).
 
 searchBTree(SearchNum,[_,_,Right],LNum,RNum,Result):-
  	MNum is (LNum+RNum)//2,
         MNum<SearchNum,
 	!,
 	searchBTree(SearchNum,Right,MNum,RNum,Result).
 
 upDateBTree([UpdateNum,Len],[_,Left,Right],LNum,RNum,[Len,Left,Right]):-
 	MNum is (LNum+RNum)//2,
 	MNum=:=UpdateNum,
 	!.
 
 upDateBTree([UpdateNum,Len],[X,Left,Right],LNum,RNum,[X,UpDateLeft,Right]):-
 	MNum is (LNum+RNum)//2,
 	UpdateNum<MNum,
 	!,
 	upDateBTree([UpdateNum,Len],Left,LNum,MNum,UpDateLeft).
 upDateBTree([UpdateNum,Len],[X,Left,Right],LNum,RNum,[X,Left,UpDateRight]):-
 	MNum is (LNum+RNum)//2,
 	MNum<UpdateNum,
 	!,
 	upDateBTree([UpdateNum,Len],Right,MNum,RNum,UpDateRight).

  
 calc(Tree,N,Result,Tree):-
  	limit(Limit),
 	N<Limit,
 	searchBTree(N,Tree,0,Limit,Result),
 	-1 < Result,
  	!.
 calc(Tree,N,Result,NewTree):-
 	!,
 	f(N,N1),
 	calc(Tree,N1,Re,ReTree),
 	Result is Re+1,
 	limit(Limit),
  	(N<Limit -> upDateBTree([N,Result],ReTree,0,Limit,NewTree);
 	NewTree=ReTree).
 
 search(1000000,_,Ans,Ans):-!.
 search(N,Tree,[Len,Ans],Result):-
 	calc(Tree,N,Len1,NewTree),
 	N1 is N+1,
 	(Len<Len1->Ans2 is N,Len2 is Len1;Ans2 is Ans,Len2 is Len),
 	!,
 	search(N1,NewTree,[Ans2,Len2],Result).
  
 
 main14:-
 	limit(Limit),
  	createBTree(0,Limit,Tree),
 	upDateBTree([1,0],Tree,0,Limit,NewTree),
 	search(1,NewTree,[1,0],Ans),
 	write([anser,Ans]).

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2014

Problem 14 「最長のコラッツ数列」 †
正の整数に以下の式で繰り返し生成する数列を定義する.

n → n/2 (n が偶数)

n → 3n + 1 (n が奇数)

13からはじめるとこの数列は以下のようになる.

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

13から1まで10個の項になる. この数列はどのような数字からはじめても最終的には 1 になると考えられているが, まだそのことは証明されていない(コラッツ問題)
さて, 100万未満の数字の中でどの数字からはじめれば最長の数列を生成するか.
注意: 数列の途中で100万以上になってもよい


解法
とりあえず計算するだけです。
計算途中ある数字になったらそのあとの結果は一意です
例えば
3　16　8　4 2 1
2ならあと１回で１
4ならあと２回で１
8ならあと３回で１
16ならあと４回で１です。
これを２分木でメモ化しておきます。


32　16ときたら
16は8の時にメモしたものがあるので4回+32～16への１回＝5回と計算すれば少しだけ計算量を減らせます。
C++ならこのメモは配列になりますがPrologでは配列がないので、２分木で実装し、また効率の問題から２５万以下までの数をメモしておきました。



 limit(250000):-!.
 f(N,N1):-N mod 2=:=0,!,N1 is N//2.
 f(N,N1):-!,N1 is 3*N+1.
 
 max(A,B,A):-A>B,!.
 max(_,B,B):-!.
 
 
 
 createBTree(LNum,RNum,nil):-
 	LNum+1=:=RNum,
 	!.
 
 createBTree(LNum,RNum,[-1,LTree,RTree]):-
 	MNum is (LNum+RNum)//2,
 	createBTree(LNum,MNum,LTree),
 	createBTree(MNum,RNum,RTree).
 
 
 searchBTree(SearchNum,[NodeNum,_,_],LNum,RNum,NodeNum):-
 	MNum is (LNum+RNum)//2,
 	SearchNum=:=MNum,
 	!.
 
 searchBTree(SearchNum,[_,Left,_],LNum,RNum,Result):-
 	MNum is (LNum+RNum)//2,
 	SearchNum<MNum,
 	!,
 	searchBTree(SearchNum,Left,LNum,MNum,Result).
 
 searchBTree(SearchNum,[_,_,Right],LNum,RNum,Result):-
  	MNum is (LNum+RNum)//2,
         MNum<SearchNum,
 	!,
 	searchBTree(SearchNum,Right,MNum,RNum,Result).
 
 upDateBTree([UpdateNum,Len],[_,Left,Right],LNum,RNum,[Len,Left,Right]):-
 	MNum is (LNum+RNum)//2,
 	MNum=:=UpdateNum,
 	!.
 
 upDateBTree([UpdateNum,Len],[X,Left,Right],LNum,RNum,[X,UpDateLeft,Right]):-
 	MNum is (LNum+RNum)//2,
 	UpdateNum<MNum,
 	!,
 	upDateBTree([UpdateNum,Len],Left,LNum,MNum,UpDateLeft).
 upDateBTree([UpdateNum,Len],[X,Left,Right],LNum,RNum,[X,Left,UpDateRight]):-
 	MNum is (LNum+RNum)//2,
 	MNum<UpdateNum,
 	!,
 	upDateBTree([UpdateNum,Len],Right,MNum,RNum,UpDateRight).
  
  
 calc(Tree,N,Result,Tree):-
  	limit(Limit),
 	N<Limit,
 	searchBTree(N,Tree,0,Limit,Result),
 	-1 < Result,
  	!.
 calc(Tree,N,Result,NewTree):-
 	!,
 	f(N,N1),
 	calc(Tree,N1,Re,ReTree),
 	Result is Re+1,
 	limit(Limit),
  	(N<Limit -> upDateBTree([N,Result],ReTree,0,Limit,NewTree);
 	NewTree=ReTree).
 
 search(1000000,_,Ans,Ans):-!.
 search(N,Tree,[Len,Ans],Result):-
 	calc(Tree,N,Len1,NewTree),
 	N1 is N+1,
 	(Len<Len1->Ans2 is N,Len2 is Len1;Ans2 is Ans,Len2 is Len),
 	!,
 	search(N1,NewTree,[Ans2,Len2],Result).
  
 
 main14:-
 	limit(Limit),
  	createBTree(0,Limit,Tree),
 	upDateBTree([1,0],Tree,0,Limit,NewTree),
 	search(1,NewTree,[1,0],Ans),
 	write([anser,Ans]).