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

プロジェクトオイラー問い71～80 - (2012/12/31 (月) 07:24:17) の編集履歴(バックアップ)

---

問い71

分母が１００万以下で１より小さい既約分数を小さい順に並べた時3/7の左にある分数の分子を答えよ。

解法
ファレイ数列で一発です。
ファレイ数列が何故既約な分数を生成するかは理屈より図解で勉強したほうが分かりやすいか。
あれ？ファレイ数列の概念を使えばファイ関数を導き出せる？

#include<stdio.h>

struct S{
	int n,m;
	S operator+(const S& s){
		S re;
		re.n=n+s.n;
		re.m=m+s.m;
		return re;
	}
};
int main(){
	S s1,s2,s3;
	s1.n=2;
	s1.m=5;
	s2.n=3;
	s2.m=7;
 	while(1){
 		s3=s1+s2;
 		if(s3.m>=1000*1000)break;
		s1=s3;
	}
	printf("%d",s1.n);
}

問い72

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2072

解法
ファイ関数という概念を知らない時に作った我流ファイテーブル生成コードでアセプト。
車輪の再発明だが自分で考えついたというのがうれしくてつい使ってしまった。
趣味のプログラムだから許されるのであって、プロのプログラマなら専門家や世間が検証済みのアルゴリズムを使う方が正しいよな。
例え天才であっても自前の怪しいコードより世間が検証済みのコードを使うべきと言われるかもしれない。
ましてや凡人の私では世間に従うべきだよな。
まプログラムの仕事なんてものにつけることが出来たらの話か。

#include<stdio.h>
#include<iostream>
const int up=1000000;
int count[up+1]={0};
int dellCount[up+1]={0};
void print(){
	for(int i=1;i<=up;i++){
		printf("%d ",count[i]);
	}
	printf("\n");
} 

int main(){
	for(int i=2;i<=up/2;i++){
		if(dellCount[i]==0){
			//printf("%d a=",i);
			int dell=-1;
			for(int j=i*2;j<=up;j+=i){
				count[j]+=dell;
				dell--;
 				dellCount[j]++;
			}
		}else if(dellCount[i]>0){
			//printf("%d b=",i);
 			int add=dellCount[i]-1;
			int base=add;
			for(int j=i*2;j<=up;j+=i){
 				count[j]+=base;
				base+=add;
				dellCount[j]-=add;
			}
		}else{
			int add=-dellCount[i]+1;
			int base=add;
			for(int j=i*2;j<=up;j+=i){
				count[j]+=base;
				base+=add;
				dellCount[j]-=add;
			}
		}
		//print();
	}
 	__int64 ans=0;
	for(int i=1;i<=up;i++){
		ans+=i+count[i]-1;
	}
	std::cout<<ans;
}

問い73

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2073
nとdを正の整数として, 分数 n/d を考えよう. n<d かつ HCF(n,d)=1 のとき, 真既約分数と呼ぶ.
d ≤ 8 について既約分数を大きさ順に並べると, 以下を得る:
1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
1/3と1/2の間には3つの分数が存在することが分かる.
では, d ≤ 12,000 について真既約分数をソートした集合では, 1/3 と 1/2 の間に何個の分数があるか?

解法
ファレイ数列で1/2と1/3は隣り合っておりファレイ数列の生成ルールは木構造になっています。
再帰式と相性がいいのでそのままファレイ数列を素直に実装します。
今気付きましたがこの問題、分母だけが必要で分子は必要ありませんね。
ファレイ数列について勉強になりました。

#include<stdio.h>
int ans=0;
struct S{
	int n,m;
	S operator+(const S& s){
		S re;
		re.n=n+s.n;
		re.m=m+s.m;
		return re;
	}
};
void saiki(S s1,S s2,S s3){
	if(s2.m>12000)return;
	ans++;
	saiki(s1,s1+s2,s2);
	saiki(s2,s2+s3,s3);
}
int main(){
	S s1,s3;
	s1.n=s3.n=1;
	s1.m=2;
	s3.m=3;
	saiki(s1,s1+s3,s3);
	printf("%d",ans);
}