簡介

先來描述一下問題,這裡以下樓梯為例:

有一個人下樓梯,一次可以走一階或兩階,假設總共有N階樓梯,共有幾總走法?例如N=3,他可以走1 + 1 + 1 、1 + 2或2 + 1三種走法。

實做一個程式能夠輸入N,能回傳共有幾總走法。

這個問題直接使用Bottom-Up可能不容易思考,所以我們先利用遞迴的Top-Down思考邏輯來想這個問題,結果我們很容易就可以這樣想:

第N階的走法相當於在N - 1階的時候走一階過來,或者在N - 2階的時候走兩階過來;換句話說,就是第N階的走法等於N - 1階的走法加上N - 2階的走法。

所以我們就可以寫出遞迴式:

F(N) = F(N - 1) + F(N - 2)
F(1) = 1
F(2) = 2

列出來的式子和費波那西數列(Fibonacci)還蠻像的,我們可以用不同的方式去實做解這問題,這問題較適合用動態規劃(Dynamic Programming)去解,直接用Divide and Conquer會重覆計算子問題。由於此問題和費波那西數列相當相似,這邊只簡單實做迭代法和動態規劃的方式。

迭代法

由於每次新的問題的答案來自於前兩個問題,所以每次運算都保留前兩次的資料即可。如果新問題的答案來自前三個問題,則保留三個,以此類推。

動態規劃

使用遞迴的動態規劃則可以記錄過計算過的部分;另外也可以使用迴圈解的動態規劃,在思路上並不複雜,而且也減少Function call的消耗,這邊就不實做此方式,可參考費波那西數列這篇文章。

語法

C#

迭代法

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace DownStairs
{
    class Iterative
    {
        public static long DownStairs(int n)
        {
            long v1 = 1;
            long v2 = 2;
            long result = n;
            for (int i = 3; i <= n; ++i)
            {
                result = v2 + v1;
                v1 = v2;
                v2 = result;
            }
            return result;
        }
    }
}

動態規劃

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace DownStairs
{
    class DynamicProgramming
    {
        static Dictionary<int, long> map = new Dictionary<int, long>() { { 1, 1 }, { 2, 2 } };
        public static long DownStairs(int n)
        {
            if (map.ContainsKey(n))
                return map[n];
            return map[n] = DownStairs(n - 1) + DownStairs(n - 2);
        }
    }
}

Java

迭代法

public class Iterative {
	public static long DownStairs(int n)
    {
        long v1 = 1;
        long v2 = 2;
        long result = n;
        for (int i = 2; i <= n; ++i)
        {
            result = v2 + v1;
            v1 = v2;
            v2 = result;
        }
        return result;
    }
}

動態規劃

import java.util.HashMap;
import java.util.Map;


public class DynamicProgramming {
	static Map map = new HashMap() {{ put(1, 1L); put(2, 2L); }};
    public static long DownStairs(int n)
    {
        if (map.containsKey(n))
            return map.get(n);
        map.put(n, DownStairs(n - 1) + DownStairs(n - 2));
        return map.get(n);
    }
}

C++

迭代法

Iterative.h

#ifndef ITERATIVE_H
#define ITERATIVE_H


class Iterative
{
    public:
        static long DownStairs(int n);
    protected:
    private:
};

#endif // ITERATIVE_H

Iterative.cpp

#include "Iterative.h"

long Iterative::DownStairs(int n)
{
    long v1 = 1;
    long v2 = 2;
    long result = n;
    for (int i = 3; i <= n; ++i)
    {
        result = v2 + v1;
        v1 = v2;
        v2 = result;
    }
    return result;
}

動態規劃

DynamicProgramming.h

#ifndef DYNAMICPROGRAMMING_H
#define DYNAMICPROGRAMMING_H

#include <map>

using namespace std;

class DynamicProgramming
{
    public:
        static long DownStairs(int n);
    protected:
    private:
        static pair init[];
        static map m;
};

#endif // DYNAMICPROGRAMMING_H

DynamicProgramming.cpp

#include "DynamicProgramming.h"

pair DynamicProgramming::init[] = { make_pair(1, 1), make_pair(2, 2) };
map DynamicProgramming::m(DynamicProgramming::init, DynamicProgramming::init + 2);
long DynamicProgramming::DownStairs(int n)
{
    if (DynamicProgramming::m.count(n) == 1)
        return DynamicProgramming::m[n];
    return DynamicProgramming::m[n] = DynamicProgramming::DownStairs(n - 1) + DynamicProgramming::DownStairs(n - 2);
}

效能實測部分同樣可參考費波那西數列一文。

下載

VS2010 C#版本

Eclipse Java版本

Code::Blocks C++版本

延伸閱讀

本文的標題叫做上下樓梯問題&(籃球)得分問題,到底跟分數有甚麼關係?其實得分問題本質上和上下樓梯是一樣的,只是換不同描述方式,通常會以籃球比賽為例:

籃球比賽可能的得分方式有一分球、兩分球和三分球,得N分的方式有幾種?

看完題目描述之後就可以看出來是差不多的,只是組合的方式變更多種。

文章標籤
創作者介紹

小殘的程式光廊

emn178 發表在 痞客邦 PIXNET 留言(0) 人氣()