Was macht dieser Algorithmus?

Question

bekam ich einen Pseudo-Code:

Input: Array A with n (= length) >= 2 
Output: x 
x = 0; 
for i = 1 to n do 
    for j = i+1 to n do 
    if x < |A[i] - A[j]| then 
     x = |A[i] - A[j]|; 
    end if 
    end for 
end for 
return x; 

Ich habe umgewandelt, das zu einem echten Code besser zu sehen, was es tut:

public class Test 
{ 
    public static void main (String[] args) 
    { 
     int A[] = {1,2,3,4,5,6,7,8,9}; 
     int x = 0; 

     for (int i = 1; i < A.length; i++) 
     { 
      for (int j = i + 1; j < A.length; j++) 
      { 
       if (x < Math.abs(A[i] - A[j])) 
       { 
        x = Math.abs(A[i] - A[j]); 
       } 
      } 
     } 
     System.out.println(x); 
    } 
} 

Der Ausgang war 7 mit dem Array im Code. Ich habe ein anderes Array (1 bis 20) verwendet und die Putput war 18. Array 1-30, die Ausgabe war 28. Das Muster scheint klar, der Algorithmus gibt Ihnen die vorletzte/dritte von letzten Array-Wert. Oder liege ich falsch?

Answer 1

Ich denke, der Pseudocode versucht, den größeren Unterschied zwischen 2 Elementen innerhalb eines Arrays zu finden.

Ihr realer Code beginnt jedoch mit 1 anstelle von 0 und schließt daher das erste Element in diesem Array aus.

Answer 2

Unter der Annahme aller positiven ganzen Zahlen, findet der Algorithmus in Kürze den Unterschied zwischen dem maximalen und dem minimalen Wert in dem Array. Es wird jedoch nicht korrekt funktionieren, wenn Sie i in der for-Schleife nicht auf 0 initialisieren.

for (int i = 0; i < A.length; i++) 

Answer 3

Der Code gibt den größten Unterschied zwischen zwei beliebigen Elementen im Array.

Es gibt 2 verschachtelte Schleifen, von denen jede über jedes Element des Arrays läuft. Die zweite Schleife beginnt am Element nach dem Element der ersten Schleife, so dass jedes mögliche Paar nur einmal betrachtet wird. Die Variable x ist das aktuelle Maximum, initialisiert auf 0. Wenn x kleiner als der absolute Wert der Differenz des aktuellen Paares ist, dann haben wir ein neues Maximum und es wird gespeichert.

Da Sie jedoch den Startindex des Pseudocodes von 1 direkt kopiert haben, überspringen Sie versehentlich das erste Element des Arrays mit dem Index 0. So gibt Ihnen Ihr Java-Code den maximalen Unterschied, ohne das erste Element zu berücksichtigen.

Wenn Sie ein Array von Werten zwischen 1 und n haben, Sie das Überspringen der 1 (in Index 0) und der zurückgegebene Wert n - 2, die der dritten in den letzten Wert in dem Array werden passiert. Wenn Sie die Werte im Array als einen anderen Testfall gemischt hätten, würden Sie sehen, dass sich der zurückgegebene Wert in n - 1 geändert hätte, da jetzt sowohl 1 als auch n berücksichtigt würden (solange n nicht an erster Stelle steht)).

In jedem Fall müssen Sie den Index des ersten Elements auf 0 setzen, damit das erste Element berücksichtigt wird. Dann würde {1,2,3,4,5,6,7,8,9}8 (oder irgendeine andere Reihenfolge dieser gleichen Elemente) ergeben.

Answer 4

Ich denke, Pseudocode versucht, den größten Unterschied zwischen zwei Zahlen in einem Array zu finden. Es sollte der Unterschied zwischen dem minimalen und maximalen Wert des Arrays sein.

Ich persönlich denke, das ist ein wirklich schlechter Algorithmus, da es diese Aufgabe in O (n^2) macht.Sie können den minimalen und maximalen Wert eines Arrays in O (n) finden. und nehmen Sie den Unterschied zwischen diesen Zahlen und Ergebnis wird das gleiche sein. Überprüfen Sie den Pseudocode

Input: Array A with n (= length) >= 2 
min=A[0];max = A[0]; 
for i = 1 to n do 
     if min > A[i] then 
     min = A[i]; 
     end if 
     if max < A[i] then 
     max = A[i] 
     end if 
end for 
return (max-min);