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

Problem 36 「二種類の基数による回文数」 †

585 = 10010010012 (2進) は10進でも2進でも回文数である.

100万未満で10進でも2進でも回文数になるような数の総和を求めよ.

(注: 先頭に0を含めて回文にすることは許されない.)



解法
10進数の回文数だけをpermとtoNumで作って、それが2ビットでも回文数であるか調べるだけです。
計算量は999*2+99*2+9*2回。

perm([_]).
perm([X,X]).
perm([X,_,X]).
perm([X,Y,Y,X]).
perm([X,Y,_,Y,X]).
perm([X,Y,Z,Z,Y,X]).

toBit(0,[]):-!.
toBit(N,[X|Result]):-
	X is N mod 2,
	N1 is N//2,
	toBit(N1,Result).

toNum([],0):-!.
toNum([X|Xs],Result):-
	toNum(Xs,Re),
	Result is Re*10+X.

commitPerm([]):-!.
commitPerm([X|Xs]):-
	member(X,[0,1,2,3,4,5,6,7,8,9]),
	commitPerm(Xs).

all_search(N):-
	perm(Perm),
	commitPerm(Perm),
	[Top|_]=Perm,
	Top>0,
	toNum(Perm,N),
	toBit(N,Bits),
 	reverse(Bits,Bits).

sum([],0):-!.
sum([X|Xs],Result):-
	sum(Xs,Re),
 	Result is Re+X.

main36:-
	findall(N,all_search(N),Nums),
	sum(Nums,Ans),
	write(Ans).