初中九年級(jí)信息技術(shù)找出那枚假幣分治算法

找出那枚假幣-分治算法校門口的小賣部是很多同學(xué)下課常去的地方，在那里可以買到同學(xué)們喜歡的零食，但是一些粗心的同學(xué)會(huì)不小心把游戲幣當(dāng)成硬幣用來買東西。假設(shè)游戲幣和真幣外觀上沒有區(qū)別，只是稍微輕一點(diǎn)，小賣部的老板每天清理硬幣時(shí)，總希望可以更迅速地找出這些假幣（游戲幣）。某一天，老板收到了16枚硬幣，其中有一枚假幣，老板希望用一臺(tái)天平來幫助找出假幣，如何迅速找出這枚假幣？試一試假設(shè)真幣重量為5g，假幣重量為3g，現(xiàn)在用一個(gè)list來模擬一組存在一枚假幣的硬幣組：coin[5，5，5，5，5，5，3，5，5，5，5，5，5，5，5，5]因?yàn)槲覀冎挥幸慌_(tái)天平，通過枚舉的方式，我們可以每次選取一枚硬幣放在天平的一端，然后依次選取一枚硬幣放在天平的另一端，如果在某次對(duì)比中發(fā)現(xiàn)其中一枚硬幣較輕，這枚就是假幣。在之前窮舉法的學(xué)習(xí)過程中，我們學(xué)習(xí)過如何在數(shù)組中查找一個(gè)數(shù)據(jù)。請(qǐng)嘗試寫一個(gè)Python程序，模擬用順序查找的方式找出假幣的過程，程序輸出假幣的位置，對(duì)于以上硬幣組，正確輸出為6。學(xué)一學(xué)現(xiàn)在，我們用另一種方式來尋找假幣。把硬幣分為兩組，每組8枚硬幣，將兩組硬幣放在天平上對(duì)比，如果重量相等，則不存在假幣，如果一組較輕，則存在假幣，且假幣在較輕的這組中。用這種方式，一次即可找出是否存在假幣。如果將硬幣分為8組，每組2枚，則最多經(jīng)過8次對(duì)比，即可找出16枚硬幣中是否存在假幣，且能夠找出假幣的位置。以下程序?qū)⒂矌欧譃?組，第i枚硬幣和第8+i枚硬幣為一組：這種將問題分而治之的方法，我們稱為分治算法，它是指將較大規(guī)模的問題分解成幾個(gè)較小規(guī)模的問題，通過對(duì)較小問題的求解達(dá)到對(duì)整個(gè)問題的求解的方法。分治的基本思想，是將一個(gè)規(guī)模為n的問題分解為k個(gè)規(guī)模較小的子問題，這些子問題互相獨(dú)立，且與原問題相似。找出各個(gè)子問題的解，然后把各個(gè)子問題的解組合成整個(gè)問題的解。做一做以下程序段，模擬在硬幣組中插入一枚假幣，輸入數(shù)據(jù)為插入假幣的位置，在自己的程序中加入以下程序段，試試輸出結(jié)果和輸入位置是否一致。分治法的一般解題步驟：先分解問題，然后逐個(gè)解決，最后合并得解。比如有種排序的方法叫快速排序，它在對(duì)一個(gè)序列進(jìn)行排序的時(shí)候，先按某個(gè)元素的值將問題進(jìn)行分解，把比這個(gè)元素小的數(shù)全部挪到這個(gè)元素的左邊，比這個(gè)元素大的全部挪到這個(gè)元素的右邊，那么左邊和右邊就成了完全獨(dú)立的兩個(gè)子問題，然后遞歸繼續(xù)分解問題，直到只有1~2個(gè)數(shù)字的時(shí)候直接比較排序，最后的序列自然由小到大排好了。16枚硬幣中存在一枚假幣的假幣問題，可以采用二分的方式來解，定義函數(shù)weight（m，n），表示將從第m枚硬幣到第n枚硬幣組成的硬幣組，每次從中間劃分為數(shù)相同的兩組，用天平進(jìn)行重量對(duì)比，編寫程序如下：運(yùn)行以上程序，嘗試改變假幣的位置，觀察程序輸出結(jié)果。練一練對(duì)于16枚硬幣中存在一枚假幣的假幣問題，通過對(duì)比，嘗試分析不同算法的效率：你還有沒有更好的做法？

問題方法判斷是否存在假幣找出假幣位置最少查找次數(shù)最多查找次數(shù)平均查找次數(shù)最少查找次數(shù)最多查找次數(shù)平均查找次數(shù)順序查找分成8組每次分為2組探一探1.在很多人中找出身高最高的那位同學(xué)，可以將大家分成10個(gè)小組，每個(gè)小組找出最高的同學(xué)，然后這10位同學(xué)再進(jìn)行最后一次比較，請(qǐng)寫出這樣的Python程序。其實(shí)很多的體育賽事，小組賽就是這樣分治進(jìn)行的。2.在n個(gè)數(shù)的無序的表中找到一個(gè)數(shù)字可能需要n次比較。但是在一個(gè)有序的表中，比較的次數(shù)會(huì)少得多，假設(shè)是由小到大排列的有序表a[1。。10]中找X，先比較a[5]與X的