當前位置:首頁 » 操作系統 » 演算法實例講解

演算法實例講解

發布時間: 2022-08-10 12:53:52

python實現的快速排序演算法詳解

Python實現的快速排序演算法詳解
本文實例講述了Python實現的快速排序演算法。分享給大家供大家參考,具體如下:
快速排序基本思想是:通過一趟排序將要排序的數據分割成獨立的兩部分,其中一部分的所有數據都比另外一部分的所有數據都要小,然後再按此方法對這兩部分數據分別進行快速排序,整個排序過程可以遞歸進行,以此達到整個數據變成有序序列。
如序列[6,8,1,4,3,9],選擇6作為基準數。從右向左掃描,尋找比基準數小的數字為3,交換6和3的位置,[3,8,1,4,6,9],接著從左向右掃描,尋找比基準數大的數字為8,交換6和8的位置,[3,6,1,4,8,9]。重復上述過程,直到基準數左邊的數字都比其小,右邊的數字都比其大。然後分別對基準數左邊和右邊的序列遞歸進行上述方法。
實現代碼如下:
def parttion(v, left, right):
key = v[left]
low = left
high = right
while low < high:
while (low < high) and (v[high] >= key):
high -= 1
v[low] = v[high]
while (low < high) and (v[low] <= key):
low += 1
v[high] = v[low]
v[low] = key
return low
def quicksort(v, left, right):
if left < right:
p = parttion(v, left, right)
quicksort(v, left, p-1)
quicksort(v, p+1, right)
return v
s = [6, 8, 1, 4, 3, 9, 5, 4, 11, 2, 2, 15, 6]
print("before sort:",s)
s1 = quicksort(s, left = 0, right = len(s) - 1)
print("after sort:",s1)
運行結果:
before sort: [6, 8, 1, 4, 3, 9, 5, 4, 11, 2, 2, 15, 6]
after sort: [1, 2, 2, 3, 4, 4, 5, 6, 6, 8, 9, 11, 15]

② 什麼是演算法試從日常生活中找3個例子,描述它們的演算法

演算法就是解決問題的方法比如你要喝茶就要先找到茶葉,燒一壺開水,然後將茶葉放到杯子里,然後將開水倒入杯中,然後等一段時間再比如你要從a地到b地,中間可能有多種汽車換乘方案,是選速度最快的,還是選最省錢的,還是平衡的,制定換乘方案就是演算法。

③ Python冒泡排序注意要點實例詳解

Python冒泡排序注意要點實例詳解
文給大家介紹了python冒泡排序知識,涉及到冒泡排序主要的細節問題,本文通過實例代碼給大家講解,介紹的非常詳細,具有參考借鑒價值,感興趣的朋友一起看看吧
冒泡排序注意三點:
1. 第一層循環可不用循環所有元素。
2.兩層循環變數與第一層的循環變數相關聯。
3.第二層循環,最終必須循環集合內所有元素。
示例代碼一:
1.第一層循環,只循環n-1個元素。
2.當第一層循環變數為n-1時,第二層循環所有元素。
s = [3, 4, 1, 6, 2, 9, 7, 0, 8, 5]
# bubble_sort
for i in range(0, len(s) - 1):
for j in range(i + 1, 0, -1):
if s[j] < s[j - 1]:
s[j], s[j - 1] = s[j - 1], s[j]
for m in range(0, len(s)):
print(s[m])
示例代碼二:
1.第一層循環所有元素。
2.第二層也循環所有元素。
s = [3, 4, 1, 6, 2, 9, 7, 0, 8, 5]
for i in range(0, len(s)):
for j in range(i, 0, -1):
if s[j] < s[j - 1]:
s[j], s[j - 1] = s[j - 1], s[j]
for m in range(0, len(s)):
print(s[m])
以上所述是小編給大家介紹的python冒泡排序演算法注意要點,希望對大家有所幫助

