資訊專欄INFORMATION COLUMN
摘要：有關(guān)排列組合的一道算法題一題目?jī)?nèi)容廢話不多說，先上題目有一個(gè)的網(wǎng)格，左下角為，右上角為，規(guī)定每次只能走一步，并且方向只能是向上或者向右，求到共有多少種走法例如一個(gè)日字形的格子就是一個(gè)的網(wǎng)格，共有種走法并用寫出程序算法。
有關(guān)排列組合的一道算法題 一、題目?jī)?nèi)容
廢話不多說，先上題目：
有一個(gè) n × m 的網(wǎng)格，左下角為A，右上角為B，規(guī)定每次只能走一步，并且方向只能是向上或者向右，求A到B共有多少種走法？(例如一個(gè)日字形的格子就是一個(gè)2 × 1的網(wǎng)格，共有3種走法)并用Javascript寫出程序算法。
二、解決方法大家可以先思考一下怎么做，再去看我的方法。
這個(gè)問題我想了很久，一直在走彎路，其實(shí)用一個(gè)抽象的數(shù)學(xué)方法就可以很輕松解決這個(gè)問題。
現(xiàn)在你可以把向右移動(dòng)想象成記錄一個(gè)數(shù)字1，把向上移動(dòng)抽象成記錄一個(gè)數(shù)字0，并且這些數(shù)字是按順序排列的。
看到這里我相信聰明的小伙伴已經(jīng)想到了如何解決這個(gè)問題。
這個(gè)問題可以抽象成n個(gè)0和m個(gè)1的不同排列的總數(shù)。比如2 × 2的網(wǎng)格就是2個(gè)0和2個(gè)1的所有不同排列的數(shù)量，也就是1100，1010，1001，0110，0101，0011。
進(jìn)而，我們可以把問題抽象成從(m + n)個(gè)0中，隨意抽取m個(gè)0并將它改為1的不同方法數(shù)，是不是覺得問題很熟悉，沒錯(cuò)！就是高中的排列組合。我先把公式亮出來?：
C(m, n + m) = (n + m)!/(m! * n!)
三、Javascript代碼描述想先復(fù)習(xí)一下排列組合知識(shí)的同學(xué)可以參見下一節(jié)。
以上的結(jié)果用JS的描述，如下：
function getMethods(n, m) {
// 定義一個(gè)求階乘的輔助函數(shù)
function factorial(x) {
if (x === 0) {
return 1
} else {
return factorial(x -1) * x
}
}
return factorial(m + n)/(factorial(m) * factorial(n))
}
四、排列組合如果小伙伴有好的算法，可以留言交流！
簡(jiǎn)單地講一下排列和組合。
排列先舉個(gè)栗子（以下n，m均為正整數(shù)），從n個(gè)含有標(biāo)有不同數(shù)字小球的袋子里，按順序抽取n個(gè)小球，且抽取后不再放入袋子里。第一次抽的時(shí)候，有n種可能；第二次抽的時(shí)候有n - 1種可能，以此類推，抽完n個(gè)小球總共的不同排列個(gè)數(shù)為n!。
如果條件不變，只把抽取的小球個(gè)數(shù)改為m（m <= n）個(gè)，結(jié)果也就變成：
n × (n - 1) × (n - 2) × ... × (n - m + 1) 整理一下即： A(m, n) = n! / (n - m)!組合
同樣是n個(gè)標(biāo)記不同數(shù)字的小球放入一個(gè)袋子中，也是抽取m個(gè)，但是此時(shí)不算抽取的順序。也就是把排列的結(jié)果n!/(n - m)!再除以m個(gè)小球隨機(jī)排列的總方法術(shù)，即m!，所以結(jié)果為：
C(m, n) = A(m, n) / m! = n! / ( (n - m)! × m! )如何得出之前的公式
運(yùn)用以上的知識(shí)，可以總結(jié)出以下公式：
C(m, n + m) = A(m, n + m) / m!
= (n + m)! / ( n! × m! )
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/84327.html
摘要：從位向右，找到比小的最大的那個(gè)數(shù)，并與交換。交換后，把位向右注意是的，不是的值的所有數(shù)字降序排列。對(duì)于來說，從右向左可以分割為，，，這三種情況都是最小排列。 題目如下： 給定某一個(gè)正整數(shù)，組成這個(gè)數(shù)的數(shù)字不變，返回下一個(gè)比它小的數(shù)，如： nextSmaller(21) == 12 nextSmaller(531) == 513 nextSmaller(907) == 790 nextS...
摘要：封裝手寫的方筆記使用檢測(cè)文件前端掘金副標(biāo)題可以做什么以及使用中會(huì)遇到的坑。目的是幫助人們用純中文指南實(shí)現(xiàn)復(fù)選框中多選功能前端掘金作者緝熙簡(jiǎn)介是推出的一個(gè)天挑戰(zhàn)。 深入理解 JavaScript Errors 和 Stack Traces - 前端 - 掘金譯者注：本文作者是著名 JavaScript BDD 測(cè)試框架 Chai.js 源碼貢獻(xiàn)者之一，Chai.js 中會(huì)遇到很多異常處理...
摘要：封裝手寫的方筆記使用檢測(cè)文件前端掘金副標(biāo)題可以做什么以及使用中會(huì)遇到的坑。目的是幫助人們用純中文指南實(shí)現(xiàn)復(fù)選框中多選功能前端掘金作者緝熙簡(jiǎn)介是推出的一個(gè)天挑戰(zhàn)。 深入理解 JavaScript Errors 和 Stack Traces - 前端 - 掘金譯者注：本文作者是著名 JavaScript BDD 測(cè)試框架 Chai.js 源碼貢獻(xiàn)者之一，Chai.js 中會(huì)遇到很多異常處理...
摘要：另外，我們還需要將所有硬幣組合起來，組成一個(gè)新的數(shù)組，其中包含了所有的硬幣。比如硬幣數(shù)組，和代表其數(shù)量的數(shù)組，組合成。 寫在前面的自我檢討 這道題的解法，剛開始我自己做的并不算是一個(gè)很好的解法，只能說題目是做出來了，但過程中的計(jì)算有大量的重復(fù)計(jì)算，導(dǎo)致函數(shù)復(fù)雜度直逼O(n^n)。查閱資料之后便有了一個(gè)改良版。感謝這篇文章Find all distinct subset (or subs...
閱讀 4036·2021-11-25 09:43
閱讀 2670·2021-11-18 13:11
閱讀 2362·2019-08-30 15:55
閱讀 3341·2019-08-26 11:58
閱讀 2899·2019-08-26 10:47
閱讀 2289·2019-08-26 10:20
閱讀 1341·2019-08-23 17:59
閱讀 3101·2019-08-23 15:54
