Buch Cover Buch Cover Buch Cover Buch Cover

Web-Code: - Webcode Help

Flaschenverteilung (Algorithmen)

Familie Kurse möchte Urlaub auf der trinkwasserlosen Insel Drøgø, deren Küste ringsherum sehr steil ist. Zum Glück gibt es einen Flaschenzug , mit dem die Getränkeflaschen nach oben gezogen werden können.Es stehen auch viele Behälter mit genügend Platz für alle Flaschen zur Verfügung, damit mehrere Flaschen auf einmal transportiert werden können.

Die Kinder Cora und Linus überlegen, wie viele Möglichkeiten es wohl insgesamt gibt, die Flaschen auf die Behälter zu verteilen.

Bei 7 Flaschen und 2 Behältern, von denen in den einen 3 und in den anderen 5 Flaschen passen, gibt es genau zwei Möglichkeiten: Der kleinere Behälter ist entweder ganz voll oder enthält genau 2 Flaschen. Auf 3 Behälter mit Platz für genau 2, 3 und 4 Flaschen lassen sich die sieben Flaschen auf genau sechs Arten verteilen.

Schreiben Sie ein Programm, das eine Anzahl N von Flaschen, eine Anzahl k von Behältern und die k Fassungsvermögen der Behälter einliest und berechnet, auf wie viele Arten die Flaschen verteilt werden können. Die Flaschen sind nicht unterscheidbar, aber die Behälter sind es, auch wenn sie gleich groß sind.

0 Kommentare

Bitte melde dich an um einen Kommentar abzugeben

6 Lösung(en)

/*------------------------------------------------------------------------------
| Mathematisch vielleicht etwas unelegant, dafür gibt's als rückgabe
| die kombinationsmöglichkeiten
\*----------------------------------------------------------------------------*/

// eingabemaske
document.write(
  '<input type="number" value="7" id="bottles" onchange="calculate()">' +
    ' Anzahl der Flaschen<br>' +
  '<input type="text" value="2 3 4" id="containers" onchange="calculate()">' +
    ' Behälter (getrennt durch Leerzeichen)<br>' +
  '<p id="out"></p>'
);

function bottleDistribution(bottles, containers) {
  var countArr = [],
      results = [],
      x;

  // summiert die werte eines arrays
  function sum(arr) { return eval(arr.join("+")); }

  // fügt dem countArr eine flasche hinzu,
  // mit rücksicht auf das fassungsvermögen der behälter
  function addBottle() {
    var i = containers.length - 1;
    while (countArr[i] >= containers[i]) i--;
    countArr[i]++;
    for (i++; i < countArr.length; i++) countArr[i] = 0;
  }

  // countArr auf 0
  for (x = 0; x < containers.length; x++) countArr[x] = 0;

  // flaschen hinzufügen und verteilung prüfen,
  // falls prüfung positiv: auf den ergebnishaufen werfen
  while (sum(countArr) != sum(containers)) {
    addBottle();
    if (sum(countArr) == bottles) results.push(countArr.join("-"));
  }
  return results;
}

// ausgabe
function calculate() {
  var b = document.getElementById("bottles").value,
      c = document.getElementById("containers").value.split(" ");
  for (var x = 0; x < c.length; x++) c[x] = parseInt(c[x]);
  var out = document.getElementById("out");

  var output = bottleDistribution(b, c);
  out.innerHTML = "<p><b>Anzahl der Möglichkeiten: " + output.length + 
    "</b></p><p>" + output.join("<br>") + "</p>";
}                                                           // lissalanda@gmx.at

                

Lösung von: Lisa Salander (Heidi-Klum-Gymnasium Bottrop)

//Laufzeit: O(n*k)
using System;
using System.Linq;

