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

这样做可以,不过时间复杂度不太好,为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