日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

問題

有這樣一個關(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份：

當(dāng)n=2時，分1種{2}，分2種{1*2}

當(dāng)n=3時，分1種{3}，分2種[1,2]的排列，分3種{1*3}

當(dāng)n=4時，分1種{4}，分2種[1,3][2,2]的排列，分3種[1,1,2]的排列，分4種{1*4}

當(dāng)n=5時，分1種{5}，分2種[1,4][2,3]的排列，分3種[1,1,3][1,2,2]的排列，分4種[1,1,1,2]的排列，分5種{1*5}

當(dāng)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的進(jì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

(非常抱歉因疏于嚴(yán)謹(jǐn)上一版中該部分推測有誤，經(jīng)查證后給出準(zhǔn)確方法。特別感謝 @張晉坤 @顧健 等同學(xué)的斧正。)

當(dāng)mh_k(n)表示將正整數(shù)n拆分分部量只含1,2,3...k的有序分拆數(shù)。該問題符合廣義斐波那契數(shù)定義，則h_k(n)滿足：

當(dāng)n<=k時，h_k(n)=2^n-1

當(dāng)n>k>=2時，h_k(n)=h_k(n-1)+h_k(n-2)+...+h_k(n-k)

因為n<=k時，正整數(shù)n拆成分部量只含1,2..k的有序分拆數(shù)，就是n的有序分拆數(shù)，而n得有序分拆數(shù)就是2^n-1。

所以，根據(jù)定理寫出了此迭代的循環(huán)版本，如下面的wideFib方法。

總結(jié)

以上總結(jié)，可以用一分段函數(shù)來描述這個問題的通解：

當(dāng)m=n時復(fù)雜度為O(1)

當(dāng)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; 
  
  
    }  
 
 

當(dāng)前標(biāo)題：對臺階步數(shù)問題的數(shù)學(xué)分析及更優(yōu)解探索
當(dāng)前路徑：http://m.5511xx.com/article/djpcssh.html