※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。


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ならあと1回で1
4ならあと2回で1
8ならあと3回で1
16ならあと4回で1です。
これを2分木でメモ化しておきます。


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



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]).