「プロジェクトオイラー問９２」の編集履歴（バックアップ）一覧はこちら
「プロジェクトオイラー問９２」(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).
解法２
Ｃ++で書き直した高速な解法
計算量は8*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);
}
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);
}
