您當前的位置：首頁 > 繪畫

十個正整數，任意兩數之差不相同，求其中最大數的最小值。如果是任意有限個正整數呢?

作者：由仙墟府君發表于繪畫時間：2022-02-11

dchen5052022-02-11 22:47:50

該問題是一個非常複雜的組合數學問題，可轉化為運籌學中的整數規劃問題。以下會看到，轉化為整數規劃問題，光是約束條件的描述也是挺複雜的。目標值的最小化是線性的，但約束條件的方程是非線性的。

設任意n個正整數

依小到大排列，即

$x_1\leq x_2\leq x_3\leq ...\leq x_n$

任意兩數之差互不相同，使

取最小值。

為簡化起見，可設

，以下會看到，只有

時，序列可取等號，

$n\geq 3$

時均不能取等號，即序列 {

} 是嚴格單調遞增的。可將所有相差數排列成如下三角形（灰色部分）：

因為要求任意兩個差數各不相同，即灰色三角形共

$\frac{n(n-1)}{2}$

個差數各不相同。因此：

第一列數（代表相鄰兩個正整數之差）彼此互不相同。

第二列數（代表相隔兩位的兩個正整數之差）與第一列數互不相同，先按同一行進行比較，有

$x_{k}-x_{k-1}\ne x_{k}-x_{k-2},或 x_{k-1}\ne x_{k-2}(k=3,4,...n)$

。因為

$x_{k-2}\leq x_{k-1}$

因此得出

$x_{k-2}<x_{k-1}$

，即

$x_{1}<x_{2}<x_{3}< ...<x_{n-1}$

，從相隔一行比較，有：

$x_{k-1}-x_{k-2}\ne x_{k}-x_{k-2},(k=3,4,...n)$

，即

$x_{k-1}\ne x_{k}$

，因

$x_{k-1}\leq x_{k}$

，故

$x_{k-1}< x_{k}$

，得出

$x_{2}<x_{3}< ...<x_{n}$

，兩者結合，得出

$x_{1}<x_{2}<x_{3}< ...<x_{n}$

，即序列 {

} 是嚴格單調遞增的（對於

$n\geq3$

）。

那麼如果第一列和第二列相隔兩行，相隔三行，相隔m進行比較呢？更進一步，第

列和第

列相隔

行進行比較呢？如何描述各相差數互不相同的約束方程呢？

第

列第

行的數為：

$x_{p}-x_{p-j}(j=1,2,...n-2, p=j+1,j+2,...,n-1)$

第

列第

行的數為：

$x_{q}-x_{q-k}(k=2,3, ...n-1,q=k+1,k+2,...,n-1)$

需滿足：

$x_{p}-x_{p-j}\ne x_{q}-x_{q-k}$

（

$p\ne q,，j< k$

）

將不等號變為：

$[(x_{p}-x_{p-j})-(x_{q}-x_{q-k})]^{2}>0$

，或

$(x_{p}-x_{q}+x_{q-k} -x_{p-j})^{2}>0$

該問題的數學描述為：

$(x_{p}-x_{q}+x_{q-k} -x_{p-j})^{2}>0$

$x_{1}<x_{2}<x_{3}< ...<x_{n}$

為正整數。

這是一個約束條件為非線性的整數規劃問題，約束方程有

$\frac{n^2(n-1)^{2}}{4}$

個。

看上去是一個典型的NP問題，當

較大時，是很難在多項式時間內獲得最優解的，

較小時可以透過列舉法獲得最優解。

對

較小時可以作如下分析：

1。

時，只有一個差數，沒有可比較的差數，因此可取

2。

時，可取 {

$x_{1},x_{2},x_{3}$

}={

}或{

}，得到三個差數

或

均不同，而且是最小的三個差數，因此

為最優解

3。

時，若以 {

$x_{1},x_{2},x_{3}$

}={

}或{

}為基數推算

$x_{4}$

只能得出

$x_{4}=8$

6個差數（灰色標註）如下：

但

$x_{4}=8$

不是最優解，取 {

$x_{1},x_{2},x_{3},x_{4}$

}={

} 即

$x_{4}=7$

才是最優解。

差數如下：

這六個差數以小到大排列正好是

，是六個最小的差數，因此

$x_{4}=7$

是最優解。這說明如果

是n個正整數的最優解，以此為基礎推算的

$x_{n+1}$

不能保證

