アルゴリズム導論第1章and第2章(python)

アルゴリズムの導論の第1章
アルゴリズム#アルゴリズム#
入力--(アルゴリズム)-->出力
 
解決した問題
DNAの識別(配列、最長共通子配列、)#一部の使用法の決定
インターネットクイックアクセスインデックス
電子商取引(数値アルゴリズムand数論)
交通図...(図論、旅行会社問題)
トポロジのソート#
 
 
第二章
2.1ソートの挿入
    
#p 11ダミーコードは注意する予定です#(アルゴリズム導論第3版中国語)
 
循環不変式?
サイクルj++
不変A[1..j-1]は常に秩序化されている
各ループは配列Aからj番目の要素を取り出して秩序領域A[1..j-1]に挿入し、jをインクリメントする.こうしてA[1..j-1]の秩序性は常に保たれ,これがいわゆる「ループ不変(loop invariant)」である.
 
正確性の証明:#数学の帰納法の構想をセットします(このノートは数学の構想を再重視したいです)
初期化:j=1の場合A[1]秩序
保持:j=n-1,j=nA[1..j-1]ともに秩序化(n-1成立nも成立)
終了:j>A.length(アルゴリズムの貧乏性:(データ構造:厳蔚敏は第1章のようです))
 

def INSERTION_SORT(A):
    for j in range(1,len(A)): # ython[,) #     1   python list 0  
        #print(A[j]) #test
        key = A[j]
        i = j - 1
        while i >=0 and A[i] > key:
            A[i + 1] = A[i]
            i -= 1
        A[i + 1] = key

if __name__ == '__main__':
    A = [5,2,6,1,3]
    INSERTION_SORT(A) #  java      c  ？：**p
    print(A)

=================== RESTART: F:/python/2_1_insert_sort.py ===================
[1, 2, 3, 5, 6]
 
環境#win 7 python 3.5.1通過
@python list設計とc++STLのarray類似(stlソース剖析:侯捷)
 
2.2分析アルゴリズム
採用モデル:シングルプロセッサランダムアクセスマシン(random-access machine,RAM)
成長レベル:O(N**2)
 
2.3分治法
思想:原問題をいくつかの規模が小さいが原問題に似たサブ問題に分解し、これらのサブ問題を再帰的に解き、その後、これらのサブ問題の解を統合して原問題の解を確立する.
ステップ:分解解決集計
集計:
ぶんかいかいかい
絶えず1/2処理に分ける(二叉木の後続遍歴のように)
 

  
import decimal
def MERGE(A,p,q,r): #  
    n1 = q - p +1
    n2 = r - q
    L = []
    R = []
    for i in range(n1):
        L.append(A[p + i]) # 0  
    for j in range(n2):
        R.append(A[q + j+1]) #A[q+1 ,r]
    L.append(decimal.MAX_EMAX ) #10    64 999999999999999999 
    R.append(decimal.MAX_EMAX)
    i = 0
    j = 0
    for k in range(p,r+1): #A[p,r]
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
 
def MERGE_SORT(A,p,r): #A[p,r]
    if p < r:
        q = (p + r)//2 
        MERGE_SORT(A,p,q)
        MERGE_SORT(A,q+1,r)
        MERGE(A,p,q,r)
 
if __name__ == '__main__':
    A = [5,2,4,7,1,3,2,6]
    print(A)
    MERGE_SORT(A,0,len(A)-1) 
    print(A)
 
'''
  ：
============== RESTART: F:\python\algorithms\2_3_merge_sort.py ==============
[5, 2, 4, 7, 1, 3, 2, 6]
[1, 2, 2, 3, 4, 5, 6, 7]
  ：win7 python3.5.1
  ： A      python  list 0       [ , ]
 
'''

 
 
参考引用:#これはどう書くか分からない--!
            http://www.jianshu.com/p/J4U6rR
            http://baike.baidu.com/link?url=MOFJI8c0V6VJUlBLvcBAPBw1WtF3wYMUkXLl0WHajyC7nyu-lyZWOaWrTd96zb1KuOYN_AtG_IShBPYFrM_HFK
            http://www.cnblogs.com/tanky_woo/archive/2011/04/10/2011133.html
     
転載先:https://www.cnblogs.com/liguan/p/5151247.html