建站
咨詢
售后
建站咨詢
新聞中心
問題
有這樣一個關(guān)于臺階和步數(shù)的題目：
假設(shè)A上臺階，一次可以跨1層，2層，3層.. 或m層，問A上n層臺階，有多少種走法？其中，m和n都是正整數(shù)，并且 m <= n
對臺階步數(shù)問題提出簡單分析，探索是否存在更優(yōu)解的方案。
分析
這個問題等價于：
對于數(shù)n，有多少種方案讓小于n的數(shù)相加等于n，且這些數(shù)中的***數(shù)不超過m(m<=n)
首先考慮m=n時情況
有多少種方案把n拆分成1...n份：
當n=2時，分1種{2}，分2種{1*2}
當n=3時，分1種{3}，分2種[1,2]的排列，分3種{1*3}
當n=4時，分1種{4}，分2種[1,3][2,2]的排列，分3種[1,1,2]的排列，分4種{1*4}
當n=5時，分1種{5}，分2種[1,4][2,3]的排列，分3種[1,1,3][1,2,2]的排列，分4種[1,1,1,2]的排列，分5種{1*5}
當n=6時，分1種{6}，分2種[1,5][2,4][3,3]的排列，分3種[1,1,4][1,2,3][2,2,2]的排列，分4種[1,1,1,3][1,1,2,2]的排列，分5種[1,1,1,1,2]的排列，分6種1*6
……
于是每一步分法都是一個將整數(shù)n的進行有序k分拆問題。
根據(jù)組合數(shù)學(xué)定理：正整數(shù)n的有序k分拆的個數(shù)等于。即(n-1)選(k-1)的組合數(shù)。
這正是楊輝三角的第n行第k項的通項：
于是，可以得到：
那么 k→1...n 總方案數(shù)(即為n從1拆分到n拆分的和的函數(shù)，用S(n)記號表示)
（根據(jù)楊輝三角性質(zhì)）
考慮1
(非常抱歉因疏于嚴謹上一版中該部分推測有誤，經(jīng)查證后給出準確方法。特別感謝 @張晉坤 @顧健 等同學(xué)的斧正。)
當mhk(n)表示將正整數(shù)n拆分分部量只含1,2,3...k的有序分拆數(shù)。該問題符合廣義斐波那契數(shù)定義，則hk(n)滿足：
當n<=k時，hk(n)=2n-1
當n>k>=2時，hk(n)=hk(n-1)+hk(n-2)+...+hk(n-k)
因為n<=k時，正整數(shù)n拆成分部量只含1,2..k的有序分拆數(shù)，就是n的有序分拆數(shù)，而n得有序分拆數(shù)就是2n-1。
所以，根據(jù)定理寫出了此迭代的循環(huán)版本，如下面的wideFib方法。
總結(jié)
以上總結(jié)，可以用一分段函數(shù)來描述這個問題的通解：
當m=n時復(fù)雜度為O(1)
當m所以有一定程度的優(yōu)化改善。
示例
利用上面的結(jié)論，給出如下代碼：
- //java
-
- static long stepsOfTerrace(int n, int m) {
- if (m > n || n < 2)
- throw new IllegalArgumentException();
- if (m == n)
- return (long) Math.pow(2, n - 1);
- else if (m > 1)
- return wideFib(n , m);
- else
- return n;
- }
- static long wideFib(int n, int k) {
- long[] steps = new long[n];
- for (int i = 1; i <= n - 1; i++) {
- if (i <= k) // hk(k)之前序列=2^n-1
- steps[i] = (int) Math.pow(2, i - 1);
- else // 之后按照廣義斐波那契計算
- for (int j = i - 1; j >= i - k; j--)
- steps[i] += steps[j];
- }
- long sum = 0;
- for (int i = n - k; i <= n - 1; i++)
- sum += steps[i];
- return sum;
- }
網(wǎng)頁標題：對臺階步數(shù)問題的數(shù)學(xué)分析及更優(yōu)解探索
標題路徑：http://m.fisionsoft.com.cn/article/djpcssh.html
(非常抱歉因疏于嚴謹上一版中該部分推測有誤，經(jīng)查證后給出準確方法。特別感謝 @張晉坤 @顧健 等同學(xué)的斧正。)
當m
當n<=k時，hk(n)=2n-1
當n>k>=2時，hk(n)=hk(n-1)+hk(n-2)+...+hk(n-k)
因為n<=k時，正整數(shù)n拆成分部量只含1,2..k的有序分拆數(shù)，就是n的有序分拆數(shù)，而n得有序分拆數(shù)就是2n-1。
所以，根據(jù)定理寫出了此迭代的循環(huán)版本，如下面的wideFib方法。
總結(jié)
以上總結(jié)，可以用一分段函數(shù)來描述這個問題的通解：
當m=n時復(fù)雜度為O(1)
當m 所以有一定程度的優(yōu)化改善。 利用上面的結(jié)論，給出如下代碼：示例
網(wǎng)頁標題：對臺階步數(shù)問題的數(shù)學(xué)分析及更優(yōu)解探索
標題路徑：http://m.fisionsoft.com.cn/article/djpcssh.html
