※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

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

プロジェクトオイラー問い51~60 - (2012/12/21 (金) 17:30:42) の1つ前との変更点

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

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

 *問い53
 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2053
 パスカルの三角形を101段目まで書いたとき、100万を超える項は何個あるかという問題です。
 
 解法
 パスカルの三角形を計算して100万以上になったらその影響下にある項は全て100万で統一して計算するのが一番シンプルですが、それもいいのですが無意味に計算量を抑えて遊んでみました。
 一段ずつ上からパスカルの三角形に基づき計算します。
 左端から計算して100万を超えたらそこより右は計算しないでその段の残りの項の数からその段の100万を超えた項の数を求め次の段へ計算をすすめます。
 この手法なら問題が100000段とかになっても計算量がそんなに増えない程度しか利点がありません。
-1段目0C0から計算が始まるので100だと101段目まで計算する点に注意するくらいです。
+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);
  }