[day.2] Joseph Ring problem, how to use arrays to replace circular linked lists (detailed explanation)

Catalog

subject

journey ：

Solution analysis ：

summary ：

---

background ：

As a vegetable chicken Xiaobai who just transferred to software engineering , Just simply know some basic c Language programming language , The first time I heard ACM, Then I took part in the school's ACM Your tryouts ,3 Hours ！! A total of nine questions , I made a ！！ I haven't touched the algorithm , I decided to start my algorithm learning ！！！

Today, I sorted out a function problem on the big purple book , It feels special and wonderful , The title is as follows ：

---

subject ：
n(n<20) Stand in a circle , The counter clockwise number is 1～n. There are two officials ,A from 1 Start counting counterclockwise ,B from n Start timing stitches . In each round , official A Count k Just stop , official B Count m Just stop （ Note that it is possible for two officials to stop on the same person ）. The next person selected by the officials （1 A or 2 individual ） Leave the team . Input n,k,m Output the number of the selected person in each round （ If there are two people , First output by A Selected ）. for example ,n=10,k=4,m=3, Output is 4 8, 9 5, 3 1, 2 6, 10, 7. Be careful ： Each number output should account for exactly 3 Column .

---

journey ：

See this question , After just learning the linked list, my first thought must be to use the circular linked list to solve this circular problem similar to the death squads problem. After writing the code in this way, I will be paired with the big purple book ,*** He used Array It's settled. , When learning circular linked list, I didn't think of such a great way to solve the problem of linked list with array , But I thought for a long time , Forget it, I'd better use the linked list ！！ Now let's see how the author of the big purple book realizes using arrays to cycle ？

---

Solution analysis ：

First , Let's draw a picture ：

Algorithm 1： Linked list , The idea is simple but very complicated 100 Line code , Waste my precious time choosing Bingbing .

Algorithm 2： Seeking remainder , This is good, this is simple .

Counterclockwise clockwise realization ： The main function is passed in q,q=1 It is counterclockwise ,q=-1 It is clockwise .

How many steps k The implementation of the ： The main function passes in the number of steps t,while（t--）

a key 1： Realize the problem of choosing Bingbing to leave ： If Bingbing is selected to leave , Then ice is marked as zero , If the ice in this position is marked 0; Then go down one step and use the loop to realize the following ：

do {
			// The most important statement to realize array loop ;
		}
		while(a[p] == 0);

In this way, the problem of ice jumping selected is solved

a key 2（ The eye of this question ）： How to realize the circular selection of arrays ？ The answer is to find the remainder ！！

If p=(p+q+n)%n We can find out , Look at the picture above, Bingbing , You choose （ Clockwise ）, If you choose No. 1 Bingbing and want to choose No. 8 Bingbing , We put p=2 Brought in p=1 No problem . But ！p=1 Brought in p=(1-1+8)%8=1 No choice 8 It's freezing ！

Ps. Because of a number n The remainder obtained from the remainder is 0<=n The remainder of <n Of , At this time, we need to subtract 1 Outside again +1 So that this number quotient 0 And the remainder can be taken to itself, and the range becomes 0<n The remainder of <=n, Amazing ！！！ At that time, I thought it was the most magical place

< To avoid that ： We're going to use p=(p+q+n-1)%n+1 When we come to this time, we will find p=8 了 , Realize the selection of cycle

At this time, another child asked , So if p=2 Is not equal to 0 Yes , No, no, no, we can find p=(2-1-1+8)%8+1=1, Because our scope has become 0<n The remainder of <=n

So choose The wife Function is ：

int go(int p, int q, int t){
	while(t--)
	{
		do {
			p = (p + q + n-1)%n + 1;
		}
		while(a[p] == 0);
	}
	return p;
}
 

When this function is written, the following problem will be solved ！！

And the problem of choosing a wife （bushi） The total code of is ：

#include <stdio.h>
#define maxn 25
int n, a[maxn];
int go(int p, int q, int t){
	while(t--)
	{
		do {
			p = (p + q + n-1)%n + 1;
		}
		while(a[p] == 0);
	}
	return p;
}
 
int main()
{
	int  k, m, p1, p2, left;
	while(scanf("%d %d %d", &n, &k, &m) == 3 && n)
	{
		left = n, p1 = n, p2 = 1; 
		for(int i = 1; i <= n; i++) a[i] = i;
		while(left) {
			p1  = go(p1, 1, k);
			p2 = go(p2, -1, m);
			printf("%d",p1);
			left--;
			a[p1] = 0;
			if(p1 != p2) 
			{
				printf(" %d", p2);
				left--;
				a[p2] = 0;
			}
			if(left) printf(",");
		}
		printf("\n");	
	}
	return 0;
}

summary ：

1. Using mathematical knowledge p=(p（ home ）+q（ Step ）+n（ The total number of ）)%n It can realize the circular implementation of the array, and the combined tag amount is 0, Can realize the problem of replacing the circular linked list . clever ！

2. Flexible use of global variables can avoid , The problem of using pointers when changing the value of the main function in the transmission of values

3. Bingbing is so beautiful . 

Love is worth years.
Love is worth years .