0
初级天翼
考试题，订正一下，这个感觉比后面的两题还难啊啊
题目描述 Description
将一个数n拆分为多个非0数相加的形式，有多少种方案数？
要求：
1、拆分的每个数字不同，比如说3=1+2就可以，3=1+1+1就不可以。
2、拆分的数字的顺序不同时，算一种方案，比如说3=1+2和3=2+1算是同一种方案。
3、将数拆为自身，也算一种方案，比如说3=3。
输入描述 Input Description
输入一个数n(1<=n<=50)
输出描述 Output Description
输出一个数字，表示拆分的方案数
样例输入 Sample Input
【样例1】 3 【样例2】 4
样例输出 Sample Output
【样例1】 2 【样例2】 2
数据范围及提示 Data Size & Hint
3=1+2和3=3，存在两种拆数方案
4=1+2和4=4，存在两种拆数方案
错误代码：
#include<iostream>
#include<cstdio>
using namespace std;
int t;
long long a[60] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50};
long long f(int n, int x) {
if(n == 0) return 1;
long long ans = 0;
for(int i=x; i<=51 && a[i]<=n; i++) {
ans += f(n-a[i], i);
}
return ans;
}
int main()
{
int n;
cin >> n;
cout << f(n, 1);
return 0;
}
0
初级天翼
加了100悬赏，求回答
0
被禁言
修练者
这题可能要用dfs
0
初级光能
你看下这个对不对
void dfs(int x,int sum){
if(x==0){
count++;
return ;
}
for(int i=sum;i<=x;i++)
dfs(x-i,i+1);
}这是dfs,x表示现在剩下的数多少,sum表示现在已经选的数的最大值+1
每次dfs枚举从选sum+1到x后的方案数
0
被禁言
修练者
int main(){
cin>>m;
a[0]=0;
dfs(m,1);
cout<<cnt+1;
return 0;
}
void print(int s){
cout<<m<<"=";
for(int i=1;i<=s-1;i++){
cout<<a[i]<<"+";
}
cout<<a[s]<<endl;
}
void dfs(int sum,int s){
for(int i=a[s-1]+1;i<=sum;i++){
if(i<m){
a[s]=i;
sum-=i;
if(sum==0){
cnt++;
}
else dfs(sum,s+1);
sum+=i;//回溯
}
}
}
#include<iostream>
#include<cstring>
using namespace std;
int m,a[10001],cnt;
0
新手光能
0
初级光能
0
高级守护
1