public class MainClass
{
	public static void Main (string[] args)
	{
		Console.Write ("Anzahl der Flaschen: ");
		int n = int.Parse (Console.ReadLine ());
		Console.Write ("Dassungsvermögen der Behälter (mit Leerzeichen getrennt): ");
		int[] k = Console.ReadLine ().Split (' ').Select (int.Parse).ToArray ();

		int[] lookup = new int[n + 1];
		lookup [0] = 1;
		int prev = 0;
		foreach (int i in k) {
			prev = lookup [n];
			for (int j = Math.Max (0, n - i); j < n; j++)
				lookup [n] += lookup [j]; //Berechne die Summe der letzten k Werte in lookup
			for (int j = n - 1; j >= 0; j--) {
				int tmp = lookup [j];
				lookup [j] = lookup [j + 1] - prev;
				if (j - i >= 0)
					lookup [j] += lookup [j - i];
				prev = tmp;
			}
			//Kontrollausgabe: Anzahl der Möglichkeiten für die ersten Behälter in Anzahl der Gesamtflaschen
			//Console.WriteLine (string.Join (", ", lookup));
		}
		Console.WriteLine ("Es gibt " + lookup [n] + " Wege");
	}
}
                

Lösung von: Name nicht veröffentlicht

/*
 * Der Algorithmus arbeitet rekursiv.
 * In jedem Iterationsschritt wird eine Kiste bi mit Fassungsvermögen ci entfernt.
 * Nun wird die Funktion für N-0, N-1, ..., N-ci Flaschen erneut aufgerufen
 * und anschliessend die Rückgabewerte summiert.
 * Das Verfahren endet, wenn nur noch eine Kiste übrig ist.
 * Finden die verbliebenen Flaschen noch Platz in der Kiste wird eins
 * zurückgeliefert, andernfalls null.
 */
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <string.h>

int readInt(char *str, ...) {

	int check, ret, args_n = 0, nr;
	va_list args;

	if (strstr(str, "%d") != NULL) {
		args_n++;
		va_start(args, str);
		nr = va_arg(args, int);
		va_end(args);
	}

	do {
		if (args_n == 0)
			printf("%s", str);
		else
			printf(str, nr);

		check = scanf("%d", &ret);
	} while (getchar() != '\n' || check != 1);

	return ret;
}

int sum(int *b, int k, int s, int ci) {
	int sum = 0;

	for (int i = 0; i <= ci; i++)
		sum += f(b, k, s - i);

	return sum;
}

int f(int *b, int b_count, int N) {

	if (b_count == 1) {
		if (b[0] < N)
			return 0;
		else
			return 1;
	}

	return sum(b, b_count - 1, N, b[b_count - 1]);
}

int main(int argc, char **argv) {

	int N, k;
	int *vol;

	N = readInt("Anzahl der Flaschen: ");
	k = readInt("Anzahl der Behälter: ");

	vol = malloc(k * sizeof(int));

	for (int i = 0; i < k; i++)
		vol[i] = readInt("Fassungsvermögen von Behälter Nr. %d: ", i + 1);

	printf("%d Flaschen können auf %d verschiedene Arten auf die %d "
			"Kisten verteilt werden\n", N, f(vol, k, N), k);

	return EXIT_SUCCESS;

}

                

Lösung von: André Trobisch ()

import java.util.Arrays;

public class BottleProblem {
	public static void main(final String[] args) {

		if (args.length <= 1) {
			System.out.println("Usage: BottleProblem <n> <k1> <k2> <k3> ...");
			System.exit(0);
		}

		int n = Integer.parseInt(args[0]);
		int[] k = new int[args.length - 1];
		
		for (int i = 0; i < args.length - 1; i++)
			k[i] = Integer.parseInt(args[i + 1]);
		
		System.out.println(rec(n, k));
	}

	private static int sum(int[] k) {
		int sum = 0;
		for (int f : k) {
			sum += f;
		}
		return sum;
	}

