---
# System prepended metadata

title: wk13
tags: [Python]

---

# wk13_ch08_演算法_排序與搜尋 高承紘

 	
    8.1  認識演算法

    8.2  排序

        泡沫排序
        追蹤泡沫排序過程
        
    8.3 搜尋

        循序搜尋
        二分搜尋
        

## 【inclass practice】

### {範例}

    由小排到大排序 \<bubble>
    追蹤泡沫排序法的過程 \<bubble_debuge>
    


```python
def switch(i):
    datas[i],datas[i+1]=datas[i+1],datas[i]

datas=[3,20,10,54,65465,5,52,5,654]

print(f"排序前:{datas}")

n=len(datas)

for i in range(0,n-1):
    for j in range(0,n-i-1):
        print(f"i={i}, j={j}")
        if(datas[j]>datas[j+1]):
            switch(j)
            print(f"{datas[j+1]}, {datas[j]}互換後: {datas}")
            

print(f"排序後:{datas}")
```

    排序前:[3, 20, 10, 54, 65465, 5, 52, 5, 654]
    i=0, j=0
    i=0, j=1
    20, 10互換後: [3, 10, 20, 54, 65465, 5, 52, 5, 654]
    i=0, j=2
    i=0, j=3
    i=0, j=4
    65465, 5互換後: [3, 10, 20, 54, 5, 65465, 52, 5, 654]
    i=0, j=5
    65465, 52互換後: [3, 10, 20, 54, 5, 52, 65465, 5, 654]
    i=0, j=6
    65465, 5互換後: [3, 10, 20, 54, 5, 52, 5, 65465, 654]
    i=0, j=7
    65465, 654互換後: [3, 10, 20, 54, 5, 52, 5, 654, 65465]
    i=1, j=0
    i=1, j=1
    i=1, j=2
    i=1, j=3
    54, 5互換後: [3, 10, 20, 5, 54, 52, 5, 654, 65465]
    i=1, j=4
    54, 52互換後: [3, 10, 20, 5, 52, 54, 5, 654, 65465]
    i=1, j=5
    54, 5互換後: [3, 10, 20, 5, 52, 5, 54, 654, 65465]
    i=1, j=6
    i=2, j=0
    i=2, j=1
    i=2, j=2
    20, 5互換後: [3, 10, 5, 20, 52, 5, 54, 654, 65465]
    i=2, j=3
    i=2, j=4
    52, 5互換後: [3, 10, 5, 20, 5, 52, 54, 654, 65465]
    i=2, j=5
    i=3, j=0
    i=3, j=1
    10, 5互換後: [3, 5, 10, 20, 5, 52, 54, 654, 65465]
    i=3, j=2
    i=3, j=3
    20, 5互換後: [3, 5, 10, 5, 20, 52, 54, 654, 65465]
    i=3, j=4
    i=4, j=0
    i=4, j=1
    i=4, j=2
    10, 5互換後: [3, 5, 5, 10, 20, 52, 54, 654, 65465]
    i=4, j=3
    i=5, j=0
    i=5, j=1
    i=5, j=2
    i=6, j=0
    i=6, j=1
    i=7, j=0
    排序後:[3, 5, 5, 10, 20, 52, 54, 654, 65465]
    


```python
print(datas[0],datas[1])

datas[0],datas[1]=datas[1],datas[0]

print(datas)
```

    3 20
    [20, 3, 10, 5]
    

## 【afterclass practice】

    綜合演練 選擇題1-10  (需抄題在markdown cell ; 有程式碼的題目要有code cell )
    名詞解釋 : 演算法、虛擬碼、流程圖
    

### 實作2 :

    俊民將中獎號碼建立成串列num=[67,12,9,52,91,3]，讓妹妹輸入三個號碼，再以循序搜尋方法檢查這三個號碼種有幾個中獎，並顯示其結果。
    


```python
def jackpot(a,b,c,d):
    if(a==d or b==d or c==d):
        return 1
    else:
        return 0

num=[67,12,9,52,91,3]

a=int(input("輸入第一個號(只可為正整數): "))
b=int(input("輸入第二個號(只可為正整數): "))
c=int(input("輸入第三個號(只可為正整數): "))
d=0
for i in range(0,len(num)):
    d+=jackpot(a,b,c,num[i])
    
print(f"共有{d}個號碼中獎!")
```

    輸入第一個號(只可為正整數): 3
    輸入第二個號(只可為正整數): 91
    輸入第三個號(只可為正整數): 2
    共有2個號碼中獎!
    

### 實作3:

    下列名單為本期大樂透的中獎名單name=['David','Lily','Chiou','Bear','Shantel','Chynthia']，讓使用者輸入一個姓名，輸入的字元大小寫不分，例如輸入 david、David、DAVID都是同一人，請以二分搜尋法檢查該名單是否中獎，並顯示查詢結果。



