单向循环链表（如何实现约瑟夫环）

电玩女神 2023-02-13 05:49 12阅读 0赞

**约瑟夫问题：总共有n个人排成一圈，从某个人开始，按顺时针方向依次编号。从编号为1的人开始顺时针报数1（下一个报号2），报到m的人退出圈子然后重新从1开始顺时针报数。这样不断循环下去，圈子里的人将不断减少。要求全部人员输出退出顺序。**

#include<stdio.h>
    #include<stdlib.h> 
    struct Node{ 
    	int num;
    	Node *next;
    };
    
    int main(){ 
    	int len, a=2;
    	Node *end, *r;
    	end = (Node*)malloc(sizeof(Node));
    	r = (Node*)malloc(sizeof(Node));
    	scanf("%d", &len);
    	
    	//尾插法构建循环链表 
    	end->num=1;
    	end->next=end;
    	for(int i=1; i<len; i++){ 
    		Node *s = (Node*)malloc(sizeof(Node));
    		s->num=a++;
    		s->next=end->next;
    		end->next=s;
    		end=s;
    	}
    	
    	//开始报数杀人
    	int m, count=0;
    	scanf("%d", &m);
    	r = end;
    	
    	while(1){ 
    		//数到 m 杀一人 
    		if(count==m-1){ 
    			count=0;
    			printf("每次被杀的序号:%d\n", r->next->num);
    			r->next=r->next->next; 
    			len--;
    			if(len==0){ 
    				break;
    			}
    		}
    		count++;
    		r = r->next;
    	}
    	
    	return 0;
    }

一直将自己的学习经验分享给有需要的人。  
我是小郑，一个坚持不懈的小白

发表评论取消回复

表情：

评论列表（有 0 条评论，12人围观）

还没有评论，来说两句吧...

相关阅读

相关约瑟夫环问题（顺序表和单向链表）

问题描述：设有n个人站成一圈，每个人有不同的编号i（1<=i<=n），即i∈\{1，2，3，4，·····，n\}，从编号为1的人开始按顺时针方向“1，2，3，···，m”循环

超、凢脫俗/ 2023年07月05日 13:12/ 0 赞/ 28 阅读

相关单向循环链表-约瑟夫问题JAVA

package linkedlist; public class Josepfu { public static void mai

「爱情、让人受尽委屈。」/ 2023年05月30日 09:11/ 0 赞/ 49 阅读

相关单向循环链表（如何实现约瑟夫环）

约瑟夫问题：总共有n个人排成一圈，从某个人开始，按顺时针方向依次编号。从编号为1的人开始顺时针报数1（下一个报号2），报到m的人退出圈子然后重新从1开始顺时针报数。这样不断循环

电玩女神/ 2023年02月13日 05:49/ 0 赞/ 13 阅读

相关 PHP实现单向链表解决约瑟夫环问题

约瑟夫环问题：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆

痛定思痛。/ 2022年09月22日 11:39/ 0 赞/ 193 阅读

相关单循环链表--约瑟夫环

include <stdio.h> include <stdlib.h> //单链表类型定义 typedef struct node

男娘i/ 2022年06月17日 07:23/ 0 赞/ 262 阅读

相关单链表实现约瑟夫环

来历：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第

悠悠/ 2022年05月12日 09:06/ 0 赞/ 252 阅读

相关约瑟夫环-(数组、循环链表、数学)

约瑟夫环（[约瑟夫问题][Link 1]）是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他

╰+哭是因爲堅強的太久メ/ 2022年05月08日 05:24/ 0 赞/ 271 阅读

相关链表实现约瑟夫环

include<stdio.h> include<malloc.h> define false 0; define ok 1;

左手的ㄟ右手/ 2022年04月22日 12:06/ 0 赞/ 245 阅读

相关循环链表解决约瑟夫环问题

　　约瑟夫环问题可以简单的使用数组的方式实现，但是现在我使用循环链表的方法来实现，因为上午看到一道面试题规定使用循环链表解决约瑟夫环问题。　　什么是约瑟夫环？　　“约瑟

Love The Way You Lie/ 2022年04月10日 08:22/ 0 赞/ 266 阅读

相关【数据结构】单向循环链表应用-约瑟夫环

编号1,2,...n的n个人按顺时针方向围坐在一圈,每人持有一个密码.一开始任选一个正整数作为报数上限值m,从第一个开始按顺时针方向自1开始顺序报数,报到m时停止报数.报m的人

落日映苍穹つ/ 2022年03月07日 05:40/ 0 赞/ 251 阅读