金氧

台阶问题

该程序给出了使用递归方式以及使用迭代方式两种算法实现。该两种实现都基于如下推导:

  • 当 m = n, n != 1 时,f(n) = 2(n-1) 即 f(n) 为 二项式 (a+b)n 展开式各项系数之和,推导如下: 设楼梯有 n 级,某人一步最多迈 m(m=n) 级,使用“隔板法”(共 n-1 个空位)可得 f(n) = ∑n=1nCnn-1 = 2n-1。
  • 当 m <=n 时,f(n) = 2f(n-1) - f(n-m-1) 即 f(n) = f(n-1) + f(n-2) + ... + f(n-m) 代入 n 后的递推式,推导如下: 归纳可得 f(n) 为先上 1 步、2 步、...、m 步走法只和:f(n) = f(n-1) + f(n-2) + ... + f(n-m)。 逐步代入展开:f(n) = (f(n-2) + f(n-3) + ... + f(n-m-1))+ f(n-2) + ... + f(n-m),即(展开 f(n-1))... => f(n) = 2f(n-1) - f(n-m-1)。

f(n) 可根据 m 分三类情况求解:

  • 当 m = 1 时,有且仅有 1 种走法,f(n)=1
  • 当 m <= n 时,f(n) = 2*(f(n-1) - f(n-m-1),特别地,
  • 当 m = n 时,f(n) = 2n-1

足见,程序员绝对需要一定的数学知识。

package steps;
 
/**
 * 台阶问题:
 * 某楼梯有 n(n>=1) 级台阶,某人一步最多迈 m(n>=m>=1)级,
 * 求有多少种不同的上楼方案 f(n)。
 *
 * <p>
 *   该程序给出了{@linkplain #f(int) 使用递归方式}以及{@linkplain #f_(int)
 *   使用迭代方式}两种算法实现。该两种实现都基于如下推导:
 *   </p><ul>
 *     <li>当 m = n, n != 1 时,f(n) = 2<sup>(n-1)</sup></li>
 *     即 f(n) 为 二项式 (a+b)<sup>n</sup> 展开式各项系数之和,推导如下:
 *     设楼梯有 n 级,某人一步最多迈 m(m=n) 级,使用“隔板法”(共 n-1 个空位)可得
 *     f(n) = ∑<sub>n=1</sub><sup>n</sup>C<sub>n</sub><sup>n-1</sup> =
 *     2<sup>n-1</sup>。
 *     <li>当 m <=n 时,f(n) = 2*f(n-1) - f(n-m-1)</li>
 *     即 f(n) = f(n-1) + f(n-2) + ... + f(n-m) 代入 n 后的递推式,推导如下:
 *     归纳可得 f(n) 为先上 1 步、2 步、...、m 步走法只和:f(n) = f(n-1) + f(n-2)
 *     + ... + f(n-m)。逐步代入展开:f(n) = (f(n-2) + f(n-3) + ...
 *     + f(n-m-1))+ f(n-2) + ... + f(n-m),即(展开 f(n-1))... => f(n) = 2*f(n-1)
 *     - f(n-m-1)。
 *   </ul>
 * <p> </p>
 *
 * <p>
 * f(n) 可根据 m 分三类情况求解:
 *   </p><ul>
 *     <li>当 m = 1 时,有且仅有 1 种走法,f(n)=1</li>
 *     <li>当 m <= n 时,f(n) = 2*(f(n-1) - f(n-m-1),特别地,</li>
 *     <li>当 m = n 时,f(n) = 2<sup>n-1</sup></li>
 *   </ul>
 * <p> </p>
 *
 * @author <a href="mailto:DL88250@gmail.com">Liang Ding</a>
 * @version 1.0.0.2, Mar 14, 2011
 */
public final class Main {
 
    /**
     * 一步最多迈 {@value #M} 级。
     */
    private static final int M = 20;
    /**
     * 楼梯共有 {@value #N} 级台阶。
     */
    private static final int N = 30;
    /**
     * 保存中间计算结果 f(0)...f(N)。
     */
    private static final long[] F = new long[N + 1];
 
    /**
     * 检查给定的 {@linkplain #N N} 与 {@linkplain #M M} 是否满足:
     * <ul>
     *   <li>N >= 1</li>
     *   <li>M >= 1</li>
     *   <li>N >= M</li>
     * </ul>
     */
    private static void check() {
        if (N < 1) {
            throw new IllegalArgumentException("N must larger or equal than 1");
        }
 
        if (M < 1) {
            throw new IllegalArgumentException("M must larger or equal than 1");
        }
 
        if (M > N) {
            throw new IllegalArgumentException("N must larger or equal than M");
        }
    }
 
    /**
     * 主程序入口。
     *
     * @param args 指定的参数(将被忽略)
     */
    public static void main(final String[] args) {
        check();
 
        if (1 == M) {
            // 有且仅有 1 种走法
            System.out.println("f(n)=1");
            return;
        }
 
        init();
        long start = System.currentTimeMillis();
        f(N);
        long used = System.currentTimeMillis() - start;
        System.out.println("Recursively, f(n)=" + F[N] + ", used " + used
                           + " millis");
 
        init();
        long start2 = System.currentTimeMillis();
        f_(N);
        long used2 = System.currentTimeMillis() - start2;
        System.out.println("Iteratively, f(n)=" + F[N] + ", used " + used2
                           + " millis");
    }
 
    /**
     * 初始化 F[0]...F[M]。
     */
    private static void init() {
        F[0] = 1;
        F[1] = 1;
        F[2] = 2;
 
        for (int n = 3; n <= M; n++) {
            F[n] = 1 << (n - 1);
        }
    }
 
    /**
     * 迭代求 f(n),计算结果保存在 F[n] 中。
     * <p>
     * 时间复杂度:
     *   </p><ul>
     *     <li>最坏 O(n),当 m == 1 时 </li>
     *     <li>最好 O(1),当 n == M 时</li>
     * <p> </p>
     * @param n 指定的 n
     */
    public static void f_(final int n) {
        for (int i = 3; i <= N; i++) {
            if (i <= M) {
                continue; // F[0]...F[M] 已在初始化中求出。
            }
 
            // 开始迭代求解, f(n)= 2 * f(n-1) - f(n-M-1)
            F[i] = 2 * F[i - 1] - F[i - M - 1];
        }
    }
 
    /**
     * 递归求 f(n),计算结果保存在 F[n] 中,时间复杂度为 O(2^n)。
     *
     * @param n 指定的 n
     * @return F[n]
     */
    public static long f(final int n) {
        // F[0]...F[M] 已在初始化中求出。
        if (0 == n || 1 == n) {
            return F[0];
        }
 
        if (2 == n) {
            return F[2];
        }
 
        if (M >= n) {
            return F[n];
        }
 
        // 开始递归求解, f(n)= 2 * f(n-1) - f(n-M-1)
        F[n] = 2 * f(n - 1) - f(n - M - 1);
 
        return F[n];
    }
 
    private Main() {
    }
}

« SVN 分支更新与合并 Go Web 开发(二) »