洛谷 数的计算 高精度算法

Question

怎么用高精度来计算呢

1.不作任何处理；

2.在它的左边加上一个正整数,但该正整数不能超过原数的一半；

3.加上数后,继续按此规则进行处理,直到不能再加正整数为止。

看谁能先找出具有以上性质数的个数(包含输入的正整数n)

算法设计思路提示：找到递推公式，当n为偶数时n%2==0，f(n)=f(n-1)+f(n/2)；当n为奇数时n%2==1 ，f(n)=f(n-1)。

编程语言

Answer 1

#include <iostream>
using namespace std;
long long dp[1005];
int main()
{
    int n;
    cin>>n;
    dp[0]=1;dp[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(i%2!=0)
            dp[i]=dp[i-1];
        else
            dp[i]=dp[i-1]+dp[i/2];
    }
    cout<<dp[n]<<endl;

    return 0;
}