LOOP-Programm - Binomialkoef. < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | A1.) Geben Sie ein LOOP-Programm an, welches folgende Funktion realisiert:
[mm] $$\operatorname{bin}: \IN_0^2 \rightarrow \IN_0: \operatorname{bin}(n,k) [/mm] = {n [mm] \choose [/mm] k}$$ |
Hallo zusammen,
ich sitze gerade an der Aufgabenstellung ein LOOP-Programm zum Bionmialkoeffizienten zu konstruieren und scheitere bereits am Ansatz. Ich weiß, dass bspw. $${n [mm] \choose [/mm] k} = {n-1 [mm] \choose [/mm] k-1} + {n-1 [mm] \choose [/mm] k} [mm] \qquad \text{bzw.} \qquad [/mm] {n [mm] \choose [/mm] k} = [mm] \prod\limits_{i = 1}^k \frac{n-(k-i)}{i}$$. [/mm] Die zweite Formel wäre unmöglich zu realisieren, da die Zwischenfaktoren im Allgemeinen nicht natürlich sind (z.B. bei [mm]{5 \choose 2}[/mm]). Mit derzeitigem Wissen (habe bereits ein Loop-Programm zur Fakultät konstruiert) wäre realisierbar die (Standard-)Formel [mm]{n \choose k} = \frac{n!}{k!(n-k)!}[/mm]. Es sollte jedoch einen kleineren Ansatz geben, als dreimalige Anwendung der Fakultät und schlussendlich noch Entwicklung eines Algorithmus der ganzzahligen Division. Daher frage ich nun euch nach einem passenderen Ansatz :)
Grüße
Joe
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:20 So 07.07.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
