作业帮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/05/02 17:58:59
![C语言：有n个人围成一圈,顺序排号.从第一个人开始报数（从1到3报 数）,凡报到3的人退出圈子 问最后留下#includestid-i(void){main(){while(1){int n,i,a[100],k=0,b[100];for(i=1;i](/uploads/image/z/7793152-16-2.jpg?t=C%E8%AF%AD%E8%A8%80%EF%BC%9A%E6%9C%89n%E4%B8%AA%E4%BA%BA%E5%9B%B4%E6%88%90%E4%B8%80%E5%9C%88%2C%E9%A1%BA%E5%BA%8F%E6%8E%92%E5%8F%B7.%E4%BB%8E%E7%AC%AC%E4%B8%80%E4%B8%AA%E4%BA%BA%E5%BC%80%E5%A7%8B%E6%8A%A5%E6%95%B0%EF%BC%88%E4%BB%8E1%E5%88%B03%E6%8A%A5+%E6%95%B0%EF%BC%89%2C%E5%87%A1%E6%8A%A5%E5%88%B03%E7%9A%84%E4%BA%BA%E9%80%80%E5%87%BA%E5%9C%88%E5%AD%90+%E9%97%AE%E6%9C%80%E5%90%8E%E7%95%99%E4%B8%8B%23includestid-i%28void%29%7Bmain%28%29%7Bwhile%281%29%7Bint+n%2Ci%2Ca%5B100%5D%2Ck%3D0%2Cb%5B100%5D%3Bfor%28i%3D1%3Bi)
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