Algorithmen für Anfänger

[stevoo]

Erstmal hallo! Ich war schon einmal in diesem Forum, wegen der java installation. Nun der zweite Schritt Um programmieren zu können muss man Algorithmen verstehen. Unten seht ihr eine Frage aus einem Buch, welche ic beantwortet habe. Ist meine Antwort richtig?

Wir betrachten den folgenden Algorithmus, dem als Eingabe ein Array a aus n natürlichen
Zahlen übergeben wird und der als Ausgabe zwei Zahlen x und y liefert.
Input: Array a der Länge n
x := a[0]
y := a[0]
for i = 1 to n − 1 do
if x > a then
x := a
end if
if y < a then
y := a
end if
end for
Output: x, y
a) Was berechnet der obige Algorithmus? Antwort: Er untersucht das Feld bis n-1. Für x sucht er den kleinsten Wert für y den größten.

 

[Gast2]

Probiers doch mit nem Beispielarray mal aus

Ja, deine Antwort stimmt.

 

[stevoo]

Probiers doch mit nem Beispielarray mal aus

Ja, deine Antwort stimmt.

Ja ich hab mir ein Feld mit n=6 aufgezeichnet und für die arrays beliebige Zahlen eingefügt

 

[stevoo]

b) Wie viele Vergleiche führt der obige Algorithmus durch? Hierbei sollen nur Vergleiche mit Elementen aus a berücksichtigt werden.
Antwort: Er führt (1,2,.....,n-1) Vergeliche für x und für y durch

Ist das richtig?

 

[stevoo]

c) Geben Sie einen Algorithmus in Pseudocode an, der dasselbe Problem wie der obige Algorithmus
löst und dafür höchstens 3/2n Vergleiche von Elementen aus a benötigt. Beschreiben
Sie zusätzlich die Grundidee Ihres Algorithmus in wenigen Sätzen.

Bei dieser Frage tue ich mich schon schwer, weil ich es eben selber schreiben muss. Ihr wisst bestimmt sofort die Antwort, aber bitte antwortet nicht, bevor ich nicht geantwortet hab.

 

[Gast2]

Es werden schonmal 2 Antworten gefordert, also fehlt bei dir schonmal was. Aber auch der erste Teil der Antwort ist nicht richtig.

 

[stevoo]

Es werden schonmal 2 Antworten gefordert, also fehlt bei dir schonmal was. Aber auch der erste Teil der Antwort ist nicht richtig.

Wie viele Vergleiche führt der obige Algorithmus durch? Hierbei sollen nur Vergleiche mit
Elementen aus a berücksichtigt werden.

Dann vielleicht für x-->n-1
für y-->(n-1)-1 (Weil die eine Position wo sich x befindet ja schon vergeben ist)

PS: Lassen wir fürs erste den 2ten Teil der Frage außer Acht

 

[stevoo]

Vergissts die Frage c, soweit bin ich noch nicht.

Aber hier eine Frage zum Programmablaufplan

Wie oft wird "Hallo" ausgegeben


Start
(Pfeil nach unten)
x<--1
(Pfeil nach unten)
x<100 (Pfeil auf die Seite mit falls "NEIN") Ende
(Pfeil nach unten mit falls "JA")
Print "Hallo"
(Der Pfeil geht links zurück an die Stelle nach "x<--1" also vor x<100)

Ich meine "Hallo" wird nur einmal ausgegeben, weil es keinen zusätzlichen Befehl gibt, dass x die Positionen von 1 bis Hundert immer einzeln verschiebt. oder?

 

[langhaar!]

X ist immer kleiner 100, da es nirgendwo erhöht wird.
Somit wird der Text unendlich oft ausgegeben (vielleicht hast du eine Zeile vergessen?)

Deine Anmerkung 'dass x die Positionen von 1 bis Hundert immer einzeln verschiebt.' verstehe ich nicht.
Wenn x eine Zahl sein soll, gibt es weder Positionen noch irgendetwas, was verschoben werden kann.

 

