Algorithmus-Problem

[Bela Mutschler]

Hallo,

vielleicht kann mir jemand bei einem kleinen Problem helfen. Mein Prof
gab mir folgende Aufgabe:

(1)Die Hörer einer Hitparade haben ihre Stimmen für je einen von 100
wählbaren Musiktiteln abgegeben. Geben Suie einen Algorithmus an, der
daraus die 10 Titel mit den meisten Stimmen heraussucht. Wieviele
Elementarschritte führt der Algorithmus im schlechtesten und im
günstigsten Fall aus?

(2)Finde einen Algorithmus, der die kleinste und die größte Zahl einer
Folge von Zahlen a1 ... an (n gerade) bestimmt. Versuche, mit möglichst
wenigen Schritten auszukommen. Wieviele Elementarschritte führt der
Algorithmus im günstigsten und im schlechtesten Fall aus?

Wäre dankbar für jede Hilfestellung oder Lösungsansatz.

Danke im voraus!!!!!!

[Andreas Krennmair]

> (1)Die Hörer einer Hitparade haben ihre Stimmen für je einen von 100
> wählbaren Musiktiteln abgegeben. Geben Suie einen Algorithmus an, der
> daraus die 10 Titel mit den meisten Stimmen heraussucht. Wieviele
> Elementarschritte führt der Algorithmus im schlechtesten und im
> günstigsten Fall aus?

Mein Ansatz: ein Feld mit 100 Elementen speichert, wie oft der jeweilige
Musiktitel gewählt wurde, und dann ein zweites Feld verwenden, in dem die
Indizes der am öftesten gewählten Stücke enthält. Die könnte man zB so
rausfinden:

for i:=1 to 100 do
p[i]:=i;
for i:=2 to 100 do
begin
v:=p[i]; (* Hilfsvariable v*)
j:=i;
while (j>1) and (a[p[j-1]] < a[v] do
begin
p[j]:=p[j-1];
dec(j);
end; (*while*)
p[j]:=v;
end; (* for *)

Die ersten 10 Elemente im Array a müssten dann die am öftesten gewünschten
Titel sein.

> (2)Finde einen Algorithmus, der die kleinste und die größte Zahl einer
> Folge von Zahlen a1 ... an (n gerade) bestimmt. Versuche, mit möglichst
> wenigen Schritten auszukommen. Wieviele Elementarschritte führt der
> Algorithmus im günstigsten und im schlechtesten Fall aus?

Ist diese Folge von Zahlen eigentlich in einem Array gespeichert??
Wenn ja, dann sieht meine Lösung so aus:

max:=a[1];
min:=a[1];
for i:=2 to n do
begin
if a[i]>max then
max:=a[i];
if a[i]<min then
min:=a[i];
end;

Antwort auf die zweite Frage: in beiden Fällen n Schritte, da man auf jeden
Fall alle Elemente überprüfen muß, um festzustellen, welches nun das größte
oder das kleinste ist.

Sollte irgendetwas daran nicht stimmen, bitte informiert mich, und klärt
mich meiner Fehler auf! :)

Andreas Krennmair

[Murat Maltas]

Program Sortieren;

const
MusikMax = 99;

Var
Musik : array[0..MusikMax] of Integer;
x, y,
Buffer : Integer;
sort : text;
Begin

Randomize;
For x := 0 to MusikMax do Begin
{Um die sache ein kleines bisken zu beschleunigen}
y := Random(10000)+1;
Musik[x] := y;
end;
For x := 0 to MusikMax do
For y := x to MusikMax do begin
If Musik[x] < Musik[y] then Begin
Buffer := Musik[y];
Musik[y] := Musik[x];
Musik[x] := Buffer;
end;
end;
Assign(Sort, 'Sort.txt');
Rewrite(Sort);
For x := 0 to MusikMax do Writeln(Sort, 'TOP 100 Nr.' , x+1 ,' ',
Musik[x]);
Close(Sort);
end.
{
Wenn du nur die Letzten 10 haben willst dann must die
letzte for-schleife so aussehen
For x := 0 to 10 do Writeln(Sort, 'TOP 10 von 100. Nr.' , x+1 ,' ',
Musik[x]);
Noch fragen, dann maile mich an.
Hoffe geholfen zu haben
}

Murat Maltas.

[Sebastian Koppehel]

Hallo,

am Wed, 27 Oct 1999 um 15:02:59 Uhr schrieb Andreas Krennmair:

> Mein Ansatz: ein Feld mit 100 Elementen speichert, wie oft der jeweilige
> Musiktitel gewählt wurde, und dann ein zweites Feld verwenden, in dem die
> Indizes der am öftesten gewählten Stücke enthält.

Dagegen habe ich im Prinzip nichts einzuwenden, allerdings: Es handelt
sich um eine Übungsaufgabe, und noch dazu um eine von Wirth abgeschriebene.
Da sollten wir doch die Hilfsmittel nützen, die uns Herr Wirth an die
Hand gegeben hat:

type
TTitel = record
Name : String;
Stimmen : Integer;
end;

var
Titel : Array[1..100] of TTitel;

Nun würde ich - ganz naiv, sozusagen - wie folgt darangehen:

1. Setze Var. "Max" auf 32767 (bzw. auf "ganz, ganz groß").
2. Finde den Titel, der die meisten Stimmen, aber weniger als Max, hat.
3. Drucke ihn aus.
4. Setze Max auf die Stimmenzahl dieses Titels.
5. Wenn noch keine 10 Titel ausgegeben sind, gehe zu 2.

Natürlich ist es eleganter, zu sortieren, aber ich denke da sozusagen an
den sozio-didaktischen Zusammenhang :-)

> for i:=1 to 100 do
> p[i]:=i;
> for i:=2 to 100 do
> begin
> v:=p[i]; (* Hilfsvariable v*)
> j:=i;
> while (j>1) and (a[p[j-1]] < a[v] do
> begin
> p[j]:=p[j-1];
> dec(j);
> end; (*while*)
> p[j]:=v;
> end; (* for *)
>
> Die ersten 10 Elemente im Array a müssten dann die am öftesten gewünschten
> Titel sein.

(Da sollte es statt a wohl p heißen.) Hoffentlich versteht der arme Bela
das... Gleichwohl wäre es in diesem Fall besser gewesen, Selectionsort zu
nehmen - da hättest du nämlich nur die ersten 10 Elemente sortieren müssen.
Während Insertionsort hierbei an seiner n^2 - Komplexität festhält, hat
Selectionsort 10*n Schritte und ist somit linearer Ordnung! (Ist es
eigentlich normal, sich an so etwas zu begeistern?)

- Sebastian

--
CASE sex: Geschlecht OF
männlich: Gewicht: REAL; bärtig: BOOLEAN |
weiblich: Umfang: ARRAY [1 .. 3] OF INTEGER
(aus: N. Wirth: Algorithmen und Datenstrukturen mit Modula-2)