-2

我如何通过归纳来解决这个问题？

假设给你一个算法作为一个黑盒子，你看不到它是如何设计的，它具有以下属性：如果你输入任何实数序列和一个整数 k，算法将回答 YES 或 NO，指示是否存在子集总和正好为 k 的数。展示如何使用这个黑盒来找到给定序列 {X1, ...., Xn} 的子集，其和为 k。您可以使用黑盒 O(n) 次。

任何想法？

4

1 回答 1

4

我并不完全相信这里有必要进行归纳。

这是我的两分钱：

假设您有一个数字序列S和整数k，并且您已经知道存在一个数字子集，其和为k。现在，从你的序列中删除一个数字（调用它i），然后在剩下的部分上使用你的黑盒子（使用与k以前相同的方法）。

  • 如果算法在新序列上返回 YES，那么它告诉您什么以及其总和为 的i任何子集？Sk
  • 如果算法在新序列上返回 NO，这告诉您什么以及其总和为 的i任何子集？Sk
于 2013-09-11T19:21:11.253 回答