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

プロジェクトオイラー問い51～60 - (2012/12/21 (金) 17:30:08) のソース

*問い53
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2053
パスカルの三角形を101段目まで書いたとき、100万を超える項は何個あるかという問題です。

解法
パスカルの三角形を計算して１００万以上になったらその影響下にある項は全て１００万で統一して計算するのが一番シンプルですが、それもいいのですが無意味に計算量を抑えて遊んでみました。
一段ずつ上からパスカルの三角形に基づき計算します。
左端から計算して100万を超えたらそこより右は計算しないでその段の残りの項の数からその段の100万を超えた項の数を求め次の段へ計算をすすめます。
この手法なら問題が100000段とかになっても計算量がそんなに増えない程度しか利点がありません。
１段目0Ｃ0から計算が始まるので100だと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);
 }