免费域名网站,oa软件定制开发,不良网站举报中心官网,中国卫生健康网官网著名的 Josephus 问题#xff1a; 据说著名犹太历史学家Josephus#xff08;弗拉维奥约瑟夫斯#xff09;有过以下的故事#xff1a;在罗马人占领乔塔帕特后#xff0c;39 个犹太人与Josephus及他的朋友躲到一个洞中#xff0c;39个犹太人决定宁愿死也不要被敌人抓到 据说著名犹太历史学家Josephus弗拉维奥·约瑟夫斯有过以下的故事在罗马人占领乔塔帕特后39 个犹太人与Josephus及他的朋友躲到一个洞中39个犹太人决定宁愿死也不要被敌人抓到于是决定了一个自杀方式41个人排成一个圆圈由第1个人开始报数每报数到第3人该人就必须自杀然后再由下一个重新报数直到所有人都自杀身亡为止。 然而Josephus 和他的朋友并不想遵从。首先从一个人开始越过k-2个人因为第一个人已经被越过并杀掉第k个人。接着再越过k-1个人并杀掉第k个人。这个过程沿着圆圈一直进行直到最终只剩下一个人留下这个人就可以继续活着。 问题是给定了和一开始要站在什么地方才能避免被处决。Josephus要他的朋友先假装遵从他将朋友与自己安排在第16个与第31个位置于是逃过了这场死亡游戏。 NC132 环形链表的约瑟夫问题 解题思路 1根据n来创建不带头单向循环链表
2逢m就删除当前节点
示例代码
/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param n int整型 * param m int整型 * return int整型*/
typedef struct ListNode ListNode;
//创建新节点
ListNode* BuyNode(int x)
{ListNode* newNode (ListNode*)malloc(sizeof(ListNode));newNode-val x;newNode-next NULL;return newNode;
}//创建链表
ListNode* CreateList(int n)
{ListNode* phead BuyNode(1);ListNode* ptail phead;for(int i 2; i n; i){ptail-next BuyNode(i);ptail ptail-next;}//循环ptail-next phead;return phead;
}
int ysf(int n, int m ) {//创建单向循环链表ListNode* head CreateList(n);ListNode* pcur head;ListNode* prev NULL;int count 1;//逢m删除节点while(pcur-next ! pcur){if(count m){//删除节点prev-next pcur-next;free(pcur);//删除pcur节点后让pcur走到新的位置count置为初始值重新计数pcur prev-next;count 1;}else{//往后找prev pcur;pcur pcur-next;count;}}return pcur-val;
}
小问题
若 m 1 时第一次进循环就要删除 pcur而此时的 prev 还是为空
解决办法
CreatList 方法不返回头节点而是返回尾节点。这样既能知道第一个节点的前驱节点也可以通过尾节点找到第一个节点。
