資料結構和算法：給空盤分蘋果

内卷之源：

https://www.nowcoder.com/practice/bfd8234bb5e84be0b493656e390bdebf?tpId=37&&tqId=21284&rp=1&ru=/ta/huawei&qru=/ta/huawei/question-ranking

題目描述：

 * 把m個同樣的蘋果放在n個同樣的盤子裡，允許有的盤子空着不放（本題潛藏意思是盤子可以空，但蘋果必須放完），問共有多少種不同的分法？（用K表示）

 * 5,1,1和1,5,1是同一種分法。———— 即蘋果、盤子均沒有編号，不講順序，分完即可

 * 資料範圍：0<=m<=10，1<=n<=10。

測試用例：

 *   input：7 3

 * output：8

 * 本題含有多組樣例輸入

思路分析：

 * 分析：用事件來描述，允許有的盤子空着不放這個事件Z包含兩個互斥事件

          事件A → 存在空盤，即至少有一個盤子空着 ———— 問題轉化為将m個蘋果放到至多(n-1)個盤子裡

          事件B → 不存在空盤，即每個盤子至少有一個蘋果 ———— 問題轉化為将(m-n)個蘋果放到n個盤子裡

          Z = A ∪ B，交集為空

 *       采用遞歸

 * 沒有蘋果(m=0)，僅1種分法 ———— 全空

 * 一個蘋果(m=1)，僅1種分法 ———— 僅1個盤子有

 * 多個蘋果(m≥2)，至少1種分法

程式設計實作(C++)：

/*
 ************************************************************
 * @author    SLF
 * @version	  V1.0.0
 * @date      26-Jun-2021
 ************************************************************
 */

#include <iostream>

using namespace::std;

int recursivePut(int m, int n);

int main(void)
{
	int K = 0;
	int m = 0, n = 0;
	
	while(cin>>m>>n)
	{
		//cout << m << " " << n << endl;
		if((0 > m) || (10 < m) \
		|| (1 > n) || (10 < n))
		{
			//printf("input param error... m=%d, n=%d\n", m, n);
			return 0;
		}
		
		K = recursivePut(m, n);
		cout << K << endl;
	}
	
	return 0;
}

int recursivePut(int m, int n)
{
	if((0 > m) || (1 > n))
	{//不存在空盤時蘋果早已分完 或 存在空盤時空盤數量早已遞歸到一個
		return 0;
	}

	if((0 == m) || (1 == m))
	{//沒有蘋果 或 僅1個蘋果(5,1,1和1,5,1是同一種分法)
		return 1;
	}

	return (recursivePut(m, n-1) + recursivePut(m-n, n)); //左邊是 存在空盤，右邊是 不存在空盤
}
           

鄭重提示：①解題思路非最優，覆寫條件可能不全，僅供練習參考。

                  ②若有更佳思路或疑問，可在評論區留言互相讨論，不亦樂乎。

                  ③本文不允許轉載，若認可本文，可點贊收藏關注。