如何證明「排列給定數字以形成最大數字」算法的正確性？

Question

Arrange given numbers to form the biggest number給出算法。 它使用以下文本來證明算法的正確性：

那麼我們該如何去做呢？這個想法是使用任何基於比較的排序算法。在使用的排序算法中，不是使用默認比較，而是編寫比較函數myCompare（）並使用它對數字進行排序。給定兩個數字X和Y，myCompare（）應該如何決定首先放置哪個數字 - 我們將兩個數字XY（Y的末尾附加Y）和YX（Y的末尾附加X）進行比較。如果XY更大，那麼X應該在Y之前輸出，否則Y應該早於之前。例如，讓X和Y分別爲542和60.爲了比較X和Y，我們比較了54260和60542.由於60542大於54260，我們首先將Y設爲Y。

考慮三個numers：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，我們需要證明應該在YZ之前整體形成一個更大的數字X(YZ) >= (YZ)X。

任何人都可以給出算法的正確性的正式證明？

Answer 1

首先，我們將證明，如果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）

但這可以簡單地通過乘以前兩個不等式和取消常用術語來證明。

既然我們已經證明關係是傳遞的（因此可以用來定義排序順序），很容易證明它可以解決問題。

假設給出的數字是A，B，C ...，例如A「<」B「<」C「<」D ...。我們會證明A必須在最後的數字中排名第一。如果沒有，我們有一個字符串，像（一些前綴）XA（一些後綴）作爲最後的數字。很容易，（某些前綴）AX（某些後綴）是一個更大的數字，因爲對於所有X而言，由於傳遞性，「<」X。以這種方式繼續氣泡向左，直到它成爲第一個元素。

現在，我們有固定的第一要素，同樣的論點可以適用於B等表明，最好的解決辦法是ABCD ...