RX0_UNICORN 的学生作业:
// joseph.h
#ifndef __JOSEPH_H__
#define __JOSEPH_H__
#include
#include
typedef int datatype_t;
typedef struct node
{
datatype_t data;
struct node *next;
}loopnode_t;
extern loopnode_t *create_circular_linklist(int n);
extern void josephus_problem(int n, int k, int m);
#endif
// joseph.c
#include "joseph.h"
// 创建循环链表
loopnode_t *create_circular_linklist(int n) {
if (n data = 1;
loopnode_t *current = head;
for (int i = 2; i data = i;
current->next = newNode;
current = newNode;
}
// 将链表首尾相连形成循环
current->next = head;
return head;
}
// 解决约瑟夫问题
void josephus_problem(int n, int k, int m) {
// 创建循环链表
loopnode_t *head = createCircularLinkedList(n);
if (head == NULL) return;
// 移动到第k个节点
loopnode_t *current = head;
loopnode_t *prev = NULL;
// 找到第k个节点
for (int i = 1; i < k; i++) {
prev = current;
current = current->next;
}
while (current->next != current) {
// 数m-1次,因为当前节点从1开始计数
for (int i = 1; i < m; i++) {
prev = current;
current = current->next;
}
// 删除当前节点
prev->next = current->next;
printf("%d ", current->data);
// 如果不是最后一个节点,打印逗号分隔
if (current->next != prev->next) {
printf(" ");
}
loopnode_t *temp = current;
current = current->next;
free(temp);
}
// 处理最后一个节点
printf("%d\n", current->data);
free(current);
}
// main.c
#include "joseph.h"
int main(int argc, const char *argv[]) {
int n, k, m;
printf("please input n k m : ");
scanf("%d%d%d", &n, &k, &m);
printf("n = %d, k = %d, m = %d 时的出列序列:\n", n, k, m);
josephus_problem(n, k, m);
return 0;
}
【图片】