约瑟夫环问题_数组解决_C语言-Toy模板网

这篇具有很好参考价值的文章主要介绍了约瑟夫环问题_数组解决_C语言。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一_题目

有n个人围成一个圈，开始报数，报到m的人出局，并且不再参加报数，依次类推，直到n个人全部出局为止。

二_分析

1.将抽象的问题实例化

假设有一个裁判：

mouth：取值范围 1~m （报到m的人出局）

finger：取值范围1~n （总共有n个人）

约瑟夫环问题_数组解决_C语言,C语言阶段相关习题总览,算法,c语言

2.对n，m赋值，个人模拟报数

假设

n==8 ， m==5

那么出局的人的依次是： 5 2 8 7 1 4 6 3

3.从个人模拟报数中发现问题

代码如下：（具体解释在代码注释中）

int n=0;  //参加报数的总人数 
int m=0;  //报到m的人出局

scanf("%d",&n);
scanf("%d",&m); 
//输入完毕 

int table[1005]={0};  //数据规模可以开大一些 
for(int i=1;i<=n;i++)  //将数组中的人先全部标号为 1 ，之后出局的人标号为 0 
{
	table[i]=1;
 } 
 
 //开始操作
 int mouth=0;  //1~m    //mouth==m怎么办？ 
 int finger=0;  //1~n   //table[finger]==0  怎么办？

易发现，问题的关键在于：

Ⅰ.mouth==m怎么办？

Ⅱ.table[finger]==0怎么办？

将以上两个问题思考清楚了，这个问题也就解决了。

4.解决问题

在代码中具体操作（多说无益，在问题中解决问题）：

 int cnt=n; //cnt需要实现--的操作，以结束代码 
 while(cnt!=0)  //表示还有人在参加报数
 {
 	mouth++;
 	finger++;
 	while(table[finger]==0)  //如果指到空位了的操作 
 	{
 		finger++;  //不管这个空位，finger继续++ 
 		if(finger>n)  //finger超过了总人数 
 		{
 			finger=1;  //重新将finger赋值为  1 
		 }
	 }
	 if(mouth==m)  //有人报到m这个数了，需要出局 
 	{
 		printf("%d ",finger);  //打印出局的人的编号
 		table[finger]=0;  //将出局的人标号为  0  ，表示不再参加报数 
		 cnt--;  //参加报数的人 --
		 mouth = 0;  //更新 mouth 的值 
	 }
 	
  }

三_总结

可以解决约瑟夫环问题的方法有很多种：

如，递归，链表等等。

本文仅仅介绍最为简单的一种（数组），学会本文万不可妄自菲薄，知识海洋深不见底，无人可窥之全貌。

下面将全部代码附上，请君观之，如有不足敬请指点！

#include<stdio.h>
int main()
{
  
int n=0;  //参加报数的总人数 
int m=0;  //报到m的人出局

scanf("%d",&n);
scanf("%d",&m); 
//输入完毕 

int table[1005]={0};  //数据规模可以开大一些 
for(int i=1;i<=n;i++)  //将数组中的人先全部标号为 1 ，之后出局的人标号为 0 
{
	table[i]=1;
 } 
 
 //开始操作
 int mouth=0;  //1~m    //mouth==m怎么办？ 
 int finger=0;  //1~n   //table[finger]== 0  怎么办？ 
 int cnt=n; //cnt需要实现--的操作，以结束代码 
 while(cnt!=0)  //表示还有人在参加报数
 {
 	mouth++;
 	finger++;
 	while(table[finger]==0)  //如果指到空位了的操作 
 	{
 		finger++;  //不管这个空位，finger继续++ 
 		if(finger>n)  //finger超过了总人数 
 		{
 			finger=1;  //重新将finger赋值为  1 
		 }
	 }
	 if(mouth==m)  //有人报到m这个数了，需要出局 
 	{
 		printf("%d ",finger);  //打印出局的人的编号
 		table[finger]=0;  //将出局的人标号为  0  ，表示不再参加报数 
		 cnt--;  //参加报数的人 --
		 mouth = 0;  //更新 mouth 的值 
	 }
 	
  }
  return 0;
}

文章来源地址https://www.toymoban.com/news/detail-769711.html

谢谢观看！

到了这里，关于约瑟夫环问题_数组解决_C语言的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！