アルゴリズムの抽象とPythonで具体的なアルゴリズムを実現する
17390 ワード
一、アルゴリズム抽象
それらは一般的に具体的なアルゴリズムに基づいて総括し、抽出し、分析し、逆に他の問題の解決を指導するために用いられる.それらはある種類の問題の解決に適用され、弁解する.
証法の観点から見ると、抽象的なアルゴリズムと具体的なアルゴリズムは抽象と具体、普遍性と特殊性、共通性と個性の関係である.馬は白馬の抽象で、白馬であれ赤であれ
馬は、すべて馬で、私たちは馬の唯一の本質的な属性--染色体で動物が馬かどうかを決定して、この本質的な属性は馬の抽象です.
(1)分治法
分治法の基本思想はまず原問題を分割して、原問題を1つ以上の簡単なサブ問題に分割して、これらのサブ問題の解は一定の組み合わせを経て原問題の解を得て、求めます
これらのサブ問題を解くと,しばしば再分解,組合せ,すなわち上の過程を反復する.さらにまとめると,分治法の手順が得られる:サブ問題の分解,解,組合せ.に着く
どのように分解して、組み合わせて、分治法は抽象的に法則を出すことができません.自分がやりたいことはどうすればいいのか、例えば集計ソートやクイックソートは、分治法を使っていますが、分解と組み合わせの過程は
違います.分治法はサブ問題に分解しやすい問題を解決するのに適している.
私たちは分治法の偽コードのフレームワークを与えることができて、ある具体的な問題に対して、適切な修正を行う必要があります.例えば、パラメータの個数など、数学の基礎はあまり牛ではありませんので、私はしていません.
法はこのフレームワークがすべての再帰関数とすべての分治法に基づくアルゴリズムに適用できることを証明したが,私はまだ適用されない状況を発見していない.また,子結節が直接原問題の対象になる場合
行の操作では、子ノードが親ノードに値を返す必要がない場合があります(Noneを返すだけでいいです).親ノードもこれらのノードの戻り値を使用しません.すべてのノードが同じであるためです.
共有リソースです.この点は迅速なソートを参照してください.また、二分検索のように、任意の検索プロセスについては、あるノードからルートノードへの経路を歩いているだけで、
分解するたびに1つのノードにしか使用されず、merge()とは言えません.
次のコードを見て、MapReduceの考えと似ているような気がしますか?はい、MapReduceは実は分治法の考えに基づいています.MapReduceのMap
次のmap()メソッドに対応しますが、Reduceはmerge()メソッドの特例です.merge()は具体的な問題によって決まり、反復関数とは限らないからです.
MapReduceは分割法に基づいているので,適用シーンと分割法適用シーンのみのサブセットである.
二、具体的なアルゴリズム
(1)発泡ソート
これは最も簡単な並べ替え方法であり,遍歴するたびに最大数を探し出し,バブル並べ替えは安定並べ替えであり,時間複雑度はO(n^2)であった.
OK、私たちはまず一回どのようにするかを見て、簡単から複雑まで、このように問題を分解して、実はそんなに難しくないと感じて、これも分治法の思想です.
それからコードを修正して、本当の泡を並べて次のようにします.
(2)クイックソート
クイックソートは実は分治法の思想であり、集計ソートも分治法であり、同じように分治法であるが、策略は異なる.私たちは「分治法」で分治法を3つに分けることに言及した.
サブ問題を分解、解く、組み合わせる.高速ソートと集計ソートの違いは分解に現れ,分解が異なり,後の組合せもしばしば異なる.クイックソート分解時
元のオブジェクト上で直接行われる操作で、操作が完了しても組み合わせは必要ありません.統合の主な仕事は組み合わせの上で、分解したことがあります
プロセスは非常に簡単で、集計のプロセスも元のオブジェクト(元のシーケンス)上で完全に行うことができます.
1回の分割をすばやくソートすると、シーケンス内の要素(任意に1つを選択すればよい)の位置が決定され、シーケンスはその要素を境界として2つの部分に分けられ、一部は等しい
この要素は、他の部分がその要素に等しいよりも小さく、その後、この2つの部分を再帰的に分解します(位置を決定した要素は、分割するまでソートする必要はありません).
の部分は要素が1つしかないか、空です.再帰はツリーの分解過程であり,サブノードは元の問題オブジェクト(元のシーケンス)を直接操作することができ,操作が完了すると元のシーケンスのいずれかに相当する.
部分は秩序正しくなった.このようなノードは、親ノードに値を返す必要はありません.次はクイックソートコードで、1つ目は分治法のフレームワークを使わず、2つ目は使いました.子結点と葉
ノードは実際には戻り値を使う必要はありませんが、分治法のフレームワークで理解するためには、戻り値を返させたほうがいいです.
分治法フレームワークを用いると,使用しないコードに比べてわずかな再構成にすぎない.
(3)二分検索
二分検索の条件は、シーケンスが秩序化されている必要があります.次に、小さいシーケンスから大きいシーケンスがソートされていると仮定し、検索に成功した場合は下付きを返し、失敗した場合はNoneを返します.両方の方法のコードはテストに合格しました.
方法1:再帰の使用
方法2:ループの使用
次はループメソッドを使用してテストします.
それらは一般的に具体的なアルゴリズムに基づいて総括し、抽出し、分析し、逆に他の問題の解決を指導するために用いられる.それらはある種類の問題の解決に適用され、弁解する.
証法の観点から見ると、抽象的なアルゴリズムと具体的なアルゴリズムは抽象と具体、普遍性と特殊性、共通性と個性の関係である.馬は白馬の抽象で、白馬であれ赤であれ
馬は、すべて馬で、私たちは馬の唯一の本質的な属性--染色体で動物が馬かどうかを決定して、この本質的な属性は馬の抽象です.
(1)分治法
分治法の基本思想はまず原問題を分割して、原問題を1つ以上の簡単なサブ問題に分割して、これらのサブ問題の解は一定の組み合わせを経て原問題の解を得て、求めます
これらのサブ問題を解くと,しばしば再分解,組合せ,すなわち上の過程を反復する.さらにまとめると,分治法の手順が得られる:サブ問題の分解,解,組合せ.に着く
どのように分解して、組み合わせて、分治法は抽象的に法則を出すことができません.自分がやりたいことはどうすればいいのか、例えば集計ソートやクイックソートは、分治法を使っていますが、分解と組み合わせの過程は
違います.分治法はサブ問題に分解しやすい問題を解決するのに適している.
私たちは分治法の偽コードのフレームワークを与えることができて、ある具体的な問題に対して、適切な修正を行う必要があります.例えば、パラメータの個数など、数学の基礎はあまり牛ではありませんので、私はしていません.
法はこのフレームワークがすべての再帰関数とすべての分治法に基づくアルゴリズムに適用できることを証明したが,私はまだ適用されない状況を発見していない.また,子結節が直接原問題の対象になる場合
行の操作では、子ノードが親ノードに値を返す必要がない場合があります(Noneを返すだけでいいです).親ノードもこれらのノードの戻り値を使用しません.すべてのノードが同じであるためです.
共有リソースです.この点は迅速なソートを参照してください.また、二分検索のように、任意の検索プロセスについては、あるノードからルートノードへの経路を歩いているだけで、
分解するたびに1つのノードにしか使用されず、merge()とは言えません.
次のコードを見て、MapReduceの考えと似ているような気がしますか?はい、MapReduceは実は分治法の考えに基づいています.MapReduceのMap
次のmap()メソッドに対応しますが、Reduceはmerge()メソッドの特例です.merge()は具体的な問題によって決まり、反復関数とは限らないからです.
MapReduceは分割法に基づいているので,適用シーンと分割法適用シーンのみのサブセットである.
def handler(obj): end_ret = is_end(obj) if end_ret[0]== True: # return end_ret[1]
else: # ， subnode_tuple = separate(obj) # ， subnode_rettuple = map(handler, subnode_tuple) # ， node_ret = merge(subnode_rettuple,obj) # ， return node_ret 二、具体的なアルゴリズム
(1)発泡ソート
これは最も簡単な並べ替え方法であり,遍歴するたびに最大数を探し出し,バブル並べ替えは安定並べ替えであり,時間複雑度はO(n^2)であった.
OK、私たちはまず一回どのようにするかを見て、簡単から複雑まで、このように問題を分解して、実はそんなに難しくないと感じて、これも分治法の思想です.
#
def bubble_sort(s):
i = 0
for index in range(i,len(s)):
if s[index] > s[i]:
s[i],s[index] = s[index],s[i]
return s それからコードを修正して、本当の泡を並べて次のようにします.
#
def func(s):
length = len(s)
for i in range(length):
for index in range(i,length):
if s[index] > s[i]:
s[i],s[index] = s[index],s[i]
return s(2)クイックソート
クイックソートは実は分治法の思想であり、集計ソートも分治法であり、同じように分治法であるが、策略は異なる.私たちは「分治法」で分治法を3つに分けることに言及した.
サブ問題を分解、解く、組み合わせる.高速ソートと集計ソートの違いは分解に現れ,分解が異なり,後の組合せもしばしば異なる.クイックソート分解時
元のオブジェクト上で直接行われる操作で、操作が完了しても組み合わせは必要ありません.統合の主な仕事は組み合わせの上で、分解したことがあります
プロセスは非常に簡単で、集計のプロセスも元のオブジェクト(元のシーケンス)上で完全に行うことができます.
1回の分割をすばやくソートすると、シーケンス内の要素(任意に1つを選択すればよい)の位置が決定され、シーケンスはその要素を境界として2つの部分に分けられ、一部は等しい
この要素は、他の部分がその要素に等しいよりも小さく、その後、この2つの部分を再帰的に分解します(位置を決定した要素は、分割するまでソートする必要はありません).
の部分は要素が1つしかないか、空です.再帰はツリーの分解過程であり,サブノードは元の問題オブジェクト(元のシーケンス)を直接操作することができ,操作が完了すると元のシーケンスのいずれかに相当する.
部分は秩序正しくなった.このようなノードは、親ノードに値を返す必要はありません.次はクイックソートコードで、1つ目は分治法のフレームワークを使わず、2つ目は使いました.子結点と葉
ノードは実際には戻り値を使う必要はありませんが、分治法のフレームワークで理解するためには、戻り値を返させたほうがいいです.
#-*- coding=utf-8 -*- def qsort(s,start_index,end_index): if start_index>=end_index: if start_index == end_index:
return [s[start_index]]
else:
return []
else: i = separate(s,start_index,end_index) # i ， left_ret = qsort(s,start_index,i-1) right_ret = qsort(s,i+1,end_index) node_ret = left_ret + [s[i]] + right_ret
return node_ret
# ， start_index ， def separate(s,start_index,end_index): key = s[start_index] empty_index = start_index # track_index = end_index # while empty_index != track_index: if track_index > empty_index: if s[track_index] < key: s[empty_index] = s[track_index] track_index,empty_index = empty_index,track_index track_index +=1
else: track_index -=1
else: if s[track_index] > key: s[empty_index] = s[track_index] track_index,empty_index = empty_index,track_index track_index -=1
else: track_index +=1 s[empty_index] = key return empty_index a = [12,3,9,10,87,25,8,9,47,11,1,100,85,47,59,81,60,33] b = qsort(a,0,len(a)-1) print a print b分治法フレームワークを用いると,使用しないコードに比べてわずかな再構成にすぎない.
# -*- coding=utf-8 -*-
def qsort(obj): s = obj[0] start_index = obj[1] end_index = obj[2] end_ret = is_end(obj) if end_ret[0]== True: return end_ret[1] else: i = separate(obj) # i ，
subnode1 = (s,start_index,i-1)
subnode2 = (s,i+1,end_index)
subnode_tuple = (subnode1,subnode2) subnode_rettuple = map(qsort,subnode_tuple) node_ret = merge(subnode_rettuple,obj[0][i]) return node_ret def is_end(obj):
s = obj[0]
start_index = obj[1]
end_index = obj[2] if start_index>=end_index: if start_index == end_index: return (True,[s[start_index]]) else: return (True,[]) else: return (False,None) # ， start_index ，
def separate(obj): s = obj[0] start_index = obj[1] end_index = obj[2] key = s[start_index] empty_index = start_index #
track_index = end_index #
while empty_index != track_index: if track_index > empty_index: if s[track_index] < key: s[empty_index] = s[track_index] track_index,empty_index = empty_index,track_index track_index +=1
else: track_index -=1
else: if s[track_index] > key: s[empty_index] = s[track_index] track_index,empty_index = empty_index,track_index track_index -=1
else: track_index +=1 s[empty_index] = key return empty_index def merge(subnode_rettuple,obj): return subnode_rettuple[0] + [obj] + subnode_rettuple[1] a = [12,3,9,10,87,25,8,9,47,11,1,100,85,47,59,81,60,33]
obj = (a,0,len(a)-1) b = qsort(obj) print a print b(3)二分検索
二分検索の条件は、シーケンスが秩序化されている必要があります.次に、小さいシーケンスから大きいシーケンスがソートされていると仮定し、検索に成功した場合は下付きを返し、失敗した場合はNoneを返します.両方の方法のコードはテストに合格しました.
方法1:再帰の使用
# ， s， s ，
def binary_search(s,start_index,end_index,key):
if start_index <= end_index:
mid_index = (start_index + end_index)/2
if key == s[mid_index]:
return mid_index
elif key > s[mid_index]:
return func(s,mid_index+1,end_index,key)
else:
return func(s,start_index,mid_index-1,key)
else:
return None方法2:ループの使用
# ，
def binary_search(s,start_index,end_index,key):
while start_index <= end_index:
mid_index = (start_index + end_index)/2
if key == s[mid_index]:
return mid_index
elif key > s[mid_index]:
start_index = mid_index + 1
else:
end_index = mid_index - 1
return None次はループメソッドを使用してテストします.
>>> a = [2,8,20,77,190,490]
>>> binary_search(a,0,len(a)-1,1)
>>> binary_search(a,0,len(a)-1,300)
>>> binary_search(a,0,len(a)-1,490)
5
>>> binary_search(a,0,len(a)-1,77)
3
>>>