2的幂

2的幂

时间: 1ms        内存:128M

描述:

输入一个正整数n,输出用2的幂组合出n的方案数。
对于正整数7,它有6种表示方式:
1) 1+1+1+1+1+1+1
2) 1+1+1+1+1+2
3) 1+1+1+2+2
4) 1+1+1+4
5) 1+2+2+2
6) 1+2+4

输入:

一个正整数n,1<=n<=1000000

输出:

一个正整数,代表用2的幂组合出n的方案数,由于结果可能很大,仅保留后九位数字。

示例输入:

7

示例输出:

6

提示:

参考答案(内存最优[4908]):

#include<stdio.h>
#include<stdlib.h>

int main()
{
    int a,i;
    int m [1000005];
    while (scanf("%d",&a)==1)
    {
        m[1] = 1;
        for (i = 2; i <= a; i++)
        {
            if (i % 2 == 0)
            {
                m[i] = (m[i - 1]+m[ i / 2])%1000000000;
            }
            else
            {
                m[i] = m[i - 1]%1000000000;
            }
        }
        printf("%d\n", m[a]%1000000000);
    }
    return 0;
}

参考答案(时间最优[3]):

#include <iostream>

using namespace std;
int s[1000001];
typedef long long ll;
int main()
{
    ll N;
    cin>>N;

    s[1]=1;
    s[2]=2;
    for(int i=3; i<=N; i++)
    {

        if(i%2!=0)
            s[i]=s[i-1];
        else
        {
            s[i]=s[i-2]+s[i/2];
            s[i]=s[i]%1000000000;
        }
    }
    cout<<s[N]<<endl;
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注