Anzahl Möglichkeiten berechnen

mit matplotlib, NumPy, pandas, SciPy, SymPy und weiteren mathematischen Programmbibliotheken.
Antworten
gkieninger
User
Beiträge: 4
Registriert: Donnerstag 17. Februar 2022, 18:31

Hallo!

Ich bräuchte eine Hilfe um die Anzahl der verschiedenen Möglichkeiten zu ermitteln. Bin leider in Mathe nicht wirklich gut unterwegs.

Gegeben sind zum Beispiel 3 Nächte (1.5 bis 4.5). Nun müsste ich wissen, wieviel Übernachtungsmöglichkeiten es gibt
Also in dem Beispiel wären das 6 Möglichkeiten
1 -> 1 Nacht von Tag 1 weg
2 -> 2 Nächte von Tag 1 weg
3 -> 3 Nächte von Tag1 weg
4 -> 2 Nächte von Tag 2 weg
5 -> 1 Nacht von Tag 2 weg
6 -> 1 Nacht von Tag 3 weg
(Hoffentlich nichts vergessen :-))

Gibt es da eine einfache Möglichkeit um das flott zu berechnen?
Vielen Dank für jeden Hinweis!
rogerb
User
Beiträge: 878
Registriert: Dienstag 26. November 2019, 23:24

@gkieninger,

ich komme auch auf 6 Übernachtungen:

Mögliche Übernachtungen (von - bis):
1.5. bis 2.5.
1.5. bis 3.5.
1.5. bis 4.5.
2.5. bis 3.5.
2.5. bis 4.5.
3.5. bis 4.5.

Eine Übernachtungsmöglichkeit ist ein Zahlenpaar aus Anreisetag und Abreisetag.
Alle möglichen Kombinationen der Tage 1, 2, 3, und 4 sind eine Übernachtung, mit der Einschränkung, dass die zweite Zahl größer sein muss als die erste.

Es gibt in Python eingebaute Werkzeuge, die einem enorm dabei helfen, diese Kombinationen aufzustellen.
Wenn man es zür Übung von Hand programmieren will, sind das zwei verschachtelte Schleifen die jeweils über Ankunftstage und Abreisetage iterieren.
nezzcarth
User
Beiträge: 1686
Registriert: Samstag 16. April 2011, 12:47

Unterbrechungen zählen also nicht? Ansonsten gibt es noch die Variante mit je einer Übernachtungen 1. und am 3.
Benutzeravatar
pillmuncher
User
Beiträge: 1511
Registriert: Samstag 21. März 2009, 22:59
Wohnort: Pfaffenwinkel

Von einem Tag zum nächsten ist es 1 Nacht: 1*1
Von einem Tag zum übernächsten sind es 2 Nächte: 1*2 + 2*1
Von einem Tag zum überübernächsten sind es 3 Nächte: 1*3 + 2*2 + 3*1
Von einem Tag zum überüberübernächsten sind es 4 Nächte: 1*4 + 2*3 + 3*2 + 4*1
...

Den jeweils zweiten Faktor kann man weglassen, weil er nicht als Zahl in das Ergebnis einfließt:

Von einem Tag zum nächsten ist es 1 Nacht: 1 == 1
Von einem Tag zum übernächsten sind es 2 Nächte: 1 + 2 == 3
Von einem Tag zum überübernächsten sind es 3 Nächte: 1 + 2 + 3 == 6
Von einem Tag zum überüberübernächsten sind es 4 Nächte: 1 + 2 + 3 + 4 == 10
...

Ganz offensichtlich haben wir es hier mit der Summe der natürlichen Zahlen von 1 bis n zu tun. Und dafür ist die Formel n(n+1)/2. Also bei insgesamt 5 Nächten:
1 + 2 + 3 + 4 + 5 == 5*(5+1)/2 == 5*6/2 == 30/2 == 15.
In specifications, Murphy's Law supersedes Ohm's.
gkieninger
User
Beiträge: 4
Registriert: Donnerstag 17. Februar 2022, 18:31

