C语言:有n个人围成一圈,顺序排号。从第一个人开始报数(从1到3报 数),凡报到3的人退出圈子 问最后留下

[复制链接]
查看11 | 回复1 | 2010-12-12 17:07:17 | 显示全部楼层 |阅读模式
#include
stid-i(void)
{
main()
{
while(1){int n,i,a[100],k=0,b[100];
for(i=1;i<=100;i++)
{a=1;b=0;
}
printf("please input a number:");
scanf("%d",&n);
while(1){for(i=1;i<=n;i++)

{b[k]=a+b[k];

if(b[k]==3){a=0;k++;}

if(b[k]==a)break;

}
}

printf("the net is%d",i);
}}
wo keyi zhe yang zuo ma ????

回复

使用道具 举报

千问 | 2010-12-12 17:07:17 | 显示全部楼层
这样做可以,不过时间复杂度不太好,为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,那么可以
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

主题

0

回帖

4882万

积分

论坛元老

Rank: 8Rank: 8

积分
48824836
热门排行