北理工LeXue乐学题目

可能有误，仅供参考，每周一/三早八,按时间排序了,暂不分类,从第四周开始

第四周

2024.09.10 约瑟夫问题

展开查看 约瑟夫问题是一个经典的问题（大一我们讲过）。这个问题可以用数组，也可以用链表。作为复习，大家可以试试你自己的算法。 已知n个人（不妨分别以编号1，2，3，…，n 代表 ）围坐在一张圆桌周围，从编号为 k 的人开始，从1开始顺时针报数1, 2, 3, ...，顺时针数到m 的那个人，出列并输出。然后从出列的下一个人开始，从1开始继续顺时针报数，数到m的那个人，出列并输出，…依此重复下去，直到圆桌周围的人全部出列。 输入：n, k, m 输出：按照出列的顺序依次输出出列人的编号，编号中间相隔一个空格,每10个编号为一行。 非法输入的对应输出如下 a) 输入：：n、k、m任一个小于1 输出：n,m,k must bigger than 0. b) 输入：k>n 输出：k should not bigger than n. 例: 输入：9,3,2 输出：4 6 8 1 3 7 2 9 5 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
    int data;
    struct Node* next;
} NODE;
NODE* createNode(int data)
{
    NODE* newNode = (NODE*)malloc(sizeof(NODE));
    newNode->data = data;
    newNode->next = newNode; // 初始化为指向自身
    return newNode;
}
// 插入节点到循环链表的末尾
void insertNode(NODE** head, int data)
{
    NODE* newNode = createNode(data);
    if (*head == NULL)
    {
        *head = newNode; // 如果链表为空，新的节点成为头节点
    }
    else
    {
        NODE* temp = *head;
        while (temp->next != *head)
        {
            temp = temp->next; // 找到最后一个节点
        }
        temp->next = newNode; // 将最后一个节点的next指向新节点
    }
    newNode->next = *head; // 新节点指向头节点，形成循环
}
void freeList(NODE* head) 
{
    if (head == NULL) return;
    NODE* current = head;
    NODE* nextNode;
    do {
        nextNode = current->next;
        free(current);
        current = nextNode;
    } while (current != head);
}
void baka(int k, NODE** head)
{
    NODE* temp = *head;
    for (int i = 1; i < k; i++)
    {
        temp = temp->next;
    }
    *head = temp;
}
int cirno(int m, NODE** head)
{
    int data;
    NODE* temp = *head;
    for (int i = 1; i < m - 1; i++)
        temp = temp->next;
    data = temp->next->data;
    *head = temp->next->next;
    temp->next = NULL;
    temp->next = *head;
    return data;
}
int main() {
    NODE* head = NULL;
    int n, k, m;
    scanf("%d,%d,%d", &n, &k, &m);
    if (n < 1 || m <1 || k <1)
    {
        printf("n,m,k must bigger than 0.\n");
        return 0;
    }
    if (k > n)
    {
        printf("k should not bigger than n.\n");
        return 0;
    }
    for (int i = 1; i <= n; i++)
        insertNode(&head, i);//构建data为顺序的循环链表
    baka(k, &head);//将head挪到第k个元素
    int count=0,j, x, past = 0;
    for (j = 0; ; j++)
    {
        if (j == 10)
        {
            putchar('\n');
            j = 0;
        }
        x = cirno(m, &head);
        if (x == past)
            break;
        else if (j == 0)
            ;
        else 
            putchar(' ');
        printf("%d",x );//从头节点遍历到第m个，再改变头节点
        count++;
        past = x;
        
    }
    if(count==0||count%10!=0)
        putchar('\n');
    freeList(head);
    return 0;
}