我必須在Python中編寫一個shell排序程序，但一方面我必須有一個程序使用一些特殊的間隙序列創建文本文件，這是我的shell排序會得到它的差距數字。如何實現Pratt間隙序列？（Python，Shell Sort）

On Wikipedia（http://en.wikipedia.org/wiki/Shellsort）Pratt序列的等式如下：「連續數字形式2^p * 3^q」，它產生1,2,3,4,6,8,9,12 ，...

我沒有得到的是如何實現這個，基本上P和Q是什麼？

最壞情況下的時間複雜度爲O（n日誌^ 2N）

我對序列發生器文件目前代碼：

def Hibbard(big): 
     H = open("Hibbard.txt","w") 
     i = 1 
     math = (2**i)-1 
     while math <= big: 
      H.write(str(math)) 
      H.write("\n") 
      i+=1 
      math = (2**i)-1 
    def Pratt(big): 
     pass 
    def SedA(big): 
     SA = open("SedgewickA.txt","w") 
     SA.write("1\n") 
     i = 1 
     math = (4**i)+3*2**(i-1)+1 
     while math <= big: 
      SA.write(str(math)) 
      SA.write("\n") 
      i+=1 
      math = (4**i)+3*2**(i-1)+1 
    def SedB(big): 
     pass 
    def main(): 
     big = int(input("Enter the largest gap: ")) 
     Hibbard(big)

普拉特（大）

 SedA(big)

SEDB（大）

main()

來源

2014-09-21 Andrew Nelson

我還沒有嘗試過編碼，因爲我根本不知道從哪裏開始。這真的是一個數學問題。如果有幫助，我已經編碼了4個我需要的其他4個，我會把它放在這裏。 – 2014-09-21 22:53:03

我n Pratt序列的定義，p和q分別是2和3分別提出的指數。你需要找到所有2和3的冪的乘積不能大於你的排序的最大間隙大小。要做到這一點，製作一張桌面，其頂部爲2，冪爲3，並填充每個單元格，直到它們超過最大間隙大小。例如，在最大間隙大小爲500的情況下，表格如下所示：

1 2 4 8 16 32 64 128 256 
    3 6 12 24 48 96 192 384 
    9 18 36 72 144 288 
    27 54 108 216 432 
    81 162 324 
243 486

現在模擬Python中該表的生成。

def generate_pratt(max_size): 
    """Generate a sorted list of products of powers of 2 and 3 below max_size""" 
    # for https://stackoverflow.com/q/25964453/2738262 
    products = [] 
    pow3 = 1 # start with q = 0 
    while pow3 <= max_size: 
     # At this point, pow3 = 3**q, so set p = 0 
     pow2 = pow3 
     while pow2 <= max_size: 
      # At this point, pow2 = 2**p * 3**q 
      products.append(pow2) 
      pow2 = pow2 * 2 # this is like adding 1 to p 
     # now that p overflowed the maximum size, add 1 to q and start over 
     pow3 = pow3 * 3 

    # the Pratt sequence is the result of this process up to the given size 
    return sorted(products) 

print(generate_pratt(12))

來源

2014-09-21 23:03:16

如何實現Pratt間隙序列？ （Python，Shell Sort）

普拉特（大）

SEDB（大）

回答

相關問題

如何實現Pratt間隙序列？（Python，Shell Sort）