2 回答

• 2

  该算法可以递归表示，因为解决方案可以用较小输入的解决方案表示 . “小”这里有两个含义：

  • 数组的子集;特别是当前元素索引之后的子数组

  • 较小长度的解决方案;这些可以加在一起，给出长度为1的解决方案

  停止条件：

  • 当数组大小 A = 1 时 - 只能生成一个组合

  • 当长度 L = 1 - 组合数=数组中的元素数

  完全递归的程序是一个非常简单的单行程序：

  return [recursive call to rest of array, same length] + 
         [recursive call to same array, length - 1]
  

  这称为动态编程 .

  码：

  int F(int A, int L)
  {
      if (A <= 1) return 1;
      if (L <= 1) return A;
      return F(A - 1, L) + F(A, L - 1);
  }
  

  测试：

  • F(4, 2) = 10

  • F(2, 3) = 4

  • F(3, 5) = 21 （用纸笔跟踪，亲眼看看）

  ---

  编辑：我给出了一个优雅而简单的解决方案，但我可能没有像@RoryDaulton那样解释它 . 考虑给予他的回答 .

  回复于 2024-04-18T22:33:56+08:00
• 4

  你没有提供目标语言，也没有说你想要多少帮助 . 因此，如果您知道某种语言的递归，我将给出一个算法的总体思路，该算法应该很容易编码 . 询问您是否需要更多Python代码，这是我目前的首选语言 .

  你知道你需要做递归，你有两件事可以解决：给定数组的长度或所需数组的长度 . 设's recurse on the second, and let'表示给定的数组是 [0, 1, ..., n-1] ，因为您知道实际内容是无关紧要的 .

  如果所需的长度 r 是 1 ，您知道只有 n 所需的数组，即 [0] ， [1] ，...， [n-1] . 所以你的递归有一个基本案例 .

  如果 r-1 的长度为 r-1 ，如何将其扩展为 r 并保持要求？查看长度为 r-1 的数组中的最后一个元素 - 将其称为 k . 下一个元素不能小于，所以扩展到 r 长度的所有可能数组都是 r-1 ，附加 k', 'k+1 ，...， n-1 . 这些是 n-k 长度为 r 的数组 .

  是否清楚如何编码？请注意，您不需要保留所有长度为 r-1 的数组，您只需要使用元素 0 或 1 或... n-1 结束的数组数量 . 这样可以方便编码 - 不需要太多内存 . 事实上，事情可以进一步减少 - 我会把它留给你 .

  请注意，面试官可能不想要代码，他希望您的思考过程能够让代码看到您的思维方式 . 这是通过思考问题的一种方式 .

  回复于 2024-04-18T22:33:56+08:00