约瑟夫环问题：一圈共有N个人，从1开始报数，报到M的人OUT，然后重新开始报数，问最后OUT的人是谁？【N=10，M=3】
/* ①数组:遇到一次m count+1 直到count=n 结束 / 循环n-1次 不用count计算 / 从后往前推: 》j = 0 》for i 从 2 到 n： 》》j = （m+j）%i 》》最终第j个人会留下来(如果从1开始编号就是第j+1个人最终会留下来。 */ /* ②**递推思想：递推公式：可以用一个式子来表示数列{an}的第n项与它前一项或几项的关系 **找规律** 当有n个人时，变成一个子问题 （n-1）个人的报数问题，编号依次为0 1 2 3 ... n-1 ，求最后一轮的人在第一轮中的编号。【对于最后一轮来说，最后留下来的人正是最后一轮开始报数的人。我们只需要求出相邻的两轮之间，同一个人在后一轮的编号和在前一轮里的编号，那么就可以求出来这个人在倒数第二轮里的编号，求出倒数第二轮的对应编号，那么这个人对应在倒数第三轮的也能求出……直到对应到第一轮。】 例：n=5 m=5 每一轮编号都从开始报数的那个人开始算，那么第二轮出列的人在第二轮的编号是(m-1)%(n-1)，在第一轮编号为[m + (m - 1) % (n-1)]%n。剩下各轮也是这样。 编号： 0 1 2 3 4 报数人：1 2 3 4 5 【5人 第一轮：报数为m的人编号为(m-1)%n，出列； 1 2 3 4 【4人 第二轮：有n - 1个人，编号为(m+0)%n的开始报数 2 3 4 【3人 2 4 【2人 4 【1人 so此轮编号为(m+i)%n的人将做为下一轮编号为i的人; 编号为F(n-1)的人肯定对应着上一轮的F(n) 所以有 F[n]=(F[n-1]+m)%n (n>1) 【F[1]=0 ：剩最后一个人 此人编号为0】 **[补充知识]**求余、取模 区分 ex：4/3=1.3 求余 4/(-3)=1 商值向0方向舍弃小数位 4rem -3=1 取模 4/(-3)=2 商值向0方向舍弃小数位为 4mod -3=-2 唯一的区别在于： 当x和y的正负号一样的时候，两个函数结果是等同的；当x和y的符号不同时，rem函数结果的符号和x的一样，而mod和y一样。 */ #include<stdio.h> int main() { int n,m; while(scanf("%d %d",&n,&m)!=EOF) { int i,result=0; for(i=2;i<=n;i++) result=(result+m)%i; printf("%d\n",result+1); } return 0; } /* ③单向循环链表 */