「プロジェクトオイラー問３６」の編集履歴（バックアップ）一覧はこちら

「プロジェクトオイラー問３６」(2014/02/14 (金) 18:17:12) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2036
*Problem 36 「二種類の基数による回文数」 †
585 = 10010010012 (2進) は10進でも2進でも回文数である.

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

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



解法
１０進数の回文数だけをpermとtoNumで作って、それが２ビットでも回文数であるか調べるだけです。

 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).

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2036
*Problem 36 「二種類の基数による回文数」 †
585 = 10010010012 (2進) は10進でも2進でも回文数である.

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

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



解法
１０進数の回文数だけをpermとtoNumで作って、それが２ビットでも回文数であるか調べるだけです。
計算量は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).