Current location - Training Enrollment Network - Mathematics courses - [Algorithms are everywhere in life] Clever use of Joseph rings
[Algorithms are everywhere in life] Clever use of Joseph rings
Joseph ring (josephus problem) is a mathematical application problem;

It is known that n people (represented by the numbers 1, 2,3 ... n) are sitting around the round table.

Count from the person numbered k, and those who count to m will turn around; His next person began to count off from 1, and the person who counted to m went out again; Repeat in turn until the last winner remains.

For example, this game has 10 people playing in a circle, and each person's number is 1- 10. If the person who counts to three is asked to turn around. The game process is as follows:

(1) starts to count off. The first person to count to 3 is number 3, and number 3 will be circled.

1,2,3,4,5,6,7,8,9, 10

(2) Starting from the 4th and counting from 1, the next person who counts to 3 is the 6th, and the 6th is out of the circle.

1,2,3,4,5,6,7,8,9, 10

(3) From the seventh number to 1, then the person who counts to 3 next is the ninth, and then the ninth is out of the circle.

1,2,3,4,5,6,7,8,9, 10

(4)? Count from 10 and then from 1. Since 10 is called a ring structure, the next person to count to 3 is No.2, and No.2 is out of the circle.

1,2,3,4,5,6,7,8,9, 10

(5) Count from the 4th to 1, then the next person who counts to 3 is the 7th, and the 7th is out of the circle.

1,2,3,4,5,6,7,8,9, 10

(6) Starting from 8 and counting from 1, the next person who counts to 3 is 1, 1 out of the circle.

1,2,3,4,5,6,7,8,9, 10

(7) Count from the 4th to 1, then the next person who counts to 3 is the 8th, and the 8th is out of the circle.

1,2,3,4,5,6,7,8,9, 10

(8) Count from 10 again, then the next person who counts to 3 is No.5, and No.5 is out of the circle.

1,2,3,4,5,6,7,8,9, 10

(9) Counting from 10 and then from 1, then the next person to count to 3 is 10 and 10.

1,2,3,4,5,6,7,8,9, 10

(10) Finally, No.4 is left, and No.4 is the winner.

The basic idea of array solution is to use an array to identify the state of these n people, which is 1 by default, that is, in the circle.

The person who counts to m goes out of the circle, the sign is set to 0 (that is, out of the circle), and the counter is cleared. The next one should start with 1.

Judge whether he is in the circle (that is, whether his logo is 1) before each count. If he is in the circle, he will continue to count. Define a variable to record the number of people outside the circle. When the number of laps is equal to n- 1, the game is over.