《圖說演算法-使用C#》要點摘錄 – 「常見演算法」

分治法

• 反覆分割問題，使子問題規模不斷縮小，直到這些子問題足夠簡單到可以解決，最後將各子問題的解合併得到原問題的解答

遞歸

• 一個函數由自身定義或呼叫

• 必須要有2個條件

  • 中止遞歸出口

  • 遞歸執行過程

• 例子：菲波那契數列

  • public static int Fibonacci(int idx)
    {
        if (idx == 0) { return 0; }
        else if (idx == 1) { return 1; }
        else { return Fibonacci(idx - 1) + Fibonacci(idx - 2); }
    }

動態規劃（Dynamic Programming）

• 類似分治法，但會利用某種數據結構將子問題的解保存起來

• 當解決一樣的子問題時，就可以直接從數據結構中得到子問題的解並返回，而不需要重新解決一次子問題。

• 例子：優化的菲波那契數列

  • static Dictionary<int, int> fibonacciResultMemo = new Dictionary<int, int>()
    {
        {0, 0 },
        {1, 1 }
    };
    ​
    public static int Fibonacci(int idx)
    {
        if (fibonacciResultMemo.ContainsKey(idx)) { return fibonacciResultMemo[idx]; }
        else
        {
            int res = Fibonacci(idx - 1) + Fibonacci(idx - 2);
            fibonacciResultMemo.Add(idx, res);
            return res;
        }
    }

迭代

• 結果無法用公式一次求解，需要利用迴圈反覆運算

• 迴圈結構的三個條件：

  • 標記迴圈起點和進度的變數

  • 循環條件

  • 迴圈變數的增減值

• 例子：計算階層

  • public static int Stairs(int targetStair)
    {
        int sum = 1;
        for (int i = 0; i <= targetStair; i++)
        {
            sum = 1;
            for (int j = i; j > 0; j--)
            {
                sum = sum * j;
            }
        }
        return sum;
    }

Pascal’s Triangle

• rC0 = 1 => 每一列的第0欄的值一定為1

• rCn = rCn-1 * (r – n + 1)/n => 某欄某列元素值公式

  • r = row

  • n = column

回溯法

• 窮舉法的一種，但在發現目標不正確後馬上返回上一層，而不遞歸到下一層

  • 作者的例子是只能局限在知道終點在起點的方位（右下角）的前提下才能生效的，但如果不知道起、終點的位置，實際上只能使用DFS進行搜索。

  • 修改版：

    • static void Main(string[] args)
      {
          (int x, int y) start = (1, 1);
          (int x, int y) exit = (8, 2);
          int[,] maze = new int[10, 12]
          {
              {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
              {1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1 },
              {1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1 },
              {1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1 },
              {1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1 },
              {1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1 },
              {1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1 },
              {1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1 },
              {1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1 },
              {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
          };
      ​
          FindPathInMaze(start, exit, maze);
      ​
          Console.WriteLine();
      }
      public static void FindPathInMaze((int x, int y) startPos, (int x, int y) goalPos, int[,] maze)
      {
          Stack<(int x, int y)> pathStack = new Stack<(int x, int y)>();
          pathStack.Push(startPos);
      ​
          while (pathStack.Count > 0)
          {
              (int x, int y) currPath = pathStack.Pop();
      ​
              //Reach Goal, Break Loop
              if (currPath.x == goalPos.x && currPath.y == goalPos.y)
              {
                  maze[currPath.x, currPath.y] = 2;
                  break;
              }
      ​
              //Set Current 
              maze[currPath.x, currPath.y] = 2;
      ​
              if (maze[currPath.x - 1, currPath.y] == 0)
              {
                  pathStack.Push((currPath.x - 1, currPath.y));
              }
              if (maze[currPath.x + 1, currPath.y] == 0)
              {
                  pathStack.Push((currPath.x + 1, currPath.y));
              }
              if (maze[currPath.x, currPath.y + 1] == 0)
              {
                  pathStack.Push((currPath.x, currPath.y + 1));
              }
              if (maze[currPath.x, currPath.y - 1] == 0)
              {
                  pathStack.Push((currPath.x, currPath.y - 1));
              }
          }
      }

貪心算法

• 只考慮局部而不考慮大局，通過每一次計算都選擇當前最好的選擇，逐步逼近目標

• 不能保證最後的解是最佳解