	public static int rec(final int n, int... k) {
		System.out.println();
		System.out.print(String.format("n: %d \t k: %s", n, Arrays.toString(k)));
		if (n <= 0) {
			System.out.print(" --> +1");
			return 1;
		}

		if (n > sum(k))
			return 0;

		int sum = 0;

		int n1;

		for (int i = Math.min(n, k[0]); i >= 0; i--) {
			n1 = n - i;

			int[] k2 = new int[k.length - 1];
			for (int j = 0; j < k2.length; j++) {
				k2[j] = k[j + 1];
			}

			sum += rec(n1, k2);
		}
		System.out.println();
		return sum;
	}
}
                

Lösung von: Florian Grummel (Hochschule Trier)

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

"""
Flaschenverteilung (Algorithmen)
https://www.programmieraufgaben.ch/aufgabe/flaschenverteilung-1/i9kdigw5
"""

# Programmieraufgabe:
#     Familie Kurse möchte Urlaub auf der trinkwasserlosen Insel Drøgø, deren
#     Küste ringsherum sehr steil ist. Zum Glück gibt es einen Flaschenzug, mit
#     dem die Getränkeflaschen nach oben gezogen werden können.Es stehen auch
#     viele Behälter mit genügend Platz für alle Flaschen zur Verfügung, damit
#     mehrere Flaschen auf einmal transportiert werden können.
#     Bei 7 Flaschen und 2 Behältern, von denen in den einen 3 und in den anderen
#     5 Flaschen passen, gibt es genau zwei Möglichkeiten: Der kleinere Behälter
#     ist entweder ganz voll oder enthält genau 2 Flaschen. Auf 3 Behälter mit
#     Platz für genau 2, 3 und 4 Flaschen lassen sich die sieben Flaschen auf
#     genau sechs Arten verteilen.
#     Schreiben Sie ein Programm, das eine Anzahl N von Flaschen, eine Anzahl k
#     von Behältern und die k Fassungsvermögen der Behälter einliest und
#     berechnet, auf wie viele Arten die Flaschen verteilt werden können. Die
#     Flaschen sind nicht unterscheidbar, aber die Behälter sind es, auch wenn
#     sie gleich groß sind.
#
# Autor, Erstellung:
#     Ulrich Berntien, 2018-08-14
#
# Sprache:
#     Python 3.6.6


from typing import *


def moeglichkeiten(flaschen: int, kisten: List[int]) -> int:
    """
    Bestimmt die Anzahl der Möglichkeiten die Flaschen zu verteilen.
    :param flaschen: Anzahl der Flaschen, die verteilt werden müssen.
    :param kisten: Liste mit den Größen der Kisten.
    :return: Anzahl der Möglichkeiten
    """
    assert flaschen >= 0
    if len(kisten) < 1:
        raise RuntimeError("Keine Kisten")
    if len(kisten) == 1:
        if flaschen > kisten[0]:
            raise RuntimeError("Flaschen passen nicht in die Kiste")
        else:
            # alle Flasch in die Kiste, es gibt nur eine Möglichkeit
            return 1
    if flaschen == 0:
        # Keine Flaschen.
        # Also genau eine Möglichkeit: alle Kisten leer
        return 1
    assert len(kisten) >= 2
    # In dieser Rekursionsstufe werden alle Möglichkeiten für die
    # Füllung der ersten Kiste betrachtet.
    (erste_kiste, *rest_kisten) = kisten
    assert erste_kiste > 0
    # Mindestens so viele Flaschen in die Kiste,
    # dass der Rest der Flaschen in den Rest der Kisten passt.
    min_flaschen = max(0, flaschen - sum(rest_kisten))
    # Höchstens so viele Flaschen in die Kiste,
    # dass alle Flaschen in der Kiste sind oder die Kiste voll ist.
    max_flaschen = min(flaschen, erste_kiste)
    # Alle Möglichkeiten aufsummieren,
    # wenn n Flaschen in diese Kiste gestellt werden.
    return sum(moeglichkeiten(flaschen - n, rest_kisten)
               for n in range(min_flaschen, 1 + max_flaschen))


