求C n m（从n个数中选m个数，有多少种组合?问题）暴力—递归——回归数学公式，三种方法，层层优化

graf 发布于2021-09-07 09:59 / 571人阅读

摘要：但如果数据不大，代码跑的结果是没有任何问题的。我只是随便找了一个例子，当然有人会说不是要比要好进行嘛，是的没错，我在这里先埋下一个伏笔，最后我会针对这个问题进行优化指的是第三种方法的优化通过这个图片，大家应该可以很好的理解这个递归。

文章将以代码+解析（简单）的方式进行，欢迎大家的阅读！

首先，任何一个问题都是有来源的，所以请先看题（我遇到的）：

暴力解法（我第一次的想法）

代码如下：

#include int main() {    int n, m, i, num;    scanf("%d", &num);    while (num--) {        scanf("%d %d", &n, &m);        int N = 1;        for (i = 1; i <= n; i++) {            N *= i;        }        int M = 1;        for (i = 1; i <= m; i++) {            M *= i;        }        int N_M = 1;        for (i = 1; i <= n - m; i++) {            N_M *= i;        }        int f = N / (M * N_M);        printf("%d/n", f);    }    return 0;}

核心：数学公式：n!/(m!*(n-m)!)

所以我们只需要分别算三次阶乘（对应代码N ,M ,N_M）就OK了，非常暴力，但最容易理解!

缺点：计算速度慢，当数据大的时候，就报不过去了，因为已经超过long long类型了（于是我进行了第二种方法——递归）。

但如果数据不大，代码跑的结果是没有任何问题的。

请看一下上述问题的测试数据：

递归解法（进一步优化）

代码如下：（仅单次输入）

#include long long f(int n, int m){    if (n < m) return 0;//分几种情况    if (n == m) return 1;    if (m == 0) return 1;    return f(n - 1, m - 1) + f(n - 1, m);//实现递归}int main(){    int n, m;    long long k = 0;    scanf("%d %d", &n, &m);    k = k + f(n, m);    printf("%lld", k);    return 0;}

核心：递归

如果不好理解请看下面，我将用图片来讲解这个递归。

我只是随便找了一个例子，当然有人会说C 6 2不是要比C 6 4要好进行嘛，是的没错，我在这里先埋下一个伏笔，最后我会针对这个问题进行优化（指的是第三种方法的优化）！

通过这个图片，大家应该可以很好的理解这个递归。

回归数学方法（加优化）

代码如下（仅单次输入）：

#includeint main(){	double n, m;	scanf("%lf %lf", &n, &m);	double sum = 1;	double i;	double q = m;	for (i = 1; i <= q; i++)	{		sum *= (n--) / (m--);	}	printf("%.0lf", sum);	return 0;}

核心：数学方法

不知道怎么描述，所以直接暴力上图(高中数学知识)：

我再解释一下我的代码：

C n m， m就是我循环的次数，为了m的值在m--的时候不会丢失，我在这里用q存储一下m的值，使得循环正常进行。

最后来到了优化环节：

举个例子C 6 4 与 C 6 2的值是一样的，前者循环4次，后者循环2次，为了减少循环次数，只需加上一个判断处理一下m的值，具体我直接上代码：

        int q;        if (n - m < m) {            q = n - m;            m = q;        }        else            q = m;

这样就可以使代码运行时，用最小的循环次数来进行！

在最后我附上最终代码（C与C++）

C：

#includeint main(){    double n, m;    int T;    scanf("%d", &T);    while (T--)    {        scanf("%lf %lf", &n, &m);        int q;        if (n - m < m)        {            q = n - m;            m = q;        }        else            q = m;        double t = 1;        for (int i = 1; i <= q; i++)            t *= (n--) / (m--);        printf("%.lf/n", t);    }    return 0;}

C++(学长提供)：

在文章最开头我提到的问题，用最后一种代码跑没有一点问题。因为在乘的过程中除也在进行，就可以保证内存够用。

此题花费我数小时来解决（我太菜了，滑稽保命！）

希望本篇文章可以很好为广大老铁们解疑答惑，同时也希望老铁们留下宝贵的建议与指导。

最后再次感谢您的阅读！

服务器托管私有云 n个数排序c语言 n个数 php求数值个数 python中求个数

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/119400.html

有关排列组合的一道算法题

摘要：有关排列组合的一道算法题一题目内容废话不多说，先上题目有一个的网格，左下角为，右上角为，规定每次只能走一步，并且方向只能是向上或者向右，求到共有多少种走法例如一个日字形的格子就是一个的网格，共有种走法并用写出程序算法。有关排列组合的一道算法题一、题目内容废话不多说，先上题目：有一个 n × m 的网格，左下角为A，右上角为B，规定每次只能走一步，并且方向只能是向上或者向右，求A...

ephererid 2019-08-20 18:18 评论0 收藏0
从“数学归纳法”到理解“递归算法”！

摘要：前言相信大家在面试或者工作中偶尔会遇到递归算法的提问或者编程，我们今天来聊一聊从数学归纳法到理解递归算法。这种广义的数学归纳法应用于数学逻辑和计算机科学领域，称作结构归纳法。 showImg(https://img-blog.csdnimg.cn/20190426221838971.gif);showImg(https://img-blog.csdnimg.cn/20190429222...

oogh 2019-08-16 17:05 评论0 收藏0
如何求ABm>Cm>的全排列？--如何理解回溯算法？

摘要：它真的是深度优先搜索吗是真的吗是真的如果是的话，那它的搜索空间解空间是什么是向量组成的集合，而。既然深度优先搜索剪枝回溯。什么是全排列？从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。那么ABC的全排列有哪些？根据定义得到：ABCACBBACBCACABCBA 如何通过程序求解？方法一：暴力...

zero 2019-08-16 16:22 评论0 收藏0