时间戳

首页 > 解决方案 > 如何从x个连续数字递归计算可能增加的序列数？

java - 如何从x个连续数字递归计算可能增加的序列数？

问题描述

令 integerx为数字组合的长度，并且有一个从 1 到 的连续整数范围max。序列必须是非递减的（序列通常是递增的，但相同的连续数字是可能的）。给定x并且max有多少这样的序列是可能的？

例如，对于x=3, max= 2，有 4 个可能的序列：

1,1,1

1,1,2

1,2,2

2,2,2

我想到了以下递归方法：

public static int howManySorted(int n, int max, int len, int i) {
        if(len > n || i > max) {
            return 0;
        }

        if(len == n && i == max) {
            return 1;
        }

        return howManySorted(n, max, len + 1, i + 1) +
                howManySorted(n, max, len + 1, i) +
                howManySorted(n, max, len, i + 1);
}

  1. howManySorted(n, max, len + 1, i + 1)指序列长度加一，下一个数比前一个大一的情况。

  2. howManySorted(n, max, len + 1, i)指序列长度加一，下一个数与前一个数相同的情况。

我确实意识到我的递归公式存在问题，因为在这样的序列中，相邻数字之间的差异最多为1. 所以我决定添加另一个调用howManySorted(n, max, len, i + 1)来弥补这种情况，但这仍然不会产生预期的结果。我究竟做错了什么？

main我像这样调用这个方法howManySorted(n, max, 1, 1)。

标签： javarecursionsequence

解决方案

让我们说len = 10和max = 5。

请注意，由于我们对实际解决方案不感兴趣，只对计数感兴趣，因此范围 2-5 的结果与范围 1-4 的结果相同。

对于第一个数字，我们可以选择一个数字 1-5，然后：

  1. 递归调用len = 9，将数字范围限制为 1-5，即max = 5
  2. 递归调用len = 9，将数字范围限制为 2-5，即max = 4
  3. 递归调用len = 9，将数字范围限制为 3-5，即max = 3
  4. 递归调用len = 9，将数字范围限制为 4-5，即max = 2
  5. 递归调用len = 9，将数字范围限制为 5-5，即max = 1

总结递归调用返回的计数。这就是这个调用的结果。

当 时len = 1，max有解，所以max作为计数返回。

当 时max = 1，只有一个解，不管len，所以返回1计数。

我会把实际的编码留给你。

推荐阅读