# Testfälle aus der Aufgabe
# Liste mit Tupel aus Anzahl Flaschen, Liste der Kistengrößen
TEST_FAELLE: List[Tuple[int, List[int]]] = [
    (7, [3, 5]),
    (7, [2, 3, 4])
]

for test_flaschen, test_kisten in TEST_FAELLE:
    print("Anzahl Flaschen:         ", test_flaschen)
    print("Kistengrößen:            ", test_kisten)
    print("Verteilungsmöglichkeiten:", moeglichkeiten(test_flaschen, test_kisten))
    print("- " * 13)
                

Lösung von: Ulrich Berntien ()

/**
 *  Programmieraufgabe: Flaschenverteilung (Algorithmen)
 *  https://www.programmieraufgaben.ch/aufgabe/flaschenverteilung-1/i9kdigw5
 */

/**
 *  Bestimmt die Anzahl der Möglichkeiten die Flaschen zu verteilen.
 *  @param flaschen Anzahl der Flaschen, die verteilt werden müssen.
 *  @param kisten Liste mit den Größen der Kisten.
 *  @return Anzahl der Möglichkeiten
 */
fun moeglichkeiten(flaschen: Int, kisten: IntArray): Int {
    assert(flaschen >= 0)
    assert(kisten.all { it > 0 })
    if (flaschen == 0) {
        // Keine Flasche läst eine Möglichkeit.
        return 1
    }
    if (kisten.isEmpty()) {
        throw IllegalArgumentException("no containers")
    }
    if (kisten.size == 1) {
        if (kisten[0] < flaschen)
            throw IllegalArgumentException("container too small")
        // Es gibt nur eine Kiste und damit eine Möglichkeit:
        // alle Flaschen in diese Kiste
        assert(kisten.size == 1 && kisten[0] <= flaschen)
        return 1
    }
    assert(kisten.size > 1)
    // In dieser Rekursionsstufe werden alle Möglichkeiten für die
    // Füllung der ersten Kiste betrachtet.
    val ersteKiste = kisten[0]
    val restKisten = kisten.sliceArray(1..kisten.size - 1)
    // Mindestens so viele Flaschen in die Kiste,
    // dass der Rest der Flaschen in den Rest der Kisten passt.
    val minFlaschen = maxOf(0, flaschen - restKisten.sum())
    // Höchstens so viele Flaschen in die Kiste,
    // dass alle Flaschen in der Kiste sind oder die Kiste voll ist.
    val maxFlaschen = minOf(flaschen, ersteKiste)
    // Alle Möglichkeiten aufsummieren,
    // wenn n Flaschen in diese Kiste gestellt werden.
    return (minFlaschen..maxFlaschen)
            .map { moeglichkeiten(flaschen - it, restKisten) }
            .sum()
}

/**
 * Automatisch die Testfälle ausführen.
 * @param argv wird ignoriert.
 */
fun main(argv: Array<String>) {
    // Testfälle aus der Aufgabe
    // Array mit Pair aus Anzahl Flaschen, Array der Kistengrößen
    val testFaelle = arrayOf(
            Pair(7, intArrayOf(3, 5)),
            Pair(7, intArrayOf(2, 3, 4))

    )
    for ((flaschen, kisten) in testFaelle)
        print("""
        |Anzahl Flaschen:          $flaschen
        |Kistengrößen:             ${kisten.contentToString()}
        |Verteilungsmöglichkeiten: ${moeglichkeiten(flaschen, kisten)}
        |-------------------------
        |
        """.trimMargin())
}

                

Lösung von: Ulrich Berntien ()

Aktionen

Bewertung

Durchschnittliche Bewertung:

Eigene Bewertung:
Bitte zuerst anmelden

Meta

Zeit:
Schwierigkeit: Schwer
Webcode: i9kd-igw5
Autor: ()

Download PDF

Download ZIP

Zu Aufgabenblatt hinzufügen