Java Algorithmus
-
Hallo Leute hab ein riesen Problem an dem ich mir nun schon sehr lange den Kopf zerbreche! Haben in der Hochschule eine Aufgabe aufbekommen, einen Algorithmus zu programmieren, ich poste diese mal!
Ein Array A enthält n-1 eindeutige ganze Zahlen aus dem Bereich [0, n-1]. Das heißt, alle Zahlen sind verschieden und es gibt eine Zahl aus diesem Bereich, die nicht in A enthalten ist. Entwerfen Sie einen O(n)-Algorithmus für die Suche nach dieser Zahl. Dabei dürfen Sie nur O(1) zusätzlichen Speicher neben dem Array A verwenden.
Also haben die Aufgabenstellung schonmal besprochen:
O(n)-Algorithmus heißt, es darf keine verschachtelte Schleife vorkommen
O(1) zusätzlicher Speicher heißt, es darf kein zusätzliches Array bei der Berechnung angelegt werden.Habt ihr vlt. eine Idee? Ich komme einfach nicht drauf!
Danke schonmal im Voraus!
Mit freundlichen Grüßen
Christopher Gies
-
überseh ich was oder würde einfach min/max element finden ausreichen?
-
strictpf schrieb:
überseh ich was oder würde einfach min/max element finden ausreichen?
Vermutlich nicht - in den meisten Fällen ist min=0, max=n-1
Mir schwirren im Moment einige Ansätze durch den Kopf, aber die entsprechen leider nicht den Vorgaben der Aufgabe.
-
1. Alle Zahlen in dem Array aufsummieren.
2. Summe über alle Zahlen von 0 bis n-1 berechnen.
2. Summe 1 von Summe 2 abziehen, da hast Du Deine fehlende Zahl.
-
ahhh ok das funktioniert! Schonmal vielen Dank!
Jetzt frag ich mich nur wie ich da von alleine drauf hätte kommen sollen?!
Hatte mir ja schon viel ausgedacht, aber an diesen Lösungsansatz hab ich nicht mal ansatzweiße gedacht!MFG
Christopher
-
christopher_gies schrieb:
Jetzt frag ich mich nur wie ich da von alleine drauf hätte kommen sollen?!
Hatte mir ja schon viel ausgedacht, aber an diesen Lösungsansatz hab ich nicht mal ansatzweiße gedacht!Was soll man da sagen... Entweder hast du zu wenig überlegt oder es fehlen dir noch algorithmische Grundlagen.
-
christopher_gies schrieb:
Jetzt frag ich mich nur wie ich da von alleine drauf hätte kommen sollen?!
Hatte mir ja schon viel ausgedacht, aber an diesen Lösungsansatz hab ich nicht mal ansatzweiße gedacht!Naja, das ist eine Erfahrungssache. Wenn man genug mit Zahlen jongliert hat, sieht man so etwas schneller. Ich wuerde mir da an Deiner Stelle noch keine grossen Gedanken machen, ob Dir etwas fehlt. Geh halt mal ein paar Probleme aehnlicher Art an und dann werden Dir nach einer gewissen Zeit derartige Loesungen ganz intuitiv erscheinen. Man muss bestimmte Wege einfach mal gegangen sein, um sie sehen zu koennen.
-
[Rewind] schrieb:
christopher_gies schrieb:
Jetzt frag ich mich nur wie ich da von alleine drauf hätte kommen sollen?!
Hatte mir ja schon viel ausgedacht, aber an diesen Lösungsansatz hab ich nicht mal ansatzweiße gedacht!Was soll man da sagen... Entweder hast du zu wenig überlegt oder es fehlen dir noch algorithmische Grundlagen.
An was fuer algorithmische Grundlagen hast Du in dem Zusammenhang gedacht?
Ok, das geht ein bisschen in Richtung Online Algorithmus. Aber ich sehe in dieser Problemstellung nicht wirklich eine Technik, die man gezielt anwendet, um auf die Loesung zu kommen. Ich habe einfach nur 1,5 Minuten auf die Problemstellung geguckt und dann ist mir der oben beschriebene Weg eingefallen. Wobei es durchaus sein kann, dass es noch schlauer geht. Da kann man bestimmt irgendetwas schlaues mit lauter XOR-Verknuepfungen oder so machen.
-
Gregor schrieb:
Wobei es durchaus sein kann, dass es noch schlauer geht. Da kann man bestimmt irgendetwas schlaues mit lauter XOR-Verknuepfungen oder so machen.
Ja, geht. Wird zwar nicht schneller, aber man hat kein Überlaufproblem.
-
volkard schrieb:
Gregor schrieb:
Wobei es durchaus sein kann, dass es noch schlauer geht. Da kann man bestimmt irgendetwas schlaues mit lauter XOR-Verknuepfungen oder so machen.
Ja, geht. Wird zwar nicht schneller, aber man hat kein Überlaufproblem.
Das hat man auch bei Gregors Algorithmus nicht.
-
Um das Lösen solcher Probleme zu üben, gibt es auch ganz gute Seiten, wo man Problemsammlungen findet, die Lösung hochlädt und der Server dann bewertet, ob die Lösung funktioniert und schnell genug ist.
Zwei ganz gute Seiten sind:
https://www.spoj.pl/ ist sehr gut und erlaubt auch viele verschiedene Programmiersprachen für die Lösungen.http://uva.onlinejudge.org/ kann ich schwer auslassen, weil das eine der bekannteren Seiten ist. Empfehlen kann ich die Seite aber nur wegen der Problemstellungen, die Webseite selber ist von der Bedienbarkeit und der Geschwindigkeit her leider nicht besonders gut.