hnsfdxyc

用户名：00000152

访问量：21518

签　名：

等　　级
排　　名	395
经　　验	4927
参赛次数	0
文章发表	24
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

[编程入门]报数问题-约瑟夫问题进一步深化（链表）
浏览：159

创建三种基本链表你都会了吗？
浏览：482

Minesweeper -（用队列，bfs）
浏览：241

你可能喜欢

[编程入门]报数问题的两种解法（一点就会）

　　作者: hnsfdxyc　　　　发表时间：2019-06-21 22:04:29 浏览：1699　|　评论：1　

原题链接：[编程入门]报数问题

该题是著名的约瑟夫算法，这里我提供两种解法

------------
###### 
一、利用数组
```c
#include<stdio.h>
int main()
{
	//n为总人数，ko为淘汰的人数，num为开始报数 
	int n,i,a[100],ko=0,num=0;   
	scanf("%d",&n);
	for(i=0;i<n;i++)       
	{
		a[i]=i+1;             //为每个人编号 
	}
	i=0;
	while(ko!=n-1)     //只剩一个人时，结束循环 
	{
		if(a[i])        //当数组里的元素不为0时，继续报数 
			num++;
		if(num==3)      //当报数报到三时，标记此元素为0，淘汰人数加1 
		{
			a[i]=0;
			num=0;
			ko++;
		}
		i++;
		if(i==n)       //一圈结束后，从头开始 
			i=0;
	}
	for(i=0;i<n;i++)
	{
		if(a[i])
			printf("%d",i+1);   //别忘了+1 
	}
	return 0;
}
```
###### 二、递归
我们把题目抽象为N个人（编号0~(N-1))，从0开始报数，报到(M-1)的淘汰，剩下的人继续从0开始报数。求最后剩下者的编号。

- N个人编号如下：
![](/image_editor_upload/20190621095246_51651.png)

- 第一个淘汰的人是（M-1）%N，例如上图中，41个人中，报到3的人淘汰，则最后剩下人的编号是（3-1）%41=2。编号（M-1)%N自杀后，剩下的人排列如下：
![](/image_editor_upload/20190621095323_74158.png)

- 有人淘汰后，下一个位置M又从零开始报数，因此环应该如下：
![](/image_editor_upload/20190621095340_44114.png)

- 将上面的排列顺序重新编号：
![](/image_editor_upload/20190621095356_44094.png)

- 问题变为（N-1）个人，报到为（M-1）的人淘汰，问题规模减小了。这样一直进行下去，最后剩下编号为0的人。
用函数表示：

- ** F(1)=0**

- 当有2个人的时候（N=2），报到（M-1）的人淘汰，最后剩下的人是谁？应该是在只有一个人时，报数时得到的最后剩下的序号加上M，因为报到M-1的人已经淘汰，只剩下2个人，另一个就是最后剩下者，用函数表示：

- **F(2)=F(1)+M**

- 可以得到递推公式：

- ** F(i)=F(i-1)+M**

- 因为可能会超出总人数范围，所以要求模

- **F(i)=(F(i-1)+M)%i**

- 有了递推公式就可以在O（N）时间求出结果：
```cpp
	#include<iostream>
	#include<stdio.h>
	using namespace std;

int yuesefu(int n,int m){
			if(n == 1){
					return 0; //这里返回下标,从0开始，只有一个元素就是剩余的元素0
			}
			else{
					return (yuesefu(n-1,m) + m) % n; //我们传入的n是总共多少个数
			}
	}
	int main(void){
			int a,b;
			cin>>a>>b;
			cout<<yuesefu(a,b)<<endl;

//或者，直接循环迭代，求出来的result如上
			int result = 0;
			for(int i = 2;i <= a;i++){
					result = (result+b) %i;
			}
			cout<<"result = "<<result<<endl;
			return 0;
	}
	```

具体参考：
https://blog.csdn.net/KangRoger/article/details/39254619
http://tingyun.site/2018/04/26/%E7%BA%A6%E7%91%9F%E5%A4%AB%E7%8E%AF%E9%97%AE%E9%A2%98%E8%AF%A6%E8%A7%A3/

0.0分

10 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

代码纠错

SQL生成与解释

　　评论区

赵艳庆

if(num==3)      //当报数报到三时，标记此元素为0，淘汰人数加1 
        {
            a[i]=0;
            num=0;
            ko++;
        }
想问一下为什么这里的num==3变成n%3==0会出错

2021-11-02 15:36:45

hnsfdxyc

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

用筛法求之N内的素数。（C++代码）

转化为字符数组

P1001 （C++代码）

【蟠桃记】（C语言代码）

[编程入门]报数问题的两种解法（一点就会）

评论区

精彩推荐

九宫重排（C++代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

【金明的预算方案】（C++代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

Hello, world! （C++代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

字符逆序（C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

最好的，

hnsfdxyc

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

用筛法求之N内的素数。 （C++代码）

转化为字符数组

P1001 （C++代码）

【蟠桃记】 （C语言代码）

[编程入门]报数问题的两种解法（一点就会）

评论区

精彩推荐

九宫重排 （C++代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

【金明的预算方案】 （C++代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

Hello, world! （C++代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

字符逆序 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

最好的，

用筛法求之N内的素数。（C++代码）

【蟠桃记】（C语言代码）

　　评论区

九宫重排（C++代码）

【金明的预算方案】（C++代码）

字符逆序（C语言代码）