算法/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