Analysis and solution of a classical Joseph problem

                                            Analysis and solution of a classic Joseph problem

One 、 The origin of Joseph's problem

　　 Joseph's question （Josephus） It was by ancient Roman historian Joseph （ full name Titus Flavius Josephus） Proposed . It is a classical problem in computer science and Mathematics . In the algorithms of computer programming , A similar problem is called Josephus ring .( More , Please see the Programmers are on the road )
　　Josephus yes 1 A Jewish historian in the th century . He wrote in his diary , He and his 40 Three comrades were surrounded by Roman troops in the cave . They discussed suicide or capture , Finally decided to commit suicide , And draw lots to decide who kills who .41 Individuals in a circle , From the first 1 Individual starts counting , Count to 3 You have to kill yourself , And then count again by the next , Until everyone killed himself . However Josephus And his friends didn't want to comply . Start with one person , Skip over k-2 personal （ Because the first one has been crossed ）, And kill No k personal . next , Over again k-1 personal , And kill No k personal . The process goes all the way around the circle , Until there's only one left , This man can live on .Josephus Arrange friends with yourself in the first 16 And 31 A place , So I escaped the game of death .
　　 Joseph's problem General description form by ： It has a number of 1,2,……,n Of N A circle of individuals , From 1 Individual starts counting , To report for duty M Stop reporting when , newspaper M People out of circles , And then from his next person to report , To report for duty M Stop reporting when , newspaper M Out of the loop ,……, Follow this rule , Until everyone is out of the circle . When any given N and M after , Build relevant data structures and algorithms to solve N The order in which individuals go out of circles .

Two 、 Typical examples

　　 Yes n A circle of individuals , Sequence number . Count from the first person （ from 1 To 3 Number off ）, Where to report 3 Of the people out of the circle , Ask the last person who stayed is the original number .

3、 ... and 、 Analysis answers

　　 You can use the data structure of array or circular linked list to solve this problem . Each has its advantages. . Array implementation is simple , But the logic is complicated . Circular links are logically simple , It's complicated to implement . Here are two ways to solve this problem .

       3.1 Use an array to store data

　　 Use an array to save this N Personal serial number , Design two counters , One k As a counting counter , One m As the exit counter . Start counting from the first person （ The array subscript i=0）, Counter k To 3 After clearing , At the end of the array element check-in, start with the first person . Everyone who quits , The corresponding array elements are set to 0, Only for non when counting 0 Element count , When counter m To n-1 It means there is only one person left , At this time, the algorithm ends , Output the number of the remaining person .

#include<stdio.h>
#define NMAX 50

int main(){

	//k  Count counter 
	//m  Exit counter 
	int i,k,m,n,num[NMAX];

	scanf("%d",&n);

   // to N Write the serial number of the individual 
	for(i=0;i<n;i++){
		num[i] = i+1;
	
	}

	i = k = m =0;
    // m = n-1   There is only one person left 
	while(m < n -1){
	
		// The value of the current position is not 0, Count , by 0 The representative quit 
		if(num[i] != 0){

			k++;
		}

	// Counter K=3 Number of positions exit , The exit position is marked as 0. Counter to 0 Recount . Number of exits m+1;
		if(k == 3){
		
			num[i] = 0;
			m++;
			k = 0;
		}

		i++;

		if(i == n){
		
			i = 0;
		}
	}

	// Output the last number left 
	    i= 0;
		while(num[i] ==0){
		
			i++;
		}

		printf("Left is %d\n", num[i]);
	
		return 0;

}

       3.2  Use circular linked list to store data

　　 Use circular linked list to store N Personal serial number . Will check in k=3 The node of is removed from the circular linked list summary , Finally, there is only one node left, and the cycle ends , Output the number of the remaining person .（ Among them, the counter K The value of can be customized ）

#include<stdio.h>
#include<stdlib.h>

typedef struct Num_node{

	int data;
	struct Num_node  *next;

}Num_Node;

int main(){

    	//n  The total number of ,m The number of people who quit ,k Count counter 
    	int n,k;
        Num_Node  *head = NULL , *tail =NULL,  *p = NULL;

		int i=0;
        // Input N, Then initialize the linked list 
    	scanf("%d",&n);
		while(i++<n){
		
				// The memory space occupied by the application node 
				if( (p = (Num_Node *)malloc(sizeof(Num_Node))) == NULL){
				
					printf("memery is not available");
					exit(1);

				}

				p->data = i;
				p->next = NULL;

				// The current application is for the first node 
				if(head == NULL){

					head = tail = p;
			
				}else{
					// Tail interpolation 
				
					tail->next = p;
					tail = p;
				
				}
				// If it's the last element , Make it point head: This forms a circular linked list 
				if(i == n){
					tail->next = head;
				}
		}

		// Always check in k=3 The node of is removed from the linked list .（ This k You can define yourself , as long as K<N Just go ）
		k = 3;
		p = head;

        Num_Node  *pre_p = NULL; //p The forerunner of , Delete p When , You need to use this pointer .

		while(p->next != p)  // until p Point to your , There is only one element left .
		{ 
				for(i = 1; i < k; i++)
				{
					pre_p = p;
					p = p->next;
				}
				pre_p->next = p->next;
				free(p);                      //  Delete node , Release the memory space occupied by this node from memory 
				p = pre_p->next;      
		}


		printf("Left is %d \n",p->data);

       return 0;
}

3、 ... and 、 summary

　　 Joseph problem is a classical computer and mathematical problem , Long-standing , The solutions are also different . The two methods above , Array is used respectively 、 Circular linked list data structure to analyze this topic , Although it can be solved , But the complexity of logic is very different . Among them, we can see the importance of data structure in the process of solving problems , Proper data structure will greatly reduce the difficulty of problem solving .