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;

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