1. Joseph Ring problem
N people numbered 1, 2,..., n sit around a round table in a clockwise direction, each holding a password (positive integer). At the beginning, select a positive integer m as the upper limit value of counting, start counting from 1 clockwise from the first person, stop counting when reporting to m, and the person reporting to m will be listed. Take his password as the new m value, start counting from 1 again from the next person in the clockwise direction, and the person counting to m will be listed again; This continues until all the people around the round table are listed. It is required to output the number of n individuals in the order of listing.
Input format:
In the first line, enter two integers, representing the number of people n and the initialization password m, separated by spaces. In the second line, enter n integers to represent the passwords of n individuals, separated by spaces.
Output format:
Output the number of each person in the column order, separated by spaces.
Input example:
A set of inputs is given here. For example:
7 20 3 1 7 2 4 8 4
Output example:
The corresponding output is given here. For example:
6 1 4 7 2 3 5 //No blank lines at the end
Answer:
#include<stdio.h>
#include<stdlib.h>
typedef struct node {
int number;
int password;
struct node * next;
}Node, *List;
int main() {
List head = NULL;
List prev = NULL;
int numbers, password;
scanf("%d%d", &numbers, &password);
for (int i = 1; i <= numbers; i++) {
List pnew = (List)malloc(sizeof(Node));
if (head == NULL) {
head = pnew;
prev = pnew;
}
prev->next = pnew;
pnew->number = i;
scanf("%d", &pnew->password);
pnew->next = head;
prev = pnew;
}
List p = head;
while (p != prev) {
for (int i = 0; i < password - 1; i++) {
p = p->next;
prev = prev->next;
}
password = p->password;
printf("%d ", p->number);
prev->next = p->next;
List t = p;
p = p->next;
free(t);
}
printf("%d ", p->number);
return 0;
}
2. Joseph's permutation problem Step1
N people numbered 1, 2,..., n sit around a round table in a clockwise direction. Given a positive integer m ≤ n, start counting from 1 in a clockwise direction from the first person, make it out of the line every time he checks in M, start counting from 1 again from the next person in a clockwise direction, and the person counting to m is out of the line again. This continues until all the people around the round table are listed. Each person's queue order defines an arrangement of integers 1, 2, 3,..., n. This arrangement is called a (n,m) Josephus arrangement. For example: (7, 3) Josephus is arranged as 3, 6, 2, 7, 5, 1, 4.
Input format:
Enter two integers, number n and password m, separated by spaces.
Output format:
Output the number of each person in the column order, separated by spaces.
Input example:
A set of inputs is given here. For example:
7 3 //No blank lines at the end
Output example:
The corresponding output is given here. For example:
3 6 2 7 5 1 4 //No blank lines at the end
Answer:
#include<stdio.h>
#include<stdlib.h>
typedef struct node {
int number;
struct node * next;
}Node, *List;
int main() {
List head = (List)malloc(sizeof(Node));
head->next = head;
List prev = head;
int numbers, password;
scanf("%d%d", &numbers, &password);
for (int i = 1; i <= numbers; i++) {
List pnew = (List)malloc(sizeof(Node));
prev->next = pnew;
pnew->number = i;
pnew->next = head;
prev = pnew;
}
List p = head->next;
prev = head;
while (head->next != head) {
for (int i = 0; i < password - 1; i++) {
if (p->next == head) {
p = p->next;
prev = prev->next;
}
p = p->next;
prev = prev->next;
}
if (p->next == head) {
printf("%d ", p->number);
prev->next = head;
prev = head;
List t = p;
p = head->next;
free(t);
} else {
printf("%d ", p->number);
prev->next = p->next;
List t = p;
p = p->next;
free(t);
}
}
return 0;
}
3. Josephus permutation problem step 2
For a given number of k in 1, 2, 3,..., N, Josephus wants to know whether there is a positive integer m(m ≤ n), so that the last number of k arranged by Josephus (n,m) is exactly the number of k specified in advance. For example, when n is 7, k is 4, and the last k numbers of the specified arrangement are 7,5,1,4; Because (7,3) Josephus is arranged as 3,6,2,7,5,1,4; So the value of M is 3.
Input format:
Enter m and k in the first line, and the number of k specified in the second line, separated by spaces.
Output format:
If there is a positive integer m satisfying the condition, M is output; Otherwise output 0.
Input example:
A set of inputs is given here. For example:
7 4 7 5 1 4
Output example:
The corresponding output is given here. For example:
3 //No blank lines at the end
Answer:
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int number;
struct node * next;
}Node, *List;
List head = NULL;
List pFront = NULL;
List per = NULL;
int n, m;
int b[100], k;
void Create();
void Joseph(int number, int m);
int main() {
scanf("%d %d", &n, &m);
int i;
int a[n];
for (i = n - m ; i < n; i++) {
scanf("%d", &a[i]);
}
for (i = 1; i <= n; i++) {
head = NULL;
pFront = NULL;
k = 0;
int flag = 1;
Create();
per = head;
Joseph(n, i);
for (int j = n - m; j < n; j++) {
if (a[j] != b[j]) {
flag = 0;
}
}
if (flag == 1) {
printf("%d", i);
return 0;
}
}
return 0;
}
void Create() {
List tail;
for (int i = 0; i < n; i++) {
List pnew;
pnew = (List) malloc(sizeof(Node));
pnew->number = i + 1;
if (head == NULL) {
head = pnew;
} else {
tail->next = pnew;
}
tail = pnew;
}
tail->next = head;
pFront = tail;
}
void Joseph(int number, int m) {
if (number == 0) {
return;
}
int count = 1;
List p = NULL;
while (count != m) {
per = per->next;
pFront = pFront->next;
count++;
}
p = per;
pFront->next = per->next;
if(number == 1) {
b[k++] = p->number;
} else {
b[k++] = p->number;
}
per = per->next;
free(p);
Joseph(number - 1, m);
}