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


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にしかなりません1回変換すると1000万までのどんな数も567以下になります。
少し多めに見積もってまずは600までで1に到達したものをメモ化して置きます。
1に到達しなかったものが89に到達するのですから、600-(1に到達したものの数)が600までの89に到達する数です。
601~999万9999までは一回変換した数字が1に到達する数にならなければそれは89に到達します。
しかしこの方法は遅いです。
もっと早い方法があります。



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






解法2
C++で書き直した高速な解法
動的計画法を適用している。
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);
}