首页 > 试题广场 >

统计累加算式

[编程题]统计累加算式
  • 热度指数：312 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
一个正整数可以表示为多个正整数相加的表达式，表达式中的各个正整数要求都是2的幂。例如给定正整数7，它有下列六个符合要求的表达式：
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
因此，正整数7符合条件的表达式个数是6. 编写一个程序，对于给定的正整数N(1 <= N <= 1,000)，输出符合条件的表达式个数。要求：时间复杂度不高于O(N)。


输入描述:
一个整数（>=1并且<=1000）


输出描述:
表达式个数
示例1

输入

7

输出

6
算法知识视频讲解
添加回答
牛客473948637号头像 牛客473948637号
#include <stdio.h>
 
intmain()
{
    intnum = 0;
    inta[1000] = {0};
    scanf("%d\n", &num);
    if((num < 0)||(num > 1000))
    {
        printf("your input is out of range\n");
        return-1;
    }
     
    a[1] = 1;
    for(inti = 2; i <= num; i++)
    {
        if(i % 2 == 0)
        {
            a[i] = a[i - 1] + a[i / 2];
        }
        else
        {
            a[i] = a[i - 1];
        }
    }
    printf("%d\n", a[num]);
    return0;
}
先根据题目找出规律
当i为1时，有1种结果
当i为奇数时，有f(n-1)种结果
当i为偶数时，有f(n-1)+f(n/2)种结果
由规律采取递归方式，递归时，有很多都是之前计算过的，因此采用数组记录的方式，加快运行速度。
发表于 2020-08-24 21:37:53 回复(0)
牛客399552483号头像 牛客399552483号 
#include <iostream>
#include <cmath>
using namespace std;

int main()
{
	int a;
	cin >> a;
    int array[1000]={0};
    array[1] = 1;
    for(int i =2;i<=1000;i++)
    {
       if(i%2 == 0)
    {
        array[i] = array[i-1]+array[i/2];
    }
    else
    {
        array[i] = array[i-1];
    } 
    }
    
        
	cout << array[a] << endl;

}

发表于 2021-09-12 22:23:09 回复(0)
牛客469834578号头像 牛客469834578号 
#include<iostream>
using namespace std;
int main(void)
{
    int num;
    cin>>num;
    int dp[num];
    for(int i=0;i<=num;i++)
    {
        dp[i]=1;
    }
    int k=2;
    while(k<=num)
    {
        for(int j=k;j<=num;j++)
        {
            dp[j]=dp[j]+dp[j-k];
        }
        k=k*2;
    }
     
    cout<<dp[num];
}

发表于 2020-08-25 09:27:18 回复(0)
提交观点

问题信息

C++工程师 深信服
来自：深信服校园招聘c/c ...
上传者：小小
难度：
3条回答 2506浏览

热门推荐

通过挑战的用户

相关试题

统计累加算式

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号