Ada 程式設計/演算法/第 6 章

第 6 章：動態規劃

斐波那契數列

簡單實現

檔案：fibonacci_1.adb (檢視, 純文字, 下載頁面, 瀏覽全部)

...

為了計算斐波那契數列，不需要負值，因此我們定義了一個從 0 開始的整數型別。定義了整數型別後，您可以計算到 Fib (87)。Fib (88) 將導致 Constraint_Error。

  type Integer_Type is range 0 .. 999_999_999_999_999_999;

您可能會注意到，原始示例中沒有 assert (n >= 0) 的等效項。Ada 將在函式呼叫之前測試引數的正確性。

  function Fib (n : Integer_Type) return Integer_Type is
  begin
     if n = 0 then
        return 0;
     elsif n = 1 then
        return 1;
     else
        return Fib (n - 1) + Fib (n - 2);
     end if;
  end Fib;

...

快取實現

檔案：fibonacci_2.adb (檢視, 純文字, 下載頁面, 瀏覽全部)

...

對於此實現，我們需要一種特殊的快取型別，它還可以儲存 -1 作為“未計算”標記

  type Cache_Type is range -1 .. 999_999_999_999_999_999;

用於計算斐波那契數列的實際型別繼續從 0 開始。由於它是子型別 的快取型別，Ada 將自動在這兩者之間進行轉換。(轉換當然會檢查有效性)

  subtype Integer_Type is Cache_Type range
     0 .. Cache_Type'Last;

為了知道快取需要多大，我們首先從命令列讀取實際值。

  Value : constant Integer_Type :=
     Integer_Type'Value (Ada.Command_Line.Argument (1));

快取陣列從元素 2 開始，因為 Fib (0) 和 Fib (1) 是常數，並以我們要計算的值結束。

  type Cache_Array is
     array (Integer_Type range 2 .. Value) of Cache_Type;

快取被初始化為快取型別的第一個有效值——即 -1。

  F : Cache_Array := (others => Cache_Type'First);

以下是實際演算法。

  function Fib (N : Integer_Type) return Integer_Type is
  begin
     if N = 0 or else N = 1 then
        return N;
     elsif F (N) /= Cache_Type'First then
        return F (N);
     else
        F (N) := Fib (N - 1) + Fib (N - 2);
        return F (N);
     end if;
  end Fib;

...

此實現忠實於演算法書籍中的原始實現。但是，在 Ada 中，您通常會以略微不同的方式進行

檔案：fibonacci_3.adb (檢視, 純文字, 下載頁面, 瀏覽全部)

當您使用稍大的陣列時，該陣列還儲存元素 0 和 1 並將其初始化為正確的值

  type Cache_Array is
     array (Integer_Type range 0 .. Value) of Cache_Type;

  F : Cache_Array :=
     (0      => 0,
      1      => 1,
      others => Cache_Type'First);

然後您可以刪除第一個if 路徑。

     if N = 0 or else N = 1 then
        return N;
     elsif F (N) /= Cache_Type'First then

這將節省大約 45% 的執行時間 (在 Linux i686 上測量)，同時只需要在快取陣列中新增兩個元素。

記憶體最佳化實現

此版本看起來與 WikiCode 中的原始版本完全一樣。

檔案：fibonacci_4.adb (檢視, 純文字, 下載頁面, 瀏覽全部)

  type Integer_Type is range 0 .. 999_999_999_999_999_999;

  function Fib (N : Integer_Type) return Integer_Type is
     U : Integer_Type := 0;
     V : Integer_Type := 1;
  begin
     for I in  2 .. N loop
        Calculate_Next : declare
           T : constant Integer_Type := U + V;
        begin
           U := V;
           V := T;
        end Calculate_Next;
     end loop;
     return V;
  end Fib;

沒有 64 位整數

您的 Ada 編譯器不支援 64 位整數嗎？然後您可以嘗試使用十進位制數。使用十進位制數會導致程式變慢 (大約需要三倍的時間)，但結果將相同。

以下示例展示瞭如何定義合適的十進位制型別。請嘗試位數 和範圍 引數，直到您從 Ada 編譯器中獲得最佳結果。

檔案：fibonacci_5.adb (檢視, 純文字, 下載頁面, 瀏覽全部)

  type Integer_Type is delta 1.0 digits 18 range
     0.0 .. 999_999_999_999_999_999.0;

您應該知道，浮點數不適合計算斐波那契數列。當計算的數字過大時，它們不會報告錯誤條件——相反，它們會失去精度，這會使結果毫無意義。