Ada 程式設計/演算法

歡迎來到演算法華夏公益教科書的 Ada 實現。對於那些不熟悉 Ada 程式設計的人，這裡有一些注意事項。

所有示例都是完全可執行的，包含所有必要的輸入和輸出操作。但是，只有用於概述演算法的程式碼被複制到文字中 - 完整的示例可以透過下載連結獲取。 (注意：更新 cvs 可能需要長達 48 小時).
本書中的演算法是用虛擬碼編寫的。每種計算機語言都有自己的約定來編寫識別符號；一些語言區分大小寫，Ada 不區分；一些語言使用駝峰式命名法。 Ada 使用約定用下劃線分隔單詞，並將每個單詞的首字母大寫。對於數值， Ada 使用約定用下劃線分隔數字組，以便更好地閱讀 - 比較 10000000 和 10_000_000 或 5000001 和 50_000_01（例如 50000 歐元和 1 分）。
我們在示例程式碼中很少使用預定義型別，而是定義適合所用演算法的特殊型別。
Ada 允許使用預設函式引數；但是，我們始終填寫並命名所有引數，以便讀者可以看到有哪些選項可用。
我們很少使用快捷方式 - 比如使用屬性 Image 或 Value 進行 String <=> Integer 轉換。

所有這些規則使程式碼比可能需要的更復雜。但是，我們也希望這能使程式碼更容易理解。

第 1 章：介紹

以下子程式是演算法中“發明演算法”例子的實現。

轉換為小寫

Ada 示例程式碼不會像演算法那樣追加到陣列中。相反，我們建立一個所需長度的空陣列，然後替換其中的字元。

  function To_Lower (C : Character) return Character renames
     Ada.Characters.Handling.To_Lower;

  --  tolower - translates all alphabetic, uppercase characters
  --  in str to lowercase
  function To_Lower (Str : String) return String is
     Result : String (Str'Range);
  begin
     for C in  Str'Range loop
        Result (C) := To_Lower (Str (C));
     end loop;
     return Result;
  end To_Lower;

Ada 中追加方法不可能嗎？不，但這會更加複雜和緩慢。

忽略大小寫比較

檔案：to_lower_2.adb (檢視, 純文字, 下載頁面, 瀏覽所有)

  --  equal-ignore-case -- returns true if s or t are equal,
  --  ignoring case
  function Equal_Ignore_Case
    (S    : String;
     T    : String)
     return Boolean
  is
     O : constant Integer := S'First - T'First;
  begin
     if T'Length /= S'Length then
        return False;  --  if they aren't the same length, they
                       --  aren't equal
     else
        for I in  S'Range loop
           if To_Lower (S (I)) /=
              To_Lower (T (I + O))
           then
              return False;
           end if;
        end loop;
     end if;
     return True;
  end Equal_Ignore_Case;

第 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 開始。由於它是快取型別的subtype， 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 位整數嗎？然後您可以嘗試使用十進位制數代替。使用十進位制數會導致程式速度變慢 (大約慢三倍)，但結果會相同。

以下示例向您展示如何定義合適的十進位制型別。試著調整digits 和range 引數，直到您從 Ada 編譯器中獲得最佳效果。

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

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

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