wk14_1207_演算法_排序與搜尋

ch08_演算法_排序與搜尋

• 8.3 搜尋

  ​​​​​​循序搜尋
  ​​​​​​二分搜尋
  

【inclass practice】

#2.追蹤泡沫排序法的過程 <bubble_debuge>
def disp_data(): # 顯示串列的自訂程序
    for item in datas:
        print(item,end=" ")
    print()        

#主程式
datas=[3,5,2,1]  
print("排序前：",end=" ")
disp_data() # 顯示排序前串列
n=len(datas)-1 # 串列長度-1

for i in range(0,n): 
    for j in range(0,n-i):      
        print("i=%d j=%d" %(i,j))
        if (datas[j]>datas[j+1]): # 由大到小排序
            print("%d,%d 互換後" %(datas[j],datas[j+1]) ,end="：")
            datas[j],datas[j+1]=datas[j+1],datas[j] # 兩數互換
        print(datas)

print("排序後：",end=" ")  
disp_data()  # 顯示排序後串列 

​​​​排序前： 3 5 2 1 
​​​​i=0 j=0
​​​​[3, 5, 2, 1]
​​​​i=0 j=1
​​​​5,2 互換後：[3, 2, 5, 1]
​​​​i=0 j=2
​​​​5,1 互換後：[3, 2, 1, 5]
​​​​i=1 j=0
​​​​3,2 互換後：[2, 3, 1, 5]
​​​​i=1 j=1
​​​​3,1 互換後：[2, 1, 3, 5]
​​​​i=2 j=0
​​​​2,1 互換後：[1, 2, 3, 5]
​​​​排序後： 1 2 3 5 

{綜合演練}

• 實作2 :

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

• 實作3:

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

num=[256,731,943,389,142,645,829,945]
name=["林小虎","王中森","邵木淼","李大同","陳子孔","鄭美麗","曾溫柔","錢來多","賈天良","吳水品"] 

n=len(num)-1 # 串列長度-1
IsFound=False
min=0
max=n
c=0 #計算比對次數 

for i in range(0,n): 
    for j in range(0,n-i):         
        if (num[j]>num[j+1]): # 由小到大排序
            num[j],num[j+1]=num[j+1],num[j]     # 兩數互換
            name[j],name[j+1]=name[j+1],name[j] # 姓名互換
 
no = int(input("請輸入中獎者的編號："))

while(min<=max):
    mid=int((min+max)/2)
    c+=1  #比對次數加 1
    if (num[mid]==no):  #號碼相符 
        IsFound=True
        break

    if (num[mid]>no):  #如果中間值大於輸入值 
       max=mid-1      #使用較小的一半區域繼續比對 
    else:             #如果中間值不大於輸入值 
       min=mid+1      #使用較大的一半區域繼續比對 
       
if (IsFound==True):
    print("中獎者的姓名為：",name[mid])
else:
    print("無此中獎號碼！")
print("共比對 ", c ," 次")   

​​​​請輸入中獎者的編號：731
​​​​中獎者的姓名為： 王中森
​​​​共比對  3  次

#3.中獎者姓名(循序搜尋) <sequential>
num=[256,731,943,389,142,645,829,945]
name=["林小虎","王中森","邵木淼","李大同","陳子孔","鄭美麗","曾溫柔","錢來多"]
no = int(input("請輸入中獎者的編號："))
 
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)) 

​​​​請輸入中獎者的編號：444
​​​​無此中獎號碼！
​​​​共比對 8次 

期末專題參考

