网站建设方案的内容,手机网站开发如何设置触摸功能,云服务器如何搭建,网络营销策划有限公司描述 编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数#xff0c;报到 m 的人离开。 下一个人继续从 1 开始报数。 n-1 轮结束以后#xff0c;只剩下一个人#xff0c;问最后留下的这个人编号是多少#xff1f; O(n) 示例1 好环形链表的约瑟夫问题是一个经典的问… 描述 编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数报到 m 的人离开。 下一个人继续从 1 开始报数。 n-1 轮结束以后只剩下一个人问最后留下的这个人编号是多少 O(n) 示例1 好环形链表的约瑟夫问题是一个经典的问题它的描述如下有n个人围成一圈从第一个人开始报数报到m的人出圈剩下的人继续从1开始报数直到剩下最后一个人。现在给定n和m求最后剩下的人的编号 这个问题可以使用环形链表来解决。具体来说我们可以先构建一个包含n个节点的环形链表然后从第一个节点开始遍历链表每次遍历m个节点将第m个节点从链表中删除。重复这个过程直到链表中只剩下一个节点为止这个节点就是最后剩下的节点 输入 5,2 返回值 3 说明 开始5个人 12345 从1开始报数1-12-2编号为2的人离开 1345从3开始报数3-14-2编号为4的人离开 135从5开始报数5-11-2编号为1的人离开 35从3开始报数3-15-2编号为5的人离开 最后留下人的编号是3 示例2 输入 1,1 复制 返回值 1 关于环形链表的约瑟夫问题具体思路如下 首先创建一个环形链表链表中每个节点代表一个人节点编号从1开始递增。 然后从第一个节点开始报数每报到第m个人就将该节点从链表中删除。 删除节点后从下一个节点重新开始报数重复上述步骤直到只剩下一个节点为止。 下面是C代码实现
#include iostream
using namespace std;struct ListNode {int val;ListNode* next;ListNode(int x) : val(x), next(NULL) {}
};int josephus(int n, int m) {ListNode* head new ListNode(1);ListNode* cur head;for (int i 2; i n; i) {cur-next new ListNode(i);cur cur-next;}cur-next head; // 将链表首尾相连while (cur-next ! cur) { // 只剩下一个节点时结束循环for (int i 1; i m; i) {cur cur-next;}ListNode* tmp cur-next;cur-next tmp-next;delete tmp;}int ans cur-val;delete cur;return ans;
}int main() {int n, m;cin n m;cout josephus(n, m) endl;return 0;
}C语言代码实现
#include stdio.h
#include stdlib.h// 定义链表节点结构体
typedef struct Node {int num; // 节点编号struct Node *next; // 指向下一个节点的指针
} Node;// 创建环形链表
Node *createList(int n) {Node *head NULL, *tail NULL;for (int i 1; i n; i) {Node *p (Node *)malloc(sizeof(Node));p-num i;if (head NULL) {head p;} else {tail-next p;}tail p;}tail-next head; // 将尾节点指向头节点形成环形链表return head;
}// 约瑟夫问题求解
void josephus(Node *head, int m) {Node *p head, *prev NULL;while (p-next ! p) { // 只剩下一个节点时结束循环for (int i 1; i m; i) {prev p;p p-next;}prev-next p-next; // 删除节点printf(%d , p-num);free(p);p prev-next; // 从下一个节点重新开始报数}printf(%d\n, p-num);free(p);
}int main() {int n, m;printf(请输入总人数n和报数m);scanf(%d%d, n, m);Node *head createList(n);josephus(head, m);return 0;
}
