記事の内容
アルゴリズムの練習として有名なものに、「天秤を使って偽造硬貨を見つける」というパズルがあります。
今回の記事では、この問題をpythonで解いてみます。基礎的な文法さえわかれば挑戦できるパズルなので、ぜひ初心者の方もチャレンジしてみてください。
[:contents]
問題解決のPythonプログラミング 偽造効果を探す
「問題解決のPythonプログラミング 数学パズルで鍛えるアルゴリズム的思考」こちらの本で紹介されている方法で、まとめます。
さて、問題はこうです。
9つのコインがあり、この中には1枚だけ重いものがあります。この重い1枚を天秤によって見つけるにはどうすればいいか。最少で済む測り方を見つけよ。
コインの枚数が9枚ではなく、枚数が増えても適用できるアルゴリズムが欲しいです。
方針 分割統治法
ここで、効率的に探す方法として分割統治法というものがあります。分割してから、比較していくというものです。例えば、9枚のうちからまず4枚を選び、その4枚をまずは2枚ずつの組にわけて比較します。
１、重さが等しければ、その4枚はいずれも重い硬貨ではない。
２、１番目の対が重ければ、そこに重い硬貨がある。
３、２番目の対が重ければ、そこに重い硬貨がある。
1の場合は、残った5枚から4枚を選び、同様の処理をしてあげればいい。最悪でも、3回の計量で重いコインが見つかる。9枚よりも多い枚数のときでも、分割統治法は強力。
今回のコードでは、3分割する方法を試してみます。ただし、元のリストの要素数を3のn乗個と仮定しています。
解答
解答を本書から引用させてもらう。
#2つのグループを比較する関数 def compare(groupA, groupB): if sum(groupA) > sum(groupB): result = 'left' elif sum(groupA) < sum(groupB): result ='right' elif sum(groupA) == sum(groupB): result = 'equal' return result #硬貨のリストを3つの同じサイズに分割 def split (coinList): length = len(coinList) group1 = coinList[0 : length//3] group2 = coinList[length//3 : length//3*2] group3 = coinList[length//3*2 : length] return group1, group2, group3 #一回目の比較 def findFakeGroup(group1, group2, group3): result1and2 = compare(group1, group2) if result1and2 == 'left': fakeGroup = group1 elif result1and2 == 'right': fakeGroup = group2 elif result1and2 == 'equal': fakeGroup = group3 return fakeGroup def CoinComparison(coinsList): counter = 0 currList = coinList while len(currList) > 1: #重い硬貨だけになると終了 group1, group2, group3 = split(currList) currList = findFakeGroup(group1, group2, group3) counter += 1 fake = currList[0] print('The fake coin is coin', coinsList.index(fake) + 1, 'in the original list') print('Number of weighings:', counter)
実行結果
coinList = [ 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] CoinComparison(coinList)
('The fake coin is coin', 7, 'in the original list')
('Number of weighings:', 3)
7番目のコインが重いことがわかった。比較回数は3回だけで済んでいる。
使用したpython記法
リストのスライス機能を利用した。いくつかの基本的な使用方法を確認しておきたい。
a[1:4]ならば、インデックス1~3の値を取り出すことができる。終端は、「取り出したいインデックス+1」と指定することに注意。
