Snooker-Aufgabe

[Playa]

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

[Guybrush Threepwood]

Guck mal hier. Da ist eine ähnliche Aufgabe

[baba007]

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.

[Guybrush Threepwood]

Ich glaube nicht das die Schwierigkeit für Playa darin bestand das immer abwechselnd die rote und eine farbige Kugel gespielt werden müssen...

[Aquano]

erinnert mich an das Rucksack Problem.

Der Algo zu diesem Problem dürfte Dir helfen.

[Matty]

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?

[baba007]

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

[Playa]

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

[baba007]

120 plus endspiel auf die Farben :

2+3+4+5+6+7 = 27 also 147 ... sorry hab mich da vertan

[Playa]

Ist es besser dieses Programm rekursiv oder iterativ zu programmieren?

[baba007]

man kann es so oder so ... besser ist relativ, anders sollte es heissen

[Klotzkopp]

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.

[Playa]

hier mein Ansatz:

snooker.doc

[Playa]

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

[Playa]

Kann mir jemand einen besseren Ansatz mittteilen. Vielen Dank im Voraus.

[Klotzkopp]

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.

[Playa]

habe die aufgabe gelöst :marine

[Matty]

Hast du es jetzt rekursiv gelöst?

SO schwer ist die Aufgabe gar nicht .. ich würde einfach eine Rekursion schreiben.

[Playa]

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.

[Klotzkopp]

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]