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

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

オイラープロジェクト61~70 - (2012/09/10 (月) 03:45:22) の編集履歴(バックアップ)


問い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の間の数が何角数であるかをメモ化します。


後は範囲が狭いのでスタートを決めて条件を満たす数を再帰で全探索するだけです。
このときn角数∧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);
}
}


問い65

http://projecteuler.net/problem=65
eについての連分数である近似分数の100項目の分子の桁の合計を求めよ。

定義通りlispで実装します。

(defun t(n)
 (if (= (mod (- n 1)  3) 0)
     (+ (* 2 (/ (- n 1) 3)) 2)
   1))
(defun calc (deep n)
 (if (= (+ 2 deep) n)
     (/ 1 (t deep))
   (/ 1 (+ (t deep) (calc (+ deep 1) n)))))
calc
(defun wa (n sum)
 (if (= n 0)
     sum
   (wa (floor (/ n 10)) (+ sum (mod n 10)))))
wa
(wa (numerator (+ 2 (calc 0 100))) 0)


問い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

オイラーのトーティエント関数、φ(n)[時々ファイ関数とも呼ばれる]は、nと互いに素なn未満の数の数を定める。たとえば、1、2、4、5、7、そして8はみな9未満で9と互いに素であり、φ(9)=6.

n 互いに素な数 φ(n) n/φ(n)
2 1 1 2
3 1,2 2 1.5
4 1,3 2 2
5 1,2,3,4 4 1.25
6 1,5 2 3
7 1,2,3,4,5,6 6 1.1666...
8 1,3,5,7 4 2
9 1,2,4,5,7,8 6 1.5
10 1,3,7,9 4 2.5
n ≤ 10ではn/φ(n)の最大値はn=6であることがわかる。

n ≤ 1,000,000で n/φ(n) が最大となる値を見つけよ。
ファイ関数の結果について2~100万までエラトステネスの篩と同じ要領で計算して記録します。
速度的に早いのかどうかはよくわかりませんがとりあえず試行錯誤の末にたどり着いた自作アルゴリズムによるコードです。
このへんは数論でも基礎的でしょうし車輪の再発明だと思いますが自分で考えつけたというのは嬉しい限りです。
分解を利用した正式なコードの方が多分早いでしょう。

まずコードはn+1の倍数はnの倍数全ての数を素でない数として含みます。
これを全てのnで計算します。
この時一度倍数で足したものは足さないようにcount[i]==0で条件をたしておきます。

後はnの倍数で重複して計算した分を引いていくだけです。


#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<vector>
const int up=1000000;
int data[up+1],count[up+1],dell[up+1];
void setData(){
int k,add;
memset(data,0,sizeof(data));
memset(count,0,sizeof(count));
memset(dell,0,sizeof(dell));
for(int i=2;i<=up;i++){
	//printf("\n%d ",i);
	if(count[i]==0){
		k=1;
		for(int p=i*2;p<=up;p+=i){
			data[p]+=k;
			//printf("(%d %d %d)",p,k,data[p]);
			k++;
			count[p]++;
			dell[p]++;
		}
	}
}
//for(int i=2;i<=up;i++){
	//printf("%d %d %d\n",i,i-data[i]-1,count[i]);
//}
for(int i=2;i<=up;i++){
	if(count[i]>1){
		k=count[i]-1;
		add=1;
	}else if(count[i]==0&&dell[i]!=0){
		k=-1;
		add=-1;
	}else{
		continue;
	}
	//printf("%d %d\n",i,k);
	for(int p=i*2;p<=up;p+=i){
		data[p]-=k;
		k+=add;
		count[p]-=add;
	}
}
//for(int i=2;i<=up;i++){
	//printf("%d %d %d\n",i,i-data[i]-1,count[i]);
//}
//printf("\n");
}
int main(){
setData();
double ans=0,t;
int ansN;
for(int i=2;i<=up;i++){
	if(i-1==data[i]){
		printf("out%d\n",i);
		continue;
	}
	//printf("%d %d\n",i,i-data[i]-1);
	t=((double)i)/(i-1-data[i]);
	//printf("%d %lf\n",i,t);
	if(t>ans){
		ans=t;
		ansN=i;
	}
	//if(i==1000||i==216||i==72)printf("%d %d\n",i,i-1-data[i]);
}
printf("%d %lf",ansN,ans);
}






解いた後で問題Noを書き間違えたために問題NO不明、、、

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);
}