C# :: Aufgabe #103

3 Lösungen Lösungen öffentlich

Das Tortenproblem mit Tortenstücken ( Möglichkeiten )

Fortgeschrittener - C# von klhlubek19 - 16.07.2015 um 13:50 Uhr
k Kinder erhalten t Torten.
Die Torten sind alle gleich groß, haben aber
verschiedene Geschmacksrichtungen:
a) Ananas, b) Brombeer, c) Chocolate, d) Datteln, e) Erdbeer, usw.
Die Torten werden zunächst je in k Stücke geteilt.
Nun erhält jedes Kind (1: Anna; 2: Bert; 3: Claude; 4: Daphne; ...)
von jeder Torte ein Stück.

Danach beginnen die Kinder zu tauschen, denn vielleicht mögen nicht alle jede
Sorte gleich gut. Beim Tauschen achten die Kinder darauf, dass immer jedes
Kind gleich viele Tortenstücke behält.

Auf wie viele Arten können die Kinder die Tortenstücke nun so verteilen,
dass immer noch alle Kinder gleich viele Stücke haben?
Alle Möglichkeiten sind auszugeben.

Lösungen:

vote_ok
von eulerscheZhl (5230 Punkte) - 17.07.2015 um 16:49 Uhr
Quellcode ausblenden C#-Code
using System;
using System.IO;
using System.Collections.Generic;
using System.Linq;

namespace trainYourProgrammer
{
	class MainClass
	{
		static void Main(string[] args)
		{
			solutions = 0;
			Console.Write ("Anzahl der Kinder: ");
			int k = int.Parse (Console.ReadLine ());
			Console.Write ("Anzahl der Torten: ");
			int t = int.Parse (Console.ReadLine ());
			int[] pieces = new int[t];
			for (int i = 0; i < t; i++)
				pieces [i] = k;
			TakePieces (k, t, pieces, new List<int[]>());
			Console.WriteLine ("\n{0} Lösungen gefunden", solutions);
		}

		static int solutions;
		static void TakePieces(int childs, int pieces, int[] remaining, List<int[]> previous) {
			if (childs == 0) {
				Console.WriteLine (String.Join ("    ", previous.Select (x => String.Join (", ", x))));
				solutions++;
				return;
			}
			foreach (int[] take in Take(remaining, pieces)) {
				TakePieces (childs - 1, pieces, 
				            Enumerable.Range (0, remaining.Length).
				            Select (i => remaining [i] - take [i]).
				            ToArray (),
				            new List<int[]>(previous) {take}
				);
			}
		}

		//nimm genau pieces Stücke aus den verfügbaren, gib alle Möglichkeiten zurück
		static List<int[]> Take(int[] remaining, int pieces) {
			List<int[]> result = new List<int[]>();
			int[] current = new int[remaining.Length];
			TakeRecurs (remaining, pieces, current, 0, result);
			return result;
		}

		static void TakeRecurs(int[] remaining, int pieces, int[] taken, int index, List<int[]> result) {
			if (index == remaining.Length) {
				if (pieces == 0)
					result.Add (taken);
				return;
			}
			for (int take = 0; take <= Math.Min(pieces, remaining[index]); take++) {
				int[] takenNew = (int[])taken.Clone ();
				takenNew [index] = take;
				TakeRecurs (remaining, pieces - take, takenNew, index + 1, result);
			}
		}
	}
}
3 Kommentare
vote_ok
von niknik (1230 Punkte) - 18.08.2015 um 10:33 Uhr
Quellcode ausblenden C#-Code
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Tortenproblem
{
    class Program
    {
        static void Main(string[] args)
        {
            int anzahlT, anzahlK;
            do
            {
                Console.Clear();
                Console.WriteLine("Wieviele Torten gibt es?");
            } while (!int.TryParse(Console.ReadLine(), out anzahlT) || anzahlT < 0);

            do
            {
                Console.Clear();
                Console.WriteLine("Wieviele Kinder gibt es?");
            } while (!int.TryParse(Console.ReadLine(), out anzahlK) || anzahlK < 0);

            int anzahlStuecke = anzahlK * anzahlT;

            // k - Kinder, 
            // t Torten, 
            // stuecke - Anzahl von Tortenstücken

            // Jedes Kind hat t stücke, es gibt "stuecke" viele Stücke
            // ==> anzahlStuecke!/((anzahlStuecke - anzahlK)! * anzahlK!)

            double anzahlMoeglichkeiten;
            ulong anzahlStueckeFakultaet = 1;

            for (uint i = 1; i <= anzahlStuecke; i++)
            {
                anzahlStueckeFakultaet *= i;
            }

            ulong anzahlStueckeMinusTortenFakultaet = 1;

            for (uint i = 1; i <= (anzahlStuecke - anzahlT); i++)
            {
                anzahlStueckeMinusTortenFakultaet *= i;
            }

            ulong anzahlKFakultaet = 1;

            for (uint i = 1; i <= anzahlK; i++)
            {
                anzahlKFakultaet *= i;
            }

            anzahlMoeglichkeiten = (anzahlStueckeFakultaet) / ((anzahlStueckeMinusTortenFakultaet) * anzahlKFakultaet);

            Console.WriteLine("Es gibt {0} Möglichkeiten die {1} Tortenstücke von {2} Torten auf die {3} Kinder zu verteilen", anzahlMoeglichkeiten, anzahlStuecke, anzahlT, anzahlK);
            Console.ReadLine();
        }
    }
}
vote_ok
von ellmaster (40 Punkte) - 21.11.2016 um 03:04 Uhr
Meine Lösung liefert dieselbe Anzahl an Lösungen, wie eulerscheZhl in Post #6 (19.08.2015 um 19:40 Uhr) erwähnt hat. Sollte also korrekt sein, wenngleich das natürlich kein "Beweis" für die Korrektheit ist. Wir können den Beweis aber Gedanklich führen:

