Original link: https://fmcf.cc/technology/910/
foreword
When I was surfing intensively on the Internet, I stumbled upon this problem, and finally, under the guidance of OI, with the help of CSDN, I came up with a solution.
topic
There are 100 bottles of disrupted potions in front of you, and only one of them is poison. You have 7 mice, and the mice that drink the poison will die, and vice versa. Now please use these 7 mice to design a Program, find out the poison according to the life and death of the mice.
It is assumed that each mouse can drink an unlimited amount of potions, and each bottle of potion will not be consumed. During the implementation of the program, you cannot know the current execution status, that is, you cannot use the previous mouse’s Live or die decides what to do next.
difficulty
In this problem, the most difficult thing is that we need to complete all the steps before we can know the result, and we cannot decide the follow-up operation based on the life and death of the previous mouse.
In the process of discussing with my classmates, everyone prefers to use the dichotomy method, which is constantly approaching, and regardless of the above difficulties, in terms of the dichotomy method alone, it is very likely that we will not be able to find it after all seven mice have died. cup of potion.
At this time, with our current high school regular math methods, we can no longer answer this question, so what should we do?
binary method
Binary is the language of computers, let’s take a rough look at binary.
We usually use decimal, that is, every 10 is 1. When we write the eleventh number, it is 11, not anything else. Just like the eleventh hexadecimal number is represented by a, the binary In the same way, every 2 is entered into 1, and when the third number is written, the binary is represented by 11.
001 # 1 002 # 2 011 # 3 100 # 4 101 # 5
The number after # is a decimal number, and the front of # is a binary number. The three-digit alignment method is adopted. If the number to the left of 1 is 0, it is meaningless.
Knowing the binary, let’s review the question again, 7 mice, 100 bottles of potion, use Python to write a binary conversion algorithm, and list the binary of all numbers from 1 to 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)
We found that the binary conversion result of 100, 1100100, is exactly a seven-digit number, which means that the number of digits in the binary representation of the number before 100 can never exceed seven digits, and each decimal number corresponds to only one binary number, exactly We have 7 mice and we can use this feature to solve this problem.
There are seven numbers from left to right, and each number corresponds to a mouse. When the corresponding digit is 1, it is necessary to drink this bottle of potion. If you drink the 35th bottle of potion, then we first calculate the corresponding value of 35. Binary, and use seven digits to match it, then the binary corresponding to the 35th bottle is 0100011, from left to right, the 2nd, 6th, and 7th digits are 1, then we let the 2nd, 6th, and 7th only The rats go and drink it. If all three rats die, then this cup of potion is poison. If it is not dead or dead, then it is not poison, because these rats may also drink other potions. We Can’t judge.
After the lecture, start the practice
practice deduction
We use Excel for statistics, which are lists. Use Python’s binary algorithm to get all binary numbers from 1-100 and import them into Excel. Number the seven rats and make them drink the corresponding potion.
Let’s assume that Potion No. 84 is poisonous, and then proceed to the deduction
We can see that when all the mice in a group die, we can judge this group as poison, that is, the 85th bottle.
Empathy
When I wrote the table, I found that if we do not use mathematical thinking, we regard it as biological inheritance. When these genes are all dominant genes at the same time, we can make the phenotype dominant, but we must understand The binary solution is a critical point, and without binary we can hardly do it.
This article is reproduced from: https://fmcf.cc/technology/910/
This site is for inclusion only, and the copyright belongs to the original author.