作业帮C语言：有n个人围成一圈,顺序排号.从第一个人开始报数（从1到3报 数）,凡报到3的人退出圈子 问最后留下#includestid-i(void){main(){while(1){int n,i,a[100],k=0,b[100];for(i=1;i
来源：学生作业帮助网 编辑：作业帮 时间：2024/11/09 10:20:16
C语言：有n个人围成一圈,顺序排号.从第一个人开始报数（从1到3报 数）,凡报到3的人退出圈子 问最后留下#includestid-i(void){main(){while(1){int n,i,a[100],k=0,b[100];for(i=1;i
C语言：有n个人围成一圈,顺序排号.从第一个人开始报数（从1到3报 数）,凡报到3的人退出圈子 问最后留下
#include
stid-i(void)
{
main()
{
while(1){int n,i,a[100],k=0,b[100];
for(i=1;i
C语言：有n个人围成一圈,顺序排号.从第一个人开始报数（从1到3报 数）,凡报到3的人退出圈子 问最后留下#includestid-i(void){main(){while(1){int n,i,a[100],k=0,b[100];for(i=1;i
这样做可以,不过时间复杂度不太好,为O(n ^ 2).
事实上,约瑟夫问题存在着时间复杂度为O(n)的解法.
要解决这个问题,要用到同余这个数学工具.
下面,假设目前还剩下K个人,这K个人从1到M报数,那么,当第M个人被杀后,剩下的人将按照怎样的规则报数呢?
如果我们将第M个人被杀后,第P个人报的数计做Q,那么可以得到下面的同余式：
（P - M % K) % K = Q
将上式变形可以得出：
P = （ Q + M）% K
那么可以知道,在第（N - K + 2）轮报数为Q的人,在第（N - K + 1）轮的报数为 （ Q + M）% K.
又易知,最后剩下的人,在最后一轮的报数必然为1,那么可以利用同余式倒推其原始编号：
（（（1 + M）% 2 + M） % 3）+ M % 4.
变成程序为：
#include
using namespace std;
const int M = 3;
int main(){
int n,i,ind;
printf("please input a number:");
scanf("%d",&n);
ind = 1;
for( i = 2; i