hnsfdxyc

用户名：00000152

访问量：24643

签　名：

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

　　自我简介：

TA的其他文章

树了解一下（c++）
浏览：362

图的深度优先遍历
浏览：314

你可能喜欢

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

A+B for Input-Output Practice (IV) （C语言代码）

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

　　作者: hnsfdxyc　　　　发表时间：2019-06-21 22:04:29 浏览：1870　|　评论：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编程助手吧

　　评论区

赵艳庆

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二级辅导-阶乘数列（C语言代码）

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

A+B for Input-Output Practice (IV) （C语言代码）

C二级辅导-求偶数和（C语言代码）

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

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

评论区

精彩推荐

分糖果（C++代码）

WU-C语言程序设计教程（第三版）课后习题11.11 （C++代码）（想学链表的可以看看）

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

1124题解

川哥的吩咐（C语言代码）

链表数据求和操作（C语言代码）

生日日数（C语言代码）

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

众数问题（C语言代码）

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

hnsfdxyc

TA的其他文章

你可能喜欢

C二级辅导-阶乘数列 （C语言代码）

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

A+B for Input-Output Practice (IV) （C语言代码）

C二级辅导-求偶数和 （C语言代码）

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

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

评论区

精彩推荐

分糖果 （C++代码）

WU-C语言程序设计教程（第三版）课后习题11.11 （C++代码）（想学链表的可以看看）

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

1124题解

川哥的吩咐 （C语言代码）

链表数据求和操作 （C语言代码）

生日日数 （C语言代码）

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

众数问题 （C语言代码）

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

C二级辅导-阶乘数列（C语言代码）

C二级辅导-求偶数和（C语言代码）

　　评论区

分糖果（C++代码）

川哥的吩咐（C语言代码）

链表数据求和操作（C语言代码）

生日日数（C语言代码）

众数问题（C语言代码）