解题思路:
将整数n分为k份,任意两份不能相同,而言,我们只需要保证这k个数,每个数都要大于等于前一个数即可。
注意事项:
int a[100]={1};//数组,存放每个值 int n,z;全局变量,方便函数使用 int ans=0;//记录符合条件的组合数
int search(int s,int t){ int i; for(int i=a[t-1];i<=s;i++){//i=a[t-1],即是等于前一个数,从前一个数开始遍历。 if(i<n){//从这个条件看,仿佛我们只满足了小于n,并没有满足小于s,实际上,我们for循环就将小于s的进行了筛选。 a[t]=i; s-=i; if(s==0&&t==z) ans+=1;//如果s=0并且t=z,就是满足了题目的要求,将整数n分为k份。 else if(t<z&&s>0) search(s,t+1);//需要继续进行搜索的条件 s+=i;//回溯。 } } } 此算法还可以用于,按照字典从小到大输出。因为是从小到大遍历的。
参考代码:
#include<bits/stdc++.h> using namespace std; int a[100]={1}; int n; int ans=0; int z; int search(int s,int t){ int i; for(int i=a[t-1];i<=s;i++){ if(i<n){ a[t]=i; s-=i; if(s==0&&t==z) ans+=1; else if(t<z&&s>0) search(s,t+1); s+=i; } } } int main(){ cin>>n>>z; search(n,1); cout<<ans; return 0; }
0.0分
1 人评分
C语言程序设计教程(第三版)课后习题7.2 (C语言代码)浏览:661 |
C语言程序设计教程(第三版)课后习题1.6 (C语言代码)浏览:661 |
【明明的随机数】 (C语言代码)浏览:788 |
A+B for Input-Output Practice (IV) (C语言代码)浏览:492 |
【偶数求和】 (C语言代码)浏览:431 |
C二级辅导-同因查找 (C语言代码)浏览:568 |
输出九九乘法表 (C语言代码)浏览:1048 |
回文数(一) (C语言代码)浏览:1120 |
test 4不要直接粘贴,修改内容浏览:245 |
图形输出 (Java代码)浏览:461 |