首页
登录 | 注册

面试题:输入两个整数 n 和 m,从数列1,2,3…….n 中 随意取几个数, 使其和等于 m

问题:

2010年中兴面试题 
编程求解: 
输入两个整数 n 和 m,从数列1,2,3…….n 中 随意取几个数, 
使其和等于 m ,要求将其中所有的可能组合列出来.

思路:

类似这种组合问题一般都是使用递归的策略,考虑到n个数和为m,假设要解决的函数为f(n,m), 假设我们选择了第n个数,那么问题就变成了f(n-1,m-n),

否则的话问题就是f(n-1,m), 再考虑下边界条件: 如果n<1 或者 m<1显然不会有结果, 如果n==m,那么显然可以输出一个结果了,然后问题就变成了f(m-1,m)

所以初步写的代码如下:

 

vector<int> queueV;
void findSum(int n, int m)
{
    if(n<1 || m<1)
        return;
    if(m==n)
    {
        vector<int>::iterator it;
        for(it = queueV.begin(); it!=queueV.end(); ++it)
        {
            cout << *it << ' ';
        }
        cout << m << endl;
        n = m-1; //从剩下的1~m-1中寻找值为m的数列
    }
    queueV.push_back(n);
    findSum(n-1, m-n);
    queueV.pop_back();
    findSum(n-1, m);
}

 

不过这个代码涉及到了很多可以避免的压栈出栈和递归等操作,会浪费比较多的时间,所以优化的版本如下:

vector<int> queueV;
void findSum2(int n, int m)
{
    if(n<1 || m<1)
        return;
    if(m>n)
    {
        queueV.push_back(n);
        findSum(n-1, m-n);
        queueV.pop_back();
        findSum(n-1, m);
    }
    else
    {
        vector<int>::iterator it;
        for(it = queueV.begin(); it!=queueV.end(); ++it)
        {
            cout << *it << ' ';
        }
        cout << m << endl;
        findSum(m-1, m);
    }
}

 


相关文章

  • 基于mapreduce实现图的三角形计数
    源代码放在我的github上,想细致了解的可以访问:TriangleCount on github 一.实验要求 1.1 实验背景         图的三角形计数问题是一个基本的图计算问题,是很多复杂网络分析(比如社交网络分析)的基础.目前 ...
  • 第四次实验
    part1 程序用于观察数组中的一组数据元素在内存中是否是连续存放的 #include <stdio.h> const int N=5; int main() { char a[5] = {'h','e','l','l','o' ...
  • 第四次上机实验
    实验结论: part 1-4:当数组名作为形式参数时,数组名后面要加[ ]:当数组名作为实际参数时,直接写数组名,后面不要加[ ]:              关于函数的调用及参数传递过程:在程序运行到函数调用这一步骤时,实参会将值赋值给调 ...
  • 如何在电脑上配置两个tomcat
    问题 准备逐渐转向idea的怀抱了,每次部署项目时和eclipse使用的都是同一个tomcat,这是很大的隐患,并且非常的不方便,遂再配置一个tomcat 1.下载tomcat和配置系统变量 CATALINA_HOME是Tomcat的安装目 ...
  • 实验4(2019.4.23)
    [实验结论] 一.对Part1-Part4的总结. 1.数组名作为函数参数时,形参.实参的语法形式书写注意事项. 这一点在书本上P154—P158有详细说明,但是叙述过于冗杂,所以借用“实验4.pdf”中的内容总结: (1)函数声明和函数定 ...
  • 实验四(数组)
    实验的总结: int型和float型都用4个字节,char型用一个字节,double型用8个字节.但是在输出5.00和5.000000的时候都没有区别的. 还有就是要注意数组元素的索引号是从零开始的,所以在用for语句的时候<注意它的 ...

2019 cecdns.com webmaster#cecdns.com
12 q. 0.062 s.
京ICP备10005923号