例6.13は、1次元配列a[1..n](n<25)が知られており、整数mも知られている.配列aの任意の数を
/*例6.13既知の1次元配列a 1..n、整数mも知られている.配列a中の任意の幾つかの要素の和をmに等しくすることができれば、YESを出力し、逆にNOとする.【解析】1つの決定された配列a[1.n]と1つの決定された数mについて、配列a中の任意のいくつかの要素の和をmに等しくできるか否かを判断することは、配列aから任意の数を取ってmにすることができるか否かを判断することに等しい.aの任意の要素a[n]に対して、取るか取らないかの2つの場合のみ:
(1)a[n]:このとき問題は、1つの決定された配列a[1.n-1]と1つの決定された数m-a[n]について、配列a[1.n-1]の任意のいくつかの要素の和をm-a[n]に等しくできるか否かを判断することに変換される.
(2)a[n]を取らない:このとき問題は、1つの決定された配列a[1.n-1]と1つの決定された数mについて、配列a[1.n-1]の任意のいくつかの要素の和をmに等しくできるかどうかを判断することに変換される.
全過程変数作成プログラムは以下の通りである:*/#includeusing namespace std;const int max1=51;int a[max1],n,m;bool flag;void sum(int ,int );int main(){ cin>>n;for (int i=1; i<=n;++i) cin>>a[i];cin>>m;
}void sum(int n,int m){if(a[n]==m)flag=true;//グローバル変数falg伝達結果else if(n==1)return;//n=1を再帰境界としてelse//再帰しない2種類の選択{sum(n-1,m-a[n]);sum(n-1,m);}}
(1)a[n]:このとき問題は、1つの決定された配列a[1.n-1]と1つの決定された数m-a[n]について、配列a[1.n-1]の任意のいくつかの要素の和をm-a[n]に等しくできるか否かを判断することに変換される.
(2)a[n]を取らない:このとき問題は、1つの決定された配列a[1.n-1]と1つの決定された数mについて、配列a[1.n-1]の任意のいくつかの要素の和をmに等しくできるかどうかを判断することに変換される.
sum(n,m) a[1..n] m，
sum(n-1,m-a[n]) sum(n-1,m) ，
sum(n,m) ， 。 ， 。
：
if (a[n]==m) sum=true;
else if (n==1) sum=false;全過程変数作成プログラムは以下の通りである:*/#includeusing namespace std;const int max1=51;int a[max1],n,m;bool flag;void sum(int ,int );int main(){ cin>>n;for (int i=1; i<=n;++i) cin>>a[i];cin>>m;
flag=false;
sum(n,m);
if (flag) cout<}void sum(int n,int m){if(a[n]==m)flag=true;//グローバル変数falg伝達結果else if(n==1)return;//n=1を再帰境界としてelse//再帰しない2種類の選択{sum(n-1,m-a[n]);sum(n-1,m);}}