「プロジェクトオイラー問い1~10」の編集履歴(バックアップ)一覧はこちら

プロジェクトオイラー問い1~10」(2012/12/12 (水) 22:57:21) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

*問い1 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%201 1000未満で3の倍数又は5の倍数となる自然数の和を求める問題。 プログラムを書くまでもなく数式で一発です。 #include<stdio.h> int main(){ printf("%d",333*167*3+199*100*5-33*67*15); } *問い2 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%202 フィボナッチ数列のうち400万以下の偶数となる項の和を求める問題。 解法 フィボナッチ数列は最初奇数、奇数で始まり 奇数+奇数=偶数 奇数+偶数=奇数 偶数+奇数=奇数 奇数+奇数=偶数 で偶数が3つごとに現れます。 そしてn=3k番目のフィボナッチ数列の項を求める関数をf(n)としたとき数式を展開することで f(n)=4*f(n-3)+f(n-6)が常に成り立ちつことが容易に判明します。 後はこれをそのままプログラムにするだけです。 もしかしたらもうひとつ深く考えて行列演算を使えば、ループを行うまでもなく一発で答えが出るかもしれません。 #include<stdio.h> int main(){ int ans=0,y=0,z=2,t; while(z<=400*10000){ t=z*4+y; y=z; z=t; ans+=y; } printf("%d",ans); } *問い3 3195 の素因数は 5, 7, 13, 29 である. 600851475143 の素因数のうち最大のものを求めよ. 解法 とりあえず試し割をしてみましたが数の特殊性に注目したもう少し賢い方法があるかもしれません。 #include<iostream> int main(){ __int64 num=600851475143L; for(__int64 i=2;i*i<=num;i+=(i&1)+1){ while(num%i==0){ std::cout<<i<<" "; num/=i; } } if(num!=1)std::cout<<num; } *問い4 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%204 左右どちらから読んでも同じ値になる数を回文数という. 2桁の数の積で表される回文数のうち, 最大のものは 9009 = 91 × 99 である. では, 3桁の数の積で表される回文数のうち最大のものを求めよ. 力づくの方法以外をコードをに組み込むとコードが長くなるのでとりやめました。 もし7桁の数同士の掛け算とかとなると難しい。 #include<stdio.h> #include<stdlib.h> #include<string.h> bool isOK(char* str){ int len=strlen(str); for(int i=0;i<len/2;i++){ if(str[i]!=str[len-i-1])return false; } return true; } int main(){ char str[7]; int ans=0; for(int i=100;i<1000;i++){ for(int j=100;j<1000;j++){ int m=i*j; sprintf(str,"%d",m); if(isOK(str)&&ans<m)ans=m; } } printf("%d",ans); } *問い5 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%205 素因数分解の一意性を使って解きます。 1~20まで自然数全ての数で割れる最小の自然数mを求めよ。 割る数をnとした時nの素因数をmが含んでいないといけないということを利用して解きます。 この方法なら、100までで割れるとかになっても答えを素因数の積で表示できます。 javaのコンテナほど便利でありませんがc++のコンテナの便利さを知るとコンテナから離れらないですね。 他の回答者のコードを見ていたら皆LCMで解いてた、確かにこの問題ならそちらの方がコードが短くなる。 言語にLCMが定義されてたら1行で済む場合もあるな、、、 #include<stdio.h> #include<map> #include<math.h> #include<iostream> void calc(int n){ int num; std::map<int,int> anss; for(int i=2;i<=n;i++){ num=i; for(int j=2;j*j<=n;j++){ int count=0; while(num%j==0){ num/=j; count++; } if(count>0){ if(anss.find(j)==anss.end()||anss[j]<count)anss[j]=count; } } if(num!=1){ if(anss.find(num)==anss.end()||anss[num]<1)anss[num]=1; } } int ans=1; for(std::map<int,int>::iterator it=anss.begin();it!=anss.end();it++){ std::cout<<(*it).first<<" "<<(*it).second<<"\n"; ans*=pow((*it).first,(*it).second); } std::cout<<ans; } int main(){ calc(20); } *問い6 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%206 最初の10個の自然数について, その二乗の和は, 12 + 22 + ... + 102 = 385 最初の10個の自然数について, その和の二乗は, (1 + 2 + ... + 10)2 = 3025 これらの数の差は 3025 - 385 = 2640 となる. 同様にして, 最初の100個の自然数について二乗の和と和の二乗の差を求めよ. 解法 プログラムを書くまでもなく数式で一発です。 #include<stdio.h> #include<math.h> int calc(int n){ return (3*pow(n,4)+2*pow(n,3)-3*pow(n,2)-2*n)/12; } int main(){ printf("%d",calc(100)); } *問い7 素数を小さい方から6つ並べると 2, 3, 5, 7, 11, 13 であり, 6番目の素数は 13 である. 10 001 番目の素数を求めよ. 解法 素数が絡むと問題の難易度が低く設定されやすくなるように思えます。 素数の判定や素数にかかわる性質は複雑で高度なために一般の参加者が知らない性質が増えます。 そのため専門知識がなくても解けるよう試し割程度で片がつく問題が出題されやすくなります。 高度な専門知識がなくても柔軟な発想力で参加できる、これが競技プログラムの良さだと思います。 #include<stdio.h> #include<math.h> bool isPrime(int n){ for(int i=2;i*i<=n;i+=(i&1)+1){ if(n%i==0)return false; } return true; } int main(){ int count=1,ans=3; while(1){ if(isPrime(ans)==true)count++; if(count>=10001)break; ans+=2; } printf("%d",ans); } *問い8 1000桁の数字から5つの連続する数字を取り出して その積を計算する. そのような積の中で最大のものの値はいくらか. 解法 尺取り虫法で高速化する方法も考えてみましたが5文字程度では大差がつかないのでやめました。 #include<stdio.h> int main(){ char text[1002]="7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"; int ans=0; for(int i=0;i<1000;i++)text[i]-='0'; for(int i=0;i<996;i++){ int k=text[i]*text[i+1]*text[i+2]*text[i+3]*text[i+4]; if(ans<k)ans=k; } printf("%d",ans); } *問い9 ピタゴラスの三つ組(ピタゴラスの定理を満たす自然数)とは a < b < c で以下の式を満たす数の組である. a2 + b2 = c2 例えば, 3^2 + 4^2 = 9 + 16 = 25 = 5^2 である. a + b + c = 1000 となるピタゴラスの三つ組が一つだけ存在する. これらの積 abc を計算しなさい. 解法 原始ピタゴラス数の公式からかなり絞り込めます。 #include<stdio.h> int main(){ for(int m=2;m*(m+1)<=500;m++){ for(int n=1;m*(m+n)<=500&&n<m;n++){ int k=m*(m+n); if(500%k==0){ int t=500/k; printf("ans=%d %d %d ans=%d",t*(m*m-n*n),t*2*m*n,t*(m*m+n*n),t*t*t*(m*m-n*n)*(2*m*n)*(m*m+n*n)); } } } }
*問い1 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%201 1000未満で3の倍数又は5の倍数となる自然数の和を求める問題。 プログラムを書くまでもなく数式で一発です。 #include<stdio.h> int main(){ printf("%d",333*167*3+199*100*5-33*67*15); } *問い2 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%202 フィボナッチ数列のうち400万以下の偶数となる項の和を求める問題。 解法 フィボナッチ数列は最初奇数、奇数で始まり 奇数+奇数=偶数 奇数+偶数=奇数 偶数+奇数=奇数 奇数+奇数=偶数 で偶数が3つごとに現れます。 そしてn=3k番目のフィボナッチ数列の項を求める関数をf(n)としたとき数式を展開することで f(n)=4*f(n-3)+f(n-6)が常に成り立ちつことが容易に判明します。 後はこれをそのままプログラムにするだけです。 もしかしたらもうひとつ深く考えて行列演算を使えば、ループを行うまでもなく一発で答えが出るかもしれません。 #include<stdio.h> int main(){ int ans=0,y=0,z=2,t; while(z<=400*10000){ t=z*4+y; y=z; z=t; ans+=y; } printf("%d",ans); } *問い3 3195 の素因数は 5, 7, 13, 29 である. 600851475143 の素因数のうち最大のものを求めよ. 解法 とりあえず試し割をしてみましたが数の特殊性に注目したもう少し賢い方法があるかもしれません。 #include<iostream> int main(){ __int64 num=600851475143L; for(__int64 i=2;i*i<=num;i+=(i&1)+1){ while(num%i==0){ std::cout<<i<<" "; num/=i; } } if(num!=1)std::cout<<num; } *問い4 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%204 左右どちらから読んでも同じ値になる数を回文数という. 2桁の数の積で表される回文数のうち, 最大のものは 9009 = 91 × 99 である. では, 3桁の数の積で表される回文数のうち最大のものを求めよ. 力づくの方法以外をコードをに組み込むとコードが長くなるのでとりやめました。 もし7桁の数同士の掛け算とかとなると難しい。 #include<stdio.h> #include<stdlib.h> #include<string.h> bool isOK(char* str){ int len=strlen(str); for(int i=0;i<len/2;i++){ if(str[i]!=str[len-i-1])return false; } return true; } int main(){ char str[7]; int ans=0; for(int i=100;i<1000;i++){ for(int j=100;j<1000;j++){ int m=i*j; sprintf(str,"%d",m); if(isOK(str)&&ans<m)ans=m; } } printf("%d",ans); } *問い5 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%205 素因数分解の一意性を使って解きます。 1~20まで自然数全ての数で割れる最小の自然数mを求めよ。 割る数をnとした時nの素因数をmが含んでいないといけないということを利用して解きます。 この方法なら、100までで割れるとかになっても答えを素因数の積で表示できます。 javaのコンテナほど便利でありませんがc++のコンテナの便利さを知るとコンテナから離れらないですね。 他の回答者のコードを見ていたら皆LCMで解いてた、確かにこの問題ならそちらの方がコードが短くなる。 言語にLCMが定義されてたら1行で済む場合もあるな、、、 #include<stdio.h> #include<map> #include<math.h> #include<iostream> void calc(int n){ int num; std::map<int,int> anss; for(int i=2;i<=n;i++){ num=i; for(int j=2;j*j<=n;j++){ int count=0; while(num%j==0){ num/=j; count++; } if(count>0){ if(anss.find(j)==anss.end()||anss[j]<count)anss[j]=count; } } if(num!=1){ if(anss.find(num)==anss.end()||anss[num]<1)anss[num]=1; } } int ans=1; for(std::map<int,int>::iterator it=anss.begin();it!=anss.end();it++){ std::cout<<(*it).first<<" "<<(*it).second<<"\n"; ans*=pow((*it).first,(*it).second); } std::cout<<ans; } int main(){ calc(20); } *問い6 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%206 最初の10個の自然数について, その二乗の和は, 12 + 22 + ... + 102 = 385 最初の10個の自然数について, その和の二乗は, (1 + 2 + ... + 10)2 = 3025 これらの数の差は 3025 - 385 = 2640 となる. 同様にして, 最初の100個の自然数について二乗の和と和の二乗の差を求めよ. 解法 プログラムを書くまでもなく数式で一発です。 #include<stdio.h> #include<math.h> int calc(int n){ return (3*pow(n,4)+2*pow(n,3)-3*pow(n,2)-2*n)/12; } int main(){ printf("%d",calc(100)); } *問い7 素数を小さい方から6つ並べると 2, 3, 5, 7, 11, 13 であり, 6番目の素数は 13 である. 10 001 番目の素数を求めよ. 解法 素数が絡むと問題の難易度が低く設定されやすくなるように思えます。 素数の判定や素数にかかわる性質は複雑で高度なために一般の参加者が知らない性質が増えます。 そのため専門知識がなくても解けるよう試し割程度で片がつく問題が出題されやすくなります。 高度な専門知識がなくても柔軟な発想力で参加できる、これが競技プログラムの良さだと思います。 #include<stdio.h> #include<math.h> bool isPrime(int n){ for(int i=2;i*i<=n;i+=(i&1)+1){ if(n%i==0)return false; } return true; } int main(){ int count=1,ans=3; while(1){ if(isPrime(ans)==true)count++; if(count>=10001)break; ans+=2; } printf("%d",ans); } *問い8 1000桁の数字から5つの連続する数字を取り出して その積を計算する. そのような積の中で最大のものの値はいくらか. 解法 尺取り虫法で高速化する方法も考えてみましたが5文字程度では大差がつかないのでやめました。 #include<stdio.h> int main(){ char text[1002]="7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"; int ans=0; for(int i=0;i<1000;i++)text[i]-='0'; for(int i=0;i<996;i++){ int k=text[i]*text[i+1]*text[i+2]*text[i+3]*text[i+4]; if(ans<k)ans=k; } printf("%d",ans); } *問い9 ピタゴラスの三つ組(ピタゴラスの定理を満たす自然数)とは a < b < c で以下の式を満たす数の組である. a2 + b2 = c2 例えば, 3^2 + 4^2 = 9 + 16 = 25 = 5^2 である. a + b + c = 1000 となるピタゴラスの三つ組が一つだけ存在する. これらの積 abc を計算しなさい. 解法 原始ピタゴラス数の公式からかなり絞り込めます。 #include<stdio.h> int main(){ for(int m=2;m*(m+1)<=500;m++){ for(int n=1;m*(m+n)<=500&&n<m;n++){ int k=m*(m+n); if(500%k==0){ int t=500/k; printf("ans=%d %d %d ans=%d",t*(m*m-n*n),t*2*m*n,t*(m*m+n*n),t*t*t*(m*m-n*n)*(2*m*n)*(m*m+n*n)); } } } } *問い10 200万以下の素数の和を求めよ。 解法 素数かどうか試し割で調べて足しこむだけです。 #include<stdio.h> #include<iostream> bool isPrime(int n){ for(int i=2;i*i<=n;i+=(i&1)+1){ if(n%i==0)return false; } return true; } int main(){ __int64 ans=2; for(int i=3;i<=200*10000;i+=2)if(isPrime(i))ans+=i; std::cout<<ans; }

表示オプション

横に並べて表示:
変化行の前後のみ表示: