算法的正确性证明 [英] Correctness proof of Algorithm
问题描述
我们的老师问我们这样的问题。
Our teacher asked us a question which goes like this.
Given a list of n distinct integers and a sequence of n boxes with preset
inequality signs inserted between them, design an algorithm that places
the numbers into the boxes to satisfy those inequalities. For example, the
numbers 2, 5, 1, and 0 can be placed in the four boxes as shown below
从在这个问题上，我们可以说数字是排序的，如果接下来出现小于符号，我们必须插入最小的数字，如果出现大于符号，我们必须插入最大数字，然后按顺序进行操作。
The from looking at the question we can say the numbers be sorted and if less than symbol appears next we have to insert the least number, if greater than symbol appears we have to insert max number and proceed as so.
- 如何说这种算法适用于每种情况？
- 在
的一个方向上遍历，我找到了一个解决方案，而在相反的顺序下，我找到了
。查找此
问题的所有解决方案的有效方法是什么？
推荐答案
要回答问题1，我想应该通过对所涉及的不同数字的数量进行归纳来完成。
To answer question 1, I'd say that should be done by induction over the number of distinct numbers involved.
说 n 是数字的数目。
对于 n = 1 没有什么可证明的。
for n = 1 there's nothing left to prove.
对于 n = 2 ，您具有大于或小于运算符。由于数字是不同的，并且自然（或实数）数的集合是有序的，因此您的算法将轻松得出一个解决方案。
for n = 2, you have either a greater than or a less than operator. Since the numbers are distinct and the set of natural (or real) numbers is well ordered, your algorithm will trivially yield a solution.
n- > n + 1 ：
情况1：第一个运算符是小于号。根据您的算法，选择最小的数字并将其放入第一个框中。然后，您可以解决最后一个 n 框的问题。通过感应可以做到这一点。由于第一个方框中的数字最小，因此它也小于第二个方框中的数字。因此，您有一个解决方案。
n -> n+1:
case 1: the first operator is a less than sign. According to your algorithm you pick the smallest number and put it into the first box. Then you solve the problem for the last n boxes. This is possible by induction. Since the number in the first box is the smallest, it is also smaller than the number in the second box. Therefor you have a solution.
情况2：第一个运算符是大于号。这也与情况1类似。
Case 2: the first operator is a greater than sign. This also works analogue to case 1.
QED
现在是问题的第二部分。我的想法来自以下描述的算法。首先我对解决问题（获得所有解决方案）感到满意，但我不能保证它是最快的解决方案。
Now for the second part of the question. My thoughts came up with the algorithm described below. Happy with the fact I solved the question (of getting all solutions) in the first place, I can't guarantee that it's the fastest solution.
注释，如果没有操作员更改，将只有一个解决方案。因此，我们假设存在运算符更改（但算法也会产生此解决方案）。
As already noted in a comment, if there are no operator changes, there will be only one solution. So we assume there are operator changes (but the algorithm will produce this solution too).
for all operator changes of the form >< or nil < (first operator is a <):
place the smallest element between them
now divide the remaining set of numbers into two.
if there are n numbers and there are k operators to the left of
the placed number, that will give you k over (n - 1) possibilities.
do this recursively with the two remaining parts.
If no operator changes of the form >< or nil < are left,
do the same with the mirrored operator changes <> and nil >,
but choose the highest element of the set.
If no operator changes are left, fill in the elements according to the
remaining operator in ascending or descending order.
好的，这不是程序代码，但是我认为这样比较容易（选择k n-1是最困难的部分）。我希望我对算法的解释是可以理解的。并且要注意，解决方案的数量在快速增长（呈指数增长，可能更糟）。
OK, this is not program code, but I think that will be comparatively easy (the choose k out of n - 1 is the hard part). I hope my explanation of the algorithm is understandable. And beware, the number of solutions grows fast (exponentially, probably worse).
这篇关于算法的正确性证明的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
