放蘋果（遞歸）

點選打開連結

m個蘋果放入n個盤子有幾種方法。

用遞歸，n個盤子有一個為空，或者n個盤子都至少有一個。

#include<iostream>   
#include<string> 
using namespace std;
int sharingapple(int m, int n){
	if (m == 1 || n == 1)//隻有一個蘋果或者隻有一個盆子，則隻有一種放法。
		return 1;
	else if (m < n)
		return sharingapple(m, m); //2個蘋果放入3個盤子與2個蘋果放入2個盆子是一樣的
	else if (m>n)
		return sharingapple(m, n - 1) + sharingapple(m - n, n);//3個蘋果放入2個盤子 可以了解為3個蘋果放入一個盤子（有某一個空）的情況+一個蘋果放入三個盤子（每個盤子都至少有一個蘋果）的情況
	else
		return 1 + sharingapple(m, n - 1);
}

void main(){
	int m, n;
	cin >> m >> n;
	cout << sharingapple(m, n) << endl;
	system("pause");
}