彈簧秤稱球問(wèn)題算法分析及程序模擬
一、拋出問(wèn)題
一開(kāi)始大家都以為是傳統(tǒng)的無(wú)砝碼天平稱球問(wèn)題，想用分治算法來(lái)解決。在趙軍老師的提示之后，才發(fā)現(xiàn)彈簧秤和無(wú)砝碼天平的區(qū)別：彈簧秤是可以稱量出小球的具體重量的，而且題目要求求出每個(gè)球的具體重量。
朱老師把小球依次編號(hào)1-6，分成3次稱量，第一次將球1,2,3合在一起稱，第二次將球2,3,4,5合在一起稱，第三次將球3,4合在一起稱，可以表示為：3x=123，4y=2345，2z=34。
?一開(kāi)始我沒(méi)怎么看懂，發(fā)現(xiàn)朱老師提供的表達(dá)式中沒(méi)有出現(xiàn)6號(hào)球，心里就產(chǎn)生了疑問(wèn)，萬(wàn)一6號(hào)球是異球呢？不稱量它怎么得出異球的重量？于是隨口說(shuō)了一句：@桐鄉(xiāng)高級(jí)中學(xué)朱海寧?有6個(gè)球哦。
朱老師耐心地回答我：可以推出來(lái)的，比如x=y，那就是6號(hào)球有問(wèn)題，單獨(dú)稱一下就好。
我又繼續(xù)思考了x!=y的情形，發(fā)現(xiàn)可以輕松地推導(dǎo)出異球?yàn)?/span>1和5的情形，即當(dāng)y=z時(shí)，異球?yàn)?/span>1；當(dāng)x=z時(shí)，則異球?yàn)?/span>5。
?
五、程序模擬
事情到這里似乎已經(jīng)結(jié)束了。但只提出算法，不編寫(xiě)程序不是我的風(fēng)格。不把事情完全做好我是不會(huì)罷休的。于是我決定編寫(xiě)程序?qū)崿F(xiàn)算法功能。
這是我的第一版程序：
def fun_1(a):x = sum(a[:3]) # 第一次稱重：3x=123y = sum(a[1:5]) # 第二次稱重：4y=2345if x/3 == y/4: # 前面5個(gè)球等重，則球6為異球z = a[5] # 第三次稱重：稱量異球6print(f"異球?yàn)?，其重量為{z}，其他球重量為{x//3}")else:z = a[2] + a[3] # 第三次稱重：2z=34if y/4 == z/2: # 異球?yàn)?print(f"異球?yàn)?，其重量為{x-z}，其他球重量為{z//2}")elif x/3 == z/2: # 異球?yàn)?print(f"異球?yàn)?，其重量為{y-x}，其他球重量為{z//2}")elif x/3 < y/4 < z/2 or x/3 > y/4 > z/2: # 異球?yàn)?print(f"異球?yàn)?，其重量為{y-3*z//2}，其他球重量為{z//2}")elif z/2 < y/4 < x/3 or z/2 > y/4 > x/3: # 異球?yàn)?print(f"異球?yàn)?，其重量為{z-x//3}，其他球重量為{x//3}")else: # 異球?yàn)?print(f"異球?yàn)?，其重量為{2*z-x}，其他球重量為{x-z}")import randomfor i in range(16):a = [3] * 6 # 初始化每個(gè)小球重量均為3num = random.randint(0, 5) # 選擇任意一個(gè)小球?yàn)楫惽?/span>a[num] = a[num] + random.choice([-1,1]) #異球重量可輕可重print(a)????fun_1(a,?2,?4)
我增加循環(huán)次數(shù)，又測(cè)了好幾次，發(fā)現(xiàn)其他小球?yàn)楫惽驎r(shí)都是對(duì)的，就是4號(hào)球出錯(cuò)。
為什么4號(hào)球總是出錯(cuò)呢？我又看了看測(cè)試結(jié)果，發(fā)現(xiàn)程序總是把4號(hào)球錯(cuò)認(rèn)為2號(hào)球。
這說(shuō)明什么問(wèn)題呢？
會(huì)不會(huì)是因?yàn)橄扰袛?/span>2號(hào)球，再判斷4號(hào)球的緣故？我嘗試著把多分支語(yǔ)句中elif語(yǔ)句的位置換了一下，讓程序先判斷4號(hào)球，再判斷2號(hào)球。
原來(lái)問(wèn)題出在這里！
2號(hào)球和4號(hào)球到底誰(shuí)才是異球？條件表達(dá)式怎么會(huì)一模一樣呢？是我漏掉了什么東西嗎？
再仔細(xì)看看算法分析。咦，我好像發(fā)現(xiàn)了點(diǎn)什么。
當(dāng)異球?yàn)?/span>2時(shí)，4號(hào)球是普通球，則z應(yīng)該為整數(shù)；同理，當(dāng)異球?yàn)?/span>4時(shí)，2號(hào)球是普通球，則x應(yīng)該為整數(shù)。
妙??！這是屬于我的尤里卡時(shí)刻！
好了，現(xiàn)在只需要加上兩個(gè)限制條件就行了，第二版程序如下：
def fun_2(a):x = sum(a[:3]) # 第一次稱重：3x=123y = sum(a[1:5]) # 第二次稱重：4y=2345if x/3 == y/4: # 前面5個(gè)球等重，則球6為異球z = a[5] # 第三次稱重：稱量異球6print(f"異球?yàn)?，其重量為{z}，其他球重量為{x//3}")else:z = a[2] + a[3] # 第三次稱重：2z=34if y/4 == z/2: # 異球?yàn)?print(f"異球?yàn)?，其重量為{x-z}，其他球重量為{z//2}")elif x/3 == z/2: # 異球?yàn)?print(f"異球?yàn)?，其重量為{y-x}，其他球重量為{z//2}")elif z/2 == z//2 and (x/3 < y/4 < z/2 or x/3 > y/4 > z/2): # 異球?yàn)?print(f"異球?yàn)?，其重量為{y-3*z//2}，其他球重量為{z//2}")elif x/3 == x//3 and (z/2 < y/4 < x/3 or z/2 > y/4 > x/3): # 異球?yàn)?print(f"異球?yàn)?，其重量為{z-x//3}，其他球重量為{x//3}")else: # 異球?yàn)?print(f"異球?yàn)?，其重量為{2*z-x}，其他球重量為{x-z}")
?
八、精益求精
現(xiàn)在，問(wèn)題應(yīng)該說(shuō)得到完美解決了。但解決問(wèn)題從來(lái)都沒(méi)有最好，只有更好。
第三次稱量的方式有4種，我只考慮了其中一種。另外3種的結(jié)果是不是和前面一致？我還沒(méi)有編程驗(yàn)證。這件事情不做好，就不算完。
于是，秉著精益求精的精神，追求完美的我又給出了第三版程序：
def fun_3(a, i, j):x = sum(a[:3]) # 第一次稱重：3x=123y = sum(a[1:5]) # 第二次稱重：4y=2345if x/3 == y/4: # 前面5個(gè)球等重，則球6為異球z = a[5] # 第三次稱重：稱量異球6print(f"異球?yàn)?，其重量為{z}，其他球重量為{x//3}")else:z = a[i-1] + a[j-1] # 第三次稱重：2z=24或25或34或35if y/4 == z/2: # 異球?yàn)?print(f"異球?yàn)?，其重量為{x-z}，其他球重量為{z//2}")elif x/3 == z/2: # 異球?yàn)?-jprint(f"異球?yàn)?span id="go7utgvlrp" class="code-snippet__subst">{9-j}，其重量為{y-x}，其他球重量為{z//2}")elif z/2 == z//2 and (x/3 < y/4 < z/2 or x/3 > y/4 > z/2): # 異球?yàn)?-iprint(f"異球?yàn)?span id="go7utgvlrp" class="code-snippet__subst">{5-i}，其重量為{y-3*z//2}，其他球重量為{z//2}")elif x/3 == x//3 and (z/2 < y/4 < x/3 or z/2 > y/4 > x/3): # 異球?yàn)閖print(f"異球?yàn)?span id="go7utgvlrp" class="code-snippet__subst">{j}，其重量為{z-x//3}，其他球重量為{x//3}")else: # 異球?yàn)閕print(f"異球?yàn)?span id="go7utgvlrp" class="code-snippet__subst">{i}，其重量為{2*z-x}，其他球重量為{x-z}")import randomfor i in range(16):a = [3] * 6 # 初始化每個(gè)小球重量均為3num = random.randint(0, 5) # 選擇任意一個(gè)小球?yàn)楫惽?/span>a[num] = a[num] + random.choice([-1,1]) #異球重量可輕可重print(a)fun_3(a, 2, 4)fun_3(a, 2, 5)fun_3(a, 3, 4)fun_3(a, 3, 5)print("#" * 20)
終于搞定了，又可以愉快地玩耍上課了。
需要本文源代碼和word文檔的，可以加入“Python算法之旅”知識(shí)星球參與討論和下載文件，“Python算法之旅”知識(shí)星球匯集了數(shù)量眾多的同好，更多有趣的話題在這里討論，更多有用的資料在這里分享。
我們專注Python算法，感興趣就一起來(lái)！
相關(guān)優(yōu)秀文章：