Buch Cover Buch Cover Buch Cover Buch Cover

Web-Code: - Webcode Help

Das Tortenproblem (Kleinprojekte)

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.

Grafik Beispiel fünf Torten und vier Kinder:

Fünf Torten und vier Kinder


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.

0 Kommentare

Bitte melde dich an um einen Kommentar abzugeben

3 Lösung(en)

package ch.programmieraufgaben.kleinprojekte.torten;

/** 
 * Vereinfachte Konsoleeingabe in Java.
 * Von hier herunterladen:
 * https://github.com/pheek/javaInput/archive/master.zip
 */
import static eu.gressly.io.utility.Input.inputInt;

import java.util.Arrays;

/**
 * Das Tortenproblem
 * *****************
 * 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.
 * 
 * Skizze von Philipps-Torten-Algorithmus mit 4 Kindern und 5 Torten.
 * 
 * Dies ist eine Spezialisierung des Algorithmus von
 * Narayana Pandita (14. Jahrhundert) aus Indien (indischer Algorithmus).
 *		Quelle: Don E. Knuth: "The art of computer Programming"
 *		      - Vol 4 Facsile 2 "Generating all Tuples and Permutations"
 *		        Seiten 39/40
 * 
 * Die Torten (a - e) werden je in 4 Teile geteilt.
 * Die ersten Varianten sehen so aus:
 *
 * Kind 1 \ Kind 2 | Kind 3 | Kind 4
 *  aaaab | bbbcc  | ccddd  | deeee
 *                       *        *
 *  aaaab | bbbcc  | ccdde  | ddeee
 *                      *        *
 *  aaaab | bbbcc  | ccdee  | dddee
 *                     *          *
 *  aaaab | bbbcc  | cceee  | dddde
 *                    *          *
 *  aaaab | bbbcc  | cdddd  | ceeee
 *                       *        *
 *  aaaab | bbbcc  | cddde  | cdeee
 *                      *         *
 *  aaaab | bbbcc  | cddee  | cddee
 *                     *          *
 *  aaaab | bbbcc  | cdeee  | cddde
 *                    *           *
 *  aaaab | bbbcc  | ceeee  | cdddd
 *                   *            *
 *  aaaab | bbbcc  | dddde  | cceee
 *                      *         *
 *  aaaab | bbbcc  | dddee  | ccdee
 *                     *          *
 *  aaaab | bbbcc  | ddeee  | ccdde
 *                    *           *
 *  aaaab | bbbcc  | deeee  | dddcc
 *              *               *
 *  aaaab | bbbcd  | cccdd  | deeee
 *                       *     *
 *  aaaab | bbbcd  | cccde  | ddeee
 *
 *  Folgendes Vorgehen kann angewendet werden.
 *  Der darunter in Java programmierte Algorithmus verwendet das selbe Prinzip 
 *  (also auch die selbe Laufzeit), bedient sich aber einer strukturierten
 *  Vorgehensweise mit Unterprogrammen (statt GOTO-Jumps).
 *  Bem.: In Java eignet es sich, die Kinder von 0 zu nummerieren; ist also
 *  im Folgenden die Variable "aktK" = 0, so ist das erste Kind (Anna) gemeint.
 *  
 *  Hier das "Flussdiagramm":
 *  0. Initialisiere Feld (1. Position der obigen Liste).
 *
 *  1. Aktuelles Kind (aktK = 2. von rechts)
 *     Die Variable "aktK" startet bei 0 (= 1. Kind) und bezeichnet die 
 *     Kind-Nummer. Aus "aktK" werden die Positionen in obigem initialiserten
 *     Array berechnet.
 *     Obiges Beispiel:
 *     aktK = 0 bezeichnet pos  0 -  4, 
 *     aktK = 1 bezeichnet pos  5 -  9,
 *     aktK = 2 bezeichnet pos 10 - 14, ...
 *
 *  2. Suche im Arraybereich "aktK" die erste Torte (? posKleiner) von rechts,
 *     von welcher ein  (alphabetisch) größeres Stück rechts von diesem Kind
 *     existiert; wähle das kleinste, das echt größer ist (? posGroesser).
 *     (Minimax).
 *     Existiert in aktK + 1, aktK + 2, ... kein solches Stück, so
 *     wird aktK ? aktK - 1. Ist nun aktK negativ, so beende. Ansonten
 *     gehe zu 2.
 *
 *     Wenn aber ein solches Stück in aktK + 1 oder aktK + 2, ... existiert,
 *     so gehen zu 3.
 *     präzisierter Schritt 2:
 *     2.1 posKleiner  ? rechteste Position in aktK
 *         wertKleiner ? ?
 *         posGroesser ? undefiniert
 *     2.2 für alle Positionen 'tempPosG' > rechtestePosIn(aktK) (tempPosG--):
 *         2.2.1
 *         ist a) array[posKleiner] < array[tempPosG]
 *          und
 *             b) array[tempPosG] < wertKleiner
 *         dann   posGroesser ? tempPosG UND wertKleiner = array[tempPos] 
 *     2.3 if posGroesser immer noch undefiniert, dann posKleiner--, dann
 *         gehe zu 2.1
 *         sonst (posGroesser definiert), Test
 *             2.3.1 ist posKleiner < aktPos(linestes), dann
 *                   aktK = aktK - 1
 *                     wenn aktK negativ -> beende
 *                   sonst (posKleiner >= aktPos(linkestes): gehe zu 3.
 *
 *  3. Tausche das in Schritt 2 gefundene Kuchenstück (posKleiner) in aktK mit
 *     dem gefundenen in aktK + 1, aktK + 2, ... (posGroesser)
 *
 *  4. Fülle alle Stücke in aktK (rechts vom gefundenen) so auf, dass
 *     eine aufsteigende (oder gleichbleibende, sicher aber keine absteigenden)
 *     Sequenz innerhalb aktK (ab posKleiner) entsteht.
 *
 *  5. Sortiere alle verbleibenden aufsteigend ab aktK + 1
 *
 *  6. Gehe zu 1.
 * 
 * @version 0.1 (Jan 28, 2015)
 * @author Philipp Gressly Freimann 
 *         (philipp.gressly@santis.ch)
 */
