首页 > 试题广场 >

整数拆分

[编程题]整数拆分

热度指数：28763 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

一个整数总可以拆分为2的幂的和，例如： 7=1+2+4 7=1+2+2+2 7=1+1+1+4 7=1+1+1+2+2 7=1+1+1+1+1+2 7=1+1+1+1+1+1+1 总共有六种不同的拆分方式。再比如：4可以拆分成：4 = 4，4 = 1 + 1 + 1 + 1，4 = 2 + 2，4=1+1+2。用f(n)表示n的不同拆分的种数，例如f(7)=6. 要求编写程序，读入n(不超过1000000)，输出f(n)%1000000000。

输入描述:

每组输入包括一个整数：N(1<=N<=1000000)。

输出描述:

对于每组数据，输出f(n)%1000000000。

示例1

输入

输出

算法知识视频讲解

健康快乐最重要

发表于 2020-03-02 15:43:33

被动态规划玩儿坏了。。。首先说明思路：每一个数都可以拆成2的次幂的形式，2的次幂有（1，2，4，6，8...），其中只包括一个奇数，那就是1。假设给定一个数N：1.N是奇数，那么N拆分的时候必定有一个1，因为2的次幂除了1都是偶数，由很多偶数不可能构成奇数。所以 f(N)=f(N-1)举例：展开全文

烤肉__

发表于 2022-01-26 20:16:22

当成完全背包求解是最容易想到的方法 #include <iostream> #include <algorithm> using namespace std; const int N = 1e6 + 10, mod = 1000000000; int n; int f[N 展开全文

flyflyfly00

发表于 2021-04-23 11:12:23

搬运一下思路：记f(n)为n的划分数，我们有递推公式： f(2m + 1) = f(2m)，f(2m) = f(2m - 1) + f(m)，初始条件：f(1) = 1。证明: 证明的要点是考虑划分中是否有1。记:A(n) = n的所有划分组成的集合，B(n) = n的所有含有1的划分组成的展开全文

philos

发表于 2021-02-03 17:00:03

思路对于一个数字 n，如果 n 是奇数，那么 n 的所有组合方式中一定包含一个 1，那么它和 n-1 的组合方式种数相同，dp[n] = dp[n-1]；如果 n 是偶数，那么它的组合方式中可能有 1，也可能没有 1，有 1 的组合方式有 dp[n - 1] 种，没有 1 的组合方式有 dp[n 展开全文

宁静的冬日

发表于 2022-03-05 16:39:13

【C++】已通过需要采用递推，递归和递归+动态规划的方式都会出现一些问题，栈溢出 #include<iostream> using namespace std; #define MAXINT 1000000000 #define MAXN 1000000 int mem[MAXN + 展开全文

Huster水仙

发表于 2023-02-13 00:20:52

完全背包变形（参考高赞回答）第i轮 dp[j]:前i种物品组合成容量恰好为j的方法数递推关系：类比完全背包（优化） dp[j]=dp[j]+dp[j-w[i]] #include<iostream> #include<cmath> using namespace s 展开全文

ImSev7en_1

发表于 2022-09-10 16:07:25

解决本题目的关键在于：对于1的处理即划分是否包含1. #include <iostream> using namespace std; #define MAXN 1000001 int main(){ & 展开全文

雨水磁浮

发表于 2025-02-23 12:47:18

一望而知的递归题，因此首先寻找规律。显然可以且仅可以展开为。对于一个非正整数，其一定可以表示为，而显然无法被进一步展开，因此其展开方法数至少应该等于，即。若为奇数，则和的展开相比仅可能在的所有展开的基础上多出一个（这是因为的所有整数幂中只有为奇数），因此另一方面，若为偶数时，其可以通过有种展开的奇展开全文