约瑟夫问题

约瑟夫问题

题目描述

$n$ 个人围成一圈，从第一个人开始报数,数到 $m$ 的人出列，再由下一个人重新从 $1$ 开始报数，数到 $m$ 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。

输入格式

输入两个整数 $n,m$。

输出格式

输出一行 $n$ 个整数，按顺序输出每个出圈人的编号。

样例 #1

样例输入 #1

10 3

样例输出 #1

3 6 9 2 7 1 8 5 10 4

提示

$1\le m,n\le 100$

题解

#include<stdio.h>
#include<stdlib.h>
struct node {int ID;struct node* next;
};
struct node* add_to_list(struct node* p, int id)
{struct node* new_node = malloc(sizeof(struct node));p->next = new_node;new_node->next = NULL;new_node->ID = id;return new_node;
}
//在尾部插入并且赋值IDint main(void)
{int n = 0, m = 0;scanf("%d%d", &m, &n);struct node* head = malloc(sizeof(struct node));head->ID = 1;head->next = NULL;struct node* end = head;for (int i = 2; i <= m; i++){end = add_to_list(end, i);}end->next = head;//尾部指向头部，构成循环链表for (int i = 1; i <= m; i++){for (int x = 1; x <= n - 2; x++){head = head->next;}if (i >= 2) printf(" ");printf("%d", (head->next)->ID);struct node* cur=(head->next);head->next = (head->next)->next;head = head->next;free(cur);//释放被删除结点的内存}
}

循环链表