前言#
私がインターネットで高強度にサーフィンしているときに、この問題を偶然発見し、OI の大神の指導と CSDN の助けを借りて、解決方法を思いつきました。
题目#
あなたの前には 100 本の乱れた薬水があり、その中にただ 1 本だけ毒薬があります。あなたは 7 匹のネズミを持っており、毒薬を飲んだネズミは死にますが、そうでないネズミは死にません。さて、この 7 匹のネズミを使って、ネズミの死活状況に基づいて毒薬を見つける方法を設計してください。
各ネズミは無限量の薬水を飲むことができ、各瓶の薬水は飲み尽くされることはありません。計画を実施する過程で、現在の実行状況を知ることはできません。つまり、前のネズミの死活に基づいて後続の操作を決定することはできません。
困难#
この問題で最も難しいのは、すべてのステップを完了した後でなければ結果を知ることができず、前のネズミの死活に基づいて後続の操作を決定できないことです。
クラスメートと議論していると、皆は二分法を使用することに傾いており、困難を考慮せずに単に二分法について論じると、7 匹のネズミがすべて死んだ後でもその薬水を見つけられない可能性が高いです。
この時点で、私たちの現在の高校の通常の数学的方法では、この問題を解決することはできません。どうすればいいのでしょうか？
二进制法#
二進法はコンピュータの言語です。二進法についてざっと理解してみましょう。
私たちが普段使用しているのは十進法で、10 で進むと 1 が繰り上がります。11 番目の数を書くときは 11 であり、他のものではありません。16 進法の 11 番目の数が a で表されるのと同様に、二進法も同じで、2 で進むと 1 が繰り上がります。3 番目の数を書くとき、二進法では 11 で表されます。
001 # 1
002 # 2
011 # 3
100 # 4
101 # 5
#の後は十進数、# の前は二進数で、3 桁の整列方法を採用し、1 の左側の数が 0 の場合は実際には意味がありません。
二進法を理解したので、再度問題を見直しましょう。7 匹のネズミ、100 本の薬水を使って、Python で二進数変換アルゴリズムを作成し、1 から 100 までのすべての数の二進数を列挙しました。
x=0
for i in range(0,100):
x=x+1
y = x
b=""
while(y>=1):
b=str(num%2)+b
num=num//2
print(b)
私たちは、100 の二進数変換結果が 1100100 であり、ちょうど 7 桁の数であることに気付きました。これは、100 未満の数の二進数表現の桁数が永遠に 7 を超えることはなく、各十進数はちょうど 1 つの二進数に対応することを意味します。ちょうど 7 匹のネズミがいるので、この特性を利用してこの問題を解決できます。
左から右に 7 つの数があり、それぞれの数が 1 のとき、その瓶の薬水を飲む必要があります。例えば、35 番目の薬水を飲むと仮定すると、まず 35 に対応する二進数を計算し、7 桁の数に整列します。35 番目に対応する二進数は 0100011 であり、左から右に 2 番目、6 番目、7 番目の数が 1 であるため、2、6、7 匹のネズミにそれを飲ませます。もし 3 匹のネズミがすべて死んだ場合、その薬水は毒薬です。死ななかったり、死にきれなかった場合は毒薬ではありません。なぜなら、これらのネズミは他の薬水を飲む可能性があるからです。私たちは判断できません。
説明が終わりましたので、実践を始めます。
实践推演#
私たちは Excel を使用して統計を行います。リストを使用します。Python の二進数アルゴリズムを使用して、1-100 のすべての二進数を取得し、Excel にインポートします。7 匹のネズミに番号を付け、それに対応する薬水を飲ませます。
私たちは 84 番目の薬水が毒であると仮定し、次に推演を行います。
私たちは、グループ内のすべてのネズミが死亡したときにのみ、そのグループが毒薬であると判断できることがわかります。つまり、85 番目の瓶です。
换位思考#
表を作成しているとき、数学的思考を使用しない場合、これを生物遺伝と見なすことができることに気付きました。複数の遺伝子がすべて顕性遺伝子である場合にのみ、表現型が顕性になります。しかし、二進法の解法が重要なポイントであることを理解しなければなりません。二進法がなければ、
この記事は Mix Space によって xLog に同期更新されています。
元のリンクは https://fmcf.cc/posts/technology/Python-Rat-Poison-Solution