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