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

プロジェクトオイラー問４ - (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が回って、暫定的に見つかった最大解より小さくなったら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という感じで個人的にいい述語が書けたなという感じがします。