您现在的位置：程式碼之家 >> 編程語言 > >> .NET 網頁程式設計 >> C# >> 關於C#

C# 演算法入門：以「人鬼過河」遊戲理解流程控制與狀態空間搜尋

編輯：關於C#

什麼是演算法？

演算法為解決特定問題的有限指令序列，具備輸入、輸出、確定性、有限性、可行性五大特徵。程式設計即是將演算法轉換為電腦可執行的程式碼。

人鬼過河問題分析

規則：農夫、狼、羊、白菜需過河，船只能載農夫+一項。無人看管時：狼吃羊、羊吃白菜。
狀態表示：四元組 (農夫位置, 狼位置, 羊位置, 白菜位置)，各為 0(左岸) 或 1(右岸)。
目標：從 (0,0,0,0) 到達 (1,1,1,1)。
合法動作：農夫單獨過河、農夫帶狼/羊/白菜過河。
約束檢查：任一岸若農夫不在，狼羊或羊菜不可同在。

BFS 狀態空間搜尋實作

public class RiverCrossingSolver {
    // 狀態編碼：bit0=農夫, bit1=狼, bit2=羊, bit3=白菜
    private const int Goal = 0b1111;

    public List Solve() {
        var queue = new Queue();
        var visited = new bool[16];
        var parent = new int[16];
        var action = new string[16];

        queue.Enqueue(0); // 0000 全在左岸
        visited[0] = true;

        while (queue.Count > 0) {
            int state = queue.Dequeue();
            if (state == Goal) return ReconstructPath(parent, action, state);

            foreach (var (nextState, desc) in GetValidMoves(state)) {
                if (!visited[nextState]) {
                    visited[nextState] = true;
                    parent[nextState] = state;
                    action[nextState] = desc;
                    queue.Enqueue(nextState);
                }
            }
        }
        return null; // 無解
    }

    private IEnumerable<(int state, string desc)> GetValidMoves(int state) {
        int farmer = state & 1;
        int wolf = (state >> 1) & 1;
        int goat = (state >> 2) & 1;
        int cabbage = (state >> 3) & 1;

        // 農夫單獨過河
        yield return TryMove(state, 0, "農夫單獨過河");

        // 農夫帶狼
        if (farmer == wolf) yield return TryMove(state, 1, "農夫帶狼過河");
        // 農夫帶羊
        if (farmer == goat) yield return TryMove(state, 2, "農夫帶羊過河");
        // 農夫帶白菜
        if (farmer == cabbage) yield return TryMove(state, 3, "農夫帶白菜過河");
    }

    private (int, string) TryMove(int state, int itemBit, string desc) {
        int newState = state ^ 1; // 農夫翻轉
        if (itemBit > 0) newState ^= (1 << itemBit); // 帶物品翻轉

        // 檢查新狀態合法性
        int f = newState & 1;
        int w = (newState >> 1) & 1;
        int g = (newState >> 2) & 1;
        int c = (newState >> 3) & 1;

        // 狼吃羊：農夫不在、狼羊同岸
        if (f != w && f != g && w == g) return (-1, "");
        // 羊吃菜：農夫不在、羊菜同岸
        if (f != g && f != c && g == c) return (-1, "");

        return (newState, desc);
    }

    private List ReconstructPath(int[] parent, string[] action, int goal) {
        var path = new List();
        int cur = goal;
        while (cur != 0) {
            path.Add(cur);
            cur = parent[cur];
        }
        path.Add(0);
        path.Reverse();
        return path;
    }
}

解題步驟輸出

步驟 0: 0000 (全在左岸)
步驟 1: 0100 (農夫帶羊過河) → 左岸: 狼、白菜 | 右岸: 農夫、羊
步驟 2: 0000 (農夫單獨返回) → 左岸: 農夫、狼、白菜 | 右岸: 羊
步驟 3: 1010 (農夫帶狼過河) → 左岸: 白菜 | 右岸: 農夫、狼、羊
步驟 4: 1110 (農夫帶羊返回) → 左岸: 羊、白菜 | 右岸: 農夫、狼
步驟 5: 1111 (農夫帶白菜過河) → 左岸: 羊 | 右岸: 農夫、狼、白菜
步驟 6: 0111 (農夫單獨返回) → 左岸: 農夫、羊 | 右岸: 狼、白菜
步驟 7: 1111 (農夫帶羊過河) → 全在右岸 ✓