• {實戰#4} :

名詞解釋 : 排序、搜尋

! pip install wikipedia

​​​​Collecting wikipedia
​​​​  Downloading wikipedia-1.4.0.tar.gz (27 kB)
​​​​  Preparing metadata (setup.py): started
​​​​  Preparing metadata (setup.py): finished with status 'done'
​​​​Requirement already satisfied: beautifulsoup4 in c:\users\cjc11\anaconda3\lib\site-packages (from wikipedia) (4.12.2)
​​​​Requirement already satisfied: requests<3.0.0,>=2.0.0 in c:\users\cjc11\anaconda3\lib\site-packages (from wikipedia) (2.31.0)
​​​​Requirement already satisfied: charset-normalizer<4,>=2 in c:\users\cjc11\anaconda3\lib\site-packages (from requests<3.0.0,>=2.0.0->wikipedia) (2.0.4)
​​​​Requirement already satisfied: idna<4,>=2.5 in c:\users\cjc11\anaconda3\lib\site-packages (from requests<3.0.0,>=2.0.0->wikipedia) (3.4)
​​​​Requirement already satisfied: urllib3<3,>=1.21.1 in c:\users\cjc11\anaconda3\lib\site-packages (from requests<3.0.0,>=2.0.0->wikipedia) (1.26.16)
​​​​Requirement already satisfied: certifi>=2017.4.17 in c:\users\cjc11\anaconda3\lib\site-packages (from requests<3.0.0,>=2.0.0->wikipedia) (2023.7.22)
​​​​Requirement already satisfied: soupsieve>1.2 in c:\users\cjc11\anaconda3\lib\site-packages (from beautifulsoup4->wikipedia) (2.4)
​​​​Building wheels for collected packages: wikipedia
​​​​  Building wheel for wikipedia (setup.py): started
​​​​  Building wheel for wikipedia (setup.py): finished with status 'done'
​​​​  Created wheel for wikipedia: filename=wikipedia-1.4.0-py3-none-any.whl size=11707 sha256=e37be62aa59d52851f55989ebf76d6e31b555a4effc93d7ab6dcd5088ccea967
​​​​  Stored in directory: c:\users\cjc11\appdata\local\pip\cache\wheels\8f\ab\cb\45ccc40522d3a1c41e1d2ad53b8f33a62f394011ec38cd71c6
​​​​Successfully built wikipedia
​​​​Installing collected packages: wikipedia
​​​​Successfully installed wikipedia-1.4.0

import wikipedia as wiki

wiki.set_lang("zh")

searchtarget = input('請輸入要搜尋的項目: ')

searchResult = wiki.search(searchtarget)
print(f'搜尋結果 => {searchResult}')

​​​​請輸入要搜尋的項目: helloworld
​​​​搜尋結果 => ['Hello World', '基於原則設計', 'Java本地接口', 'Java applet', 'Object Pascal', 'Apache Ant', 'Scala', 'OTcl', 'Hello World程序样例', 'JUnit']

que = ''
for i in range(len(searchResult)):
    que += f'{i} - {searchResult[i]}\n'
    
index = int(input(f'{que}請選擇想要的結果'))
target =searchResult[index]

summary = wiki.summary(target)
print(f'[{target}]摘要 => {summary}')

​​​​0 - Hello World
​​​​1 - 基於原則設計
​​​​2 - Java本地接口
​​​​3 - Java applet
​​​​4 - Object Pascal
​​​​5 - Apache Ant
​​​​6 - Scala
​​​​7 - OTcl
​​​​8 - Hello World程序样例
​​​​9 - JUnit
​​​​請選擇想要的結果0
​​​​[Hello World]摘要 => “Hello, World!”程序通常指一类输出或顯示「Hello, World!」（你好，世界！）字串的電腦程式。在大多数通用编程语言中，这样的程序只有一小段代码，因此可以用来展示该编程语言的基本语法。“Hello, World!”往往是初学者学习某种编程语言所接触的第一个程序内容，同時它也是用來確認源代码編譯器、程序開發或运行环境是否已經安裝妥當并被操作者理解的常用手段。

【selfpractice】

names=["Charlie","Charles","Martin","Ray"]
n=len(names)-1 
for i in range(0,n): 
    for j in range(0,n-i):         
        if (names[j]>names[j+1]): 
            names[j],names[j+1]=names[j+1],names[j]   
                
while True:     
    name = input("請輸入中獎者的名單(Enter結束)：")
    if (name==""):
        break    

    IsFound=False
    min=0
    max=n    
    while(min<=max):
        mid=int((min+max)/2)
        if (names[mid].upper()==name.upper()):  #姓名相符 
            IsFound=True
            break
        if (names[mid].upper()>name.upper()): #如果中間值大於輸入值 
           max=mid-1      #使用較小的一半區域繼續比對 
        else:             #如果中間值不大於輸入值 
           min=mid+1      #使用較大的一半區域繼續比對 
           
    if (IsFound==True):
        print("恭喜您，",name,"中獎了!")
    else:
        print("可惜，",name,"未中獎！")   

​​​​請輸入中獎者的名單(Enter結束)：Ray
​​​​恭喜您， Ray 中獎了!
​​​​請輸入中獎者的名單(Enter結束)：