Klammerungsanzahl (ohne Rechenregeln) |
NoobinInfo
Grünschnabel
Dabei seit: 05.11.2013
Beiträge: 1
|
|
|
05.11.2013 16:50 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Also ich denke es mir iterativ:
- bei jedem Schritt wird ein Paar gewählt was mit einer Rechenoperation verbunden ist.
- danach wird dieses Paar zu einem Wert Reduziert.
- wiederhole bei 1. bis nur noch ein wert übrig ist.
D.h. bei der ersten Iteration sind folgende 5 Paare möglich:
Beim nächsten Schritt ist ja ein Paar auf einen Wert reduziert und es sind nur noch 4 Paarbildungen möglich. Folglich komme ich auf 5! = 120 mögliche Berechnungsarten.
VG,
Karlito
|
|
05.11.2013 17:15 |
|
|
|
Kannst du mir deine 6 Bäume für 3 Rechenzeichen mal zeigen, Karlito?
Ich finde da nur 5.
Und für die 5 Rechenzeichen aus der Aufgabe finde ich (war ja eh klar
) 42 Bäume.
Ich baue erst die kleinen Bäume(wie viele Bäume für 2 Zeichen, ...) auf und setze dann ein Rechenzeichen dazwischen, multipliziere die Werte der kleineren Bäume, sodass ich auf die gewünsche Anzahl an Zeichen insgesamt komme.
code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
|
#include "stdio.h"
int main(void)
{
int baeume[10] = {0};
int anzahlRechenzeichen, einfuegePos;
baeume[0] = 1; //bei nur einer Zahl ohne Rechenzeichen eine Möglichkeit: (a)
baeume[1] = 1; //auch bei 2 Zahlen: (a+b)
for(anzahlRechenzeichen = 2; anzahlRechenzeichen <= 5; anzahlRechenzeichen++)
for(einfuegePos = 0; einfuegePos < anzahlRechenzeichen; einfuegePos++)
baeume[anzahlRechenzeichen] += baeume[einfuegePos] * baeume[anzahlRechenzeichen - einfuegePos - 1];
for(anzahlRechenzeichen = 1; anzahlRechenzeichen <= 5; anzahlRechenzeichen++)
printf("Moeglichkeiten bei %d Rechenzeichen:%d\n", anzahlRechenzeichen, baeume[anzahlRechenzeichen]);
} |
|
Ausgabe:
code: |
1:
2:
3:
4:
5:
|
Moeglichkeiten bei 1 Rechenzeichen:1
Moeglichkeiten bei 2 Rechenzeichen:2
Moeglichkeiten bei 3 Rechenzeichen:5
Moeglichkeiten bei 4 Rechenzeichen:14
Moeglichkeiten bei 5 Rechenzeichen:42 |
|
Habe ich da einen Denkfehler?
edit: @NoobinInfo
bei deinen ersten beiden Beispielen hast du je nur vier Klammern zu
edit2: du zählst diesen Baum hier doppelt, Karlito:
code: |
1:
2:
3:
4:
5:
|
+
/ \
+ +
/ \ / \
a b c d |
|
einmal machst du erst (a+b) und dann (c+d) und einmal erst (c+d)
edit3:
aller guten Dinge sind 3
Folge in OEIS
Zitat: |
Catalan numbers: C(n) = binomial(2n,n)/(n+1)
[...]
Number of ways to insert n pairs of parentheses in a word of n+1 letters. E.g. for n=3 there are 5 ways: ((ab)(cd)), (((ab)c)d), ((a(bc))d), (a((bc)d)), (a(b(cd))). |
__________________ Syntax Highlighting fürs Board (Link)
Dieser Beitrag wurde 3 mal editiert, zum letzten Mal von eulerscheZahl: 05.11.2013 17:53.
|
|
05.11.2013 17:28 |
|
|
Noobinlnfo
Grünschnabel
Dabei seit: 05.11.2013
Beiträge: 3
|
|
|
05.11.2013 17:53 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Hallo,
@euler: Danke! Bezieht man sich nur auf die Klammern, so hast du absolut recht, das habe ich auch übersehen. Bezieht man sich jedoch auf die Reihenfolge der Berechnung, so gibt es einen Unterschied, ob man zuerst (1,2) und dann (3,4) berechnet oder umgekehrt. Auch wenn das Ergebnis das selbe ist, so sind es doch 2 verschiedene Berechnungsarten. Man könnte noch argumentieren, dass (1,2) und (3,4) parallel berechnet werden. Das sind alles Spitzfindigkeiten...
Es ist die Frage, wie die Aufgabe gemeint ist. Von diesen Catalan-Zahlen habe ich noch nichts gehört.
Gruß,
Karlito
|
|
05.11.2013 18:02 |
|
|
|
Da hast du natürlich Recht, ich bin nur nach dem Baum am Ende gegangen. Ich dachte auch erst, dass es auf n! rausläuft, bis ich auf dem Papier etwas herumprobiert habe.
Und die Catalan-Zahlen kannte ich bis eben auch nicht, aber auf OEIS findet man ja so ziemlich jede Zahlenfolge, die einem unterkommt.
__________________ Syntax Highlighting fürs Board (Link)
|
|
05.11.2013 18:07 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Jaja, ich dachte auch zuerst an n!. Zettel und Stift sind doch trotz Technik immer noch das Beste
Gute Zusammenarbeit
Gruß,
Karlito
|
|
05.11.2013 18:27 |
|
|
|