*問い11 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2011 与えられた20*20の数字表の中から連続する４つの数字を縦横斜めで掛けた時、４つの数字の最大値を見つける問題。 解法 与えられた数字表に０以下の数がないこと、それと縦横斜めの計算をマトリックス化して少しコードを短くしてみました。 もし数字表が数万*数万以上になるとオンメモリにするわけにもいきません。 この場合きちんと処理できるようハードディスクからデータを取り出す関数が必要になります。 #include<stdio.h> int map[20][20]; int toRe(int y,int x){ if(y<0||y>19||x<0||x>19)return 0; return map[y][x]; } int main(){ int ans=0,t; int dxs[4]={-1,-1,0,1},dys[4]={0,-1,-1,-1}; for(int y=0;y<20;y++){ for(int x=0;x<20;x++){ scanf("%d",&map[y][x]); for(int k=0;k<4;k++){ t=toRe(y,x)*toRe(y+dys[k],x+dxs[k])*toRe(y+2*dys[k],x+2*dxs[k])*toRe(y+3*dys[k],x+3*dxs[k]); if(t>ans)ans=t; } } } printf("%d\n",ans); } *問い12 三角数の約数の個数が５００個以上になる最小の数を求めよという問題。 解法 答えはm=(n*(n+1))/2の約数の個数となります。 nとｎ+1は互いに素なので約数の個数を求める関数をf(m)とするとf(m)=f(n/2)f(n+1)かf(m)=f((n+1)/2)f(n)となります。 簡単ですね。 #include<stdio.h> int calc(int n){ int ans=1; int num=n%2==0?n/2:n; for(int i=2;i*i<=num;i+=(i&1)+1){ int count=0; while(num%i==0){ num/=i; count++; } ans*=(count+1); } if(num!=1)ans*=2; num=(n+1)%2==0?(n+1)/2:n+1; for(int i=2;i*i<=num;i+=(i&1)+1){ int count=0; while(num%i==0){ num/=i; count++; } ans*=(count+1); } if(num!=1)ans*=2; return ans; } int main(){ int n; for(n=1;calc(n)<500;n++); printf("%d",(n*(n+1))/2); } *問い13 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2013 ５０桁の数字１００個が与えられるのでこれの和を求め上位１０ケタを答えよ。 言語によっては多倍張整数ライブラリか自前の実装が必要ですがLisp系統の言語なら+演算子一つで片が付きます。 計算で出てきた数字の上位１０ケタをコピーすれば答えが出ます。 (+ 37107287533902102798797998220837590246510135740250 ,,,データなので省略。 53503534226472524250874054075591789781264330331690) *問い14 正の整数に以下の式で繰り返し生成する数列を定義する. n → n/2 (n が偶数) n → 3n + 1 (n が奇数) 13からはじめるとこの数列は以下のようになる. 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 13から1まで10個の項になる. この数列はどのような数字からはじめても最終的には 1 になると考えられているが, まだそのことは証明されていない(コラッツ問題) さて, 100万未満の数字の中でどの数字からはじめれば最長の数列を生成するか. 注意: 数列の途中で100万以上になってもよい 解法 メモ化で少しだけ速度を出しつつ地道に計算してみました。 コラッツ問題は再帰を使えばメモ化がスムーズに働き計算量は落ちますが、再帰関数を呼び出すコストが上がりますしスタックオーバーフローの可能性も出てきます。 その辺を取って地道な関数で解いてみました。 #include<stdio.h> #include<iostream> const int up=1000*1000; int memo[up+1]={0,1,0}; int main(){ __int64 num; int count,ansLen=0,ansNum; for(int i=2;i<up;i++){ num=i; count=0; while(num>=i){ num=num%2==0?num/2:num*3+1; count++; } memo[i]=count+memo[(int)num]; if(memo[i]>ansLen){ ansLen=memo[i]; ansNum=i; } } std::cout<<ansNum<<" "<<ansLen; } *問い15 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2015 2×2 のマス目の左上からスタートした場合, 引き返しなしで右下にいくルートは 6 つある. では, 20×20 のマス目ではいくつのルートがあるか. *解法 答えは40C20なので電卓でちょちょいでもいいのですがそれでは楽しくありません。 メモ化計算も悪くないのですが、コードで遊ぼうと思ってコンバインで実装してみました。 #include<stdio.h> #include<iostream> #include<map> #include<math.h> std::map<int,int> calc(int down,int up){ std::map<int,int> re; for(int i=down;i<=up;i++){ int num=i; for(int j=2;j<=num;j++){ int count=0; while(num%j==0){ num/=j; count++; } if(count>0){ if(re.find(j)==re.end())re[j]=0; re[j]+=count; } } } return re; } __int64 combin(int n,int r){ std::map<int,int> m1,m2; std::map<int,int>::iterator it; m1=calc(n-r+1,n); m2=calc(1,r); int u,k; __int64 ans=1; for(it=m1.begin();it!=m1.end();it++){ u=(*it).first; k=(*it).second; if(m2.find(u)!=m2.end())k-=m2[u]; if(k>0)ans*=pow(u,k); } return ans; } int main(){ std::cout<<combin(40,20); } *問い17 2＾1000の各桁の和がいくつになるか答えよ。 解法 C++でもいいのですが処理が面倒です。 簡単に処理できるlispで実装してみました。 ２＾１０００を求めてこれを文字列に変換。 ループで一文字ずつ足しこみました。 Lispは苦手。 (let ((str (format nil "~A" (expt 2 1000))) (ans 0)) (dotimes (i (length str) ans) (setq ans (+ ans (- (char-code (char str i)) 48)))))
