Search- 2008年6月19日 16:58
- Algorithm
１つだけ重いコインが混じっているN個のコインを天秤にかけて最小回数の計量で重いコインを見つけるアルゴリズムを紹介します。今回紹介するのは、N個のコインの中で偽のコインは重いと分かっているということを仮定したものです。重いか軽いか分からないコインを見つけるアルゴリズムは後々紹介しようと思います。
The algorithm which finds only one heavy coin in number of coin(N) by the minimum times measurement.
このコードは、アルゴリズムが完全に成立してない状態で書いたコードなので、継ぎはぎだらけの乱雑なコードになってます。説明は難しいので書いてません。書き直して簡略化させたものを紹介しようと思いましたが、とりあえずプログラムは動きますので記事にしました。後々、しっかりしたものができたら紹介しようと思っています。
Since the algorithm is the code written when it is not materialized completely, this code is a disorderly code and too difficult to explain. Although this program work without problem, I will introduce with explaination after I simplify the code.
配列Aｒに1～27の数値を格納して、Call FalseCoin(Ar, 10)を実行するとイミディエイトウィンドウに以下のように表示されます。
２７枚のコインから２７番目のコインを探す場合、下のような量り方をします。
- まず１～９<--->10～18までを量るとコインは２７番目ですので、重さは同じです。
- 次に、19～21<--->22～24までを量ると、これも重さは同じになります。
- 次に、25と26を量るとこれも重さは同じなので、重いコインは27ということが分かります。
n=27 Call FalseCoin(Ar, 27) ''<---find 27th from 27 coins 第 1 回目の計量 1 2 3 4 5 6 7 8 9 = 10 11 12 13 14 15 16 17 18 第 2 回目の計量 19 20 21 = 22 23 24 第 3 回目の計量 25 = 26 False Coin = 27
２７枚のコインから10番目のコインを探す場合、下のような量り方をします。
- まず１～９<--->10～18までを量るとコインは10番目ですので、重さは10番目のコインが含まれている方が重くなります。
- 次に、10～12<--->13～15までを量ると、これも重さは10番目のコインが含まれている方が重くなります。
- 次に、10と11を量ると、重いコインは10ということが分かります。
n = 27 Call FalseCoin(Ar, 10) ''<--- find 10th from 27 coins 第 1 回目の計量 1 2 3 4 5 6 7 8 9 < 10 11 12 13 14 15 16 17 18 26here:9 第 2 回目の計量 10 11 12 > 13 14 15 第 3 回目の計量 10 > 11 False Coin = 10