约瑟夫问题、圆桌问题

1.约瑟夫问题：

有n个人，编号为1~n，从第一个人开始报数，从1开始报，报到m的人会死掉，然后从第m+1个人开始，重复以上过程。在死了n-1个人后，问最后一个人的编号是？

1.学前代码

#include<stdio.h> #include<string.h> #include<stdlib.h> int main() { int n,i,m; while(scanf("%d%d",&n,&m)!=EOF) {int j=0,a[200]={0},k=0; for(i=0;i<n;i++) a[i]=1; for(i=1;i<m+1;i=i%m+1) { if(a[j]==1&&i==m) { a[j]=0; k++; if(k==n-1) break; j=(j+1)%n;//向后移j+1，范围为0~n-1 continue; } if(a[j]==0) { j=(j+1)%n; i--; continue; } j=(j+1)%n; } for(i=0;i<n;i++) { if(a[i]==1) printf("%d\n",i+1); } } }

2.进阶：

#include <cstdio> int n,k; int main() { scanf("%d %d",&n,&k); int ans=0; for(int i=1;i<=n;i++) ans=(ans+k)%i; printf("%d",ans+1); }

衍生： 圆桌问题：

圆桌上围坐着2n个人。其中n个人是好人，另外n个人是坏人。如果从第一个人开始数数，数到第m个人，则立即处死该人；然后从被处死的人之后开始数数，再将数到的第m个人处死……依此方法不断处死围坐在圆桌上的人。试问预先应如何安排这些好人与坏人的座位，能使得在处死n个人之后，圆桌上围坐的剩余的n个人全是好人。