- POJ 1012 - Joseph
- Time: 1000MS
- Memory: 10000K
- 难度: 初级
- 分类: 递推关系
问题描述
有 k 个坏人 k 个好人坐成一圈，前 k 个为好人（编号 1~k），后 k 个为坏人(编号 k+1~2k)
现在有一个报数 m，从编号为 1 的人开始报数，报到 m 的人就要自动死去。
问当 m 为什么值时，可以使得在出现好人死亡之前，k 个坏人先全部死掉？
注意 ：
- 当前一轮第 m 个人死去后，下一轮的编号为 1 的人 为 前一轮编号为 m+1 的人
- 前一轮恰好是最后一个人死掉，则下一轮循环回到开头那个人报 “1”
解题思路
经典的约瑟夫水题。
由于 k 值比较小（1~13），暴力枚举 m 就可以了
递推公式为：
ans[i]; // 第i轮杀掉 对应当前轮的编号为ans[i]的人
ans[0]=0;
ans[i]=(ans[i-1]+m-1)%(n-i+1); // i>1, 总人数n=2k 则n-i为第i轮剩余的人数有耐心的同学可以自己推导一下公式，推导时要注意 2 点:
第一点：每轮都是以前一轮死掉的人的后一个人作为 “1” 开始顺序编号的。
如： k=2 (n=4) m=7
1
4
3
2那么最初的编号如下：
第一轮报数后，3 号被杀掉，那么以 3 号后面的一个人 “4” 作为下一轮的 “1” 重新编号：
第二点： f[i]=(f[i-1]+m)%(n-i); (i>1)
这是网上一些地方给出的递推公式，对于本题而言是不正确的。因为这种递推公式针对的是从 0 开始报数的 Joseph，本题是从 1 开始报数的，必须要变形
最后就是由于本题 k 值有限，只有 13 个值，那么 POJ 的数据测试就极有可能重复测试每个 k 值的结果，为了节省总体时间，我们的程序只在第一次得到 k 值的时候计算 m 值，然后保存下来，当 k 值再次出现时，就直接把保存的结果输出，不再计算 m。这是在服务器打表的处理。
另外有了递推的程序后，我们就知道了每个 k 值对应的 m 值。
此时追求 0ms AC 的同学可以利用递推程序的结果，再写一个程序，直接在程序里面打表：
int Joseph[]={0,2,7,5,30,169,441,1872,7632,1740,93313,459901,1358657,2504881,1245064};
AC 源码
//Memory Time
//184K 250MS
#include<iostream>
using namespace std;
int main(void)
{
int Joseph[14]={0}; //打表，保存各个k值对应的m值
int k;
while(cin>>k)
{
if(!k)
break;
if(Joseph[k])
{
cout<<Joseph[k]<<endl;
continue;
}
int n=2*k; //总人数
int ans[30]={0}; //第i轮杀掉 对应当前轮的编号为ans[i]的人
//PS:每一轮都以报数为“1”的人开始重新编号
int m=1; //所求的最少的报数
for(int i=1;i<=k;i++) //轮数
{
ans[i]=(ans[i-1]+m-1)%(n-i+1); //n-i为剩余的人数
if(ans[i]<k) //把好人杀掉了,m值不是所求
{
i=0;
m++; //枚举m值
}
}
Joseph[k]=m;
cout<<m<<endl;
}
return 0;
}
