Playa Geschrieben 11. Mai 2005 Teilen Geschrieben 11. Mai 2005 Hallo, ich habe mir den Kopf zerbrochen um diese Schulaufgabe zu lösen, jedoch ohne Erfolg. Ich hoffe dass mir einer von Ihnen weiterhelfen kann. Die Aufgabe soll in der Programmiersprache C programmiert werden. Kann mir jemand Lösungsansätze bzw. Algorithmusvorschläge nennen? Die Aufgabe lautet wie folgt: Auf einem Snookertisch befinden sich 15 rote Kugeln und jeweils eine gelbe, grüne, braune, blaue, pinke und schwarze Kugel. Diese werden auch farbige Kugeln genannt. Die roten Kugeln haben eine Wertigkeit 1 und die Farbigen die Wertigkeit 2 bis 7 (in der genannten Reihenfolge). Ziel von Snokker ist es, so viele Kugeln wie möglich hintereinander einzulochen. Dabei muss abwechselnd immer eine rote gefolgt von einer farbigen Kugel gespielt werden. Die Farbigen werden nach dem Lochen wieder auf den Tisch zurückgelegt. Als Eingabe wird eine mögliche Punktzahl übergeben. Geben Sie alle Varianten der Reihenfolgen an, in welchen die Kugeln eingelocht werden müssen, um genau diese Punktzahl zu erreichen. Dabei sollen die Permutationen von möglichen Reihenfolgen nur einmal berücksichtigt werden. z.B.: Eingabe = 8 1. rot schwarz 2. rot pink rot 3. rot braun rot gelb 4. rot gelb rot braun !!!Diese Permutation nicht anzeigen; siehe 3.!!! 5. rot grün rot grün Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
Guybrush Threepwood Geschrieben 11. Mai 2005 Teilen Geschrieben 11. Mai 2005 Guck mal hier. Da ist eine ähnliche Aufgabe Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
baba007 Geschrieben 11. Mai 2005 Teilen Geschrieben 11. Mai 2005 ist doch easy ... 172 ist ja max glaube ich, int i,rote=15,hilfe=1; for (i=0;eingabe<=172 || eingabe >=1;i++) if hilfe ==1 {eingabe - 1; PRINTF("rot "); hilfe =0; rote -=1; } if hilfe ==0 { ..... usw. Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
Guybrush Threepwood Geschrieben 11. Mai 2005 Teilen Geschrieben 11. Mai 2005 Ich glaube nicht das die Schwierigkeit für Playa darin bestand das immer abwechselnd die rote und eine farbige Kugel gespielt werden müssen... Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
Aquano Geschrieben 11. Mai 2005 Teilen Geschrieben 11. Mai 2005 erinnert mich an das Rucksack Problem. Der Algo zu diesem Problem dürfte Dir helfen. Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
Matty Geschrieben 12. Mai 2005 Teilen Geschrieben 12. Mai 2005 ist doch easy ... 172 ist ja max glaube ich, int i,rote=15,hilfe=1; for (i=0;eingabe<=172 || eingabe >=1;i++) if hilfe ==1 {eingabe - 1; PRINTF("rot "); hilfe =0; rote -=1; } if hilfe ==0 { ..... usw. So einfach wird es wohl doch nicht sein, schließlich will er alle Möglichkeiten ermitteln wie man einen bestimmten Wert erreichen kann ... das schreit nach Rekursion. Die Aufgabe schon gelöst, Playa? Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
baba007 Geschrieben 12. Mai 2005 Teilen Geschrieben 12. Mai 2005 habs gestern für den optimalen weg gemacht. heute setze ich mich hin und versuche es für die anderen möglichkeiten. poste den ansatz wenn sich playa wieder meldet und seinen ansatz präsentiert Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
Playa Geschrieben 12. Mai 2005 Autor Teilen Geschrieben 12. Mai 2005 Ich arbeite noch an der Aufgabe, kamme aber nicht wirklich weiter. Werde mich noch heute abend oder morgen melden. Eins steht aber fest, max ist 120 und nicht 172 (15 * schwarz + 15 * rot = 15 * 7 + 15 * 1 = 120) Grüsse Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
baba007 Geschrieben 12. Mai 2005 Teilen Geschrieben 12. Mai 2005 120 plus endspiel auf die Farben : 2+3+4+5+6+7 = 27 also 147 ... sorry hab mich da vertan Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
Playa Geschrieben 13. Mai 2005 Autor Teilen Geschrieben 13. Mai 2005 Ist es besser dieses Programm rekursiv oder iterativ zu programmieren? Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
baba007 Geschrieben 13. Mai 2005 Teilen Geschrieben 13. Mai 2005 man kann es so oder so ... besser ist relativ, anders sollte es heissen Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
Klotzkopp Geschrieben 13. Mai 2005 Teilen Geschrieben 13. Mai 2005 Der rekursive Ansatz ist normalerweise "eleganter". Entscheidend für die Geschwindigkeit ist hier aber IMHO, ob man einen Algorithmus findet, bei dem man die Permutationen nicht rausfiltern muss, denn das kostet sehr viel Zeit. Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
Playa Geschrieben 13. Mai 2005 Autor Teilen Geschrieben 13. Mai 2005 hier mein Ansatz:snooker.doc Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
Playa Geschrieben 13. Mai 2005 Autor Teilen Geschrieben 13. Mai 2005 ich denke, dass ich mit meinem Ansatz auf dem falschen weg bin, weil (wenn 15 farbige Kugeln verwendet werden) ich dann auch 15 ineinander verschachelte schleifen habe. Grüsse Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
Playa Geschrieben 13. Mai 2005 Autor Teilen Geschrieben 13. Mai 2005 Kann mir jemand einen besseren Ansatz mittteilen. Vielen Dank im Voraus. Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
Klotzkopp Geschrieben 14. Mai 2005 Teilen Geschrieben 14. Mai 2005 Du könntest es mit 6 verschachtelte Schleifen machen, eine für die Anzahl der jeweiligen nicht roten Kugeln in der Kombination. Das hätte gegenüber deinem Ansatz den Vorteil, dass du die gleichbedeutenden Permutationen nicht entfernen musst. Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
Playa Geschrieben 16. Mai 2005 Autor Teilen Geschrieben 16. Mai 2005 habe die aufgabe gelöst :marine Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
Matty Geschrieben 17. Mai 2005 Teilen Geschrieben 17. Mai 2005 Hast du es jetzt rekursiv gelöst? SO schwer ist die Aufgabe gar nicht .. ich würde einfach eine Rekursion schreiben. Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
Playa Geschrieben 17. Mai 2005 Autor Teilen Geschrieben 17. Mai 2005 ne, ich habe es iterativ gemacht; und zwar mit 15 ineinander verschachtelten Schleifen; in der ersten Schleife werden Kombinations- möglichkeiten ermittelt, wenn eine farbige Kugel verwendet wird, in der 2. Schleife wenn 2 farbige Kugeln verwendet werden usw. bis schließlich in der 15 Schleife alle möglichen Kombinationen ermittelt werden, wenn 15 farbige Kugeln verwendet. Wie man es rekursiv programmieren könnte, wüsste ich gar nicht bzw. mir ist keine gescheite Idee eingefallen. Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
Klotzkopp Geschrieben 18. Mai 2005 Teilen Geschrieben 18. Mai 2005 Hier ist meine rekursive Lösung. Müsste halt noch kommentiert werden. Mach ich vielleicht später noch, wenn ich Zeit habe #include <vector> #include <algorithm> #include <iostream> using namespace std; typedef vector<int> sequence; void recurse(vector<sequence>& result, sequence& s, int lowestball, int score) { switch(score) { case 0: result.push_back(s); break; case 1: if(s.size() < 30) { s.push_back(1); result.push_back(s); } break; case 2: // geht nicht break; default: if(s.size() < 30) { s.push_back(1); --score; int maxball = min(score, 7); for(int i=lowestball; i<=maxball; ++i) { sequence test(s); test.push_back(i); recurse(result, test, i, score - i); } } } } int main() { for(int i=1; i<=120; ++i) { vector<sequence> result; sequence s; recurse(result, s, 2, i); cout << "Score: " << i << " No. of sequences: " << result.size() << '\n'; } }[/CODE] Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
Empfohlene Beiträge
Dein Kommentar
Du kannst jetzt schreiben und Dich später registrieren. Wenn Du ein Konto hast, melde Dich jetzt an, um unter Deinem Benutzernamen zu schreiben.