プロジェクトオイラー 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は正整数の和として何通りに書けるか.
&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. の記事を書きましたが,考え方はほとんど同じです.
整数を以下の正整数の和として表す方法の個数を通りとすると,以下の漸化式が成り立つ:
の場合について,整数を使わない場合が通り,整数を使う場合が通りです.
以下がプログラム例です.メモ化再帰?を使ってみました.
#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通り以上の方法で書くことのできる最小の数は何か.
&7+3\\
&5+5\\
&5+3+2\\
&3+3+2+2\\
&2+2+2+2+2
\end{align*}の5通りに書ける.では,素数の和として5000通り以上の方法で書くことのできる最小の数は何か.
考え方とプログラム例.(c++)
答えはあまり大きな数にはならないと予想されるので,考える範囲の上限を仮にとしておきます.以下の素数を計算しておく必要がありますが,これはエラトステネスの篩を用いれば計算できるので,番目の素数をとしておきます.
()
整数を以上の素数の和として表す方法の個数を通りとすると,以下の漸化式が成り立つ:
\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*}
の場合について,素数を使わない場合が通り,素数を使う場合が通りです.
以下がプログラム例です.上の漸化式はの値が大きい順に計算しないといけないので,ここでは関数の再帰を用いて実装しています.
#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; }