Montag, 18. Mai 2015

Enter the matrix



Given the following definitions...

const
  SIZE = 5;
  type
  tMatrix = array [1..SIZE,1..SIZE] of integer;

  var
  A : tMatrix;
  temp,
  i,
  j : integer;

...and some code to read the matrix values from the command line...

{ read the matrix values for A: }
  for i := 1 to SIZE do
    for j := 1 to SIZE do
      readln (A[i,j]);

...which of the following code snippets transforms this matrix...


...into...

?

[A] begin
        for i := 1 to SIZE-1 do
          for j := i+1 to SIZE do
          begin
            temp := A[i,j];
            A[i,j] := A[j,i];
            A[j,i] := temp
          end
        end;

Outer for-loop i = 1 and inner for-loop j = 2, j = 3, j = 4 and j = 5


Outer for-loop i = 2 and inner for-loop j = 3, j = 4 and j = 5


Outer for-loop i = 3 and inner for-loop j = 4 and j = 5


Outer for-loop i = 4 inner for-loop j = 5


Done. Correct transformation.

[B] begin
        for i := 1 to SIZE do
          for j := 1 to i do
          begin
            temp := A[i,j];
            A[i,j] := A[j,i];
            A[j,i] := temp
          end
        end;

Outer for-loop i = 1, inner for-loop j = 1
Outer for-loop i = 2, inner for-loop j = 1 and j = 2
Outer for-loop i = 3, inner for-loop j = 1, j = 2 and j = 3
Outer for-loop i = 4, inner for-loop j = 1, j = 2, j = 3 and j = 4
Outer for-loop i = 5, inner for-loop j = 1, j = 2, j = 3, j = 4 and j = 5

This algorithm basically does the same as the algorithm of option A.
In addition it also touches the elements at position A[1, 1], A[2, 2], A[3, 3]... and replaces those elements with themselves.

Correct but slower than the algorithm of option A.

[C] begin
        for i := 1 to SIZE do
          for j := 1 to SIZE do
          begin
            temp := A[i,j];
            A[i,j] := A[j,i];
            A[j,i] := temp
          end
        end;

Looks similar to the algorithm of option B with one subtle difference:
"for j := 1 to SIZE do" instead of "for j := 1 to i do"

Outer for-loop i = 1, inner for-loop j = 1, j = 2, j = 3, j = 4 and j = 5
So far so good. All elements in the first row changed places with the elements in the first column.

Outer for-loop i = 2, inner for-loop j = 1, j = 2, j = 3, j = 4 and j = 5

That's where the algorithm fails. The algorithm already touched the element A[2, 1] to replace it with element A[1, 2]. Now it replaces those elements again.

[D] begin
        for i := 1 to SIZE do
          for j := 1 to SIZE-i do
          begin
            temp := A[i,j];
            A[i,j] := A[j,i];
            A[j,i] := temp
          end
        end;

Basically the same error as the algorithm of option C. Elements that already changed places, change places again.
In addition, "for j := 1 to SIZE-i do" causes the algorithm to touch less and less columns as the value of the row count i increases.

[E] begin
        for i := 1 to SIZE-1 do
          for j := i+1 to SIZE do
          begin
            temp := A[i,j];
             A[j,i] := A[i,j];
             A[j,i] := temp
           end
         end;

This one cannot work.
The assigned value of variable temp is A[i,j].
Next, the value of A[i,j] is assigned to A[j,i], which is the same value as temp.
In the end value of temp is assigned to A[j,i], a value it already holds.
A[i,j] never gets a new value though.

Keine Kommentare:

Kommentar veröffentlichen