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

「プロジェクトオイラー問い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);
}



















問い60

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2060
素数3, 7, 109, 673は非凡な性質を持っている. 任意の2つの素数を任意の順で繋げると, また素数になっている. 例えば, 7と109を用いると, 7109と1097の両方が素数である. これら4つの素数の和は792である. これは, このような性質をもつ4つの素数の組の和の中で最小である.
任意の2つの素数を繋げたときに別の素数が生成される, 5つの素数の組の和の中で最小のものを求めよ.

解法
全然だめでした、賢い解法思いつきませんね。
素数を点、結合可能な素数の組を線からなるグラフとみて、3万以下の素数についてグラフが五望星をなしている場所を探索で探してみましたがコードは膨らむし速度は出ないしで駄目ですね。
グラフの生成部分が物凄く遅くc++なのに答えを出すのに34秒もかかってます。
こんなコードではプロジェクトオイラーでは負け組みな気がします。


#include<stdio.h>
#include<vector>
#include<algorithm>
#include<map>
#include<stdlib.h>
#include<set>
#include<string.h>
#include<string>
#include<time.h>

const int up=100000;
std::vector<__int64> sosuu;
bool isPrime[up+1];
std::map<int,std::set<int> > cons;
int ans=0;

void setPrime(){
	int i2;
	memset(isPrime,true,sizeof(isPrime));
	isPrime[0]=isPrime[1]=false;
	for(int i=4;i<=up;i+=2)isPrime[i]=false;
	sosuu.push_back(2);
 	for(int i=3;i<=up;i+=2){
		if(isPrime[i]==false)continue;
		sosuu.push_back(i);
		i2=i*2;
		for(int j=i*3;j<=up;j+=i2){
			isPrime[j]=false;
		}
	}
}
bool checkPrime(__int64 n){
	if(n<2)return false;
	for(int i=0;sosuu[i]*sosuu[i]<=n;i++){
		if(n%sosuu[i]==0)return false;
	}
	return true;
}

void setConnect(){
	char text[20];
	__int64 a,b;
	for(int i=0;sosuu[i]<=30000;i++){
		for(int j=i+1;sosuu[j]<=30000;j++){
			sprintf(text,"%I64lld%I64lld",sosuu[i],sosuu[j]);
			sscanf(text,"%I64lld",&a);
			sprintf(text,"%I64lld%I64lld",sosuu[j],sosuu[i]);
			sscanf(text,"%I64lld",&b);
			if(checkPrime(a)==true&&checkPrime(b)==true){
				cons[sosuu[i]].insert(sosuu[j]);
			}
		}
	}
}
bool addOK(std::set<int>& perm,int addNum){
	for(std::set<int>::iterator it=perm.begin();it!=perm.end();it++){
		if(cons[(*it)].find(addNum)==cons[(*it)].end())return false;
	}
	return true;
}

void print(std::set<int> perm,int num){
	printf("解候補の組(%d ",num);
	for(std::set<int>::iterator it=perm.begin();it!=perm.end();it++){
		printf("%d ",(*it));
	} 
	printf(")\n");
}

void saiki(int num,std::set<int>::iterator it,int count,int wa,std::set<int>& perm){
	if(ans!=0&&ans<=wa)return;
	if(count==4){
		print(perm,num);
		ans=wa;
 		return;
	}
	int wa2;
	if(count!=0)it++;
	for(;it!=cons[num].end();it++){
		if(addOK(perm,(*it))==true){
			wa2=wa+(*it);
			perm.insert(*it);
			saiki(num,it,count+1,wa2,perm);
			perm.erase(*it);
		}
	}
	
}

int main(){
	double start=clock();
	setPrime();
	printf("処理0終了\n");
	setConnect();
	printf("処理1終了 サイズ%d\n",cons.size());
	std::set<int> perm;
	for(std::map<int,std::set<int> >::iterator it=cons.begin();it!=cons.end();it++){
		if((*it).second.size()>3)saiki((*it).first,(*it).second.begin(),0,(*it).first,perm);
	}
	printf("\nans=%d time=%lf",ans,clock()-start);
}