c語言問題: 什麼是演算法試從日常生活中找3個例子,描述它們的演算法。 詳細點,謝謝!

c語言中的演算法是指:一系列解決問題的清晰指令,用系統的方法描述解決問題的策略機制。也就是說,能夠對一定規范的輸入,在有限時間內獲得所要求的輸出。通俗說就是解決問題的方法和步驟。

描述演算法的例子:

  1. 問題:從上海去到北京。

    其中的演算法:做汽車、做飛機、或者徒步。

  2. 問題:喝茶。

    其中的演算法:先找到茶葉,再燒一壺開水,然後將茶葉放到杯子里,將開水倒入杯中,等茶葉泡好。

  3. 問題:開車。

    其中的演算法:首先要打開車門,駕駛員坐好,插上車鑰匙,發動汽車。

⑤ 演算法時間復雜度的計算例題

第一題:
int i=1,k=100這條語句演算法步數是2步,執行頻率是1;
循環中, k=k+1;這條語句每次演算法步數是1;執行頻率是n/2-1; i+=2這條語句每次演算法步數是1;執行頻率是n/2-1;
所以演算法復雜度為1*(n/2-1)+1*(n/2-1)+2=n=o(n);

⑥ c語言中什麼是演算法有哪些描述演算法的例子

1、有窮性(有限性)。任何一種提出的解題方法都是在有限的操作步驟內可以完成的。
如果在有限的操作步驟內完不成,得不到結果,這樣的演算法將無限的執行下去,永遠不會停止。除非手動停止。例如操作系統就不具有有窮性,它可以一直運行。
2、一個演算法應該具有以下七個重要的特徵:
1)有窮性(finiteness)
演算法的有窮性是指演算法必須能在執行有限個步驟之後終止
2)確切性(definiteness)
演算法的每一步驟必須有確切的定義;
3)輸入項(input)
一個演算法有0個或多個輸入,以刻畫運算對象的初始情況,所謂0個輸入是指演算法本身定出了初始條件;
4)輸出項(output)
一個演算法有一個或多個輸出,以反映對輸入數據加工後的結果.沒有輸出的演算法是毫無意義的;
5)可行性(effectiveness)
演算法中執行的任何計算步都是可以被分解為基本的可執行的操作步,即每個計算步都可以在有限時間內完成;
6)
高效性(high
efficiency)
執行速度快,佔用資源少;
7)
健壯性(robustness)
健壯性又稱魯棒性,是指軟體對於規范要求以外的輸入情況的處理能力。所謂健壯的系統是指對於規范要求以外的輸入能夠判斷出這個輸入不符合規范要求,並能有合理的處理方式。

php幾種排序演算法實例詳解

下面給你介紹四種排序方法:

1) 插入排序(Insertion Sort)的基本思想是:
每次將一個待排序的記錄,按其關鍵字大小插入到前面已經排好序的子文件中的適當位置,直到全部記錄插入完成為止。實現代碼如下:

⑧ 分治演算法的應用實例

