问题来源
约瑟夫是犹太军队的一个将军，在反抗罗马的起义中，他所率领的军队被击溃，只剩下残余的部队40余人，他们都是宁死不屈的人，所以不愿投降做叛徒。一群人表决说要死，所以用一种策略来先后kill所有人。于是约瑟夫建议：每次由其他两人一起kill一个人，而被kill的人的先后顺序是由抽签决定的，约瑟夫有预谋地抽到了最后一签，在kill了除了他和剩余那个人之外的最后一人，他劝服了另外一个没死的人投降了罗马。
大致题意
在一间房间总共有n个人（下标0～n-1），只能有最后一个人活命。
按照如下规则去清除人：
- 所有人围成一圈
- 顺时针报数，每次报到m的人将被清除掉
- 被清除掉的人将从房间内被移走
- 然后从被kill掉的下一个人重新报数，继续报数，报m的再清除，直到剩余一人
警示注意
用队列或链表模拟的话时间会超限（时间复杂度为n!）
思路分析
过程（找规律）：
1、第一轮下标为m-1的人被清除
2、将m看成0，之后的加1，一一对应，将完全变成从0到n-2的情况
对应情况为：
0，1，2，3，4，5，，，，m-1，m，，，，n-2，n-1（共n个数，删m-1）
m，，，，n-2，n-1，0，1，2，3，4，5，，，m-2(删m-1后，m变成第0个数，共n-1个数)
0，1，2，3，4，5，，，，m-1，m，，，，n-3，n-2(把上一列转换（一一对应）)
推出规律====> 假设从0到n-2获胜的人是X，（根据转换规则）则从0到n-1获胜的是(X+m)%n
实现代码
易懂型
#include "stdio.h"
#include "stdlib.h"
int main(void)
{
int n, m,i, f[20]={0};
scanf("%d %d",&n,&m);
for(i=2;i<=n;i++)
{
f[i]=(f[i-1]+m)%i;
printf("%d个人报数，报到%d的出列，最后的胜者下标为%d\n", i,m,f[i]);
}
printf("The winner is %d\n", f[n]+1);
system("pause");
}优化型
#include<iostream>
using namespace std;
//约瑟夫函数实现
int cir(int n,int m)
{
int p=0;
for(int i=2;i<=n;i++)
{
p=(p+m)%i;
}
return p+1;
}
int main()
{
int n,m;
cin>>n>>m;
//调用输出
int num=cir(n,m);
cout<<num;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/103309.html