```python
def f(a):
    if(a<2):
        if(a%1!=0):
            a-=0.5
    if(a%1!=0):
        a+=0.5
    a=int(a)
    return a

def switch(i):
    name[i],name[i+1]=name[i+1],name[i]

name=['David','Lily','Chiou','Bear','Shantel','Chynthia']
for i in range(0,len(name)-1):
    for j in range(0,len(name)-i-1):
        if(len(name[j])>len(name[j+1])):
            switch(j)

a=input("請輸入人名(大小寫都可): ")
b=0

maxi=len(name)-1
mini=0
mid=int((maxi+mini)/2)

while(a.lower()!=name[mid].lower()):
    mid=f((maxi+mini)/2)
    if(len(a)>len(name[mid])):
        mini=mid
    else:
        maxi=mid
    if(maxi==mini):
        if(a.lower()!=name[mini].lower()):
            print("查無此人")
            break
    if(maxi==mini+1):
        b+=1
        if(b==3):
            print("查無此人")
            break
            
if(a.lower()==name[mid].lower()):
    print("恭喜",name[mid],"有中獎!!!")
```

    請輸入人名(大小寫都可): cHynTHia
    恭喜 Chynthia 有中獎!!!
    

( C ) 1. 執行下列程式，下列結果何者正確？

    datas=[3,5,2,1]
    n=len(datas)-1
        for i in range(0,n):
            for j in range(0,n-i):
                if (datas[j]>datas[j+1]):
                datas[j],datas[j+1]=datas[j+1],datas[j]
    print(datas)

    (A) [3,5,2,1] (B) [ 5,3,2,1] (C) [1,2,3,5] (D) [3,5,1,2 ]


```python
datas=[3,5,2,1]
n=len(datas)-1
for i in range(0,n):
    for j in range(0,n-i):
        if (datas[j]>datas[j+1]):
            datas[j],datas[j+1]=datas[j+1],datas[j]
print(datas)
```

    [1, 2, 3, 5]
    

( D ) 2. 執行下列程式，下列顯示結果何者正確？

    num=[67,12,9,52,91,3]
    no=52
    for i in range(len(num)):
        if (num[i]==no):
            break
    print(i)

    (A) 52 (B) i (C) no (D) 3


```python
num=[67,12,9,52,91,3]
no=52
for i in range(len(num)):
    if (num[i]==no):
        break
print(i)
```

    3
    

( B ) 3. 下列那一個排序法，在執行搜尋前必須先將資料排序？

    (A) 循序搜尋法 (B) 二分搜尋法 (C) 泡沫搜尋法 (D) 以上皆是
    
( A ) 4. 有 10000 筆資料時，使用循序搜尋最少需多少次？

    (A) 1 (B) 10000 (C) 15 (D) 14

( B ) 5. 有 10000 筆資料時，使用循序搜尋最多需多少次？

    (A) 1 (B) 10000 (C) 15 (D) 14

( D ) 6. 有 10000 筆資料時，使用二分搜尋最多需多少次？

    (A) 1 (B) 10000 (C) 15 (D) 14

( A ) 7. 下列那一種搜尋方法效率最好？

    (A)二分搜尋 (B)循序搜尋 (C)泡沫搜尋 (D)三者效率相同
    
( D ) 8. 執行下列程式，下列結果何者正確？

    num=[256,731,943,389,142,645,829,945]
    name=["林小虎","王中森","邵木淼","李大同",
    "陳子孔","鄭美麗","曾溫柔","錢來多"]
    no = 100
    IsFound=False
    for i in range(len(name)): #逐一比對搜尋
        if (num[i]==no): #號碼相符
            IsFound=True #設旗標為 True
            break #結束比對
        if (IsFound==True):
            print("中獎者的姓名為：",name[i])
        else:
            print("無此中獎號碼！")
    print("共比對 %d次 " %(i+1))

    (A) no = 256 (B) IsFound=True (C)共比對 9 次 (D)以上皆非


```python
num=[256,731,943,389,142,645,829,945]
name=["林小虎","王中森","邵木淼","李大同",
"陳子孔","鄭美麗","曾溫柔","錢來多"]
no = 100
IsFound=False
for i in range(len(name)): #逐一比對搜尋
    if (num[i]==no): #號碼相符
        IsFound=True #設旗標為 True
        break #結束比對
    if (IsFound==True):
        print("中獎者的姓名為：",name[i])
    else:
        print("無此中獎號碼！")
print("共比對 %d次 " %(i+1))
```

    無此中獎號碼！
    無此中獎號碼！
    無此中獎號碼！
    無此中獎號碼！
    無此中獎號碼！
    無此中獎號碼！
    無此中獎號碼！
    無此中獎號碼！
    共比對 8次 
    

( D ) 9. 同第 8 題，中獎者的姓名為？

    (A)錢來多 (B)曾溫柔 (C)鄭美麗 (D)無此中獎號碼！

( B ) 10. 同第 8 題，這個程式是？

    (A)二分搜尋 (B)循序搜尋 (C)泡沫搜尋 (D)以上皆非
