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

ephererid 发布于2019-08-20 18:18 / 939人阅读

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

有关排列组合的一道算法题 一、题目内容

废话不多说，先上题目：

有一个 n × m 的网格，左下角为A，右上角为B，规定每次只能走一步，并且方向只能是向上或者向右，求A到B共有多少种走法？(例如一个日字形的格子就是一个2 × 1的网格，共有3种走法)并用Javascript写出程序算法。

大家可以先思考一下怎么做，再去看我的方法。

二、解决方法

这个问题我想了很久，一直在走弯路，其实用一个抽象的数学方法就可以很轻松解决这个问题。

现在你可以把向右移动想象成记录一个数字1，把向上移动抽象成记录一个数字0，并且这些数字是按顺序排列的。

看到这里我相信聪明的小伙伴已经想到了如何解决这个问题。

这个问题可以抽象成n个0和m个1的不同排列的总数。比如2 × 2的网格就是2个0和2个1的所有不同排列的数量，也就是1100，1010，1001，0110，0101，0011。

进而，我们可以把问题抽象成从(m + n)个0中，随意抽取m个0并将它改为1的不同方法数，是不是觉得问题很熟悉，没错！就是高中的排列组合。我先把公式亮出来?：

C(m, n + m) = (n + m)!/(m! * n!)

想先复习一下排列组合知识的同学可以参见下一节。

三、Javascript代码描述

以上的结果用JS的描述，如下：

function getMethods(n, m) {
  // 定义一个求阶乘的辅助函数
  function factorial(x) {
    if (x === 0) {
      return 1
    } else {
      return factorial(x -1) * x
    }
  }
  return factorial(m + n)/(factorial(m) * factorial(n))
}

如果小伙伴有好的算法，可以留言交流！

四、排列组合

简单地讲一下排列和组合。

排列

先举个栗子（以下n，m均为正整数），从n个含有标有不同数字小球的袋子里，按顺序抽取n个小球，且抽取后不再放入袋子里。第一次抽的时候，有n种可能；第二次抽的时候有n - 1种可能，以此类推，抽完n个小球总共的不同排列个数为n!。

如果条件不变，只把抽取的小球个数改为m（m <= n）个，结果也就变成：

n × (n - 1) × (n - 2) × ... × (n - m + 1)
整理一下即：
A(m, n) = n! / (n - m)!

组合

同样是n个标记不同数字的小球放入一个袋子中，也是抽取m个，但是此时不算抽取的顺序。也就是把排列的结果n!/(n - m)!再除以m个小球随机排列的总方法术，即m!，所以结果为：

C(m, n) = A(m, n) / m! = n! / ( (n - m)! × m! )

如何得出之前的公式

运用以上的知识，可以总结出以下公式：

C(m, n + m) = A(m, n + m) / m!

            = (n + m)! / ( n! × m! )

云服务器专线服务排列组合算法排列组合算法排列组合算法java 排列组合

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

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

一道算法题（next smaller）

摘要：从位向右，找到比小的最大的那个数，并与交换。交换后，把位向右注意是的，不是的值的所有数字降序排列。对于来说，从右向左可以分割为，，，这三种情况都是最小排列。题目如下：给定某一个正整数，组成这个数的数字不变，返回下一个比它小的数，如： nextSmaller(21) == 12 nextSmaller(531) == 513 nextSmaller(907) == 790 nextS...

mgckid 2019-08-20 13:32 评论0 收藏0
一篇算法讲解的注解

摘要：前言从公式到算法之前的完整路径应该是数学公式中文公式中文算法英文算法偶然看到一篇算法文章，讲解了百度校园招聘之编程题的核心算法思路，我根据它又整理出自己的解题思路。前言从公式到算法之前的完整路径应该是：数学公式->中文公式->中文算法->英文算法偶然看到一篇算法文章，讲解了百度2016校园招聘之编程题的核心算法思路，我根据它又整理出自己的解题思路。第一题题目在原文中可以找到，...

fevin 2019-06-27 13:40 评论0 收藏0
前端空间 - 收藏集 - 掘金

摘要：封装手写的方笔记使用检测文件前端掘金副标题可以做什么以及使用中会遇到的坑。目的是帮助人们用纯中文指南实现复选框中多选功能前端掘金作者缉熙简介是推出的一个天挑战。深入理解 JavaScript Errors 和 Stack Traces - 前端 - 掘金译者注：本文作者是著名 JavaScript BDD 测试框架 Chai.js 源码贡献者之一，Chai.js 中会遇到很多异常处理...

you_De 2019-08-29 12:34 评论0 收藏0
前端空间 - 收藏集 - 掘金

摘要：封装手写的方笔记使用检测文件前端掘金副标题可以做什么以及使用中会遇到的坑。目的是帮助人们用纯中文指南实现复选框中多选功能前端掘金作者缉熙简介是推出的一个天挑战。深入理解 JavaScript Errors 和 Stack Traces - 前端 - 掘金译者注：本文作者是著名 JavaScript BDD 测试框架 Chai.js 源码贡献者之一，Chai.js 中会遇到很多异常处理...

lwx12525 2019-08-20 16:35 评论0 收藏0
有多少种硬币组合——找出独特子数组之和

摘要：另外，我们还需要将所有硬币组合起来，组成一个新的数组，其中包含了所有的硬币。比如硬币数组，和代表其数量的数组，组合成。写在前面的自我检讨这道题的解法，刚开始我自己做的并不算是一个很好的解法，只能说题目是做出来了，但过程中的计算有大量的重复计算，导致函数复杂度直逼O(n^n)。查阅资料之后便有了一个改良版。感谢这篇文章Find all distinct subset (or subs...

xiaoqibTn 2019-08-23 12:34 评论0 收藏0