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

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

オイラープロジェクト41~50 - (2012/08/31 (金) 20:25:47) の編集履歴(バックアップ)


問い41

n桁Pandigitalであるとは, 1からnまでの数を各桁に1つずつもつこととする.
#下のリンク先にあるような数学的定義とは異なる
例えば2143は4桁Pandigital数であり, かつ素数である. n桁(この問題の定義では9桁以下)Pandigitalな素数の中で最大の数を答えよ.

パンデジタル数を大きい順に順列で生成して後は素数かどうか簡易検査するだけです。



#include<stdio.h>
#include<math.h>
bool perms[10];
int ans=-1;
bool isSosuu(int n){
//素数かどうかの簡易チェック
int m=sqrt(n);
if(n==m*m||n%2==0)return false;//2の倍数かmで割り切れるなら
for(int i=3;i<m;i+=2){
	if(n%i==0)return false;//奇数で割ってみる
}
return true;
}
void saiki(int sum,int deep,int k){
if(deep==k){
	//printf("%d\n",sum);
	if(isSosuu(sum)==true){
		ans=sum;
	}
}else{
	for(int i=k;i>0;i--){
		if(perms[i]==true){
			perms[i]=false;
			saiki(sum*10+i,deep+1,k);
			if(ans!=-1)return ;
			perms[i]=true;
		}
	}
}

}
int main(){
perms[0]=false;
for(int i=9;i>0;i--){
	//桁数i
	for(int j=1;j<=i;j++)perms[j]=true;
	saiki(0,0,i);
	if(ans!=-1)break;
}
printf("%d\n",ans);
}



問い42

三角語と呼ばれる単語がテキストファイルの中にいくつあるか数える問題。
最大値の見極めがつかないので少しメモリをぜいたくに使って後は愚直に一つずつ計算。
まあ計算すればいいわけだけどファイルは中身が見えないブラックなファイルとして扱いたいし、練習問題でコードサイズは膨らましたくないのでこのコードに落ち着いた感じ。




#include <stdio.h>
#include <string.h>
 #include <map>
int main(){
	FILE *fp;
	if((fp=fopen("words.txt","r"))==NULL){
		printf("fileOpenError");
		exit(EXIT_FAILURE);
	}
	char text[102];
	int max=0;
	std::map<int,int> memo;
	while(fscanf(fp,"\"%[^\"]\",",text)>0){
		int sum=0;
		for(int i=0;i<strlen(text);i++){
			sum+=text[i]-'A'+1;
		}
	//printf("(%s %d %d)",text,sum,max);
		if(max<sum)max=sum;
		if(memo.find(sum)!=memo.end()){
			memo[sum]++;
		}else{
			memo[sum]=1;
		}
	}
	fclose(fp);
int t=0,ans=0; 
	for(int i=1;t<=max;i++){
		t=((i+1)*i)/2;
		ans+=memo.find(t)!=memo.end()?memo[t]:0;
	} 
	printf("%d\n",ans);
}




問い43

数1406357289は0から9のPandigital数である (0から9が1度ずつ現れるので). この数は部分語が面白い性質を持っている.
d1を1桁目, d2を2桁目の数とし, 以下順にdnを定義する. この記法を用いると次のことが分かる.
d2d3d4=406は2で割り切れる
d3d4d5=063は3で割り切れる
d4d5d6=635は5で割り切れる
d5d6d7=357は7で割り切れる
d6d7d8=572は11で割り切れる
d7d8d9=728は13で割り切れる
d8d9d10=289は17で割り切れる
このような性質をもつ0から9のPandigital数の総和を求めよ.

saiki関数をつかってパンデジタル数を順列生成しチェック関数で条件を満たすかチェックします。


#include<stdio.h>
#include<math.h>
#include<iostream>
bool perms[10];
__int64 ans=0;
bool check(__int64 n){
int so[]={17,13,11,7,5,3,2};
for(int i=0;i<7;i++){
	if((n%1000)%so[i]!=0){
		return false;
	}
	n/=10;
}
return true;
}
void saiki(__int64 sum,int deep){
if(deep==10){
	if(check(sum)==true){
		std::cout<<sum<<" ";
		ans+=sum;
	}
}else{
	for(int i=0;i<10;i++){
		if(deep==0&&i==0)continue;//先頭は0になってはいけない
		if(perms[i]==true){
			perms[i]=false;
			saiki(sum*10+i,deep+1);
			perms[i]=true;
		}
	}
}

}
int main(){
for(int i=0;i<10;i++)perms[i]=true;
saiki(0,0);
std::cout<<"\n\n"<<ans;
}


問い44

