使用自定義函數代替素數的海明碼

Hamming Problem是一個着名的問題，它基本上會生成素數因子僅爲{2,3,5}的所有整數。（它可以擴展到任何一組的素因子我覺得）使用自定義函數代替素數的海明碼

爲了找到的第n個漢明號碼，有一個聰明O（N）通過迪傑斯特拉，其中僞碼是如下構建的算法：

List<int> H 
int i=0,j=0,k=0, n=10 // find the 10-th hamming number 
H.add(1) 
for(i=0 to 10) 
    int next = min(2*H[i], 3*H[j], 5*H[k]) 
    H.add(next) 
    if(next == 2*H[i]) ++i 
    if(next == 3*H[j]) ++j 
    if(next == 5*H[k]) ++k 

output(H[10])

在這種解決方案的關鍵點在於，如果H是一個漢明號碼，然後2H，3H，5H也是漢明數目

予跨越problem來了，這是我所感測這有點像海明問題，b UT它不使用構建素因子集數，而是如果我重聚問題的陳述，它是這樣的：

1是在結果集中。如果H在結果集中，那麼2H + 1和3H + 1也在結果集中。找到結果集中的第n個號碼

然後我想知道是否同樣的構造算法適用於這個問題，事實證明它確實！（我甚至不知道爲什麼它的工作原理）

Def f(x) 2x+1 
Def g(x) 3x+1 

List<int> H 
int i=0,j=0,n=10 // find the 10-th hamming number 
H.add(1) 
for(i=0 to 10) 
    int next = min(f(H[i]), g(H[j])) 
    H.add(next) 
    if(next == f(H[i])) ++i 
    if(next == g(H[j])) ++j 

output(H[10])

於是我想：

這是構建算法的工作產生的數字問題，給出像「如果x是一個規則在結果中，則所有f(x), g(x), p(x), q(x)...也都在結果中「，前提是這些函數會給出結果> = x？

來源

2016-12-16 shole

函數需要是單調的：如果f（2）> f（3），那麼生成的數字將不會按升序排列。如果函數是單調的，我認爲你可以通過歸納法證明所有數字都是以正確的順序生成的。生成所有數字到N之後，必須準備好一個指針，以生成序列中的下一個數字。 – mcdowella

@mcdowella謝謝，我認爲你對單調部分是正確的。對於證明，我試圖做到這一點，但對我來說這並不是微不足道的...... – shole

單調（或其他強烈的假設）是必不可少的。如果'f'，'g'等可用可證明無界範圍計算，但沒有其他假設，則通過應用這些函數從{1}生成的集合是遞歸可枚舉的，但不是一般遞歸的。在非遞歸的情況下，由於停機問題是不可判定的，因此沒有算法可能工作。事實上，沒有一個通用算法可以確定2是否在集合中。 –

的充分條件是從整數到整數的所有功能f_i必須是單調遞增，並有n < f_i(n)所有i和n。

說明您需要類似規則的整數部分的示例是一對函數。這將導致序列1, 3/2, 7/4, 15/8, ...，你永遠不會去2。

函數(2^n, 20 - 5n + n^2)以1, 2, 4, 16, 14, ...的順序出現，顯然不是按順序排列的。因此需要不減少。

函數(n-3)給出了序列（1，-2，-5，...）並顯示了n < f_i(n)的重要性。

那麼爲什麼這個工作？

首先很清楚，這個算法輸出的任何東西都在集合中。

換個角度來說，假設滿足所有三個條件。然後，我們必須通過歸納證明，如果你屬於這個序列，那麼在我們到達那裏之前我們就開始尋找你，然後當我們通過你時，它必須產生它。（我們傳遞給你的是由序列是一組不斷增加的整數組成的事實。）證明有點混亂，但直截了當。

來源

2017-06-27 00:38:14 btilly

使用自定義函數代替素數的海明碼

回答

相關問題