「プロジェクトオイラー問い51~60」の編集履歴(バックアップ)一覧に戻る

プロジェクトオイラー問い51~60 - (2012/12/21 (金) 19:37:34) のソース

*問い51
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2051
 *3の第1桁を置き換えることで, 13, 23, 43, 53, 73, 83という6つの素数が得られる.
 56**3の第3桁と第4桁を同じ数で置き換ることを考えよう. この5桁の数は7つの素数をもつ最初の例である: 56003, 56113, 56333, 56443, 56663, 56773, 56993. よって, この族の最初の数である      56003は, このような性質を持つ最小の素数である. 
 桁を同じ数で置き換えることで8つの素数が得られる最小の素数を求めよ. (注:連続した桁でなくても良い)

解法
100万までの素数をvectorに格納し、素数の数字それぞれについて*文字にチェンジした全パタンを求めてその出現回数をカウントしてみました。
答えは正しいですし34秒で答えは出るのですが何か間違ったコードを書いてる感がすごくあります。
C++なら遅くても数秒程度で答えが出るコードが正しいコードのような気がします。
答えはもっとシンプル。
そんな気がするのでこの問題後日再チャレンジする予定です。


 #include<stdio.h>
 #include<map>
 #include<string>
 #include<vector>
 #include<stdlib.h>
 #include<iostream>
 #include<string.h>
 #include<set>
 struct S{
 	int num,count;
 };
 std::set<std::string> patternSet;
 std::map<std::string,S> memo;
 const int up=1000000;
 std::vector<int> sosuu;
 bool so[up+1];
 void setMemo(char text[10],char num,int p,int n){
 	if(p==0)patternSet.clear();
 	if(num!=-1){
 		if(patternSet.find(text)==patternSet.end()){
 			patternSet.insert(text);
 			if(memo.find(text)==memo.end()){
 				S s;
 				s.count=1;
 				s.num=n;
 				memo[text]=s;
 			}else{
 				memo[text].count++;
 			}
 		}
 	}
 	if(text[p]=='\0')return;
 	if(num==-1){
 		setMemo(text,-1,p+1,n);
 		char c=text[p];
 		text[p]='*';
 		setMemo(text,c,p+1,n);
 		text[p]=c;
 	}else{
 		setMemo(text,num,p+1,n);
 		if(text[p]==num){
 			text[p]='*';
 			setMemo(text,num,p+1,n);
 			text[p]=num;
 		}
 	}
 }
 void setSo(){
 	int i2;
 	memset(so,true,sizeof(so));
 	so[0]=so[1]=false;
 	for(int i=4;i<=up;i+=2)so[i]=false;
  	sosuu.push_back(2);
  	for(int i=3;i<=up;i+=2){
 		if(so[i]==false)continue;
 		sosuu.push_back(i);
 		i2=i*2;
 		for(int j=i*3;j<=up;j+=i2){
 			so[j]=false;
 		}
 	}
 }
 int main(){
 	setSo();
 	int num;
 	std::string str,str2;
 	for(int i=0;i<sosuu.size();i++){
 		int p=sosuu[i];
 		char text[10];
 		sprintf(text,"%d",p);
 		setMemo(text,-1,0,p);
 		//std::cout<<"\n";
 	}
 	int ans=up+1;
 	std::cout<<memo["56**3"].count<<"\n";
 	for(std::map<std::string,S>::iterator it=memo.begin();it!=memo.end();it++){
 		if((*it).second.count==8&&ans>(*it).second.num){
 			ans=(*it).second.num;
 		}
 	}
 	printf("%d",ans);
 }




*問い53
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2053
パスカルの三角形を101段目まで書いたとき、100万を超える項は何個あるかという問題です。

解法
パスカルの三角形を計算して100万以上になったらその影響下にある項は全て100万で統一して計算するのが一番シンプルですが、それもいいのですが無意味に計算量を抑えて遊んでみました。
一段ずつ上からパスカルの三角形に基づき計算します。
左端から計算して100万を超えたらそこより右は計算しないでその段の残りの項の数からその段の100万を超えた項の数を求め次の段へ計算をすすめます。
この手法なら問題が100000段とかになっても計算量がそんなに増えない程度しか利点がありません。
1段目0C0から計算が始まるので100Crだと101段目まで計算する点に注意するくらいです。


 #include<stdio.h>
 #include<string.h>
 #include<time.h>
 int main(){
 	double start=clock();
 	int memo[102]={0,1,0},ans=0;
 	for(int n=1;n<=101;n++){
 		int next[102]={0};
 		int r;
 		for(r=1;r<=n;r++){
 			next[r]=memo[r-1]+memo[r];
 			if(next[r]>=1000*1000)break;
 		}
 		if(r<n){
 			if(n%2==0){
 				ans+=(n/2-r+1)*2;
 			}else{
 				ans+=(n+1)/2==r?1:1+((n+1)/2-r)*2;
 			}
 		}
 		memcpy(memo,next,sizeof(next));
 	}
 	printf("ans=%d time=%lf",ans,clock()-start);
 }