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 (倍長整数) であることに注意してください。したがって、範囲チェックを行わない限り、使用される型のサイズは必ずしも互換性があるとは限りません。ただし、中間に c の 2 倍の幅の整数型と pmod を使用した場合、中間計算のオーバーフローがないことを保証できます。

どのパスカル コンパイラを使用しているかわかりません。古い (DOS) バージョンでは、整数は 16 ビット、倍長整数は 32 ビットだったと思います。Delphi では、integer と longint はどちらも 32 ビットで、int64 は 64 ビットです。したがって、コンパイラによっては、a、b および中間体に longint を、c および pmod に整数を使用できます (または、新しい Pascal バージョンの場合、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 に答える