pillmuncher hat geschrieben: Donnerstag 17. Februar 2022, 19:37 Ganz offensichtlich haben wir es hier mit der Summe der natürlichen Zahlen von 1 bis n zu tun. Und dafür ist die Formel n(n+1)/2. Also bei insgesamt 5 Nächten:
1 + 2 + 3 + 4 + 5 == 5*(5+1)/2 == 5*6/2 == 30/2 == 15.
Perfekt. Genau was ich brauche.
Ich habe die Routine schon, die mir die ganzen möglichen Übernachtungsblöcke ermittelt, aber damit kann ich jetzt auch meine Tests vereinfachen :)
Vielen Dank!
gkieninger
User
Beiträge: 4
Registriert: Donnerstag 17. Februar 2022, 18:31

nezzcarth hat geschrieben: Donnerstag 17. Februar 2022, 19:27 Unterbrechungen zählen also nicht? Ansonsten gibt es noch die Variante mit je einer Übernachtungen 1. und am 3.
Was meinst du mit Unterbrechungen?
Benutzeravatar
__blackjack__
User
Beiträge: 13533
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

@gkieninger: Na genau was da steht. Übernachtung am 1., *nicht* am 2. und, aber am 3. Tag wäre ja theoretisch auch eine Möglichkeit die Du nicht ausgeschlossen hast, weil in den Randbedingungen nicht von Übernachtungen ”am Stück” die Rede ist. Das wären dann ``2**anzahl_naechte - 1`` Möglichkeiten, weil man die Nächte dann zum Beispiel als Bits sehen kann die gesetzt sind, wenn in der entsprechenden Nacht eine Übernachtung stattfindet. Eins abgezogen für die Bitkombination wo alle Nächte 0 ist.

Code: Alles auswählen

- (void)countSheep {
    unsigned int sheep = 0;
    while ( ! [self isAsleep]) { ++sheep; }
}
tonikae
User
Beiträge: 90
Registriert: Sonntag 23. Februar 2020, 10:27

Mathematisch ist das was du willst (und wie du es beschrieben hast) nur eine einfache Fakultät (mathematisch: x!)
Ansonsten ist es Binominalkoeffizient (mathematisch: n über k)

Für alles gibt es Befehle. Sollte also keine große Sache sein.
Zuletzt geändert von tonikae am Freitag 18. Februar 2022, 10:41, insgesamt 2-mal geändert.
Benutzeravatar
pillmuncher
User
Beiträge: 1511
Registriert: Samstag 21. März 2009, 22:59
Wohnort: Pfaffenwinkel

@tonikae: Nein, das ist es beides nicht. Lies meinen Beitrag weiter oben.
In specifications, Murphy's Law supersedes Ohm's.
gkieninger
User
Beiträge: 4
Registriert: Donnerstag 17. Februar 2022, 18:31

__blackjack__ hat geschrieben: Freitag 18. Februar 2022, 09:59 @gkieninger: Na genau was da steht. Übernachtung am 1., *nicht* am 2. und, aber am 3. Tag wäre ja theoretisch auch eine Möglichkeit die Du nicht ausgeschlossen hast, weil in den Randbedingungen nicht von Übernachtungen ”am Stück” die Rede ist. Das wären dann ``2**anzahl_naechte - 1`` Möglichkeiten, weil man die Nächte dann zum Beispiel als Bits sehen kann die gesetzt sind, wenn in der entsprechenden Nacht eine Übernachtung stattfindet. Eins abgezogen für die Bitkombination wo alle Nächte 0 ist.
Da hast du recht, ich war da ungenau, für mich wären das natürlich zwei Übernachtungen und nicht eine. Also Inanspruchnahme von zwei Möglichkeiten.
Aber die genannte Formel war einfach und hat auch bei meinen Tests einwandfrei funktioniert.
Antworten