数学の力

京大生が数学の定理・公式の証明や入試問題の解説をするブログ.

プロジェクトオイラー 76. 〜Counting Summations〜

No.76 Counting Summations

問題.

5は正整数の和として:\begin{align*}
&4+1\\
&3+2\\
&3+1+1\\
&2+2+1\\
&2+1+1+1\\
&1+1+1+1+1
\end{align*}の6通りに書ける.では,100は正整数の和として何通りに書けるか.


考え方とプログラム例.(c++)

動的計画法です.先に問題77. の記事を書きましたが,考え方はほとんど同じです.

整数 n k以下の正整数の和として表す方法の個数を f(n, k)通りとすると,以下の漸化式が成り立つ:

 \begin{align*}
 f(n, k) &=\begin{cases}
  1,&k=1,\\
  f(n, k-1),&k>n,\\
  f(n, k-1) + g(n-k, k),&k\leq n.
 \end{cases}
\end{align*}

 k\leq nの場合について,整数 kを使わない場合が f(n, k-1)通り,整数 kを使う場合が f(n-k, k)通りです.

以下がプログラム例です.メモ化再帰?を使ってみました.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

vector<vector<int>> F(101, vector<int>(100, 0));

ll f(int n, int k){
	ll ret = 0;
	if(F[n][k] > 0)
		return F[n][k];
	if(n - k >= 0)
		ret += f(n-k, k);
	ret += f(n, k-1);
	F[n][k] = ret;
	return ret;
}

int main(){
	for(int n = 0; n <= 100; n++)	F[n][1] = 1;
	cout << f(100, 99) << endl;
	return 0;
}

プロジェクトオイラー77. ~ Prime Summations ~

No.77 Prime Summations

問題.

10は素数の和として:\begin{align*}
&7+3\\
&5+5\\
&5+3+2\\
&3+3+2+2\\
&2+2+2+2+2
\end{align*}の5通りに書ける.では,素数の和として5000通り以上の方法で書くことのできる最小の数は何か.


考え方とプログラム例.(c++)

答えはあまり大きな数にはならないと予想されるので,考える範囲の上限を仮に N=1000としておきます.

 N以下の素数を計算しておく必要がありますが,これはエラトステネスの篩を用いれば計算できるので, i番目の素数 p_iとしておきます.

( p_1=2, p_2=3, p_3=5, p_4=7, ...)

整数 n p_k以上の素数の和として表す方法の個数を g(n, k)通りとすると,以下の漸化式が成り立つ:

\begin{align*}
g(n, k) &=\begin{cases}
1,& n=0,\\
0,&p_k>n\geq1,\\
g(n, k+1) + g(n-p_k, k),&p_k\leq n.
\end{cases}
\end{align*}

 p_k\leq nの場合について,素数 p_kを使わない場合が g(n, k+1)通り,素数 p_kを使う場合が g(n-p_k, k)通りです.

以下がプログラム例です.上の漸化式はkの値が大きい順に計算しないといけないので,ここでは関数の再帰を用いて実装しています.

#include<bits/stdc++.h>
using namespace std;

int g(int n, int k, vector<int>& primes){
	if(n == 0)
		return 1;
	if(primes[k] > n)
		return 0;
	else
		return (g(n, k+1, primes) + g(n-primes[k], k, primes));
}

int main(){
	int N = 1000; //考える最大値(仮)
	vector<int> num(N+1, 0);
	vector<int> primes; //N以下の素数列挙
	for(int i = 2; i <= N; i++){
		if(num[i] == 0){
			primes.push_back(i);
			if(i > sqrt(N))
				continue;
			for(int n = 2 * i; n <= N; n += i)
				num[n] = 1;
		}
	}

	for(int n = 1; n <= N; n++){
		int cnt = g(n, 0, primes);
		if(cnt >= 5000){
			cout << n << ", " << cnt << "通り" << endl;
			break;
		}
	}
	return 0;
}