Multiple solutions to one problem × 5 (array + circular linked list)

Catalog

subject ：

Solution 1 ：

Solution 2 ：

---

subject ：

A bunch of monkeys have m individual , The numbers are 1,2,3 ...m, this m Monkeys are numbered 1,2,…,m Sit in a circle , And then from the 1 Starting number , Every time I count to the n individual , The monkey is about to leave the circle , In this order , Until there's only one monkey left in the circle , Then the monkey is the king . Ask for a set of m and n, Output the corresponding Monkey King .

         This is the meaning of the question , hypothesis m=9,n=4, As clockwise or counterclockwise selection has little effect on the results , Might as well Sort clockwise and select , The composition is as follows ：

frequency	The number of the monkey at the beginning	The number of the monkey chosen to leave	The number of the remaining monkeys	m
1	1	4	1、2、3、5、6、7、8、9	8
2	5	8	1、2、3、5、6、7、9	7
3	9	3	1、2、5、6、7、9	6
4	5	9	1、2、5、6、7	5
5	1	6	1、2、5、7	4
6	7	5	1、2、7	3
7	7	7	1、2	2
8	1	2	1	1

This example suggests that you can operate with your own pen , Increase the depth of understanding the meaning of the question . It can be seen that , The number of remaining monkeys is decreasing , When there is only one monkey's number, the monkey is the monkey king . 
That means , After the monkey was picked away , We continue to select from its next monkey . After understanding the meaning of the title , Let's think again m and n The meaning of ,m Represents the number of monkeys ,n Represents the number of intervals between two adjacent selections . Then the truth is obvious ,m And n There is a size comparison . In the discussion m and n When the comparison of size relation is useful for solving this problem , I have to explain a concept first , Take the example above ：

A cycle in the process of picking the monkey king refers to the process from the starting point to the starting point . In the picture above, the first time I picked a monkey , The number of steps we need to take in a cycle is m+1=9+1=10, The process is 1->2->3->4->5->6->7->8->9->1, It was used 10 Step .

Explain that this concept may be used in m>=n It doesn't help much , But in m<n In this case, it is very important .

         Because the process of picking the monkey king is a dynamic process , After picking out a monkey ,m It also requires corresponding self subtraction . therefore ,m>n\m=n\m<n One of these three cases cannot always be true , This problem can also be seen in the above example ： In the 5 After the first selection , It's just 4 A monkey , This was greater than 4 only , After that, it is less than 4 only , Although this is in m>n The results obtained in the case of , But he applies to these three situations . So we just need to put this 3 The codes required for the conditions in are indicated respectively , Then let the part that meets the conditions operate .

        Now let's discuss these three situations ：

1、m==n：

The one who was picked out was No m A monkey , When re labeling, the first monkey happens to be the first monkey in the previous round of selection . for example ,m=n=9, So after the first selection , We are still from 1 Monkey No. 1 began to pick ：

2、m>n：

This situation is very routine , No need to discuss .

3、m<n：

This situation is similar to m>n, just n Something has changed . because m<n, And the monkey needs to loop through it m+1 Time to get back to the starting point , So use a temporary variable n_tem obtain n With m+1 If it is modulo, you can get the remainder . for example ,m=9,n=10, So I actually went back to 1 Monkey No , But because of n_tem=n%(m+1)=0, On this basis, it is equivalent to not moving , so 1 Monkey No. 1 was picked away ：

Now we have a general understanding of the subject , So the code ：

Solution 1 ：

#include<stdio.h>
int main()
{
	int m, n;
	int n_tem;
	int a[101];//max=100
	int b[101];// We gave up a[0] And b[0], For ease of operation 
	scanf("%d%d", &m, &n);//input m&n
	for (int i = 1; i <= m; i++)
		a[i] = i;
	while (m != 1)
	{
		if (n < m)
		{
			for (int i = n + 1; i <= m; i++)
			{
				b[i - n] = a[i];// Will be the first n+1 A to m Node codes are saved in b[]
			}
			for (int i = 1; i <= n - 1; i++)
			{
				b[m - n + i] = a[i];// Will be the first 1 A to n-1 Node codes are saved in b[], Be careful b[] Element subscript from m-n Start 
			}
			for (int i = 1; i <= m - 1; i++)
				a[i] = b[i];// Copy elements 
			m--;
		}
		else if (n > m)
		{
			n_tem = n % m;
			if (n_tem == m)// for example m=5,n=11, In the end m Monkeys will be picked away ,m Subtract... From the original basis 1, And the first one below for In circulation i Should not reach m
			{
				m--;
				continue;
			}
			for (int i = n_tem + 1; i <= m; i++)// Will be the first n_tem+1 A to m Node codes are saved in b[]
			{
				b[i - n_tem] = a[i];
			}
			for (int i = 1; i <= n_tem - 1; i++)// Will be the first 1 A to n_tem-1 Node codes are saved in b[], Be careful b[] Element subscript from m-n_tem+1 Start 
			{
				b[m - n_tem + i] = a[i];
			}
			for (int i = 1; i <= m - 1; i++)
				a[i] = b[i];
			m--;
		}
		else
		{
			m--;
		}
	}
	printf("%d", a[1]);
	return 0;
}

Running results ：

First , Input m And n Value , The result is the label of the final Monkey King , And for the convenience of operation , We gave up a[0] and b[0], From the subscript 1 Start storing elements . Use the 9、10 Line code labels each monkey . And then in m And n In the size comparison of 3 In this case , Discussion by situation :

