北理工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
#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;
}

2024.09.18

展开查看 约瑟夫问题是一个经典的问题，我们不妨将这个经典问题进行扩展，变成一个双向的约瑟夫问题。

　　已知 n 个人（不妨分别以编号 1，2，3，…，n 代表 ）围坐在一张圆桌周围，首先从编号为 k 的人从 1 开始顺时针报数，1, 2, 3, …，记下顺时针数到 m 的那个人，同时从编号为 k 的人开始逆时针报数，1, 2, 3, …，数到 m 后，两个人同时出列。然后从出列的下一个人又从 1 开始继续进行双向报数，数到 m 的那两个人同时出列，…；。依此重复下去，直到圆桌周围的人全部出列。直到圆桌周围只剩一个人为止。

　　如果双向报数报到 m 时落在同一个人身上，那本次出列的只有一个人。

　　例如：5,1,2。则总共5个人，从1开始顺时针报数，数到2，定位编号2；同时从1开始报数数到2，定位编号5；2和5同时出列。然后继续开始报数，顺时针报数3,4，定位到4；逆时针报数4,3，定位3；4和3同时出列。最后剩余的为编号1。输出为：2-5,4-3,1,。

　　如果输入：6,2,3。则输出：4-6,2,1-3,5,。其中第2次只输出一个2，表示第二次双向报数时，恰好都落在编号2上，所以只有一个编号出列。

输入：
n,k,m

输出：
按照出列的顺序依次输出编号。同时出列编号中间用减号”-”连接。

非法输入的对应输出如下
a)

输入：n、k、m任一个为0
输出：n,m,k must bigger than 0.

b)

输入：k>n
输出：k should not bigger than n.

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
#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
    int data;
    struct Node* next;
    struct Node* prev;
} NODE;
NODE* createNode(int data)
{
    NODE* newNode = (NODE*)malloc(sizeof(NODE));
    newNode->data = data;
    newNode->next = newNode;
    newNode->prev = newNode;// 初始化为指向自身
    return newNode;
}
void makeNode(NODE** head, int data) 
{
    Node* newNode = createNode(data);
    if (*head == NULL)
    {
        *head = newNode;
    }
    else
    {
        Node* tail = (*head)->prev;
        tail->next = newNode;
        newNode->prev = tail;
        newNode->next = *head;
        (*head)->prev = newNode;
    }
}
void pos(NODE* head,NODE** fp, NODE** dp, int k)
{
    *fp = head;
    *dp = head;
    while ((*fp)->data!=k)
    {
        *fp = (*fp)->next;
        *dp = (*dp)->next;
    }
    //printf("%d,%d\n", (*fp)->data, (*dp)->data);
}
void delNode(int count,int m,NODE**fp,NODE**dp)
{
    while (count > 0)
    {
        for (int j = 1; j < m; j++)
        {
            *fp = (*fp)->next;
            *dp = (*dp)->prev;
        }
        
        if ((*fp)->data == (*dp)->data)
        {
            printf("%d", (*fp)->data);
            count--;
        }
        else
        {
            printf("%d-%d", (*fp)->data, (*dp)->data);
            count -= 2;
        }
        (*fp)->prev->next = (*fp)->next;
        (*fp)->next->prev = (*fp)->prev;
        *fp = (*fp)->next;
        (*dp)->prev->next = (*dp)->next;
        (*dp)->next->prev = (*dp)->prev;
        *dp = (*dp)->prev;
        //if (count >0)不是？？？这末尾还得有逗号吗
            printf(",");
    }
    putchar('\n');
}
int main()
{
    NODE* head=NULL;
    int n=0, k=0, m=0;
    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 = 0;i<n; i++)
    {
        makeNode(&head,i+1);
    }
    NODE* fp = NULL;
    NODE* dp = NULL;
    pos(head,&fp, &dp, k);//将顺逆指针移动到第k个位置
    delNode(n,m, &fp, &dp);
    return 0;
}