有關排列組合的一道算法題

ephererid 發布于2019-08-20 18:18 / 1053人閱讀

摘要：有關排列組合的一道算法題一題目內容廢話不多說，先上題目有一個的網格，左下角為，右上角為，規定每次只能走一步，并且方向只能是向上或者向右，求到共有多少種走法例如一個日字形的格子就是一個的網格，共有種走法并用寫出程序算法。

有關排列組合的一道算法題 一、題目內容

廢話不多說，先上題目：

有一個 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! )

GPU云服務器云服務器排列組合算法排列組合算法排列組合算法java 排列組合

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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