确定O（n）中子集序列的算法？ [英] An algorithm to determine a subset sequence in O(n)?

问题描述

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

How can i aproach this problem by induction?

假设您将一个算法当作黑匣子，则看不到它是如何设计的，它具有以下特性：如果您输入任何实数序列和整数k，则算法将回答YES或NO，指示是否存在一个总和为k的数字子集。演示如何使用此黑盒来查找总和为k的给定序列{X1，…。，Xn}的子集。您可以使用黑盒O（n）次。

Suppose that you are given an algorithm as a black box you cannot see how it is designed it has the following properties: if you input any sequence of real numbers and an integer k, the algorithm will answer YES or NO indicating whether there is a subset of numbers whose sum is exactly k. Show how to use this black box to find the subset of a given sequence {X1, …., Xn} whose sum is k. You can use the black box O(n) times.

有什么想法吗？

推荐答案

我并不完全相信此处需要进行归纳。

I'm not entirely convinced that induction is necessary here.

这是我的两分钱：

假设您有一个数字 S 和整数 k 的序列，并且您已经知道存在一个子集总和为 k 的数字。现在，从序列中删除一个数字（称为 i ），然后在剩余的内容上使用黑框（使用相同的 k 像以前一样。）

Suppose you have a sequence of numbers S, and integer k, and you already know that there exists a subset of numbers whose sum is k. Now, remove a number from your sequence (call it i), and use your black box on what remains (using the same k as before).

• 如果算法在新序列上返回是，那么对 i 和 S 的任何子集，其总和为 k ？


• 如果算法在新序列上返回否，那么这将告诉您有关 i 和 S 的总和为 k ？



• If the algorithm returns YES on the new sequence, what does that tell you about i and any subset of S whose sum is k?
• If the algorithm returns NO on the new sequence, what does that tell you about i and any subset of S whose sum is k?

这篇关于确定O（n）中子集序列的算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！