演算法/Ada 實現

頂部，章節：1，2，3，4，5，6，7，8，9，A

歡迎來到華夏公益教科書演算法的 Ada 實現。對於那些剛接觸 Ada 程式設計的人，以下是一些注意事項。

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

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

第 1 章：簡介

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

轉換為小寫

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

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

  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;

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

頂部，章節：1，2，3，4，5，6，7，8，9，A