C Rekursionsaufgabe

[Himb33rtoni]

Hallo alle miteinander,
nachdem mir schon diverse Male Beiträge aus euerm Forum weitergeholfen haben, ist es nun an der Zeit für mich auch mal selber eine Frage zu stellen:
An folender Aufgeabe drohe ich zu scheitern:
Man hat eine Balkenwaage (2 Wagschalen, die man beide mit Gewichten belegen darf). Nun soll ich eine rekursiveFunktion

int IsMeasurable(int target, int weights[], int nWeights)

schreiben, die folgendes tut:
target ist das Gewicht, das man messen will.
in weights[] stehen die Werte der verschiedenen Gewichte (z.B. 1,5,10) und
nweights gibt die Anzahl der verschiedenen Gewichte an (also hier 3).
Als Wert soll die Funktion 1 zurückliefern, wenn man das Gewicht(target) mit den vorhandenen Gewichten(weights) messen kann, andernfalls 0.

Ich hoffe, dass mir da einer (oder mehrere ) weiterhelfen kann

 

[Zeiner-Rider]

Irgendwie ist nWeights überflüssig, da man es von weights[] ableiten kann. Oder hab ich da einen Denkfehler?

Also. Am Anfang einer rekursiven Lösung steht immer? Genau, - der Rekursionsanker. Wie wird der wohl lauten?

 

[mausweazle]

Man braucht nweights, weil man in C nicht die Länge eines Array bestimmen kann.

Edit:
Ich würde bei jeder Rekursionsstufe solange die Funktion selbst aufrufen, bis nur noch ein Element in nWeigths[] ist. Dann machste einen Vergleich, berechnest ggf die Differenz und gibts das Ergebnis in die nächst höhere Rekursionsstufe zurück.

 

[SoDaTierchen]

Eine Mögliche Idee ist das "Probieren".

Rekursionsabbruch: Gewicht = 0.

Rekursionsabstieg: entferne ein Gewicht aus weights, reduziere target um dieses Gewicht, rufe mit den neuen Parametern sich selbst auf. nWeigths sollte logischerweise auch angepasst werden. Und das einfach für jedes Gewicht.

Ist je nach implementierung deterministisch und effizient. Code darfst du selber schreiben

 

[ph1lipp]

Du gehst am besten wie folgt vor:
In einem Rekursionsschritt wird immer ein Gewicht getestet. Sprich alle noch vorhandenen Gewichte werden aus der Menge der Gewichte genommen(immer nur eines auf einmal!) und dann wird mit dem noch übrig gebliebenen Gewichten ein neuer Rekursionsschritt gemacht. Solange bis keine Gewichte mehr in der Menge sind. In jedem Schritt ziehst du das Gewicht des Gewichtes, das du aus der Menge nimmst von target ab. Wenn keine Gewichte mehr übrig sind, und im letzten Schritt 0 herauskommt, kann man das Gewicht messen, falls nicht, dann nicht.

Das wären dann bei n Gewichten n! Schritte glaub ich. ^^
Im ersten Schritt wird n mal die Funktion rekursiv aufgerufen, im zweiten dann n-1 mal, etc.
Wenn du die Gewichte auf beiden Seiten der Waage verteilen willst, dann sind es noch mehr Schritte. (2*n)! schätze ich jetzt einfach mal. ^^

Gerade gemerkt, das hat schon jemand gepostet.
Rekursionsabbruch ist aber nicht nur target = 0, sondern auch target <= 0 und eben wenn weights leer ist und target > 0 immer noch gilt.

 

[asdfman]

Subset-Sum-Problem! NP-Vollständig! Besser gleich aufgeben :3

 

[Freezedevil]

Wieso aufgeben? NP-vollständig heißt ja keineswegs nicht berechenbar. Im Gegenteil, wenn man weiß, dass das Problem NP-vollständig ist, braucht man sich nicht mehr den Kopf über einen Algorithmus zu zerbrechen, da man eh alles durchprobieren muss. Mit anderen Worten muss man sich nur einen Baum mit allen Möglichkeiten erstellen und diesen rekursiv durchlaufen.

 

[maxwell-cs]

Im Gegenteil, wenn man weiß, dass das Problem NP-vollständig ist, braucht man sich nicht mehr den Kopf über einen Algorithmus zu zerbrechen, da man eh alles durchprobieren muss. .

sorry, aber das ist unsinn. die (wahrscheinliche) nicht-existenz eines poly. algos impliziert nicht, dass es nicht schneller (theoretisch als auch praktisch) geht, als auf eine triviale art und weise alle "lösungskandidaten" zu enumerieren.

es gibt viele ziemlich ausgeklügelte und komplizierte exakte algorithmen für np-harte probleme, die versuchen, die theoretische und/oder praktische laufzeit so niedrig wie möglich zu halten.

als ganz einfaches beispiel sei tsp genannt: alle touren durchprobieren dauert O(n!), mit dynamischer programmierung kommt man auf eine laufzeit von O(n^2 * 2^n), was sehr viel besser ist, falls man sich den speicherverbrauch leisten kann.

 

[Freezedevil]

Ja das ist wahr, da hab ich Quatsch erzählt. Sorry dafür.