Abwiegen mit vorgebebenen Gewichten

Sima · Anmeldungsdatum: 04.05.2005 Beiträge: 9

Betrachtet wird das Problem:Finde alle Möglivhkeiten,einen Gegenstand,der 25 g wiegt, mit 3g-, 5 g-. 7g- und 11-g Gewichten abzuwiegen.

a)Setzen Sie diese verbale Spezifikation in eine formale um.Bestimmen Sie dazu insbesondere eine endliche Menge M möglicher Lösungen.

b)Formulieren Sie einen Algorithmus zur Lösung des Problems,der auf "Erschöpfendem Durchsuchen"beruht.

also bei a soll ich da einfach versuchen und aufschreiben mit was für möglichkeiten ich finde..und b)was ist den mit erschöpfendem Durchsuchen gemeint??

kann mir bitte jemand helfen muss das morgen beim lehrer zeigen:(((

Tobias · Anmeldungsdatum: 15.02.2005 Beiträge: 149

Mit "erschöpfendem Durchsuchen" ist gemeint, dass du aus der unter (a) formulierten Menge alle Elemente durchtestest und die Gewinnerelemente rausfindest.

Sima · Anmeldungsdatum: 04.05.2005 Beiträge: 9

ich kenne das nur mit dem damenproblem kannst du mir da bei der lösungsmenge zu a helfen??soll ich a nur schreiben was ich für möglickeiten habe??

Tobias · Anmeldungsdatum: 15.02.2005 Beiträge: 149

Mein Tipp wäre Folgender:

Du hast die Gewichte 3g-, 5 g-. 7g- und 11-g. Die Anzahl der Gewichte, die du benutzt bezeichnest du durch Unbekannte:

3g - a
5g - b
7g - c
11g - d

Was du nun suchst ist ein Tupel (a, b, c, d), so dass

Nun hast du aber für a,b,c,d prinzipiell unendlich viele natürliche Zahlen zur Verfügung. Dies lässt sich aber leicht beschränken, indem du guckst, wie groß a (bzw. b,c,d) maximal werden darf unter der Voraussetzung, dass die anderen Unbekannten 0 sind.

So erhälst du eine obere Schranke für jede Unbekannte a, b, c, d und somit auch eine endliche Menge von möglichen Lösungen.

Sima · Anmeldungsdatum: 04.05.2005 Beiträge: 9

Dein Zitat:"Nun hast du aber für a,b,c,d prinzipiell unendlich viele natürliche Zahlen zur Verfügung. Dies lässt sich aber leicht beschränken, indem du guckst, wie groß a (bzw. b,c,d) maximal werden darf unter der Voraussetzung, dass die anderen Unbekannten 0 sind. "

wie soll das gehen soll ich etwa 3*a für a eine zahl einsetzen und rest null einsetzen oder wie??verstehe nicht ganz

Tobias · Anmeldungsdatum: 15.02.2005 Beiträge: 149

Die Idee ist folgende:

In der Gleichung

ist das maximal mögliche a stets kleiner als 8 (25/3), denn wenn ich noch andere Gewichte dazunehme, dann landest du schon über 25. So kannst du also für a sagen:

Das machst du für alle Unbekannte und erhälst eine endliche Menge.