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

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

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



C++で書き直した正しいコード。
リストをstd::mapに書き換えた結果
計算量も　log2(n)/nだけ低減している。
桁数の計算で微妙な誤差が出る可能性があるので少しマージンを取っています。


 #include<stdio.h>
 #include<iostream>
 #include<map>
 #include<vector>
 #include<algorithm>
 #include<set>
 struct S{
 	__int64 N3;
 	std::vector<char> zisyo;
 	bool operator<(const S& s)const{
		return zisyo<s.zisyo;
   	}
 	void setN(__int64 N){
 		N3 = N;
 		zisyo.clear();
 		while(N>0){
 			zisyo.push_back(N%10+'0');
  			N/=10;
 		}
 		std::sort(zisyo.begin(),zisyo.end());
 	}
 };
 
 
 int main(){
 	std::map<S,int> memo;
 	std::map<S,int>::iterator mIt;
  	std::set<__int64> tempAns;
 	S s1;
 	for(__int64 i=4;;i++){
 		__int64 N3A =i*i*i;
  		__int64 N3B =(i-3)*(i-3)*(i-3);
 		int ketaA=floor(log(N3A)/log(10));
 		int ketaB=floor(log(N3B)/log(10));
 		if(ketaA>ketaB&&tempAns.size()>0){
 			break;
 		}else{
 			s1.setN(N3A);
 			if(memo.find(s1)==memo.end())memo[s1]=0;
 			memo[s1]++;
 			mIt=memo.lower_bound(s1);
  			s1=(*mIt).first;
			int c=(*mIt).second;
 			if(c==5)tempAns.insert(s1.N3);
 			if(c>5)tempAns.erase(s1.N3);
 		}
 	}
 	for(std::set<__int64>::iterator it=tempAns.begin();it!=tempAns.end();it++){
 		std::cout<<(*it)<<" ";
 	}
 }