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

オイラープロジェクト61～70 - (2012/09/02 (日) 07:25:33) の編集履歴(バックアップ)

---

問い61

三角数, 四角数, 五角数, 六角数, 七角数, 八角数は多角数であり, それぞれ以下の式で生成される.
三角数 P3,n=n(n+1)/2 1, 3, 6, 10, 15, ...
四角数 P4,n=n2 1, 4, 9, 16, 25, ...
五角数 P5,n=n(3n-1)/2 1, 5, 12, 22, 35, ...
六角数 P6,n=n(2n-1) 1, 6, 15, 28, 45, ...
七角数 P7,n=n(5n-3)/2 1, 7, 18, 34, 55, ...
八角数 P8,n=n(3n-2) 1, 8, 21, 40, 65, ...
3つの4桁の数の順番付きの集合 (8128, 2882, 8281) は以下の面白い性質を持つ.
この集合は巡回的である. 最後の数も含めて, 各数の後半2桁は次の数の前半2桁と一致する
それぞれ多角数である: 三角数 (P3,127=8128), 四角数 (P4,91=8281), 五角数 (P5,44=2882) がそれぞれ別の数字で集合に含まれている
4桁の数の組で上の2つの性質をもつはこの組だけである.
同じように, 6つの4桁の数からなる順番付きの集合で,
集合は巡回的である
三角数, 四角数, 五角数, 六角数, 七角数, 八角数が全て表れる 唯一の集合を求め, その和を求めよ.

最初に1000～9999の間の数が何角数であるかをメモ化します。

後は範囲が狭いのでスタートを決めて条件を満たす数を再帰で全探索するだけです。
このときｎ角数∧m角数であるような数に対処するために探索を分岐するだけです。

#include<stdio.h>
int memo[10000]={0};
int ans[6];
void saiki(int num,int perm,int deep,int ss){
if(deep==6){
	int sum=0;
	if(num==ss&&perm==63){
		for(int i=0;i<6;i++){
			printf("%d ",ans[i]);
			sum+=ans[i];
		}
		printf(" %d\n",sum);
	}
}else{
	int next;
	for(int i=0;i<100;i++){
		next=num+i;
		int p=memo[next];
		for(int k=1;k<=32;k*=2){
			if(((p&k)!=0)&&((perm&k)==0)){
				ans[deep]=next;
				saiki(i*100,perm|k,deep+1,ss);
			}
		}
	}
}
}
int up=10000;
int main(){
int m;
for(int n=1;n<=up;n++){
	m=(n*(n+1))/2;
	if(m<up&&m>999)memo[m]|=1;
	m=n*n;
	if(m<up&&m>999)memo[m]|=2;
	m=(n*(3*n-1))/2;
	if(m<up&&m>999)memo[m]|=4;
	m=n*(2*n-1);
	if(m<up&&m>999)memo[m]|=8;
	m=(n*(5*n-3))/2;
	if(m<up&&m>999)memo[m]|=16;
	m=(n*(3*n-2));
	if(m<up&&m>999)memo[m]|=32;
}
for(int i=10;i<100;i++){
	saiki(i*100,0,0,i*100);
}
}

問い67

http://projecteuler.net/problem=67
三角形に並んだ数字を上から下へ向かいながら途中の経路の計が最高になるルートの合計値を見つけよという問題。
問い18のコードのサイズを少し変更するだけで作成可能。

#include<stdio.h>
#include<algorithm>
#include<string.h>
int main(){
int memo[2][101],a,now,next;
sizeof(memo,0,sizeof(memo));
scanf("%d",&memo[0][0]);
for(int i=1;i<100;i++){
	now =(i+1)%2;
	next=i%2;
	for(int j=0;j<=i;j++){
		scanf("%d",&a);
		if(j==i){
			memo[next][j]=memo[now][j-1]+a;
		}else if(j>0&&j<i){
			memo[next][j]=std::max(memo[now][j-1],memo[now][j])+a;
		}else{
			memo[next][j]=memo[now][j]+a;
		}
	}
}
int ans=0;
for(int i=0;i<100;i++)ans=std::max(ans,memo[next][i]);
printf("%d\n",ans);
}

69

5桁の数 16807 = 7^5は自然数を5乗した数である. 同様に9桁の数 134217728 = 8^9も自然数を9乗した数である.
自然数をn乗して得られるn桁の正整数は何個あるか?
対数を使って式変形すれば簡単に解ける

#include<stdio.h>
#include<math>
int main(){
int ans=1;//1を最初に足す
for(int i=2;i<10;i++){
	//10以上は桁数の増加より数字の増加が早いので無視
	double d=log(i)/log(10);
	printf("%lf\n",1/(1-d));
	ans+=(int)(1/(1-d));
}
printf("%d\n",ans);
}