问题描述

把M个同样的苹果放在N个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?(用K表示)注意:5,1,1和1,5,1是同一种分法。

输入

第一行是测试数据的数目t(0<=t<= 20) 。以下每行均包含两个整数M和N,以空格分开。1<=M,N<=10。

输出

对输入的每组数据M和N,用一行输出相应的K。

输入样列

1
7 3

输出样例

8

算法实现

using System;

namespace Questions{
    class Program{
        public static void Main(string[] args){
            int t = int.Parse(Console.ReadLine());
            for (int i = 0; i < t; i++)
            {
                string input = Console.ReadLine();
                string[] data = input.Split(' ');
                int m = int.Parse(data[0]);
                int n = int.Parse(data[1]);
                Console.WriteLine(Apply(m, n));
            }
            Console.ReadKey();
        }

        public static int Apply(int m, int n)
        {
            if (n == 1 || m == 0)
                return 1;
            else
            {
                if (n > m)
                    return Apply(m, m);
                else
                    return Apply(m, n - 1) + Apply(m - n, n);
            }
        }
    }
}