洛谷P1028 数的计算 C++
题目
我们要求找出具有下列性质数的个数(包含输入的自然数n):
先输入一个自然数n(n≤1000),然后对此自然数按照如下方法进行处理:
1、不作任何处理;
2、在它的左边加上一个自然数,但该自然数不能超过原数的一半;
3、加上数后,继续按此规则进行处理,直到不能再加自然数为止.
输入格式
1个自然数n(n≤1000)
输出格式
1个整数，表示具有该性质数的个数。
输入输出样例
输入 #1
6
输出 #1
6
说明/提示
满足条件的数为
6，16，26，126，36，136
原题链接—>链接
分析
先说一下感受，刚看完题，（md他到底想表达什么，不清不楚。6左边+3=9？9/2=4，4+9=13？，13/2=6，6+13=19？ 哪里有＋到是0的时候？什么破题）遂，去google查看了一番。原来题目不是我想的样子，而是左边+一个数，是在左边放上一个数 （例如： 2 左边＋1是12， 是一个新的数）。
具体情况分析：
0的情况： 0 左边没法加了 所以 f(0)=1
1的情况： 1 01 1和01是一回事 所以f(1)=1
2的情况： 2 12 f(2)=2
3： 3 13 f(3)=2
....
方法1
由数学归纳法，得递推公式
f(i)=f(i-1)+f(i/2);
f(偶数)=f(奇数); eg:f(6)=f(7)
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
int n;
cin >> n;
int f[10001];
memset(f,0, sizeof(f));
f[0]=1;
for (int i = 1; i <=n ; ++i) {
if(i%2!=0) f[i]=f[i-1]; //奇数的情况 等于偶数的情况（相邻的偶数=奇数-1）
else f[i]=f[i-1]+f[i/2];
}
cout << f[n];
return 0;
}
方法 2
函数递归，设计递归函数，大问题划分为小问题，设置递归出口。
下边代码的思路是正确的，但是只能部分AC，原因很简单，递归地本质是不断地调用函数，所以时间上会很慢，没办法全部AC
#include <iostream>
using namespace std;
void f(int n,unsigned long long &count)
{
if(n==0) return;
for (int i = 1; i <= n/2 ; ++i) {
count++;
f(i,count);
}
}
int main()
{
int n;
cin >> n;
unsigned long long count=1;//鉴于这样的数会太多，所以定义地长一些
f(n,count);
cout << count;
return 0;
}
