Question

4. Joseph ring

【Problem description】

N people numbered as 1,2...,n sit in a circle in clockwise, and each has only one password of positive integer. Firstly a positive integer is arbitrarily selected as the upper limit value m, then numbering off from 1 to m in clockwise is carried out, and the person reporting m will leave the circle and his password will be used as the new m value for the next round of numbering off. This process will carry on until everyone has left. Design a program to obtain the sequence of people leaving the circle..

【Requirements】

Use the unidirectional circular linked list to simulate this process, and print out the number of each person in the sequence of leaving the circle.

【Test data】

The initial value of m is 20, n=7, and the password of the 7 people is 3,1,7,2,4,7,4, First m=6, (the correct sequence for leaving the circle should be 6,1,4,7,2,3,5).

【Implementation hint】

When the program begins to run, the user will be asked to input the initial limit value m, and then input the password of each person. The value of n can be set to equal or less than 30. There is no need for header node in the circular linked list used in this application. Please note the boundary between empty list and non-empty list.

Answer 1

//please check the test data once for the mentioned n=7,m=20(initially) the output should be [6,7,4,1,5,3,2] not  [6,1,4,7,2,3,5]

//the code goes as follows

#include<bits/stdc++.h>
using namespace std;

struct node
{
int info;
int cnt;
struct node *link;
};

int main()
{
int n,m,x; //n is for no of persons, m is for arbitrary value, x is to store password
struct node *ptr,*head=NULL,*prev=NULL;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
//creating a node of type struct
struct node *ptr=(struct node*)malloc(sizeof(struct node));
cin>>x;
ptr->info=x;
ptr->cnt=i;
ptr->link=NULL;
//for first node
if(head==NULL)
{
head=ptr;
prev=ptr;
}
else
{
prev->link=ptr;
prev=ptr;
ptr->link=head;
}
}
ptr=head;
prev=head;
while(ptr->link!=ptr)
{
for(int i=1;i<m;i++)
{
prev=ptr;
ptr=ptr->link;
}
cout<<ptr->cnt<<" ";
m=ptr->info;
prev->link=ptr->link;
ptr=prev->link;
}
cout<<ptr->cnt<<" ";
return 0;
}