解题思路:首先可以先列深度搜索的整体代码,这时只能获得部分分数,因为暴力搜索范围很大会导致超时,然后进行剪枝操作,第一个剪枝如果n减着剪着变成了0,说明n分着分着不够用了,这条路就走不通了,回溯,第二个要剪枝是可以选择一种顺序来找,我选择的是升序,所以应该让后一个数比前一个数大,最后要注意,当递归深度和输入的k一样了,我们还要比较当前的n是否比前一个数大这样才能形成升序。
注意事项:
参考代码:
# include<iostream>//n=7,k=3,一共三层for可以选择的数是1-6
using namespace std;
int num=0,sum=0;
int n,k;
int a[20]={1};
void dfs(int t)
{
if(n==0)return ;//剪枝1,如果n减到0就立马返回说明此路不行
if(t==k)
{
if(n>=a[t-1])//剪枝2 最后一个属数应该比前一个数大
{
num++;
}
return;
}
for(int i=1;i<=(n-1);i++)
{
if(i>=a[t-1])//剪枝3 前几个数应该是依次递增,也就是最后一个数字比前一个大
{
a[t]=i;
n-=i;//让n减去当前的数
dfs(t+1);//深度搜索
n+=i;//回溯
}
}
}
int main()
{
cin>>n>>k;
dfs(1);
cout<<num;
return 0;
}
0.0分
0 人评分
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:465 |
C语言程序设计教程(第三版)课后习题6.11 (C语言代码)浏览:549 |
WU-小九九 (C++代码)浏览:1684 |
用筛法求之N内的素数。 (C语言代码)浏览:669 |
1025题解浏览:738 |
2003年秋浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:683 |
C语言程序设计教程(第三版)课后习题6.2 (C语言代码)浏览:541 |
2^k进制数 (C语言描述,蓝桥杯)浏览:1420 |
C语言程序设计教程(第三版)课后习题7.3 (C语言代码)浏览:403 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:385 |