# Algorithmen für Anfänger



## stevoo (9. Nov 2011)

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 (9. Nov 2011)

Probiers doch mit nem Beispielarray mal aus 

Ja, deine Antwort stimmt.


----------



## stevoo (9. Nov 2011)

EikeB hat gesagt.:


> 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 (9. Nov 2011)

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 (9. Nov 2011)

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 (9. Nov 2011)

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


----------



## stevoo (9. Nov 2011)

EikeB hat gesagt.:


> 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 (9. Nov 2011)

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! (10. Nov 2011)

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 (10. Nov 2011)

langhaar! hat gesagt.:


> 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! (10. Nov 2011)

Du verwechselst anscheinend Felder, Feldindices, Variablen und Zahlen.


----------



## stevoo (10. Nov 2011)

Jetzt habe ich es verstanden. Danke


----------



## stevoo (10. Nov 2011)

passt


----------



## stevoo (14. Nov 2011)

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 (14. Nov 2011)

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 (14. Nov 2011)

Marcinek hat gesagt.:


> Hallo,
> 
> daraus Pseudocode zu machen ist mehr als Trivial.
> 
> ...



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


----------



## Marcinek (14. Nov 2011)

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


----------



## stevoo (14. Nov 2011)

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 (14. Nov 2011)

Nein.

Wie es richtig ist, steht in meinem Post oben.


----------

