eggs，二廣高速公路地圖

eggs，二廣高速公路地圖

Description:

Erin買了不少雞蛋，她發現一天吃不完這麼多，於是決定把n個同樣的雞蛋放在m個同樣的籃子裡，允許有的籃子空著不放，請問共有多少種不同的放法呢？

注意：2，1，1和1，2，1 是同一種分法。

 第一行是測試數據的數目t（0 <= t <= 20）。以下每行均包含二個整數m和n，以空格分開。1<=m，n<=10。

對輸入的每組數據m和n，用一行輸出相應的結果。

例如：

Input:

4

3 8

4 7

2 4

4 2

Output:

10

11

3

2

(注意結尾有換行)

Hint:

嘗試利用遞歸去分析解題，即不同情況下應該怎麼返回。

可以嘗試用樹狀圖（然而我覺得用處不大）。

注意籃子可以空著不放，請先想明白示例中最後兩個例子再做題。

我的代碼：

#include<stdio.h>
int egg(int m, int n);
int main() {
    int t, m, n, i, result = 0;
    scanf("%d", &t);
    for (i = 0; i < t; i++) {
        scanf("%d%d", &m, &n);
        result = egg(m, n);
        printf("%d\n", result);
    }
    return 0;
}
int egg(int m, int n) {
    if (m == 1 || n == 1) {
        return 1;
    }
    if (n <= m) {
        return 1 + egg(n-1, n);
    } else {
        return egg(m-1, n) + egg(m, n-m);
    }
}

標答：

#include<stdio.h>
int egg(int m, int n);
 
int main() {
    int t;
    // m for baskets, n for eggs
    int m, n;
    int result = 0;
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d", &m, &n);
        result = egg(m , n);
        printf("%d\n", result);
    }
    return 0;
}
 
int egg(int m, int n) {
    if (m == 1 || n == 0)
        return 1;
    if (n < 0)
        return 0;
    return egg(m-1, n) + egg(m, n-m);
}