数据结构——练习之约瑟夫环问题

爱被打了一巴掌 2022-07-03 12:22 112阅读 0赞

# 数据结构——练习之约瑟夫环问题 #

约瑟夫环是一个数学的应用问题:已知n个人(以编号1，2，3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列;他的下一个人又从1开始报数，数到m的那个人又出列;依此规律重复下去，直到圆桌周围的人全部出列。很简单，直接附上代码了：

#include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    #include <string.h>
    
    /**定义人的数据对象的结构体**/
    struct node{
    	int id;
    	struct node *next;
    };
    typedef struct node NodeList;
    /**函数声明**/
    NodeList* InitList(int n);
    void FindM(NodeList *list,int m,int n);
    
    /**初始化**/
    NodeList* InitList(int n){
    	NodeList *head,*pre,*p;
    	head = (NodeList *)malloc(sizeof(NodeList));
    	head->next = NULL;
    	head->id = 1;
    	pre = head;
    	for(int i =2;i<=n;i++){
    		p = (NodeList *)malloc(sizeof(NodeList));
    		p->id = i;
    		pre->next = p;
    		pre = p;
    	}
    	p->next = head;
    	return head;
    }
    /**剔除数到m的人**/
    void FindM(NodeList *list,int m,int n){
    	NodeList *pre = list;
    	NodeList *p;
    	int i = 1;
    	while(pre->id!=pre->next->id){
    		if(i==m-1){
    			p = (NodeList *)malloc(sizeof(NodeList));
    			p = pre ;
    		}else if(i==m){
    			p->next = pre->next;
    			printf("Delete %d\n",pre->id);
    			n--;
    			i=0;
    		}
    		i++;
    		pre = pre->next;
    	}
    	printf("Delete %d\n",pre->id);
    }
    void main(){
    	NodeList *h;
    	int n,m;
    	printf("Input the number of people:");
    	scanf("%d",&n);
    	printf("Input the number to count:");
    	scanf("%d",&m);
    	h = InitList(n);
    	FindM(h,m,n);
    	system("pause");
    }

发表评论取消回复

表情：

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

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

相关阅读

相关【go写数据结构】练习--约瑟夫环

git地址：https://gitee.com/HappyTeemo/go\_for\_algorithm 约瑟夫环 19个人报数，1-3，当谁报数为3，谁就淘汰。现在

川长思鸟来/ 2022年12月12日 04:53/ 0 赞/ 136 阅读

相关约瑟夫环问题

题目：n 个数字（0,1,…,n-1）形成一个圆圈，从数字 0 开始，每次从这个圆圈中删除第 m 个数字（第一个为当前数字本身，第二个为当前数字的下一个数字）。当一个

分手后的思念是犯贱/ 2022年08月08日 00:57/ 0 赞/ 48 阅读

相关约瑟夫环问题

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

╰半橙微兮°/ 2022年08月02日 06:12/ 0 赞/ 32 阅读

相关数据结构——练习之约瑟夫环问题

数据结构——练习之约瑟夫环问题约瑟夫环是一个数学的应用问题:已知n个人(以编号1，2，3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出

爱被打了一巴掌/ 2022年07月03日 12:22/ 0 赞/ 113 阅读

相关约瑟夫环问题

list1 = [1 for _ in range(30)] 用1代表活人,0代表死人,先创建一个30个活人的列表 index = 0 索引,用来遍历

青旅半醒/ 2022年05月30日 10:39/ 0 赞/ 233 阅读

相关约瑟夫环问题

问题描述： N个人围成一圈，从第一个开始报数，第M个将淘汰，退出圈外，重复上述过程n-1次，最后剩下一个，最后留下来的人获胜。求出最后获胜者的编号。 if __n

╰+哭是因爲堅強的太久メ/ 2022年05月17日 01:20/ 0 赞/ 220 阅读

相关约瑟夫环问题

/ 约瑟夫环问题(Josephus) 用户输入M,N值，从1至N开始顺序循环数数，每数到M输出该数值，直至全部输出。写出C程序。（约瑟夫环问题 Joseph

青旅半醒/ 2022年03月27日 14:54/ 0 赞/ 301 阅读

相关约瑟夫环问题

先贴着慢慢研究： [https://www.cnblogs.com/cmmdc/p/7216726.html][https_www.cnblogs.com_cmmdc_

àì夳堔傛蜴生んèń/ 2022年03月17日 14:14/ 0 赞/ 262 阅读

相关约瑟夫环问题

转载自[https://my.oschina.net/jack90john/blog/1791110?p=1][https_my.oschina.net_jack90john_

拼搏现实的明天。/ 2022年03月01日 04:12/ 0 赞/ 307 阅读

相关约瑟夫环问题

问题描述 1 - n 个人围坐一圈，约定编号为k的人开始报数，数到m的那个人出列，直到所有人出列，由此产生一个队编号的序列问题分析 1. 先构造一个环形的单向

叁歲伎倆/ 2021年11月01日 22:40/ 0 赞/ 377 阅读