RX0_UNICORN 的學生作業(yè):
// 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"
// 創(chuàng)建循環(huán)鏈表
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;
}
// 將鏈表首尾相連形成循環(huán)
current->next = head;
return head;
}
// 解決約瑟夫問題
void josephus_problem(int n, int k, int m) {
// 創(chuàng)建循環(huán)鏈表
loopnode_t *head = createCircularLinkedList(n);
if (head == NULL) return;
// 移動到第k個節(jié)點
loopnode_t *current = head;
loopnode_t *prev = NULL;
// 找到第k個節(jié)點
for (int i = 1; i < k; i++) {
prev = current;
current = current->next;
}
while (current->next != current) {
// 數(shù)m-1次,因為當前節(jié)點從1開始計數(shù)
for (int i = 1; i < m; i++) {
prev = current;
current = current->next;
}
// 刪除當前節(jié)點
prev->next = current->next;
printf("%d ", current->data);
// 如果不是最后一個節(jié)點,打印逗號分隔
if (current->next != prev->next) {
printf(" ");
}
loopnode_t *temp = current;
current = current->next;
free(temp);
}
// 處理最后一個節(jié)點
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;
}
【圖片】