1、m==n:

The corresponding statement block only needs to have m--; sentence , This is because the one who was picked out is the m A monkey , When re labeling, the first monkey happens to be the first monkey in the previous round of selection , and m After subtraction, it indicates that the remaining m-1 Choose the monkey king from the monkeys .

2、m>n:

a[] The array is what we use to store the remaining monkeys , Its element value is the number of the monkey it represents ;b[] Array is used to store an array from the next monkey of the selected monkey in order a[] The monkeys in the are kept one by one , After the b[] Copy the elements in to a[] in . for example ：

if n=3, So there are

b[1]=4;
b[2]=5;
b[3]=6;
b[4]=7;
b[5]=8;
b[6]=9;
b[7]=1;
b[8]=2;

After the b[] Copy the elements in to a[] in , Then there is

a[1]=4;
a[2]=5;
a[3]=6;
a[4]=7;
a[5]=8;
a[6]=9;
a[7]=1;
a[8]=2;

then m--; Represents that the total number of monkeys is reduced by one . Shown here ：

 

3、m<n:

This kind of situation similar m>n, just n Something has changed . because m<n, And the monkey needs to loop through it m+1 Time to get back to the starting point , So use temporary variables n_tem access n With m Remainder obtained for modulo , You can get and m>n A similar situation .

To better illustrate what I said , I need to talk about 29、30 Line code means ：

Because our array is subscript 1 Start storing elements , Has always been a The first n Nodes We picked it out . If m=3,n=4, Then it should be the 1 Nodes are picked up first , So it should be n_tem=n%m=4%3=1, The first node is picked by us , So the first 29 The line code is n_tem=n%m;; As for the 30 Yes if Judging structure , This is a special case , such as m=5,n=11, In the end m Monkeys will be picked away , This is related to m==n This situation It's the same , Therefore, the statement block only needs to have m--; To reduce the number of monkeys and continue; End this cycle .

stay m=1 Time indicates that there is only one monkey left , Jump out at the same time while loop , and a[1] Keep the monkey king's number , because a[] The remaining number of monkeys is always kept , When it has only one element , Nature is the number of the monkey king .

Post a similar code ：

#include<stdio.h>
int main()
{
	int m, n;
	int n_tem;
	int a[100];//max=100
	int b[100];
	scanf("%d%d", &m, &n);//input m&n
	for (int i = 0; i < m; i++)
		a[i] = i + 1;
	while (m != 1)
	{
		if (n < m)
		{
			for (int i = n; i < m; i++)
			{
				b[i - n] = a[i];
			}
			for (int i = 0; i < n - 1; i++)
			{
				b[m - n + i] = a[i];
			}
			for (int i = 0; i < m - 1; i++)
				a[i] = b[i];
			m--;
		}
		else if (n > m)
		{
			n_tem = n % m;
            if(n_tem==m)
            {
            m--;
            continue;
            }
			for (int i = n_tem; i < m; i++)
			{
				b[i - n_tem] = a[i];
			}
			for (int i = 0; i < n - 1; i++)
			{
				b[m - n_tem + i] = a[i];
			}
			for (int i = 0; i < m - 1; i++)
				a[i] = b[i];
			m--;
		}
		else
		{
			m--;
		}
	}
	printf("%d", a[0]);
	return 0;
}

The only difference between this code and the above code is a[0] and b[0] Is to be used .

Solution 2 ：

#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
	int iId;
	struct node* next;
}*node;
int main()
{
	int m, n;
	node head = NULL;
	node new=NULL;
	node end=NULL;
	node temp = NULL;
	scanf("%d%d", &m,&n);
	for (int i = 0; i < m; i++)
	{
		new = (node)malloc(sizeof(struct node));
		new->iId = i + 1;
		if (head == NULL)
		{
			head = new;
			end = new;
		}
		else
		{
			end->next = new;
			end = new;
		}
	}
	new->next = head;
	temp = head;
	node temp_pos=NULL;
	while (m > 1)
	{
		for (int i = 1; i <= n; i++)
		{
			if (i == n - 1)
			{
				temp_pos = temp->next;
				temp->next = temp->next->next;
				free(temp_pos);
				m--;
				continue;
			}
			temp = temp->next;
		}
			
	}
	printf("%d", temp->iId);
	return 0;
}

         This is the second solution written by bloggers , Next, let me give you a simple idea . Compared with the first solution , The idea is much simpler . Let's create a circular linked list first , It is not difficult to create a circular linked list , If not, please refer to this blog post ： Circular linked list × Double linked list (C Language ). After successfully creating the circular linked list , Then release the selected monkey nodes by counting , Before that, connect the previous node of the node with its next node to form a circular linked list .

        We are the first 32 Lines of code temp The pointer points to the logical queue head node , And then in 33 OK defines a temp_pos The pointer is used in 38 Yes if Point to in the judgment structure temp Next node of , in fact temp_pos Node is the monkey node we want to select .

        In this solution , The node we are going to pick is still No n Nodes , So in 38 Yes if Judge when in the structure i==n-1 namely temp When the pointer points to the previous node of the monkey node we want to pick , To execute the contents of the judgment statement block .

Hypothesis number 1 40 The diagram after code execution is as follows ：

  So the first 41 The figure after line code execution is ：

  The first 42 The figure after line code execution is ：

  The first 46 The figure after line code execution is ：

  That's all for this blog post .

---

Welcome to correct my last blog ：typedef And the structure

My next blog ： To be continued