$x_1, x_2,x_3,...x_{n+1}$

是n+1個正整數的最優解，這是需要特別注意的。

4。

時，取 {

$x_{1},x_{2},x_{3},x_{4},x_{5}$

}={

} 即

$x_{5}=13$

是最優解。

可以發現，隨著

的增大，差數按順序排列不再是連續的。上述10個差數從1到12，當中8和10沒有出現。透過電腦計算，對於

$n\leq10$

應該還是能推算出

$x_{10}$

的最優解。

對於

下面是按未出現相差數的最小者優先考慮的原則，得到的一個近似解

感謝知友【田宮水口鉗子】和【rice0208】提供的反例，後者給出的解（如下圖）

$x_{10}=56$

似乎是最優解的。

對較大的正整數

，尋求最優解是很困難的。因為該問題等同於NP問題，是很難在多項式時間內找到最優解的。如果能有演算法在時間複雜度

$O(n^{k})$

（

為某正整數）找到最優解，那就解決了NP問題，這可是世界級數學難題。

補充資料：

可以給出該問題解的一個上界。取

$x_{n}-x_{n-1}=x_{n-1}-x_{1}+1$

，即

$x_n=2x_{n-1}$

，或者

$x_{n}=2^{n}$

，則

$x_{n}$

是最優解的一個上界。因為如果

$x_1,x_2,x_3,..x_{n-1}$

是問題的一個可行解，其形成的所有差數均互不相同，最大差數為

$x_{n-1}-1$

，而

$x_{n}-x_{n-1}=x_{n-1}-x_{1}+1$

能確保新出現的差數均大於已經出現的差數。新出現差數的最小值為

$x_{n}-x_{n-1}=x_{n-1}>x_{n-1}-1$

，因此

$x_{n}=2^{n}$

是一個可行解，也就是最優解的一個上界。

這個可行解是很粗糙的，這裡給出該問題一個近似解的演算法，比上界

$x_{n}=2^{n}$

要好許多。以上面

的解為例，闡述如何從

推算到

$x_{n+1}$

：

將可行解序列 {

}形成的差（上面灰色三角形部分）共45個數以小到大排列如下，並標記為藍色：

我們看到，1到55之間，未出現的差數有十個：{

}

近似解演算法的思路是：從這十個未出現差數中依小到大進行試用，36是首選，即

$x_{11}=x_{10}+36=56+36=92$

，檢查新出現的差數是否與已出現的差數中任何一個重複，若有重複，則棄用，選擇下一個數

，依次進行，直到選擇某個數不出現重複為止。假如試用這十個數均會出現重複數，則只能選擇可行解

$x_{11}=2x_{10}=112$

。

經驗證，取

$x_{11}=x_{10}+36=92$

是可行的，於是確定

$x_{11}=92$

是一個近似解。比上界

更小。序列如下：

該演算法可以針對n很大時無法獲得最優解的情況下，能獲得一個較好的近似解。

田宮水口鉗子2022-02-15 11:11:49

我有一個c++演算法，用窮舉，但是太笨了，計算量非常大，我的電腦跑不過來。希望有大神可以來指點，或者給出更好的演算法。

#include

using namespace std；

bool bijiao（int a［］）；

int main （）

{

int a［10］；

int i；

for（a［0］=10；；a［0］++）

for（a［1］=9；a［1］

for（a［2］=8；a［2］

for（a［3］=7；a［3］

for（a［4］=6；a［4］

for（a［5］=5；a［5］

for（a［6］=4；a［6］

for（a［7］=3；a［7］

for（a［8］=2；a［8］

for（a［9］=1；a［9］

{

if（bijiao（a））

{

cout<<“哈哈”<

for（i=9；i>=0；i——）

cout<

return 0；

}

cout<

}

}

bool bijiao（int a［］）

{

int i，j，k（0），b［45］；

for（i=0；i<9；i++）

{

for（j=i+1；j<10；j++）

{

b［k］=a［i］-a［j］；

k++；

}

}

for（i=0；i<44；i++）

{

for（j=i+1；j<45；j++）

{

if（b［i］==b［j］）

{

return false；

}

}

}

cout<<“差都不同”；

return true；

}

標簽：差數最優正整數 int ++

上一篇:2021春節穿搭參考：春節過年穿衣打扮技巧分享～

下一篇：讀懂這三點，走到哪裡你都有貴人相助

猜你喜歡