前言#
私がインターネットで高強度にサーフィンしているときに、この問題を偶然発見し、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