5角数Pi,Pjについて考える。
Pi+PjとD=|Pi-Pj|の両方が5角数になる時の最小のDを答えよ。
とりあえず最初に見つかった条件を満たす数を投稿したら合格したものの、厳密にはきちんとは解けてない問題。
このコードはもっと大きな数の差分に条件を満たす数がないか続きを調べさせるといつまでも計算が終わらない。




#include<stdio.h>
#include<set>
#include<iostream>
int main(){
__int64 min=-1,num1,num2,i=2,j,ansD,ansUP;
std::set<__int64> memo,next;
std::set<__int64>::reverse_iterator it;
memo.insert(1);
	
while(1){
	num1=(i*(3*i-1))/2;
	j=i-1;
	num2=(j*(3*j-1))/2;
	if(min>-1&&num1-num2>=min)break;
	__int64 k=i+1;
	next.clear();
	while((k*(3*k-1))/2<=num1*2){
		next.insert((k*(3*k-1))/2);
		k++;
	}
	for(it=memo.rbegin();it!=memo.rend();it++){
		if((*it)>num1)continue;
		num2=num1-(*it);
		if(min>-1&&num2>=min)break;
		if((min==-1||min>num2)&&memo.find(num2)!=memo.end()&&next.find(num1+(*it))!=next.end()){
			min=num2;
			ansUP=num1;
			ansD=(*it);
			std::cout<<min<<" "<<ansUP<<" "<<ansD;
			return 0;
		}
	}
	memo.insert(num1);
	i++;
}
}





問い45

三角数∧5角数∧6角数∧40755より大きな最小の数を求めよ。
マージソートの考え方で小さい分を少しずつ増量させればいいです。
意外と大きな数が答えになりました。

#include<stdio.h>
#include<iostream>
int main(){
__int64 n3=286,n5=166,n6=144,p3,p5,p6;
p3=(n3*(n3+1))/2;
p5=(n5*(3*n5-1))/2;
p6=(n6*(2*n6-1));

while(p3!=p5 || p5!=p6 || p3!=p6){
	if(p3<=p5 && p3<=p6){
		n3++;
	}else if(p5<=p3 && p5<=p6){
		n5++;
	}else if(p6<=p3 && p6<=p5){
		n6++;
	}
	p3=(n3*(n3+1))/2;
	p5=(n5*(3*n5-1))/2;
	p6=(n6*(2*n6-1));
	//std::cout<<p3<<" "<<p5<<" "<<p6<<"\n";
}
std::cout<<p3<<" "<<p5<<" "<<p6; 
}





問い46

Christian Goldbachは全ての奇合成数は平方数の2倍と素数の和で表せると予想した.
9 = 7 + 2×12
15 = 7 + 2×22
21 = 3 + 2×32
25 = 7 + 2×32
27 = 19 + 2×22
33 = 31 + 2×12
後に, この予想は誤りであることが分かった.
平方数の2倍と素数の和で表せない最小の奇合成数を答えよ.
答えは5777、あのゴールドバッハがこんな小さな数で間違いが出る予想をするというのも面白い。
おそらく理論的に考えて理論的ミスを犯したんだろうな。



#include<stdio.h>
#include<vector>
#include<algorithm>
const int up=1000000;
std::vector<int> kiGousei;
bool so[up];
void setKiGousei(){
int i2;
memset(so,true,sizeof(so));
for(int i=0;i<=up;i+=2)so[i]=false;//まあ大した計算量じゃないし手抜き
so[1]=false;
so[2]=true;
for(int i=3;i<=up;i+=2){
	if(so[i]==false){
		kiGousei.push_back(i);
	}else{
		i2=i*2;
		for(int j=i*3;j<up;j+=i2){
			so[j]=false;
		}
	}
}
}
int main(){
setKiGousei();
//for(int i=0;i<10;i++){
	//printf("%d ",kiGousei[i]);
//}
int n,m;
for(int i=0;i<kiGousei.size();i++){
	n=kiGousei[i];
	bool hit=false;
	for(int j=1;2*j*j<n;j++){
		m=n-2*j*j;
		if(so[m]==true){
			hit=true;
			break;
		}
	}
	if(hit==false){
		printf("%d",n);
		break;
	}
}
}




問い48

Σi^i(i=1...1000)の下10ケタを求めよという問題。


int main(){
__int64 ans=0,b,m=10000000000;
for(int i=1;i<1001;i++){
	b=1;
	for(int j=0;j<i;j++){
		b=(b*i)%m;//ここは工夫して計算量を落としてもいいんだけどたった100万回だしまあいいか
	}
	ans=(ans+b)%m;
}
std::cout<<ans;
}