public class Torten {

	public static void main(String[] args) {
		new Torten().top();
	}


	char[]  array               ; // Bsp. siehe oben
	int     anzahlKinder        ;
	int     anzahlTorten        ;
	boolean fertig       = false;


	void top() {
		initialisiere();
		ausgabe("start: ");
		while(! fertig) {
			tauscheUndSortiereNeu();
			if(! fertig) {
			  ausgabe("next : ");
			}
		}
	}

/**
 * Die Methode "findeTauschPlaetze()" liefert zwei Werte:
 * Tauschpartner A und Tauschpartner B;
 * @version 0.1 (Feb 3, 2015)
 * @author Philipp Gressly Freimann 
 *         (philipp.gressly@santis.ch)
 */
	class Swap {
		int posKleiner, posGroesser;
	}


	/**
	 * Hauptschritt. Mache dies solange, bis es keine weitere Tauschmöglichkeit
	 * gibt.
	 */
	void tauscheUndSortiereNeu() {
		Swap tauschPlaetze = findeTauschplaetze();
		if(null != tauschPlaetze) {
			swap(tauschPlaetze.posKleiner, tauschPlaetze.posGroesser);
			sortiereAllesNeuAbTauschPosition(tauschPlaetze.posKleiner);
		} else {
			fertig = true;
		}
	}


	/**
	 * Betrachte element posKleiner. 
	 * Sortiere innerhalb "aktK" so, dass rechts von posKleiner
	 * alle >= posKleiner sind. 
	 * Ab aktK + 1 soll danach ganz normal aufsteigend sortiert werden
	 * @param posKleiner
	 */
	private void sortiereAllesNeuAbTauschPosition(int posKleiner) {
		int aktK = posKleiner / anzahlTorten;
		sortiereGroessergleichInnelhalbVonAktK(posKleiner, aktK);
		sortiereAufsteigendAb(aktK + 1);
	}


	private void sortiereGroessergleichInnelhalbVonAktK(int posKleiner, int aktK) {
		int posLast = rechtestesInnerhalbVonAktK(aktK);
		char referenz = array[posKleiner];
		for(int sortPos = posKleiner + 1; sortPos <= posLast; sortPos++) {
			int tauschPos = findeKleinstesDasGroesserGleichReferenzIst(referenz, sortPos);
			referenz = array[tauschPos];
			swap(sortPos, tauschPos);
		}
	}


	private int findeKleinstesDasGroesserGleichReferenzIst(char referenz,
			int sortPos) {
		for(char min = referenz; ; min++) {
			for(int tst = sortPos; tst < array.length; tst++) {
				if(array[tst] == min) {
					return tst;
				}
			}
		}
	}


	private void sortiereAufsteigendAb(int aktK) {
		int pos = anzahlTorten * aktK;
		Arrays.sort(array, pos, array.length);
	}


	void swap(int a, int b) {
		char temp = array[a];
		array[a]  = array[b];
		array[b]  = temp    ;
	}


