Dies ist eine statische Kopie unseres alten Forums. Es sind keine Interaktionen möglich.
This is a static copy of our old forum. Interactions are not possible.

Sinan

Senior Schreiberling

  • "Sinan" is male
  • "Sinan" started this thread

Posts: 1,021

Date of registration: Jul 5th 2003

Location: Malaga

Occupation: Senior Cloud Solution Engineer bei Oracle

1

Saturday, November 6th 2004, 1:21pm

D & A 3.Übung

Hallo,
Ich versteh Aufgabe 1 nicht so richtig

Quoted


Gegeben sei ein Feld der Länge n. Entwerfen Sie einen O(n)-Algorithmus, der die zwei Elemente des Feldes findet, die zueinander den größten Abstand haben, d.h. | a - a[j] | = max!


Sind diese nicht immer das erste und das letzte Element des Feldes und sie haben den Abstand n-1 zueinander??
Dann kann ich sofort sagen, der Abstand ist n-1!!!!
Oder was ist da genau gefragt ?(
With great power comes great responsibility

Ray-D

Alter Hase

  • "Ray-D" is male

Posts: 690

Date of registration: Oct 9th 2002

Location: Zimbabwe-Island Ost Beiträge: 3.427

Occupation: Informatiker

2

Saturday, November 6th 2004, 1:37pm

ich verstehe das so, dass man ein unsortiertes feld hat, in dem verschiedene zahlenwerte vorkommen können, so zum beispiel:

[1,4,3,8,-2,-1,0]

dann wäre von 8 zu -2 der abstand 10 der größte.

HTH
"ob ich alles weiss, was wir wissen, weiss ich auch nicht, aber ich weiss natürlich niemand von uns weiss etwas was er nicht weiss" - Wolgang Schäuble
Freiheit wird nicht erbettelt, sondern erkämpft


Dieser Beitrag wurde bereits 7 mal editiert, zuletzt von »Ray-D« (Heute, 04:29)

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

3

Saturday, November 6th 2004, 1:42pm

RE: D & A 3.Übung

Quoted

Original von Sinan
Ich versteh Aufgabe 1 nicht so richtig

Quoted


Gegeben sei ein Feld der Länge n. Entwerfen Sie einen O(n)-Algorithmus, der die zwei Elemente des Feldes findet, die zueinander den größten Abstand haben, d.h. | a - a[j] | = max!


Sind diese nicht immer das erste und das letzte Element des Feldes und sie haben den Abstand n-1 zueinander??
Dann kann ich sofort sagen, der Abstand ist n-1!!!!
Oder was ist da genau gefragt ?(
Mit Abstand ist hier der Betrag der Differenz der Werte dieser Elemente gemeint, steht ja auch in der Aufgabenstellung.

Bei dem Feld (-10, 3, -12, 34, 9) haben -12 und 34 den größten Abstand zueinander.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

This post has been edited 1 times, last edit by "Joachim" (Nov 6th 2004, 1:43pm)


Sinan

Senior Schreiberling

  • "Sinan" is male
  • "Sinan" started this thread

Posts: 1,021

Date of registration: Jul 5th 2003

Location: Malaga

Occupation: Senior Cloud Solution Engineer bei Oracle

4

Saturday, November 6th 2004, 2:12pm

RE: D & A 3.Übung

jawohl, vielen Dank :)
eigentlich hab ich das auch vermutet,
dann dachte ich, wenn das so ist, hätte man geschreiben
"... einen Algorithmus, der das Minimun und das Maximus findet, ...".

EDIT:
Oder hat die Frage gar nicht mit Max. und Min. zu tun
und ist nach der 2 BENACHBARTEN elemente mit der größten Differenz gefragt?
With great power comes great responsibility

This post has been edited 3 times, last edit by "Sinan" (Nov 6th 2004, 2:19pm)


  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

5

Saturday, November 6th 2004, 3:16pm

RE: D & A 3.Übung

Quoted

Original von Sinan
jawohl, vielen Dank :)
eigentlich hab ich das auch vermutet,
dann dachte ich, wenn das so ist, hätte man geschreiben
"... einen Algorithmus, der das Minimun und das Maximus findet, ...".
Es geht ja unter anderem darum zu erkennen, daß es sich dabei um Minimum und Maximum handelt.

Quoted

EDIT:
Oder hat die Frage gar nicht mit Max. und Min. zu tun
und ist nach der 2 BENACHBARTEN elemente mit der größten Differenz gefragt?
Du hast die mathematische Definition doch gepostet: | a - a[j] | = max

i und j sind hier wohl beliebig zu wählen, sonst würde da doch i und i + 1 stehen.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

Sinan

Senior Schreiberling

  • "Sinan" is male
  • "Sinan" started this thread

Posts: 1,021

Date of registration: Jul 5th 2003

Location: Malaga

Occupation: Senior Cloud Solution Engineer bei Oracle

6

Saturday, November 6th 2004, 3:33pm

RE: D & A 3.Übung

Quoted

Original von Joachim
i und j sind hier wohl beliebig zu wählen, sonst würde da doch i und i + 1 stehen.

