Description

有N个士兵站成一队列, 现在需要选择几个士兵派去侦察。
为了选择合适的士兵, 多次进行如下操作: 如果队列超过三个士兵, 那么去除掉所有站立位置为奇数的士兵, 
或者是去除掉所有站立位置为偶数的士兵。直到不超过三个战士，他们将被送去侦察。现要求统计按这样的方法，
总共可能有多少种不同的正好三个士兵去侦察的士兵组合方案。

注: 按上法得到少于三士兵的情况不统计。

1 <= N <= 2的32次方-1

输入格式

有多行，每行一个数字N，最后一行是0

输出格式

对每一行的数字N，输出针对N的方案数

直到没有数字

输入样例

10
4
0

输出样例

2
0

作者

admin

　　巡逻的士兵—递推。试从n=3开始一直往后写，就能得到这么一个递推公式：如果n为偶数那么答案a[n]=2*a[n/2]; 如果为奇数则为a[n]=a[n/2]+a[n/2+1];直接递归可以压线过，，但先预处理一小部分再在递归时用记忆化的话会快很多。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <cctype>
 6 #include <cmath>
 7 #include <algorithm>
 8 #include <set>
 9 #include <map>
10 #include <queue>
11 #include <stack>
12 #include <utility>
13 #include <vector>
14 #define ll long long
15 #define inf 0x3f3f3f3f
16 using namespace std;
17 
18 int a[5005];//用于预处理的数组
19 int recur(int n)
20 {
21     if(n<=5000)
22         return a[n];
23     else if(n%2)
24         return recur(n>>1)+recur((n>>1)+1);
25     else
26         return recur(n>>1)*2;
27 }
28 int main()
29 {
30     //freopen("input.txt","r",stdin);
31     memset(a,0,sizeof(a));
32     a[3]=1;
33     for(int i=4;i<=5005;i++)
34     {
35         if(i%2) //奇数
36             a[i]=a[i>>1]+a[(i>>1)+1];
37         else   //偶数
38             a[i]=2*a[i>>1];
39     }
40     //
41     int n;
42     while(scanf("%d",&n)&&n)
43         printf("%d
",recur(n));
44     return 0;
45 }