题目:假设有n头待宰的猪,杀猪的人比较变态,他会先杀单数位置上的猪,一次杀完之后,将剩下的猪按照原来的相对位置,又从1开始排列,接着宰单数位置上的猪,直到最后杀完为止。那里有压迫哪里就有反抗,有这么变态的屠夫,就有非常聪明的猪猪。问题是最聪明的猪会站在什么位置,才能保证最后一个被宰?
解这道题目的思路跟约瑟夫环有点类似:
首先在只有一头猪的时候,最后被宰的猪的位置肯定为1;
接着递推,假设在n=m的时候,这头猪的位置(最后一头被宰的)为k。那么,在n = 2 * m(因为每次要杀掉差不多一半的猪)的时候,它的位置应该是2*k。
一直晚上推,直到n为指定猪的数目。
unsigned int getLastPig(unsigned int n) { if(1 >= n) return 1; unsigned int res(1); for(unsigned int nb(2); nb <= n; nb <<= 1) { res <<= 1; } return res; }
举个例子,假设总共有5头猪:
1, 2, 3, 4, 5 ---> 2, 4 ----> 1, 2 ---> 2 ---> 1
测试代码
int main(int argc, char** argv) { for(unsigned int n = 1; n < 10; ++n) { std::cout << getLastPig(n) << std::endl; } return 0; }