「プロジェクトオイラー問4」の編集履歴(バックアップ)一覧はこちら
「プロジェクトオイラー問4」(2014/02/12 (水) 09:30:55) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%204
*Problem 4 「最大の回文積」 †
左右どちらから読んでも同じ値になる数を回文数という. 2桁の数の積で表される回文数のうち, 最大のものは 9009 = 91 × 99 である.
では, 3桁の数の積で表される回文数の最大値を求めよ.
解法
まずは数字を一桁ごとのリストに変える述語toList。
リストが左右対称であるかをしらべる述語palindromeを書きます
palindrome(List,[],List):-!.
palindrome(List,[X|Rest],RevList):-
palindrome(List,Rest,[X|RevList]).
toList(0,[]):-!.
toList(N,[X|Result]):-
X is N mod 10,
N1 is N //10,
toList(N1,Result).
次に再帰でループを作ります。
C風に書けば以下のような記述です。
for(int A=999;A>=100;A--){
for(int B=999;B>=A;B--){
//処理
}
}
Aが回ってBが回って、暫定的に見つかった最大解より小さくなったらループを止める、シンプルな話です。
Prologに直訳したものは下記の通り。
stopB(A,B,_):-A>B,!.
stopB(A,B,TempAns):-A*B =< TempAns,!.
loopB(A,B,TempAns,TempAns):-
stopB(A,B,TempAns),
!.
loopB(A,B,_,C):-
C is A*B,
toList(C,KetaList),
palindrome(KetaList,KetaList,_),
!.
loopB(A,B,TempAns,Result):-
B1 is B-1,
loopB(A,B1,TempAns,Result).
loopA(100,Ans,Ans):-!.
loopA(A,TempAns,Result):-
loopB(A,999,TempAns,UpdateAns),
A1 is A-1,
loopA(A1,UpdateAns,Result).
コード全体は以下の通り。
palindrome(List,[],List):-!.
palindrome(List,[X|Rest],RevList):-
palindrome(List,Rest,[X|RevList]).
toList(0,[]):-!.
toList(N,[X|Result]):-
X is N mod 10,
N1 is N //10,
toList(N1,Result).
stopB(A,B,_):-A>B,!.
stopB(A,B,TempAns):-A*B =< TempAns,!.
loopB(A,B,TempAns,TempAns):-
stopB(A,B,TempAns),
!.
loopB(A,B,_,C):-
C is A*B,
toList(C,KetaList),
palindrome(KetaList,KetaList,_),
!.
loopB(A,B,TempAns,Result):-
B1 is B-1,
loopB(A,B1,TempAns,Result).
loopA(100,Ans,Ans):-!.
loopA(A,TempAns,Result):-
loopB(A,999,TempAns,UpdateAns),
A1 is A-1,
loopA(A1,UpdateAns,Result).
main4:-loopA(999,0,Ans),write(Ans).
palindrome述語はいかにもPrologという感じで個人的にいい述語が書けたなという感じがします。
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%204
*Problem 4 「最大の回文積」 †
左右どちらから読んでも同じ値になる数を回文数という. 2桁の数の積で表される回文数のうち, 最大のものは 9009 = 91 × 99 である.
では, 3桁の数の積で表される回文数の最大値を求めよ.
解法
まずは数字を一桁ごとのリストに変える述語toList。
リストが左右対称であるかをしらべる述語palindromeを書きます
palindrome(List,[],List):-!.
palindrome(List,[X|Rest],RevList):-
palindrome(List,Rest,[X|RevList]).
toList(0,[]):-!.
toList(N,[X|Result]):-
X is N mod 10,
N1 is N //10,
toList(N1,Result).
次に再帰でループを作ります。
C風に書けば以下のような記述です。
for(int A=999;A>=100;A--){
for(int B=999;B>=A;B--){
//処理
}
}
Aが回ってBが回って、暫定的に見つかった最大解より小さくなったらBループを抜け出る、シンプルな話です。
Prologに直訳したものは下記の通り。
stopB(A,B,_):-A>B,!.
stopB(A,B,TempAns):-A*B =< TempAns,!.
loopB(A,B,TempAns,TempAns):-
stopB(A,B,TempAns),
!.
loopB(A,B,_,C):-
C is A*B,
toList(C,KetaList),
palindrome(KetaList,KetaList,_),
!.
loopB(A,B,TempAns,Result):-
B1 is B-1,
loopB(A,B1,TempAns,Result).
loopA(100,Ans,Ans):-!.
loopA(A,TempAns,Result):-
loopB(A,999,TempAns,UpdateAns),
A1 is A-1,
loopA(A1,UpdateAns,Result).
コード全体は以下の通り。
palindrome(List,[],List):-!.
palindrome(List,[X|Rest],RevList):-
palindrome(List,Rest,[X|RevList]).
toList(0,[]):-!.
toList(N,[X|Result]):-
X is N mod 10,
N1 is N //10,
toList(N1,Result).
stopB(A,B,_):-A>B,!.
stopB(A,B,TempAns):-A*B =< TempAns,!.
loopB(A,B,TempAns,TempAns):-
stopB(A,B,TempAns),
!.
loopB(A,B,_,C):-
C is A*B,
toList(C,KetaList),
palindrome(KetaList,KetaList,_),
!.
loopB(A,B,TempAns,Result):-
B1 is B-1,
loopB(A,B1,TempAns,Result).
loopA(100,Ans,Ans):-!.
loopA(A,TempAns,Result):-
loopB(A,999,TempAns,UpdateAns),
A1 is A-1,
loopA(A1,UpdateAns,Result).
main4:-loopA(999,0,Ans),write(Ans).
palindrome述語はいかにもPrologという感じで個人的にいい述語が書けたなという感じがします。