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

プロジェクトオイラー問６２ - (2014/02/20 (木) 13:46:16) のソース

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2062
Problem 62 「立方数置換」 †
立方数 41063625 (3453) は, 桁の順番を入れ替えると2つの立方数になる: 56623104 (3843) と 66430125 (4053) である. 41063625は, 立方数になるような桁の置換をちょうど3つもつ最小の立方数である.

立方数になるような桁の置換をちょうど5つもつ最小の立方数を求めよ.


解法
３乗の数字を小さいほうから試していき、数字を辞書順で並べ替えたものを基準に集計していきます。
例えば345002なら002345が一つ見つかったとそれぞれ集計していきます。
最初に5個Hitした辞書順があればそれが答えです。
集計で新しい辞書順が出てきたらその時に３乗の数字をカウンタに保管しておきます。

注意深く考えると、ある桁で答えが見つかってもその次の桁に行くまでにより小さな答えが見つからないか、先に６個見つかってないかチェックするかそれが不要なことを証明する必要がありますが。
答えが出たのでこれでもいいかと考えます。
プロジェクトオイラーは趣味のサイト、仕事ではないので気楽に解きます。
正確な回答はn^3と(n-1)^3の桁数が違ったときに、その時に5つと数えられているものがあればその集合を全て求めてその中で最小のものを答えとする必要があります。



 numToList(N,Result):-!,
 	N3 is N*N*N,
 	number_chars(N3,List),
 	msort(List,Result).
 
 
 search(N,Counts,N3):-
 	numToList(N,List),
 	member([4,List,N3],Counts),
 	!.
 
 search(N,Counts,Result):-
 	numToList(N,List),
  	select([C,List,N3],Counts,Counts1),
 	!,
 	N1 is N+1,
 	C1 is C+1,
 	search(N1,[[C1,List,N3]|Counts1],Result).
 search(N,Counts,Result):-
 	!,
 	N1 is N+1,
 	N3 is N^3,
 	numToList(N,List),
 	search(N1,[[1,List,N3]|Counts],Result).
 
 main62:-
 	search(1,[],Ans),write(Ans).