下面通過實例加以說明: 給你一個裝有1 6個硬幣的袋子。1 6個硬幣中有一個是偽造的,並且那個偽造的硬幣比真的硬幣要輕一些。你的任務是找出這個偽造的硬幣。為了幫助你完成這一任務,將提供一台可用來比較兩組硬幣重量的儀器,利用這台儀器,可以知道兩組硬幣的重量是否相同。比較硬幣1與硬幣2的重量。假如硬幣1比硬幣2輕,則硬幣1是偽造的;假如硬幣2比硬幣1輕,則硬幣2是偽造的。這樣就完成了任務。假如兩硬幣重量相等,則比較硬幣3和硬幣4。同樣,假如有一個硬幣輕一些,則尋找偽幣的任務完成。假如兩硬幣重量相等,則繼續比較硬幣5和硬幣6。按照這種方式,可以最多通過8次比較來判斷偽幣的存在並找出這一偽幣。
另外一種方法就是利用分而治之方法。假如把1 6硬幣的例子看成一個大的問題。第一步,把這一問題分成兩個小問題。隨機選擇8個硬幣作為第一組稱為A組,剩下的8個硬幣作為第二組稱為B組。這樣,就把1 6個硬幣的問題分成兩個8硬幣的問題來解決。第二步,判斷A和B組中是否有偽幣。可以利用儀器來比較A組硬幣和B組硬幣的重量。假如兩組硬幣重量相等,則可以判斷偽幣不存在。假如兩組硬幣重量不相等,則存在偽幣,並且可以判斷它位於較輕的那一組硬幣中。最後,在第三步中,用第二步的結果得出原先1 6個硬幣問題的答案。若僅僅判斷硬幣是否存在,則第三步非常簡單。無論A組還是B組中有偽幣,都可以推斷這1 6個硬幣中存在偽幣。因此,僅僅通過一次重量的比較,就可以判斷偽幣是否存在。
假設需要識別出這一偽幣。把兩個或三個硬幣的情況作為不可再分的小問題。注意如果只有一個硬幣,那麼不能判斷出它是否就是偽幣。在一個小問題中,通過將一個硬幣分別與其他兩個硬幣比較,最多比較兩次就可以找到偽幣。這樣,1 6硬幣的問題就被分為兩個8硬幣(A組和B組)的問題。通過比較這兩組硬幣的重量,可以判斷偽幣是否存在。如果沒有偽幣,則演算法終止。否則,繼續劃分這兩組硬幣來尋找偽幣。假設B是輕的那一組,因此再把它分成兩組,每組有4個硬幣。稱其中一組為B1,另一組為B2。比較這兩組,肯定有一組輕一些。如果B1輕,則偽幣在B1中,再將B1又分成兩組,每組有兩個硬幣,稱其中一組為B1a,另一組為B1b。比較這兩組,可以得到一個較輕的組。由於這個組只有兩個硬幣,因此不必再細分。比較組中兩個硬幣的重量,可以立即知道哪一個硬幣輕一些。較輕的硬幣就是所要找的偽幣。 在n個元素中找出最大元素和最小元素。我們可以把這n個元素放在一個數組中,用直接比較法求出。演算法如下:
void maxmin1(int A[],int n,int *max,int *min)
{ int i;
*min=*max=A[0];
for(i=0;i <= n;i++)
{ if(A[i]> *max) *max= A[i];
if(A[i] < *min) *min= A[i];
}
}
上面這個演算法需比較2(n-1)次。能否找到更好的演算法呢?我們用分治策略來討論。
把n個元素分成兩組:
A1={A[1],...,A[int(n/2)]}和A2={A[INT(N/2)+1],...,A[N]}
分別求這兩組的最大值和最小值,然後分別將這兩組的最大值和最小值相比較,求出全部元素的最大值和最小值。如果A1和A2中的元素多於兩個,則再用上述方法各分為兩個子集。直至子集中元素至多兩個元素為止。
例如有下面一組元素:-13,13,9,-5,7,23,0,15。用分治策略比較的演算法如下:
void maxmin2(int A[],int i,int j,int *max,int *min)
/*A存放輸入的數據,i,j存放數據的范圍,初值為0,n-1,*max,*min 存放最大和最小值*/
{ int mid,max1,max2,min1,min2;
if (j==i) {最大和最小值為同一個數;return;}
if (j-1==i) {將兩個數直接比較,求得最大會最小值;return;}
mid=(i+j)/2;
求i~mid之間的最大最小值分別為max1,min1;
求mid+1~j之間的最大最小值分別為max2,min2;
比較max1和max2,大的就是最大值;
比較min1和min2,小的就是最小值;
} 題目:在一個(2^k)*(2^k)個方格組成的棋盤上,有一個特殊方格與其他方格不同,稱為特殊方格,稱這樣的棋盤為一個特殊棋盤。我們要求對棋盤的其餘部分用L型方塊填滿(註:L型方塊由3個單元格組成。即圍棋中比較忌諱的愚形三角,方向隨意),且任何兩個L型方塊不能重疊覆蓋。L型方塊的形態如下:
題目的解法使用分治法,即子問題和整體問題具有相同的形式。我們對棋盤做一個分割,切割一次後的棋盤如圖1所示,我們可以看到棋盤被切成4個一樣大小的子棋盤,特殊方塊必定位於四個子棋盤中的一個。假設如圖1所示,特殊方格位於右上角,我們把一個L型方塊(灰色填充)放到圖中位置。這樣對於每個子棋盤又各有一個「特殊方塊」,我們對每個子棋盤繼續這樣分割,直到子棋盤的大小為1為止。
用到的L型方塊需要(4^k-1)/3 個,演算法的時間是O(4^k),是漸進最優解法。
本題目的C語言的完整代碼如下(TC2.0下調試),運行時,先輸入k的大小,(1<=k<=6),然後分別輸入特殊方格所在的位置(x,y), 0<=x,y<=(2^k-1)。 #include<stdio.h>//#include<conio.h>//#include<math.h>inttitle=1;intboard[64][64];voidchessBoard(inttr,inttc,intdr,intdc,intsize){ints,t;if(size==1)return;t=title++;s=size/2;if(dr<tr+s&&dc<tc+s)chessBoard(tr,tc,dr,dc,s);else{board[tr+s-1][tc+s-1]=t;chessBoard(tr,tc,tr+s-1,tc+s-1,s);}if(dr<tr+s&&dc>=tc+s)chessBoard(tr,tc+s,dr,dc,s);else{board[tr+s-1][tc+s]=t;chessBoard(tr,tc+s,tr+s-1,tc+s,s);}if(dr>=tr+s&&dc<tc+s)chessBoard(tr+s,tc,dr,dc,s);else{board[tr+s][tc+s-1]=t;chessBoard(tr+s,tc,tr+s,tc+s-1,s);}if(dr>=tr+s&&dc>=tc+s)chessBoard(tr+s,tc+s,dr,dc,s);else{board[tr+s][tc+s]=t;chessBoard(tr+s,tc+s,tr+s,tc+s,s);}}voidmain(){intdr=0,dc=0,s=1,i=0,j=0;printf(printinthesizeofchess: );scanf(%d,&s);printf(printinspecalpointx,y: );scanf(%d%d,&dr,&dc);if(dr<s&&dc<s){chessBoard(0,0,dr,dc,s);for(i=0;i<s;i++){for(j=0;j<s;j++){printf(%4d,board[i][j]);}printf( );}}elseprintf(thewrongspecalpoint!! );getch();}

⑨ 何為演算法用生活中的實例給予說明

計算方法,生活中的一句名言:走對了,算背了,算對了,走背了,說明:生活中的演算法真多!

熱點內容
怎麼用紙做豌豆解壓玩具 發布:2022-09-29 04:39:17 瀏覽:729
雲存儲播放時間表 發布:2022-09-29 03:58:31 瀏覽:598
新英朗4缸買哪個配置劃算 發布:2022-09-29 03:51:54 瀏覽:121
紅旗5配置怎麼選 發布:2022-09-29 03:44:21 瀏覽:886
linux安裝maven 發布:2022-09-29 03:29:18 瀏覽:595
吉利星瑞豪華天窗版有什麼功能配置 發布:2022-09-29 03:20:28 瀏覽:816
伺服器固定ip和彈性ip一起用 發布:2022-09-29 02:40:49 瀏覽:507
gpioc語言 發布:2022-09-29 02:34:40 瀏覽:951
h乚c語言 發布:2022-09-29 02:34:39 瀏覽:410
迷你世界體驗服正式服密碼是多少 發布:2022-09-29 02:21:19 瀏覽:419