Rekursive Impl. Binominalkoeff < Analysis < Oberstufe < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:23 So 19.03.2006 | | Autor: | sheriff |
| Aufgabe | | [mm] \vektor{n+1 \\ k} [/mm] = [mm] \vektor{n \\ k} [/mm] + [mm] \vektor{n \\ k-1} [/mm] |
Hallo, wie komme ich von der Ausgangsstellung auf eine rekursive Lsg?
Kann ich:
[mm] \vektor{n+1 \\ k} [/mm] = [mm] \vektor{n \\ k} [/mm] + [mm] \vektor{n \\ k-1}
[/mm]
umstellen nach
[mm] \vektor{n+1 \\ k} [/mm] - [mm] \vektor{n \\ k-1} [/mm] = [mm] \vektor{n \\ k} [/mm] oder wie fang ich an??
D A N K E im voraus.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:35 So 19.03.2006 | | Autor: | Hiroschiwa |
Mein TI sagt das deine 2. Gleichung richtig ist. Und der läst mich nur selten im Stich :)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:03 So 19.03.2006 | | Autor: | Bastiane |
Hallo!
> [mm]\vektor{n+1 \\ k}[/mm] = [mm]\vektor{n \\ k}[/mm] + [mm]\vektor{n \\ k-1}[/mm]
>
> Hallo, wie komme ich von der Ausgangsstellung auf eine
> rekursive Lsg?
> Kann ich:
> [mm]\vektor{n+1 \\ k}[/mm] = [mm]\vektor{n \\ k}[/mm] + [mm]\vektor{n \\ k-1}[/mm]
>
> umstellen nach
> [mm]\vektor{n+1 \\ k}[/mm] - [mm]\vektor{n \\ k-1}[/mm] = [mm]\vektor{n \\ k}[/mm]
> oder wie fang ich an??
Ich weiß nicht so ganz, was du genau als Ergebnis haben möchtest!?
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:57 So 19.03.2006 | | Autor: | sheriff |
Wir müssen mit Hilfe der obigen Definition eine rekursive Implementierung binom(n, k) erstellen. Abbruchbed: [mm] \vektor{n \\ 0} [/mm] = [mm] \vektor{n \\ n} [/mm] = 0;
mein Vorschlag nach (oben) umgestellter Formel:
unsigned binom3(unsigned n, unsigned k)
{
unsigned result;
if (k == 0)
return 1;
result = fakul(n+1) / (fakul(k) * fakul(n +1 -k));
result -= binom3(n, k-1);
return result;
}
Weiß nur nicht, ob das so richtig ist. Ergebnis stimmt, aber ich find es sau umständlich, da ich die Standardimplementierung (n über k) = n! / (k! * (n-k)! ) zu Hilfe genommen habe.
|
|
|
| |
|
Moin zusammen,
die Darstellung
[mm] {n\choose k} [/mm] = [mm] {n-1\choose k} [/mm] + [mm] {n-1\choose k-1}
[/mm]
ist doch schon rekursiv, und wenn ich die später im Strang gepostete Aufgabenstellung lese,
so ist zu sagen: Die von Dir angegebenen Implementation ist gerade nicht rekursiv. Folgendermassen
(in Pseudo-Code) sollte die Loesung in etwa aussehen:
function binomial (int n, int k)
begin
if k== 0 return 1
if k == n return 1
return binomial(n-1,k-1) + binomial(n-1,k)
end
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 08:43 Mo 20.03.2006 | | Autor: | sheriff |
Hallo, Danke für die schnelle Hilfe. Die Lösung sieht gut aus, aber wie kommst du von der Ausgangsdefinition drauf? Oder seh ich den Wald vor lauter Bäumen nicht?
[mm] \vektor{n+1 \\ k} [/mm] = [mm] \vektor{n \\ k} [/mm] + [mm] \vektor{n \\ k-1} \hat= \vektor{n \\ k} [/mm] = [mm] \vektor{n-1 \\ k} [/mm] + [mm] \vektor{n-1 \\ k-1} [/mm] ???
Wie kommt man darauf????
|
|
|
| |
|
Hallo nochmal,
nun, in der zweiten Formel ist n+1 durch n ersetzt.
Wohlgemerkt ist natürlich [mm] {n\choose k} [/mm] nur für [mm] 0\leq k\leq [/mm] n definiert bzw ansonsten ist [mm] {n\choose k}=0.
[/mm]
es ist ja [mm] {n\choose k} [/mm] nichts anderes als die Anzahl der k-elementigen Teilmengen einer Menge mit n Elementen.
Wenn Du dies weisst, dann sollte übrigens die Rekursionsformel auch klar sein: Wie kannst Du aus n Elementen k auswählen ?
Nun, entweder Du nimmst das erste Element und wählst aus den verbleibenden n-1 noch k-1 aus, oder Du nimmst das erste Element nicht und
wählst aus den verbleibenden n-1 noch k Elemente aus.
Alles klar soweit ?
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:42 Mo 20.03.2006 | | Autor: | sheriff |
Jau, Danke.
n+1 durch n ersetzt ist das selbe wie n durch n-1 ersetzen um zur Gegebenen rekursiven zu kommen
Ich Hohli. Danke nochmal.
|
|
|
|