	/**
	 * Hier wird oben beschriebenes "MiniMax" gefunden.
	 * 
	 */
	Swap findeTauschplaetze() {
		int aktK = zweitesKindVonRechts();
		while(aktK >= 0) {
			Swap resultat = new Swap();
			resultat.posKleiner   = rechtestesInnerhalbVonAktK(aktK);
			while(resultat.posKleiner > rechtestesInnerhalbVonAktK(aktK - 1)) {
				char ref = array[resultat.posKleiner];
				int posMin = findeKleinstesGroesserAlsRefAbAktK(ref, aktK + 1);
				if(-1 == posMin) { // not found
					resultat.posKleiner --;
				} else {
					resultat.posGroesser = posMin;
					return resultat;
				}
			}
			aktK --;
		}
		return null;
	}


	/**
	 * Suche ab linkstes in aktK bis Ende, ob ein größeres als "ref" gefunden
	 * wird.
	 * Wenn so eines existiert, nimm davon das kleinste (minimax)
	 * @param ref
	 * @param aktK
	 * @return -1 if not found
	 */
	private int findeKleinstesGroesserAlsRefAbAktK(char ref, int aktK) {
		// TODO FIND ERROR HERE???
		int posAb = linkestesInnerhalbVonAktK(aktK);
		char fndVal = Character.MAX_VALUE;
		int  fndPos = posAb;
		while(posAb < array.length) {
			if(array[posAb] > ref && array[posAb] < fndVal) {
				fndPos = posAb;
				fndVal = array[fndPos];
			}
			posAb ++;
		}
		if(fndVal > ref && fndVal < Character.MAX_VALUE) {
			return fndPos;
		}
		return -1;
	}


	/**
	 * Finde rechteste, bzw. linkeste position innerhalb der Gruppe "aktK".
	 * @param aktK 1. Kind hat Nummer 0 (Beschreibung s. o.)
	 * @return gefundene Position im Array.
	 */
	private int linkestesInnerhalbVonAktK(int aktK) {
		return this.rechtestesInnerhalbVonAktK(aktK - 1) + 1;
	}


	private int rechtestesInnerhalbVonAktK(int aktK) {
		return anzahlTorten * (aktK + 1) - 1;
	}


	/**
	 * Starte immer beim zweiten von rechts.
	 * Beispiel: es sind 5 Kinder (nummeriert von 0..4)
	 * Dann ist das zweite von rechts die nummer 3
	 * @return position des 2. Kindes von rechts.
	 */
	private int zweitesKindVonRechts() {
		return anzahlKinder - 2;
	}


	/**
	 * Ausgabe mit senkrechtem Strich zwischen den Kindern.
	 * @param prefix wird vor der Ausgabe ausgedruckt.
	 */
	void ausgabe(String prefix) {
		System.out.print(prefix);	
			for(int k = 0; k < anzahlKinder; k++) {
				for(int t = 0; t < anzahlTorten; t++) {
				int pos = anzahlTorten * k + t;
				if(0 == t && k > 0) {
					System.out.print(" | ");
				}
				System.out.print(array[pos]);
			}
		}
		System.out.println();
	}


	/**
	 * Erzeuge den array und die erste (aufsteigend sortierte) Liste aller
	 * Tortenstücke.
	 */
	void initialisiere() {
		anzahlKinder = inputInt("Anzahl Kinder: ");
		anzahlTorten = inputInt("Anzahl Torten: ");
		array = new char[anzahlKinder * anzahlTorten];
		int pos = 0;
		for(char t = 'a'; t < ('a' + anzahlTorten); t++) {
			for(int k = 0; k < anzahlKinder; k++) {
				array[pos++] = t;
			}
		}
	}

}  // end of class Torten
                

Lösung von: Philipp Gressly Freimann (SANTIS Training AG)

// Vira  - Thomas Rührig
namespace DasTortenProblem
{
    using System;
    using System.Collections.Generic;
    using System.Linq;
    class Program
    {
        static void Main(string[] args)
        {
            Console.Title = "Das Tortenproblem";

            //Add Torten to a list
            List<Torte> Torten = new List<Torte>(new Torte[]{
                new Torte("Ananas"),
                new Torte("Bromber"),
                new Torte("Chocolate"),
                new Torte("Datteln"),
                new Torte("Erdbeer")
            });

            //Add Kinder to a list
            List<Kind> Kinder = new List<Kind>(new Kind[]{
                new Kind("Anna"),
                new Kind("Bert"),
                new Kind("Claude"),
                new Kind("Daphene")
            });

            //Add Torten to Kinder
            foreach (var item in Kinder)
            {
                item.Torten.AddRange(Torten);
            }

            ulong CounterDerVarianten = 0;

            foreach(var item in Kinder)
            {
                Console.WriteLine(item.Name + ":\n");
                ulong counter=0;
                foreach(IEnumerable<Torte> t in AlleVarianten(Kinder, Torten))
                {
                    Console.Write("Variante {0}: ", counter++);
                    t.ToList().ForEach(asdf=> Console.Write(" "+asdf));
                    CounterDerVarianten++;
                    Console.WriteLine();
                }
                Console.WriteLine();
                Console.WriteLine();
            }

            //Output Counter
            Console.WriteLine("Wie oft kann getauscht werden? - {0} mal!", CounterDerVarianten);

            Console.ReadKey(true);
        }

