*問い53 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2053 パスカルの三角形を101段目まで書いたとき、100万を超える項は何個あるかという問題です。 解法 パスカルの三角形を計算して100万以上になったらその影響下にある項は全て100万で統一して計算するのが一番シンプルですが、それもいいのですが無意味に計算量を抑えて遊んでみました。 一段ずつ上からパスカルの三角形に基づき計算します。 左端から計算して100万を超えたらそこより右は計算しないでその段の残りの項の数からその段の100万を超えた項の数を求め次の段へ計算をすすめます。 この手法なら問題が100000段とかになっても計算量がそんなに増えない程度しか利点がありません。 1段目0C0から計算が始まるので100Crだと101段目まで計算する点に注意するくらいです。 #include<stdio.h> #include<string.h> #include<time.h> int main(){ double start=clock(); int memo[102]={0,1,0},ans=0; for(int n=1;n<=101;n++){ int next[102]={0}; int r; for(r=1;r<=n;r++){ next[r]=memo[r-1]+memo[r]; if(next[r]>=1000*1000)break; } if(r<n){ if(n%2==0){ ans+=(n/2-r+1)*2; }else{ ans+=(n+1)/2==r?1:1+((n+1)/2-r)*2; } } memcpy(memo,next,sizeof(next)); } printf("ans=%d time=%lf",ans,clock()-start); }