「プロジェクトオイラー問９２」の編集履歴（バックアップ）一覧に戻る

プロジェクトオイラー問９２ - (2014/03/04 (火) 20:04:23) のソース

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

*Problem 92 「桁の2乗による連鎖」 †
各桁の2乗を足し合わせて新たな数を作ることを, 同じ数が現れるまで繰り返す.

例えば

　　44 → 32 → 13 → 10 → 1 → 1
　　85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89

のような列である. どちらも1か89で無限ループに陥っている. 
驚くことに, どの数から始めても最終的に1か89に到達する.
では, 10,000,000より小さい数で89に到達する数はいくつあるか.

解法
まずは素朴で低速な方法。
999万9999を変換しても567にしかなりません１回変換すると１０００万までのどんな数も567以下になります。
少し多めに見積もってまずは600までで1に到達したものをメモ化して置きます。
1に到達しなかったものが８９に到達するのですから、600-（1に到達したものの数）が600までの８９に到達する数です。
601～999万9999までは一回変換した数字が1に到達する数にならなければそれは８９に到達します。
しかしこの方法は遅いです。
もっと早い方法があります。



 next_calc1([],0):-!.
 next_calc1([X|Xs],Result):-
 	!,
 	next_calc1(Xs,Re),
 	Result is Re+(X-48)^2.
 
 next_calc(N,Result):-
 	!,
 	number_codes(N,L),
  	next_calc1(L,Result).
 
 
 searchN(1):-!,fail.
 searchN(89):-!.
 searchN(N):-
 	next_calc(N,N1),
 	searchN(N1).
 list1(N):-
 	between(1,600,N),
 	not(searchN(N)).
 search(10000000,_,Ans):-
 	!,
 	write(Ans).
 search(N,List1,Ans):-
 
 	next_calc(N,NN),
 	not(member(NN,List1)),
 	!,
 	N1 is N+1,
 	Ans1 is Ans+1,
 	search(N1,List1,Ans1).
 search(N,List1,Ans):-
 	!,
 	N1 is N+1,
 	search(N1,List1,Ans).
 
 main92:-
 	findall(N,list1(N),List1),
 	length(List1,Len),
 	Ans is 600-Len,
 	search(601,List1,Ans). 






解法２
Ｃ++で書き直した高速な解法
動的計画法を適用している。
97は0000097と解釈して計算している。

計算量は10*7*567+567+567回に低下している。


 #include<stdio.h>
 #include<string.h>
 
 const int BAD=-1;
 const int LIMIT=567;
 
 int memo[8][LIMIT+1];
 int ok89[LIMIT+1]={0};
 
 
 int next_calc(int n){
 	int result=0;
 	while(n!=0){
 		result+=(n%10)*(n%10);
 		n/=10;
 	}
 	return result;
 }
 
 int search(int n){
 	if(n==1){
 		return (ok89[n]=BAD);
 	}
 	if(n==89){
 		return (ok89[n]=1);
 	}
 	return (ok89[n]=search(next_calc(n)));
 } 
 
 
 int main(){
 	memset(memo,0,sizeof(memo));
 	memo[0][0]=1;
 	for(int i=1;i<=LIMIT;i++){
  		if(ok89[i]==0){
 			search(i);
 		}
 	}
 	
 	for(int i=0;i<7;i++){
 		for(int j=0;j<=9;j++){
 			int d=j*j;
  			for(int k=0;k+d<=LIMIT;k++){
 				memo[i+1][k+d]+=memo[i][k];
 			}
 		}
 	}
 	int ans=0;
 	for(int i=1;i<=LIMIT;i++){
 		ans+=ok89[i]==BAD?0:memo[7][i];
 	}
 	printf("%d\n",ans);
 }