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


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という感じで個人的にいい述語が書けたなという感じがします。