        private static IEnumerable<IEnumerable<Torte>> AlleVarianten(List<Kind> Kinder, List<Torte> Torten)
        {
            return GetPermutations(Torten, Torten.Count).Where(a => a.Count() == Torten.Count);
        }

        private static IEnumerable<IEnumerable<T>>GetPermutations<T>(IEnumerable<T> list, int length)
        {
            if (length == 1) return list.Select(t => new T[] { t });
            return GetPermutations(list, length - 1)
                .SelectMany(t => list.Where(e => !t.Contains(e)),
                    (t1, t2) => t1.Concat(new T[] { t2 }));
        }
    }

    class Kind
    {
        public Kind(string Name)
        {
            this.Name = Name;
            this.Torten = new List<Torte>();
        }
        public string Name { get; set; }
        public List<Torte> Torten { get; set; }
    }

    class Torte
    {
        public Torte(string Name)
        {
            this.Name = Name;
        }
        public string Name { private get; set; }

        public override string ToString()
        {
            return this.Name;
        }
    }
}

                

Lösung von: Thomas Rührig (Htl-Donaustadt (bzw ÖZBF nominiert - TU-Wien))

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

"""
Tortenproblem
https://www.programmieraufgaben.ch/aufgabe/das-tortenproblem/8ijpjc7u
"""

# Programmieraufgabe:
#     k Kinder erhalten t Torten.
#
#     Die Torten sind alle gleich groß, haben aber verschiedene
#     Geschmacksrichtungen. Die Torten werden zunächst je in k Stücke geteilt.
#     Nun erhält jedes Kind 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.
#
# Autor, Erstellung:
#     Ulrich Berntien, 2018-11-06
#
# Sprache:
#     Python 3.6.6


from typing import *


def minus(a: Tuple[int], b: Tuple[int]) -> Tuple[int]:
    """
    Vektor a minus Vektor b.
    :param a: Von den Werten in dieser Liste wird subtrahiert.
    :param b: Diese Werte werden subtrahiert.
    :return: Elementweise Differenz.
    """
    assert len(a) == len(b)
    return tuple(ax - bx for ax, bx in zip(a, b))


def plus(a: Tuple[int], b: Tuple[int]) -> Tuple[int]:
    """
    Vektor a plus Vektor b.
    :param a: Diese Werte werden addiert.
    :param b: Diese Werte werden addiert.
    :return: Elementweise Summe.
    """
    assert len(a) == len(b)
    return tuple(ax + bx for ax, bx in zip(a, b))


def combinations(pool: Tuple[int, ...], number: int) -> Tuple[int, ...]:
    """
    Alle Kombinationen von Elementen erzeugen.
    Es gibt einen Pool von Elementen unterschiedlichen Typs. Die Anzahl
    der verfügbaren Elementen pro Typ sind in "pool".
    Jede Kombination muss die gleiche Anzahl von Elementen enthalten: number.
    :param pool: Liste von unterschiedlichen Elementen. Der Wert[i] ist
     die Anzahl der verfügbaren Elemente der Sorte i
    :param number: Anzahl der Elemente die kombiniert werden müssen.
    :return: Generator für alle Kombinationen.
    """
    assert sum(pool) >= number
    assert all(p >= 0 for p in pool)
    # Anzahl unterschiedlicher Elemente
    n_types = len(pool)
    # Aktuell gewählte Anzahl von Elementen jedes Typs
    current_elements = [0] * n_types
    # Maximale Anzahl von Elementen, die von Typ i genommen werden können.
    max_elements = [0] * n_types
    # index der zuletzt geänderten Element-Anzahl
    index = -1
    # Anzahl der Elemente, die noch ausgewählt werden müssen nach index
    rest = number
    while True:
        # Auswahl der Elemente nach index: immer minimale Anzahl wählen
        while index < n_types - 1:
            index += 1
            max_elements[index] = min(pool[index], rest)
            current_elements[index] = max(0, rest - sum(pool[index + 1:]))
            rest -= current_elements[index]
        # Eine Kombination ist vollständig ausgewählt
        assert index == n_types - 1
        assert rest == 0
        assert number == sum(current_elements)
        assert all(c <= m for c, m in zip(current_elements, max_elements))
        yield tuple(current_elements)
        # Beim höchst möglichen index die Anzahl der Elemente um 1 vergrößern
        while current_elements[index] == max_elements[index]:
            index -= 1
            if index < 0:
                return
        current_elements[index] += 1
        rest = number - sum(current_elements[:index + 1])