Eine Kombination ist eine Sortierung der Zahlen, nämlich aufsteigend. Somit sind nur gewisse Zahlenpaare möglich. Dies wird in jeder Rekursionsstufe durch i >= letzteTortenNummer sichergestellt. Weiterhin haben wir nur einen gewissen Zahlenvorrat zur Verfügung. Dies wird durch vorrat[i] - 1 >= 0 sichergestellt.

Weiterhin werden (tiefe) Kopien der Parameter erstellt, so dass auf jeder Rekursionsebene nichts verändert wird, was für die höhere Ebene noch von Bedeutung sein könnte. Dann wird der aktuelle Rekursionsschritt festgehalten und die Rekursion, falls gewünscht, neu gestartet. Der aktuelle Rekursionsschritt besteht aus der Verringerung des Vorrats sowie der Erweiterung der String-Repräsentation durch die Aktuelle Zahl (welche einer gewissen Tortensorte entspricht).

Wie die Rekursion weiterläuft, wird so entschieden:
Jedes Kind hat genau t Tortenplätze. Sind alle belegt, dann wechsel zum nächsten Kind, ansonsten wiederhole die Rekursion für die verbleibenden Tortenplätze.
Erhöhe dabei entweder den tortenRekursionsIndex oder den kinderRekursionsIndex. Bei einem Wechsel von Kind zu Kind setze den Tortenindex sowie die letzteTortennummer zurück.

Dies stellt sicher, dass jede Tortenvergabe pro Kind "terminiert" und dass nach allen Kindern terminiert wird. Dabei gibt jedes Blatt des Rekursionsbaumes seinen aktuellen Zustand aus, also eine Zeile der Konsolen-Ausgabe.

Zusammengefasst:
Wir schauen uns für jedes Kind nur eine aufsteigende Tortensortierung an, also gilt 1,2,3 = 2,1,3, womit 1,2,3 als einzige Möglichkeit geführt wird.
Für jedes Kind wiederholen wir das, wobei der aktuell verfügbare Vorrat berücksichtigt wird, also keinerlei unmögliche Lösung entstehen kann.
Da die Rekursion für alle Kinder jede (zu diesem Zeitpunkt noch mögliche) Kombination berechnet, bekommen wir für das 1. Kind zu einer bestimmten Tortenverteilung alle Kombinationen der restlichen Kinder und analog für mehrere Kinder.
Damit werden alle gültigen Möglichkeiten gefunden, weil prinzipiell nur die Permutation korrekt auf die "erweiterte" Kombination eingeschränkt wird.

Format:
Jeder Block symbolisiert ein Kind, von links nach rechts aufsteigend, wenngleich das ja egal ist, solange die Reihenfolge immer gleich bleibt!
Jede Zeile (blockübergreifend) symbolisiert eine mögliche Verteilung aller Tortenstücke auf alle Kinder.
Jede Zeile (in einem Block) symbolisiert den Tortenbestand eines Kindes, jede Torte durch Komma getrennt (damit theoretisch auch Zahlen > 9 als "12" und nicht "1" und "2" erkannt werden können.

Ausgabe für die Werte im Code:

0,0 = "1. Stück, 2. Stück"

"1. Kind" "2. Kind" "3. Kind"
0,0 0,1 1,1 "1. Möglichkeit"
0,0 1,1 0,1
0,1 0,0 1,1
0,1 0,1 0,1 "4. Möglichkeit"
0,1 1,1 0,0
1,1 0,0 0,1
1,1 0,1 0,0 "7. Möglichkeit"


Anzahl verschiedener Möglichkeiten: 7


Quellcode ausblenden C#-Code
class Program
{
    public static int anzahlKinder = 3;
    public static int anzahlTorten = 2;
    public static ulong anzahlMöglichkeiten = 0;

    static void Main(string[] args)
    {
        int[] vorrat = new int[anzahlTorten];

        for (int i = 0; i < vorrat.Length; i++)
        {
            vorrat[i] = anzahlKinder;
        }

        AlleKombinationen(vorrat, 0, 0, "", 0);
        System.Console.WriteLine(System.Environment.NewLine + "Anzahl verschiedener Möglichkeiten: " + anzahlMöglichkeiten);
        System.Console.In.Read();
    }

    static void AlleKombinationen(int[] vorrat, int tortenRekursionsIndex, int kinderRekursionsIndex, string s, int letzteTortennummer)
    {
        string tempS;
        int[] tempVorrat;

        for (int i = 0; i < anzahlTorten; i++)
        {
            if (i >= letzteTortennummer && vorrat[i] - 1 >= 0)
            {
                tempS = s;
                tempVorrat = (int[])vorrat.Clone();

                tempS += (tortenRekursionsIndex > 0) ? "," + i : "" + i;
                tempVorrat[i] -= 1;

                if (anzahlTorten != tortenRekursionsIndex + 1)
                {
                    AlleKombinationen(tempVorrat, tortenRekursionsIndex + 1, kinderRekursionsIndex, tempS, i);
                }
                else if (anzahlKinder != kinderRekursionsIndex + 1)
                {
                    AlleKombinationen(tempVorrat, 0, kinderRekursionsIndex + 1, tempS + "\t\t\t", 0);
                }
                else
                {
                    System.Console.WriteLine(tempS);
                    anzahlMöglichkeiten++;
                }
            }
        }
    }
}
1801135

Du scheinst einen AdBlocker zu nutzen. Ich würde mich freuen, wenn du ihn auf dieser Seite deaktivierst und dich davon überzeugst, dass die Werbung hier nicht störend ist.