1

我正在尝试为我学校编程团队的在线评委制作一个 Pascal 程序。程序必须输出 a^b mod c，其中 a、b 和 c 作为输入给出。您不能使用蛮力，因为测试用例都有非常大的数字。

经过一番研究，事实证明我可以使用分而治之的策略。这是我想出的代码：

function pmod(a,b,c:longint):integer;
begin
     if b = 0 then
        pmod := 1;
     if b = 1 then
        pmod := a mod c;
     if b > 1 then
     begin
          if (b mod 2) = 0 then
             pmod := (pmod(a,b div 2,c) * pmod(a,b div 2,c)) mod c
          else
              pmod := (pmod(a,b-1,c) * (a mod c)) mod c;
     end;
end;

但是，在线法官返回了错误的答案。有人能指出代码有什么问题吗？

4

1 回答 1

0

您的算法基本上是合理的，应该可以工作。您的代码中肯定有一些小事情可以改进，但我不会称之为“错误”。让我们看看一些可能的问题。

  1. 递归。它的优点是保持算法简单且相当容易阅读。然而，这是一种非常缓慢且低效的方法。由于相同的基本算法可以相当容易地进行迭代，因此法官可能已将您标记为低级。

  2. 更好地处理无效输入是个好主意。如果有人为“b”输入负整数，则不会为 pmod 分配返回值。由于模数总是返回一个肯定的结果，我们可以制定一个约定，例如如果 b<0，则返回“-1”作为错误标志。

  3. 注意 pmod 返回整数，但是模的最大值是 c-1，也就是 longint。所以使用的类型的大小不一定兼容，除非你做一些范围检查。但是，如果您使用两倍于 c 和 pmod 宽度的整数类型用于中间计算，则可以保证中间计算不会溢出。

我不确定您使用的是什么帕斯卡编译器。在较旧的（DOS）版本中，我认为整数是 16 位，而 longint 是 32 位。在 Delphi 中，整数和 longint 都是 32 位的，而 int64 是 64 位的。因此，根据编译器的不同，您可以为 a、b 和中间体设置 longint，为 c 和 pmod 设置整数（或者在较新的帕斯卡版本的情况下，a、b 和中间体的 int64 以及 c 和 pmod 的整数。

这是这些小改进的示例。

function pmod(a,b: int64; c:integer):integer;
var tmp: int64;
 begin
   if b < 0 then pmod := -1; {flag an error}
   if b = 0 then pmod := 1;
   if b = 1 then pmod := a mod c;
   if b > 1 then
    begin
      if (b mod 2) = 0 then
         begin
           tmp  :=pmod(a,b div 2,c) * pmod(a,b div 2,c);
           pmod := tmp mod c
         end
      else
         begin
           tmp  := pmod(a,b-1,c) * (a mod c);
           pmod := tmp mod c
         end
    end;
 end;
于 2013-03-07T16:23:29.403 回答