Description

有N个士兵站成一队列, 现在需要选择几个士兵派去侦察。
为了选择合适的士兵, 多次进行如下操作: 如果队列超过三个士兵, 那么去除掉所有站立位置为奇数的士兵, 
或者是去除掉所有站立位置为偶数的士兵。直到不超过三个战士，他们将被送去侦察。现有一个“聪明”的士兵，
经常通过选择站在合适的初始位置，成功避免被选中去侦察。这引起了陈教官的注意。陈教官希望你编写一个程序，
当给定士兵数之后，输出有多少个位置上的士兵是不可能被选中去巡逻的。注: 按上法得到少于三士兵的情况不用去巡逻。1 <= N <= 21亿

输入格式

有多行（可能有上百行，请尽量优化代码），每行一个数字N，最后一行是0

输出格式

对每一行的数字N，不可能被选中去巡逻的位置数直到没有数字

输入样例

10
6
0

输出样例

4
0

 题意：

对于n个士兵每次去除站在奇数位或站在偶数位的士兵，最终若剩三个人，则将那三个人抓去巡逻，求不可能被抓去巡逻的位置数量。

分析：

在巡逻的士兵当中已经求出f（n），即被抓去巡逻的士兵的方案数，每一种方案对应3个位置被抓去巡逻，那么最多有3*f（n）个位置被抓去巡逻，那么答案就应该是n-3*f（n）

#include <iostream> 
#include <algorithm>
using namespace std;
const int N=1e8;
int d[N];
int f(int n){if(n<N&&d[n]){return d[n];}if(n<3){return 0;}if(n==3){return 1;}int t=f(n/2)+f((n+1)/2);if(n<N){d[n]=t;}return t;
}int main(){int n;while(cin>>n&&n){cout<<n-3*f(n)<<endl;}return 0;
}

#include <iostream> 
#include <algorithm>
using namespace std;
int f(int n){if(n<3){return 0;}else if(n==3){return 1;}else{if(n%2==0){return 2*f(n/2);}else{return f(n/2)+f((n+1)/2);}}
}int main(){int n;while(cin>>n&&n){cout<<n-3*f(n)<<endl;}return 0;
}

小故事大全