Josephus problem, who knows how to solve the Josephus problem

1 All topics]: I have heard the old legend that 64 warriors were captured by the enemy.

The enemy ordered them to form a circle and make numbers 1, 2, 3....，64。The enemy killed No. 1 and No. 3, and they killed one by one, and they went around in circles. In the end, there was only one person left, and that person was Josephus.

What is Josephus' number? (This is the "Josephus" problem.) ）

The answer to this question is relatively simple: the enemy starts with the 1st, kills one by one, and kills all the odd-numbered fighters in the first round. The remaining 32 fighters need to be renumbered, and the enemy kills in the second lap with the renumbered odd number.

Since all that remains of the first lap is the even number 2,4,6,...，64。Remove them all with 2 to get 1, 2, 3 ,...，32。This is the number of the second circle.

After the second round, all the odd numbers were killed, and there were 16 people left. If this continues, it can be imagined that the last remaining one must be No. 64.

64=26, which is divisible by 2 6 times in a row, is the number that can be divisible by 2 from 1 to 64 the most, so it is inevitable that 64 will be left at the end.

If 65 warriors were captured, and the enemy still slaughtered the warriors in the same way as described above, would Josephus be left in the end?

After calculation, it is easy to come to the conclusion that it is not. Because after the first person is killed, that is, after No. 1 is killed, the second person who is killed is necessarily No. 3. If No. 1 is excluded, then there are still 64 people left, and the new No. 1 is No. 3.

In this way, the original No. 2 becomes the new No. 64, so the rest must be No. 2.

Further classification, it is not difficult to find that if there are 2k people originally, the last remaining number must be 2k; If there are 2k+1 people in the original, there will be 2 left in the end; If there are 2k+2 people, there will be 4 ...... leftIf there are 2k+m people in the original, there will be 2m numbers left in the end.

For example: there were originally 100 people, and since 100 = 64 + 36 = 26 + 36, the last thing left was 36 2 = 72; Another example: there were originally 111 people, and since 100 = 64 + 47 = 26 + 47, the last thing left was 47 2 = 94.

When m is relatively small, it can be solved by pen calculation, m=2

That is, n people form a circle, 1, 2, 1, 2 report the number, report 2 and die, until only one person remains.

When n=2 k, the first person to report the number is the last to die, and for any natural number n can be expressed as n=2 k+t, where tn mod 3 then the last person to die is the new round of f(n-[n 3])-n mod 3) person.

3. The k-th person in the new round corresponds to the original 3*[(K-1) 2]+(K-1)mod 2+1 person.

Combined 1,2,3 yields:

f(1)=1, f(2)=2, f(3)=2, f(4)=1, f(5)=4, f(6)=1, when f(n-[n 3])<=n mod 3 k=n-[n 3]+f(n-[n 3])-n mod 3), f(n)=3*[(k-1) 2]+(k-1)mod 2+1

When f(n-[n 3])>n mod 3, k=f(n-[n 3])-n mod 3), f(n)=3*[(k-1) 2]+(k-1)mod 2+1

This algorithm needs to be calculated [log(3 2)2009] times This number is not greater than 22, and it can be calculated with a pen.

So: in the first round, 669 people will be killed, the last person killed in this circle is 2007, and there are 1340 people left, and in the second circle, 446 people will be killed, and 894 people will remain.

In the third round, 298 people were killed, and 596 people remained.

In the fourth round, 198 people were killed, and 398 people remained.

In the fifth lap, 132 people were killed, and 266 people remained.

In the sixth lap, 88 people were killed, and 178 people remained.

In the seventh round, 59 people were killed, and 119 people remained.

In the eighth lap, 39 people were killed, and 80 people remained.

In the ninth lap, 26 people were killed, and 54 people remained.

In the tenth lap, 18 people were killed, and 36 people remained.

Eleven laps, 12 people killed, 24 people remain.

Twelve laps, 8 people killed, 16 people remained.

Thirteen laps, 5 killed, 11 people remained.

Fourteen laps, 3 killed, 8 people left.

Fifteen laps, 2 killed, 6 people left.

f(1)=1, f(2)=2, f(3)=2, f(4)=1, f(5)=4, f(6)=1, and then push back.

f（8）=7 f（11）=7 f（16）=8 f（24）=11 f（36）=16 f（54）=23 f（80）=31 f（119）=43 f（178）=62 f（266）=89 f（398）=130

f（596）=191 f（894）=286 f（1340）=425 f（2009）=634

-Come from.

Titus Flavius Josephus (37-100 CE), also known as Joseph, is known in the Hebrew Bible as Joseph Ben Mattityahu, in Jerusalem in the Jewish province of Rochun.

Born as a Jewish historian in the first century A.D.

His representative works include "Ancient History of Judea".

and The Jewish War. He served as an officer in the Jewish rebels during the First Judeo-Roman War, and after his surrender he served as a staff officer and interpreter for Rome**, and was granted Roman citizenship.

The Joseph problem is a well-known problem: n people gather in a circle, start counting from the first, the m will be killed, the last one will be left, and the rest will be killed. For example, n = 6, m = 5, and the serial number of the person killed is 5, 4, 6, 2, 3.

In the end, No. 1 remains.

Assuming that the first k people in the circle are good and the last k are bad people, your task is to determine the minimum m so that all the bad guys are killed before the first good guy.

It is said that the famous Jewish historian Josephus told the following story: after the Romans occupied Chotapat, 39 Jews hid in a hole with Josephus and his friends, and the 39 Jews decided that they would rather die than be caught by the enemy, so they decided on a way to commit suicide, 41 people lined up in a circle, the first person began to count, and each third person had to commit suicide, and then the next one recounted until all of them had committed suicide. Josephus and his friends, however, did not want to comply.

Start with one person, cross the k-2 person (because the first person has already been crossed), and kill the k-th person. Then, get past K-1 and kill the k-1 person. The process continues along the circle until eventually only one person remains, and that person can continue to live.

The question is, given the and, where do you have to stand in the first place to avoid being executed? Josephus asked his friend to pretend to be compliant, and he escaped the game of death by placing him in the 16th and 31st positions.

The 17th-century French mathematician Gaspar told a story in "The Problem of the Game of Numbers" that 15 believers and 15 non-believers were in distress at sea, and half of them had to be thrown into the sea before the rest could survive, so he came up with a solution: 30 people formed a circle, starting with the first person, and every ninth person was thrown into the sea, and so on until only 15 people remained.

Ask how to arrange the law, so that every time you throw yourself into the sea, you are non-believers.

Problem analysis and algorithm design.

Joseph's problem is not difficult, but there are many ways to solve it; There are also many variations of the topic. Here's an implementation method.

In the problem, 30 people are in a circle, which inspires us to use a circular chain to represent it, and we can use an array of structures to form a circular chain. There are two members in the structure, one of which is a pointer to the next person to form a circular chain; The second is a mark of whether the person has been thrown overboard, and a 1 indicates that he is still on board. Starting with the first person, count the person who has not yet been thrown into the sea, and every time you count to 9, change the mark in the structure to 0 to indicate that the person has been thrown into the sea.

This cycle counts until 15 people are thrown into the sea.