[stevoo]

X ist immer kleiner 100, da es nirgendwo erhöht wird.
Somit wird der Text unendlich oft ausgegeben (vielleicht hast du eine Zeile vergessen?)

Deine Anmerkung 'dass x die Positionen von 1 bis Hundert immer einzeln verschiebt.' verstehe ich nicht.
Wenn x eine Zahl sein soll, gibt es weder Positionen noch irgendetwas, was verschoben werden kann.

Ich dachte hier ist x nur die Position und keine Zahl. Mit Unendlich hast du schon Recht. Wenn x immer an der Position 1 bleibt wird es ein Kreislauf. Ich hätte gedacht, dass 100 in diesem Fall =(z.B.)n ist. Also die Anzahl der Felder und nicht eine Zahl im Feld.

Ich stelle mir das so vor: x wird an Position 1 gesetzt. Dann: Falls x ist kleiner die mögliche Anzahl der Positionen(hier n=100 x=1) dann Print hallo. Da es dann keine Befehle zum verschieben von Positionen gibt, wird es ein unendlicher Kreislauf. ODER VERWECHSLE ICH hier x mit i vom ersten Beispiel(ganz oben)?

 

[langhaar!]

Du verwechselst anscheinend Felder, Feldindices, Variablen und Zahlen.

 

[stevoo]

Jetzt habe ich es verstanden. Danke

 

[stevoo]

passt

 

[stevoo]

Wie schaut der Pseudocode für diesen Algorithmus(siehe Link) aus. Ich habe keine Idee, weil er so viele Bedinungen hat.

Link: Img002 - Speedy Share - upload your files here

Ungefähr so?:

j=n

While j>1 do
max=1
i=2

If i<==j

If K(i)>K(max) //Wie knöpfe ich eine zweite Bedinung an?
max=i
i=i+1

Else
i=i+1
EndIF

Else
Hilf=K(j)
K(j)=K(max)
K(max)=Hilf
j=j-1
ENDIF
?
?

Ps: DAS IST KEINE HAUSAUFGABE, DAS WILL ICH ENFACH LERNEN.

 

[Marcinek]

Hallo,

daraus Pseudocode zu machen ist mehr als Trivial.

Du musst das doch nur ablesen -.-

function x (int n, K) {

  int j = n;
  int max;

  while ( j > 1 ) {
    max = 1;
    i = 2;
    while (i <= j) {
        if ( K[i] > K[max] ) {
          max = i;
          i = i +1;
        } // if
       } // while
      int Hilf = K[j];
      K[j] = K[max];
      K[max] = Hillf;
      j = j-1;
    } // außen while
  }

Was der Algo macht steht auf deinem Bild.

Gruß,
Martin

 

[stevoo]

Hallo,

daraus Pseudocode zu machen ist mehr als Trivial.

Du musst das doch nur ablesen -.-

function x (int n, K) {

  int j = n;
  int max;

  while ( j > 1 ) {
    max = 1;
    i = 2;
    while (i <= j) {
        if ( K[i] > K[max] ) {
          max = i;
          i = i +1;
        } // if
       } // while
      int Hilf = K[j];
      K[j] = K[max];
      K[max] = Hillf;
      j = j-1;
    } // außen while
  }

Was der Algo macht steht auf deinem Bild.

Gruß,
Martin

Wenn K(i)<K(max) ist müsste er doch max=1 auslassen, oder? Bei dir wird es aber nicht erwähnt.

 

[Marcinek]

ja da endet oder wird die while schleife (innere) nicht betreten.

 

[stevoo]

Passt das so?:
j=n

While j>1 do
max=1
i=2

While i<==j

If K(i)>K(max)
max=i
i=i+1

Else
i=i+1
EndIF
Endwhile

Hilf=K(j)
K(j)=K(max)
K(max)=Hilf
j=j-1
Endwhile

 

[Marcinek]

Nein.

Wie es richtig ist, steht in meinem Post oben.