Zwar nicht Java, aber Algo. :) Divide & Conquer

[JHedron]

Hallo,

ich habe hier eine Übungsaufgabe, die ich gerne verstehen würde... nach stundenlangem Suchen nach der Lösung hab ich's aufgegeben... Kann mir da von euch vielleicht jemand helfen... Ich weiß nicht mal wie ich an die Sache ran gehen soll. (Die Aufgabe wird nicht benotet... ist also freiweillig... aber ne Herausforderung!)

Ich weiß, dass ich die Zahlenreihen aufbrechen muss... dann die Einzelstück so hinsetzen, dass zwischen 2 Zahlen kein Wert ist, der ihr Mittelwert ist. Aber ich sitze hier vor meinen Zahlenreihen und weiß nicht weiter...

Beschreiben Sie einen korrekten Divide-and-Conquer Algorithmus für das folgende Problem:
Zu einer gegebenen natürlichen Zahl n sollen alle Zahlen von 1 bis n von links nach rechts
hingeschrieben werden, so dass nie irgendwo zwischen zwei beliebigen dieser Zahlen ihr Mittelwert
steht.

(1) Geben Sie Beispiellösungen f¨ur n = 5, n = 11 und n = 21 an!
(2) Bestimmen Sie die Laufzeit des Verfahrens nach einer der bekannten Methoden!

Falls Ihr die Lösung habt auch her damit... aber nur mit Erklärung, vielleicht verstehe ich das dann...

Gruß

James

 

[vop]

Hi zwar nicht die Lösung, aber ein paar Gedanken, die dich auf die Sprünge bringen könnten.

Betrachte die Zahlen
1,2,3,4,5,6,7,8,9,10,11

Man stellt fest, das 1 + 11 = 2 + 10 = 3 + 9 = 4 + 8 = 5 + 7 = 12 ist
12 / 2 ist 6 und damit der Mittelwert der Zahlen 1 und 11, 2 und 10, 3 und 9, 4 und 8 sowie 5 und 7.

Ermitteltst Du also den Mittelwert von a1 und an , so hast Du eine Zahl, die auch Mittelwert für die Zahlen a1+1 und an-1.

Um Dein Problem zu lösen, gehst Du etwa so (rekursiv) vor
TeileUndHerrsche(start, ende)

function TeileUndHerrsche(1,n)
Mittelwert = ErmittleMittelwert(1,n):
EntferneMittelwert ( Mittelwert);
TeileUndHerrsche(1, Mittelwert-1);
TeileUndHerrsche(Mittelwert+1, n);


Das ganze mußt Du natürlich etwas ausfeilen ( Abbruchkriterium in der rekursiven Funktion etc).

Mein Tipp: Verwalte die Zahlen in einem String-array und verwende einen leeren String, wenn Du eine Zahl gestrichen hast.
Nachdem die alles durchlaufen hast, gib den String-Array von links nach rechts aus.

vop

 

[vop]

ooops.

Leider genügt das wohl nicht!?

Wie Ich bemerke, bleibt die 7 in der Liste erhalten. Aber die ist der Mittelwert von 4 und 10.

Hmm. Da müßte man wohl doch noch weiter drüber nachdenken.....

vop

 

[kabel2]

hier eine idee:

die liste ist geordnet. das letzte und das erste element können also irgendwo in der ergebnisliste stehen, ohne dass die geforderte eigenschaft verletzt wird.

das letzte element wird in die mitte der liste gesetzt, und der algo rekursiv auf die beiden sublisten angewandt.

es gibt eine kritische stelle, wo man zeigen müsste, dass dieser algo korrekt ist.