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;

您应该知道浮点数不适合计算斐波那契数列。当计算的数字变得太大时，它们不会报告错误条件 - 而是会失去精度，这使得结果变得毫无意义。