ZOJ 1088 System Overload

时间:2023-03-08 16:50:30
ZOJ 1088 System Overload

原题链接

题目大意:浙大的破网络容量有限,太多人同时使用BBS就会系统崩溃。为了保持系统正常工作,过载时就需要切断部分用户。规则是把玉泉所有的建筑从1到n编号,设定一个常数m。从1开始数,第m幢建筑的网络被切断,然后再从1开始继续往下数。数到n之后回到第1幢。曹光彪大楼的编号是2,这是计算机学院的大本营。此题的目的就是根据上述规则,确定常数m,使得曹楼是全校最后一幢被切断网络的建筑。

解法:在数学界有一个经典的约瑟夫环问题(Josephus Problem)。约瑟夫环问题是这样的,有n个人围成一个圈,分别编号为1,2,3…n,从第1个人开始报数,报到偶数的人出列,剩下的人继续,直到仅剩最后一个人位置。那么,如果我想做这个站到最后的人,最开始我应该站在哪个编号的位置?如果是隔2个人报数,我又应该站在哪里?如果是隔k个人呢?我在Google上搜索的时候看到有人推荐一本书《具体数学》。在这本书的第一章(也许第二章)里有详细的分析和证明。

这道题和约瑟夫环的问题也差不多,指是从后往前倒推。要保证坚持到最后的人是2号,起始位置是1号,报数的间隔是多少。间隔数m从2开始往上一个个地试。判断的精髓就是这个递归公式:k=(k+m-1)%i+1。如果经过n-1次的递归计算,k的值是1,那么这个m就是所求的答案了。

参考代码:

#include<iostream>
using namespace std; int main(){
int n,m,i,k;
while(cin>>n&&n!=0){
for(m=2;m<32767;m++){
k=1;
for(i=2;i<n;i++)
k=(k+m-1)%i+1; //Josephus Problem
if(k==1){
cout<<m<<endl;
break;
} }
} return 0;
}