0

グラフでのシンク検出に関する Pascal への実装があります。コードは次のとおりです。

FUNCTION KATAVOTHRA (A:MATRIX; N:INTEGER): INTEGER;
VAR 
  I,J,K,S:INTEGER;
BEGIN
  KATAVOTHRA:=0;  
  I:=1;
  WHILE (KATAVOTHRA=0 AND I<N) DO   {1}
  BEGIN
    J:=1;
    WHILE (A[I,J]=0 AND J<N) DO J:=J+1;  {2}
    IF (J=N) THEN BEGIN
      S:=0;
      FOR K:=1 TO N DO S:=S+A[K,I];
      IF (S=N-1) THEN 
        KATAVOTHRA:=1;
    END;
    I:=I+1;
  END;    
END;

次の隣接行列があると仮定します。

 0 0 1
 1 0 1
 0 0 0

V1、V2およびV3頂点用。(2 つのノード間に接続がある場合は 1 コード、それ以外の場合はゼロ コード)。

この入力でコードをトレースしようとしていますが、できません。その理由は、私が 3 のときに結果を取得しないためです。これまでに行ったことを見てみましょう: (KATAVOTHRAはシンクの名前です)。

BEGIN with I:=1; and J:=1(最初の while ループの内側)

最初にA[1,1]がゼロかどうかを確認し、それが (続行するために 1 < 3 もちろん) であることを確認します。J= J+1 => J=2

A[1,2]もゼロなので、J を再度インクリメントすると、J は 3 になります。3 は 3 未満でA[1,3]はなく、0 ではありません。したがって、IF ステートメントにIF( J = N) => IF( 3 = 3 ) then S=0 (sum) 進むので、FOR ループに進み、要約します。A[1,1] + A[2,1] + A[3,1]

IF( S = N-1) THEN私たちはシンクを見つけました。しかし、ここでは 2 ではありS=1ません。FOR ループから出ます。私は今 2 になります。再びWHILE(KATAVOTHRA=0 AND 2<3)J は 1 です。今チェックしてA[2,1]いますが、ゼロではなく、2 は 3 ではありません。しかし、今回は 3 < 3 は偽なので、ループ全体がそこで終了しますか? 理解できません（パスカル言語の経験はあまりありませんが）。

これの何が問題なのですか？

4

1 に答える 1

1

そして私は今3になります....しかし、今回は3 < 3は偽なので、ループ全体がそこで終了しますか?

すでに指摘したように、ループの終了は 1 つの数値が早すぎます。これを回避するには、 をテストする必要がありますI <= N。

2 つのバリアントを示す短いプログラムを次に示します。

PROGRAM LoopTest;

VAR
   i : Integer;

BEGIN
   WriteLn("Example with <");
   i := 0;
   WHILE (i < 3) DO
   BEGIN
      WriteLn(" Loopvar: ", i);
      i := i + 1;
   END;
   WriteLn;

   WriteLn("Example with <=");
   i := 1;
   WHILE (i <= 3) DO
   BEGIN
      WriteLn(" Loopvar: ", i);
      i := i + 1;
   END;
END.

そして出力：

Example with <
 Loopvar: 0
 Loopvar: 1
 Loopvar: 2

Example with <=
 Loopvar: 1
 Loopvar: 2
 Loopvar: 3

簡単に確認できるようになりました。

  • <ゼロベースの配列に使用されます
  • <=1 ベースの配列に使用されます
于 2014-11-22T01:06:37.493 に答える