「プロジェクトオイラー問い71～80」の編集履歴（バックアップ）一覧に戻る
*問い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);
}
*問い74
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2074
145は各桁の階乗の和が145と自分自身に一致することで有名である.
1! + 4! + 5! = 1 + 24 + 120 = 145
169の性質はあまり知られていない. これは169に戻る数の中で最長の列を成す. このように他の数を経て自分自身に戻るループは3つしか存在しない.
169 → 363601 → 1454 → 169
871 → 45361 → 871
872 → 45362 → 872
どのような数からスタートしてもループに入ることが示せる.
例を見てみよう.
69 → 363600 → 1454 → 169 → 363601 (→ 1454)
78 → 45360 → 871 → 45361 (→ 871)
540 → 145 (→ 145)
69から始めた場合, 列は5つの循環しない項を持つ. また100万未満の数から始めた場合最長の循環しない項は60個であることが知られている.
100万未満の数から開始する列の中で, 60個の循環しない項を持つものはいくつあるか?
解法
次の数字を生成して数字列を生成しますが、数字を点とみ次の数字を線で結んで最初にグラフを生成してグラフを探索してみました。
メモリを贅沢に使いましたが、何も考えずに計算しながら探索したほうが少しくらい遅くてもメモリを節約できるので賢い気がします。
#include<stdio.h>
const int up=2540160;
int G[up+1]={0};
int facts[]={1,1,2,6,24,120,720,5040,40320,362880};
int calc(int n){
int re=0;
while(n!=0){
re+=facts[n%10];
n/=10;
}
return re;
}
int saiki(int deep,int num){
if(deep==60){
return num;
}
if(G[num]==0)return 0;
int t=G[num];
G[num]=0;
int re=saiki(deep+1,t);
G[num]=t;
return re;
}
int main(){
for(int i=1;i<up;i++){
G[i]=calc(i);
}
int ans=0;
for(int i=1;i<1000*1000;i++){
int re=saiki(0,i);
if(re!=0){
ans++;
}
}
printf("%d",ans);
}
*問い75
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2075
周長が整数Ｌ＜150万の棒を折り曲げて各辺が整数長さとなる直角三角形を作るとき、一通りの折り曲げかたしかできないＬはいくつあるか？
解法
原始ピタゴラス数の公式で一瞬で答えが出ますがメモリをたくさん使ってます。
答えは妙に霧のいい数字なのでもしかしたら簡単な数式があるのかもしれません。
#include<stdio.h>
const int up=150*10000;
int memo[up];
int gcd ( int a, int b ){
int c;
while ( a != 0 ) {
c = a; a = b%a; b = c;
}
return b;
}
int main(){
for(int m=2;(m*m+1*1)+(2*m*1)+(m*m-1*1)<up;m++){
for(int n=1;n<m;n++){
if(gcd(n,m)!=1||(m-n)%2==0)continue;
int L=(m*m+n*n)+(2*m*n)+(m*m-n*n);
int add=L;
while(L<up){
memo[L]++;
L+=add;
}
}
}
int ans=0;
for(int i=1;i<up;i++){
ans+=(memo[i]==1);
}
printf("%d",ans);
}
*問い76
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2076
100を２つ以上の自然数の和として表す時表し方は何通りになるか？
解法
動的計画法で一発です。
#include<stdio.h>
int main(){
int memo[101]={0};
memo[0]=1;
for(int i=1;i<100;i++){
for(int j=0;j<=100-i;j++){
memo[j+i]+=memo[j];
}
}
printf("%d",memo[100]);
}
*問い77
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2077
10は素数の和として5通りに表すことができる:
7 + 3
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2
素数の和としての表し方が5000通り以上になる最初の数を求めよ.
解法
考え方は問い76と同じで素数になっただけです。
理想をいえば、答えが見つかるまで勝手に探索する範囲の値が増加するのがいいのですが、手抜きで解きました。
素数の上限を少しずつ増加して答えが出てくるかヒュースティリックに探索しました。
#include<stdio.h>
#include<vector>
#include<algorithm>
const int up=100;
std::vector<int> sosuu;
bool so[up+1];
__int64 memo[up+1]={0};
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();
memo[0]=1;
int ans=up+1;
for(int i=0;i<sosuu.size();i++){
int p=sosuu[i];
for(int j=0;j<=up-p;j++){
memo[j+p]+=memo[j];
if(memo[j+p]>=5000){
if(ans>j+p)ans=j+p;
memo[j+p]=5000;
}
}
}
printf("%d",ans);
}
*問い78
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2078
n 枚のコインを異なった方法で山に分ける場合の数を p(n) と表わす. 例えば, 5枚のコインを山に分ける異なったやり方は７通りなので p(5)=7 となる.
p(n) が100万で割り切れる場合に最小となる n を求めよ.
解法
分割数の公式を使います。
桁あふれが起きるので100万で割ったあまりを使って計算するくらいです。
#include<stdio.h>
#include<vector>
#include<iostream>
int main(){
std::vector<__int64> memo;
memo.push_back(1);
memo.push_back(1);
memo.push_back(2);
__int64 num;
__int64 mod=1000*1000;
while(1){
int p=memo.size();
num=0;
int b=1;
while(1){
int d=(b*(3*b-1))/2;
if(p-d<0)break;
num=(num+memo[p-d])%mod;
d=(-b*(3*-b-1))/2;
if(p-d<0)break;
num=(num+memo[p-d])%mod;
b++;
d=(b*(3*b-1))/2;
if(p-d<0)break;
num=(num-memo[p-d])%mod;
d=(-b*(3*-b-1))/2;
if(p-d<0)break;
num=(num-memo[p-d])%mod;
b++;
}
if(num==0)break;
memo.push_back(num);
}
std::cout<<memo.size();
}
*問い79
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2079
オンラインバンクで通常使われるsecurity methodは, パスコードからランダムに選んだ3文字をユーザーに要求するものである.
たとえば, パスコードが531278のとき, 2番目, 3番目, 5番目の文字を要求されるかもしれない. このとき, 期待される答えは: 317 である.
テキストファイルkeylog.txtには, ログインに成功した50回の試行が記録されている.
3つの文字が常に順番通りに要求されるとするとき, ファイルを分析して, 可能なパスコードのなかでもっとも短いものを見つけよ.
*解法
この問題は解く人の性格が出そうな問題です。
私の場合賢い方法を思いつかなかったので、８文字程度だろうと決め打ちして単純に全探索してみました。
駄目な場合桁数を増やす予定でしたが８桁でいけました。
人によって解法が全く違うようです。
#include<stdio.h>
int ans[8]={0};
char data[50][4];
void saiki(int);
void saiki2(int p,int deep1,int deep){
if(deep1==3){
saiki(deep+1);
}else{
int num=data[deep][deep1];
for(int i=p;i<8;i++){
if(ans[i]==10){
ans[i]=num;
saiki2(i+1,deep1+1,deep);
ans[i]=10;
}else if(ans[i]==num){
saiki2(i+1,deep1+1,deep);
}
}
}
}
void saiki(int deep){
if(deep==50){
for(int i=0;i<8;i++)printf("%d",ans[i]);
printf("\n");
}else{
saiki2(0,0,deep);
}
}
int main(){
for(int i=0;i<8;i++)ans[i]=10;
for(int i=0;i<50;i++){
scanf("%s",data[i]);
for(int j=0;j<3;j++)data[i][j]-='0';
}
saiki(0);
}
