poj_1664_りんごを入れる問題解決レポート

テーマの出典
---------------------------------------------------------------------------------------------------------------------------------
Description
M個の同じリンゴをN個の同じ皿の中に置いて、ある皿が空いていることを許して、何種類の異なる分け方がありますか?(Kで表す)5,1,1と1,5,1は同じ分法である.
Input
1行目は、テストデータの数t(0<=t<=20)である.以下の各行は、2つの整数MとNを含み、スペースで区切られている.1<=M、N<=10である.
Output
入力されたデータMおよびNのセット毎に、対応するKが1行で出力される.
Sample Input
1
7 3
Sample Output
8
---------------------------------------------------------------------------------------------------------------------------------
解法:再帰
考え方(再帰的に詳しく述べる):
再帰的な役割は問題の規模を簡単に解決できるように縮小することにある.
問:では、この問題では、どのように問題の規模を減らすのでしょうか.
答え:この問題はm個のリンゴとn個の皿があり、明らかに、それぞれmとnの個数を減らす.問題全体の規模を減らすことができます.mの減少は皿の個数を最小限に抑える必要がある.
新しい問題はもとの問題と同じ形式を持っている
規模を縮小すると、新しい問題は元の問題と同じ意味になる.つまり、新しい問題は同じ形式を持っています.同じようにm個のリンゴをn個の皿に置く方法を求めます.
再帰的な終了には簡単なシナリオが必要です
問:この問題の簡単な光景は何ですか.
答え:下への再帰が進むにつれて、次のような簡単なシナリオが発生します.

n=1で、皿は1つ残っています.つまり、1つの置き方しかありません. 

m<0、すなわち空の皿が存在する.したがって、この場合はnが減少し続ける場合に含まれる. 

m=0、つまりりんごはもう全部置いておいて、余計なことはありません.だからこれは1種の放法に属します;

再帰ジャンプの信頼
問題の規模を減らすにはどうすればいいのか、簡単な状況をどのように正確に分析すればいいのかを考えるだけです.私たちは詳細を実現するために多くのことを考える必要はありません.
----------------------------------------------------------------------------------------------------------------------------------------

#include <iostream>
using namespace std;
int fun(int m, int n)
{
	//         
	if (m == 0) return   1;
	//        
	if (n == 1) return   1;
	// m<0        fun(m,n-1) 
	if (m < 0)  return   0;

	return fun(m-n, n) + fun(m, n-1);
}
int main()
{
	int    t;
	int    m, n;
	cin >> t;
	while (t--)
	{
		cin >> m >> n;
		cout << fun(m, n) << endl;
	}
	return   0;
}