Arrange given numbers to form the biggest number给出算法。 它用下面的文字来证明算法的正确性:
So how do we go about it? The idea is to use any comparison based sorting algorithm. In the used sorting algorithm, instead of using the default comparison, write a comparison function myCompare() and use it to sort numbers. Given two numbers X and Y, how should myCompare() decide which number to put first – we compare two numbers XY (Y appended at the end of X) and YX (X appended at the end of Y). If XY is larger, then X should come before Y in output, else Y should come before. For example, let X and Y be 542 and 60. To compare X and Y, we compare 54260 and 60542. Since 60542 is greater than 54260, we put Y first.
考虑三个数字:X
、Y
和 Z
。使用 X -> Y
表示 X
应该在 Y
之前。基于比较的算法可以使用以下两个比较将 X
、Y
和 Z
排序为 XYZ
: XY >= YX
=> X -> Y
和 YZ >= ZY
=> Y -> Z
。但是这两次比较并不能保证XYZ
是最大的数。换句话说,X
应该在 Y
之前和 Y
应该在 Z
之前的事实不一定确保XYZ
构成最大的数字。以YZX
为例。要证明 XYZ >= YZX
,我们需要证明 X(YZ) >= (YZ)X
这意味着 X
应该在 YZ
作为一个整体组成一个更大的数。
谁能给出算法正确性的正式证明?
最佳答案
首先我们要证明如果X"<"Y和Y"<"Z则X"<"Z。假设他们分别有p,q和r位,前两个关系简化为
- X * 10^q + Y ≥ Y * 10^p + X ⇒ X * (10^q - 1) ≥ Y * (10^p - 1)
- Y * 10^r + Z ≥ Z * 10^q + Y ⇒ Y * (10^r - 1) ≥ Z * (10^q - 1)
我们要证明
- X * 10^r + Z ≥ Z * 10^p + X 等价于 X * (10^r - 1) ≥ Z * (10^p - 1)
但这可以简单地通过将前两个不等式相乘并抵消公共(public)项来证明。
既然我们已经证明该关系是可传递的(因此可以用来定义排序顺序),那么很容易证明它可以解决问题。
假设给定的数字是 A, B, C … 这样 A "<"B "<"C "<"D...。我们将证明 A 必须在最后的数字中排在第一位。如果不是,我们有一个像 (some prefix)XA(some suffix) 这样的字符串作为最终数字。很容易,(一些前缀)AX(一些后缀)是一个更大的数字,因为由于传递性,所有 X 的“<”X。以这种方式继续,A 向左冒泡,直到它成为第一个元素。
现在我们已经确定了第一个元素,可以将相同的论证应用于 B 等等,以表明最佳解决方案是 ABCD...
关于algorithm - 如何证明 "Arrange given numbers to form the biggest number"算法的正确性?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41799870/