其实是个背包问题。
- voidFindSum(intsum,intn)
- {
-
staticvector<int>l;
-
if(n<=0||sum<=0)
-
return;
-
if(sum>n)
- {
- l.push_back(n);
- FindSum(sum-n,n-1);
- l.pop_back();
- FindSum(sum,n-1);
- }
-
else
- {
- cout<<sum;
-
for(vector<int>::iteratoriter=l.begin();iter!=l.end();iter++)
-
cout<<""<<*iter;
- cout<<endl;
-
-
if(sum!=1)
- FindSum(sum,sum-1);
- }
- }
扩展一:要求组合的个数一定
- voidFindSum1(intsum,intn,intnumber)
- {
-
staticvector<int>l;
-
if(sum<=0||n<=0||number<=0||n<number)
-
return;
-
if(sum>n)
- {
- l.push_back(n);
- FindSum1(sum-n,n-1,number-1);
- l.pop_back();
- FindSum1(sum,n-1,number);
- }
-
elseif(number==1)
- {
- cout<<sum;
-
for(vector<int>::iteratoriter=l.begin();iter!=l.end();iter++)
-
cout<<""<<*iter;
- cout<<endl;
- }
-
else
- {
-
if(sum!=1)
- FindSum1(sum,sum-1,number);
- }
- }
扩展二:给定不重复数组a, 求数组a中number个数和为sum的所有组合,其中n为(数组长度-1)
- voidFindSum2(int*a,intsum,intn,intnumber)
- {
-
staticvector<int>l;
-
if(number==0&&sum==0)
- {
-
for(vector<int>::iteratoriter=l.begin();iter!=l.end();iter++)
-
cout<<*iter<<"";
- cout<<endl;
-
return;
- }
-
if(sum<0||n<0||n<number-1)
-
return;
- l.push_back(a[n]);
- FindSum2(a,sum-a[n],n-1,number-1);
- l.pop_back();
- FindSum2(a,sum,n-1,number);
- }
扩展三:不重复数组中和等于sum的所有组合,n是(数组的长度-1)
- voidFindSum3(int*a,intsum,intn)
- {
-
staticvector<int>l;
-
if(sum==0)
- {
-
for(vector<int>::iteratoriter=l.begin();iter!=l.end();iter++)
-
cout<<*iter<<"";
- cout<<endl;
-
return;
- }
-
if(sum<0||n<0)
-
return;
- l.push_back(a[n]);
- FindSum3(a,sum-a[n],n-1);
- l.pop_back();
- FindSum3(a,sum,n-1);
- }
扩展四:给定可重复数组a(首先要将数组a排序,递增递减都可以), 求数组a中number个数和为sum的所有组合,其中n为(数组长度-1)
- voidFindSum4(int*a,intsum,intn,intnumber)
- {
-
staticvector<int>l;
-
if(number==0&&sum==0)
- {
-
for(vector<int>::iteratoriter=l.begin();iter!=l.end();iter++)
-
cout<<*iter<<"";
- cout<<endl;
-
return;
- }
-
if(sum<0||n<0||n<number-1)
-
return;
- l.push_back(a[n]);
- FindSum4(a,sum-a[n],n-1,number-1);
- l.pop_back();
-
if(a[n]==a[n-1])
-
return;
- FindSum4(a,sum,n-1,number);
- }
扩展五:可重复数组(首先要将数组a排序,递增递减都可以)中和等于sum的所有组合,n是(数组的长度-1)
- voidFindSum5(int*a,intsum,intn)
- {
-
staticvector<int>l;
-
if(sum==0)
- {
-
for(vector<int>::iteratoriter=l.begin();iter!=l.end();iter++)
-
cout<<*iter<<"";
- cout<<endl;
-
return;
- }
-
if(sum<0||n<0)
-
return;
- l.push_back(a[n]);
- FindSum5(a,sum-a[n],n-1);
- l.pop_back();
-
if(a[n]==a[n-1])
-
return;
- FindSum5(a,sum,n-1);
- }
分享到:
相关推荐
编程求解:输入两个整数 n 和 m,从数列 1,2,3.......n 中随意取几个数,使其和等于m ,要求将其中所有的可能组合列出来。
1.5.6. 输入两个整数 n 和 m,从数列 1,2,3.......n 中 随意取几个数 ....... 116 1.5.7. 输入一个表示整数的字符串,把该字符串转换成整数并输出.............. 118 1.5.8. 给出一个数列,找出其中最长的单调...
python斐波那契数列第n项 斐波那契数列是指从0和1开始,后面的每一项都是前面两项的和。即:0、1、1、2、3、5、8、13、21、34、55、89、144、233、377、610……以此类推。这个数列在数学上有着重要的应用,也是...
Java 求出数列前20项的和,有一分数序列:2/1,3/2,5/3,8/5,13/8,21/13...求出这个数列的前20项之和。可以得出规律为:后一个数的分母为前一个数分子和分母之和,因此可以得出计算方法如下: for(int i = 1;i;...
C语言程序设计-编程实现求数列1/2,3/4,5/8,9/32 的所有大于等于0.000001的数据项之和,显示输出计算结果(运行结果:s=2.999999。提示:利用while编写)。
# 题目: # 有一分数序列:2/1,3/2,5/3,8/5,13/8,21/13...求出这个数列的前20项之和。 # 分析: # 请抓住分子与分母的变化规律。
高中数学数列1PPT课件.pptx
已知Fibonacci数列:1,1,2,3,5,8,13,……。观察数列,可发现这样的规则:从第3项开始,每一项都是其前面两项之和。
0-1背包问题:输入两个整数n和m,从数列1,2,3....n中随意取几个数,使得其和等于m,求所有组合
数列极差问题:给定n个正整数数列,进行如下操作:每次删去两个数 a和b,添加1个数 a*b+1,直到只剩1个数N。在所有的这样的N中,有1个最大Max的和最小的Min,M=Max-Min是极差,设计程序计算M。
已知斐波那契数列 F n =F n−1 +F n−2 (n>=3),F 1 =1,F 2 =1 用递归的方法求解该数列的第n项。...输出一个数,数列的第n项 输入样例1: 1 输出样例1: 1 输入样例2: 3
对任意给定的一个自然数n,将分母小于等于n的不可约的真分数按升序排列,并且在第一个分数之前加上0/1,在最后一个分数之后加上1/1,这个序列称为n级法雷数列,以...现在给出n让你求其n级法雷数列中元素的排列和个数。
高中数学等比数列前n项和时等比数列前n项和PPT课件.pptx
C语言程序设计-用函数求fibonacci数列前n项的和;说明:fibonacci数列为数列的第一项值为1,第二项值也为1,从第三项开始,每一项均为其前面相邻两项的和;例如:当n=28时,运行结果:832039.c
F(N)=F(N-1)+F(N-2) (N>=3) 请计算第N项斐波那契的值. 输入描述 输入数据只包含一个正整数N(1<N); 输出描述 请根据要求计算输出F(N)的结果,为方便计算,只要求输出F(N) MOD 2000000003 后的值. 输入样例 ...
Fibonacci数列斐波那契数列PPT学习教案.pptx
高中数学等差数列前n项和时等差数列前n项和应用PPT课件.pptx
有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总数为多少? 程序分析: 兔子的规律为数列1,1,2,3,5,8,13,21....
【问题描述】编写函数f,功能是用递归的方法求斐波那契数列的第n项,函数原型为 int f(int n),在主函数中输入一个正整数n,调用函数f求出斐波那契数列的第n项,并在主函数中输出。 斐波那契数列:1,1,2,3,5,8,13,...
(学)高中数学数列放缩专题:用放缩法处理数列和不等问题.doc