0

递归方法来查找整数 k 可以表示为 sum 的不同方式的数量，其中每个操作数都是小于 n 的整数...请帮助我使用算法。我想不出这个问题的递归解决方案

4

1 回答 1

1

基本上，我的第一个想法是：

int numberOfWays(int x)
{
    if(x <= 1)
        return 0;
    if(x == 2)
        return 1;
    // else:
    int res = 0;
    int i;
    for(i = 1; i <= x / 2; i++)
        res += numberOfWays(x - i);
    return res;
}

我将给它一些测试和想法，但仅此而已。

或许多解释几句...

显然，没有办法把 1 写成整数之和 < 1，只有一种方法把 2 写成整数和 < 2：2 = 1 + 1。

从那里开始，事情变得有趣。每个整数 x > 2 都可以写成 (x-1) + 1。因为我们是递归的，所以我们现在得到方法的数量，(x-1) 可以写成整数之和 < (x-1) 等等上。最终，我们将达到 (xn) = 2，这将返回 1。

从那里开始，我们向上回溯，总结我们找到的表示数字的方式的数量，瞧：）

于 2012-09-08T19:08:20.610 回答