首页 > 代码库 > Poj 3517 And Then There Was One(约瑟夫环变形)
Poj 3517 And Then There Was One(约瑟夫环变形)
简单说一下约瑟夫环：约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。
想要求出最后剩下的那个人的在初始的时候的编号的话。
f[1]=0;
f[i]=(f[i-1]+m)%i; (i>1)
可以推出剩下i个人内叫到m的时候的编号。注意这是逆推。推到最后初始的时候的情况
#include<stdio.h>int main(void){ int i,n,k,m; int fn[10001]; while(scanf("%d%d%d",&n,&k,&m),n,k,m) { fn[1]=0; for(i=2;i<n;i++) fn[i]=(fn[i-1]+k)%i; printf("%d\n",(fn[n-1]+m)%n+1); } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。