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

プロジェクトオイラー問76 - (2014/03/02 (日) 09:30:57) の最新版との変更点

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

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

+http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2076
+*Problem 76 「和の数え上げ」 †
+5は数の和として6通りに書くことができる:
+
+4 + 1
+3 + 2
+3 + 1 + 1
+2 + 2 + 1
+2 + 1 + 1 + 1
+1 + 1 + 1 + 1 + 1
+
+2つ以上の正整数の和としての100の表し方は何通りか.
+
+
+
 解法
 足す数を辞書順で考える。
 例えば
 5=3+1+1だと3が一番大きな数で合計が5で左が3という情報以外組み合わせの計算にいらなくなる。
 9を作るとき5=3+1+1の左に4を足して9=4+3+1+1、すると合計が9で左が4という情報だけ残しておけばよいt。
 7=6+1の左に2を足して9を作ろうとしても辞書順は壊れる。
 これを考慮して動的計画法を立てると簡単に求まる。
 Wikiの分割数のほうが解き方としては本格的だが、実装はできても原理がよくわからないので掲載していない。
 
 
 
  #include<stdio.h>
  #include<string.h>
  
  int memo[101][101];
  
  int main(){
  	memset(memo,0,sizeof(memo));
   	for(int i=1;i<100;i++){
   		memo[i][i]=1;
  	}
  	for(int i=2;i<=100;i++){
  		for(int j=1;j<i;j++){
  			for(int k=1;k<=j;k++){
  				memo[i][j]+=memo[i-j][k];
  			}
   		}
 	}
   	int ans=0;
  	for(int i=1;i<=99;i++){
  		ans+=memo[100][i];
  	}
  	printf("%d\n",ans);
  }