völlig richtig :)
nur sowohl in Deinem Beispiel aus auch in dem von Ray-D standen die Zahlen nebeneinander.
Jetzt sind alle Unklarheiten beseitigt und die Aufgabe in < 1 min gelöst :D
With great power comes great responsibility

NullAhnung

Erfahrener Schreiberling

  • "NullAhnung" is female

Posts: 332

Date of registration: Apr 28th 2003

7

Sunday, November 7th 2004, 7:06pm

Ist es relevant dass es sich bei der 2. Aufgabe um eine verkettete Liste handelt? Die Operationen des ADT Liste sind doch für alle gleich oder nicht?

Markus

the one and only Unterstrich!

Posts: 2,571

Date of registration: Oct 9th 2003

8

Sunday, November 7th 2004, 7:32pm

Quoted

Original von NullAhnung
Ist es relevant dass es sich bei der 2. Aufgabe um eine verkettete Liste handelt? Die Operationen des ADT Liste sind doch für alle gleich oder nicht?


Ich denke mal, es geht darum, dass man die List halt an einer Stelle aufmachen muss, um dann die neue Liste einzufügen, und danach muss man halt die Verkettug wiederherstellen.

Auch mal ne Frage: Kann mir jemand mal die Operationen posten, die in der Vorlesung für den ADT Liste definiert wurden? Habe die nämlich leider nicht (und Skript ist ja auch noch nicht da).

Danke
Charmant sein? Hab ich längst aufgegeben. Glaubt mir doch eh keiner...

This post has been edited 3 times, last edit by "Markus" (Nov 7th 2004, 7:46pm)


Torrero

Senior Schreiberling

  • "Torrero" is male

Posts: 854

Date of registration: Oct 16th 2003

Location: Laatzen

Occupation: Angewandte Informatik

9

Tuesday, November 9th 2004, 10:17am

Weiß jemand, ob man die Übungszettel zwingend vor der Übungsstunde abgeben muss, oder reicht es, wenn man sie bis zum Ende der zweiten Übung am Donnerstag bei jemandem, der dafür verantwortlich ist, im Büro abgibt ?

np

Junior Schreiberling

Posts: 155

Date of registration: Oct 23rd 2002

10

Tuesday, November 9th 2004, 11:49am

Quoted

Original von Torrero
Weiß jemand, ob man die Übungszettel zwingend vor der Übungsstunde abgeben muss, oder reicht es, wenn man sie bis zum Ende der zweiten Übung am Donnerstag bei jemandem, der dafür verantwortlich ist, im Büro abgibt ?
Du kannst sie abgeben, wann und wo Du möchstest, wichtig ist nur, dass die Übung spätestens Donnerstag, 10.00 Uhr bei mir vorliegt. Nicht vergessen: Termin der Übung draufschreiben, in der Du die Zettel wieder abholen möchtest. Zettel, die Donnerstags abgegeben werden, können evtl. nicht bis zum darauffolgenden Dienstag korrigiert werden.

Sinan

Senior Schreiberling

  • "Sinan" is male
  • "Sinan" started this thread

Posts: 1,021

Date of registration: Jul 5th 2003

Location: Malaga

Occupation: Senior Cloud Solution Engineer bei Oracle

11

Tuesday, November 9th 2004, 6:29pm

Quoted

Original von Markus
Auch mal ne Frage: Kann mir jemand mal die Operationen posten, die in der Vorlesung für den ADT Liste definiert wurden? Habe die nämlich leider nicht (und Skript ist ja auch noch nicht da).
Danke

Das Skript hast du schon :)
dennoch:

1. L.first() liefert die Position des ersten Elements der Liste L zurück.
Ist L leer, dann wird Position.NULL zurückgegeben.

2. L.end() liefert die Position des letzten Elements der Liste L zurück.
Ist L leer, dann wird Position.NULL zurückgegeben.

3. Wenn p auf das i-te Element ai von L verweist, dann liefert L.next(p) die Position des Elementes ai+1. Ist das i-te Element das letzte Element, dann liefert L.next(p) Position.NULL zurück.
Verweist p auf kein Element in L, dann ist die Operation undefiniert.

4. L.retrieve(p) gibt das Element in L zurück, auf das p verweist. Verweist p auf kein Element in L, dann ist diese Operation undefiniert.

5. L.insert(x,p) setzt x hinter dem Element auf Position p in die Liste L
ein. Ist p == Position.NULL, dann wird x an den Anfang der Liste L
gesetzt. Für Positionen p, die auf kein Element der Liste verweisen, ist die Operation undefiniert.

6. L.delete(p) löscht das Element in L, auf das p verweist und gibt es zurück.
Die Operation ist undefiniert, falls p auf kein Element in L verweist.
With great power comes great responsibility

Markus

the one and only Unterstrich!

Posts: 2,571

Date of registration: Oct 9th 2003

12

Tuesday, November 9th 2004, 7:09pm

Dankedanke ^^
Charmant sein? Hab ich längst aufgegeben. Glaubt mir doch eh keiner...