poj1781In Danger（删数） 递归问题

链接

之前队内赛中的一道题目 当时怎么想也没想到，就一直放到了今天，刚才看另一题的讲解突然看到时拿这个题作为引子来讲的，就仔细看了下。

参考《《具体数学》》 p7。 Joscphus问题

开始是讲了一个古老的故事，说J和同伴陷入险境，大家不愿做俘虏，就想了个游戏来进行自杀，每第二个人就要去死。。J觉得这样很傻，并很快的算出了自己该在的位置，逃脱了这无聊的自杀。由此引出了这个有趣的算法。

这本书上讲的很清楚， 我就大体概括一下。

可以先从10个人来看 很明显第一次死掉的是全部的偶数， 然后是 是3 7 1 9.那么J（10） = 5；

可以猜测所有的J（n)都为奇数，因为第一轮就杀掉了全部的偶数，很明显。。

然后再猜J（n) = n/2? 很明显 不是。不过假如有2N个人 第一次还是杀掉所有的偶数 那么剩下了n个数，那么这n个数不就是跟之前的n同样来处理。。，

只不过编号变成了原来的2*i -1. 所以J(20) = 2*j(10)-1 = 9; 类推 J（40） = 17 所以得出j（5*2^m） = 2^(m+1)+1;

那么奇数呢，类似可知 J（2n+1) = 2*J(n)+1；

所以归纳可得

j(1) = 1;

j(2n) = 2j(n)-1;

j(2n+1） = 2j(n)+1;

这样是很快的，每次以减少2倍或多的速度来算，不过这可关乎J的性命，所以J还得想更快的方法才能确保他逃得过此劫。

那么继续看 1  2 3  4 5 6 7  8 9 10 11 12 13 14 15  16

　　　　　1   1 3  1 3 5 7  1 3 5 7 9 11  13 15 17   1

下面对的是J（n)的值 ，结论应该可以猜出来了，与2的幂有关。

结论：对于每一个n可以写成n=2^m+k的形式 。那么J（2^m+k) = 2k+1;

上式是由 上上的递归式推出来的，书上用的归纳法，数学不好就不再证了。

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 #include<vector>
 7 #include<cmath>
 8 #include<queue>
 9 #include<set>
10 using namespace std;
11 #define N 100000
12 #define LL long long
13 #define INF 0xfffffff
14 const double eps = 1e-8;
15 const double pi = acos(-1.0);
16 const double inf = ~0u>>2;
17 int main()
18 {
19     int n,m;
20     char c;
21     while(cin>>n>>c>>m)
22     {
23         if(!n&&!m) break;
24         n = n*pow(10.0,m);
25         int k = log(n*1.0)/log(2.0);
26         int s = pow(2.0,k);
27         cout<<(n-s)*2+1<<endl;
28     }
29     return 0;
30 }

View Code

poj1781In Danger（删数） 递归问题,布布扣,bubuko.com

poj1781In Danger（删数） 递归问题

原文：http://www.cnblogs.com/shangyu/p/3597712.html