def distributions(sources: Tuple[int], destinations: int) -> List[Tuple[int]]:
    """
    Verteilung von Elementen aus verschiedenen Typen.
    :param sources: Anzahl der verfügbaren Elemente von jedem Element-Typ.
    :param destinations: Auf diese Anahl soll verteilt werden.
    :return: Generator, der Listen liefert mit verteilten Elementen.
    """
    # Die Anzahl der Elemente, die jeder erhalten muss,
    per_destination = sum(sources) // destinations
    assert destinations > 0
    assert sum(sources) == per_destination * destinations
    index: int = -1
    rest = sources
    # Ein Generator erzeugt alle Kombintationen
    generator = [None] * destinations
    # Das ist die aktuell ausgewählte Kombination
    current = [None] * destinations
    while True:
        # Die möglichen Kombinationen für i-1 sind abhängig von den
        # ausgewählten Kombinationen 0..i. Wurde die Kombination für
        # i-1 geändert, dann müssen die Generatoren für i, i+1, ...
        # neu gestartet werden.
        while index < destinations - 1:
            index += 1
            generator[index] = combinations(rest, per_destination)
            current[index] = generator[index].__next__()
            # Die folgenden können aus dem rest auswählen.
            rest = minus(rest, current[index])
        assert index == destinations - 1
        assert all(r == 0 for r in rest)
        yield current
        # Die nächste Kombination nehmen.
        while index >= 0:
            try:
                rest = plus(rest, current[index])
                current[index] = generator[index].__next__()
                break
            except StopIteration:
                # Hier gab es keine weitere Kombination, also
                # einen Schritt zurück und dort die nächste
                # Kombination wählen.
                index -= 1
        rest = minus(rest, current[index])
        if index < 0:
            return


def tortenproblem(torten: int, kinder: int) -> None:
    """
    Alle möglichen Verteilungen von Tortenstücken auf Kinder.
    Die Anzahl der Stücke von jeder Torte ist gleich der Anzhl der Kinder.
    Die Anzahl der Stücke für jedes Kind ist gleich der Anzahl der Torten.
    :param torten: Anzahl der Torten.
    :param kinder: Anzahl der Kinder.
    """
    assert torten > 0
    assert kinder > 0
    print("Kinder:", kinder, "Torten:", torten)
    print("Ausgabe in jeder Zeile: Kind 1|Kind 2|....")
    print("Ausgabe für jedes Kind: Anzahl von Torte 1, Anzahl von Torte 2, ...")
    anzahl: int = 0
    # Die Anzahl der Stücke von jeder Torte ist gleich der Anzahl der Kinder.
    # Jedes Kind bekommt die gleiche Anzahl von Stücke.
    for verteilung in distributions((kinder,) * torten, kinder):
        print("|".join(",".join(str(t) for t in k) for k in verteilung))
        anzahl += 1
    print("------> Anzahl:", anzahl)


if __name__ == '__main__':
    tortenproblem(torten=2, kinder=3)
    tortenproblem(torten=3, kinder=2)
    tortenproblem(torten=5, kinder=4)
                

Lösung von: Ulrich Berntien ()

Verifikation/Checksumme:

Anzahl Kinder: 3
Anzahl Torten: 2
start: aa | ab | bb
next : aa | bb | ab
next : ab | aa | bb
next : ab | ab | ab
next : ab | bb | aa
next : bb | aa | ab
next : bb | ab | aa

 

Anzahl Kinder: 2
Anzahl Torten: 3
start: aab | bcc
next : aac | bbc
next : abb | acc
next : abc | abc
next : acc | abb
next : bbc | aac
next : bcc | aab

Aktionen

Bewertung

Durchschnittliche Bewertung:

Eigene Bewertung:
Bitte zuerst anmelden

Meta

Zeit: 8
Schwierigkeit: Schwer
Webcode: 8ijp-jc7u
Autor: Philipp Gressly Freimann (SANTIS Training AG)

Download PDF

Download ZIP

Zu Aufgabenblatt hinzufügen