Binomialkoeffizient < Haskell < Programmiersprachen < Praxis < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:43 Fr 07.12.2007 | | Autor: | Ole-Wahn |
| Aufgabe | Implementieren Sie eine Funktion binom :: Int -> Int -> Int, mit der man die
Binomialkoeffizienten rekursiv berechnet, wobei die Koeffizienten [mm] $\binom [/mm] n 0 = [mm] \binom [/mm] n n =1 $ als Verankerung verwendet werden. Implementieren Sie eine Funktion countBinomCalls:: Int -> Int -> Int mit der für die Eingabeparameter n und k die Anzahl der Aufrufe der Funktion binom bei der rekursiven Bestimmung von [mm] $\binom [/mm] n k$ gezählt werden. |
Der erste Teil ist mit der Rekursionsformel einfach:
binom::Int->Int->Int
binom n k
|k==0 = 1
|n==k = 1
|otherwise = binom (n-1) k + binom (n-1) (k-1)
Allerdings verstehe ich nicht, wie ich countBinomCalls implementieren soll!!
Klar ist, dass wie bei binom für k=0 und n=k eine 1 ausgegeben werden muss.
Ist n>k und [mm] $k\neq [/mm] 0$, dann wird durch die Rekursionsformel schon mindestens 2mal binom abgerufen. Je nachdem wie groß n und k sind, wird es dann weitere 2mal aufgerufen. Das bedeutet, ich hab wahrscheinlich ne Zweierpotenz, aber wie komm ich drauf?
Für Ideen bin ich dankbar!!
Gruß,
Ole
|
|
| |
|
Hallo,
> Das bedeutet, ich hab wahrscheinlich ne Zweierpotenz, aber wie komm ich drauf?
Erstens ist es keine Zweierpotenz und zweitens musst du dir darüber überhaupt keine Gedanken machen, denn ds Stichwort ist hier Rekursion.
Hilft es dir weiter, wenn ich dir sage, dass du deine binom-Funktion nur geringfügigst umbauen muss, um die Zählfunktion zu bekommen?
Die Basisfälle hast du ja schon. Beim rekursiven Abstieg musst du nur den aktuellen Aufruf zählen und die beiden rekursiven egeben sich schon durch die Rekursion.
Du wirst sehen, dass die Anzahl der Aufrufe größer ist als der Binoialkoeffizient selbst (bis auf die Basisfälle).
GrRuß
Martin
|
|
|
| |
|
| Status: |
(Korrektur) oberflächlich richtig  | | Datum: | 13:20 Sa 08.12.2007 | | Autor: | Ole-Wahn |
Wow, da stand ich ganz schön auf dem SChlauch...
Klar, dass es so geht:
countBinomCalls::Int->Int->Int
countBinomCalls n k
|k==0 = 1
|n==k = 1
|otherwise = countBinomCalls (n-1) k + countBinomCalls (n-1) (k-1)
Danke dir für die Hilfe Martin!!
Gruß,
Ole
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:44 Sa 08.12.2007 | | Autor: | Martin243 |
Hallo,
ich hätte jetzt gesagt:
|otherwise = 1 + countBinomCalls (n-1) k + countBinomCalls (n-1) (k-1),
weil ich den aktuellen Aufruf noch mitgezählt hätte. Ich bin mir aber nicht ganz sicher, wie gezählt werden soll.
Gruß
Martin
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:31 Sa 08.12.2007 | | Autor: | Ole-Wahn |
Ja, du hast natürlich recht. So, wie ich es aufgeschrieben habe, ist es nur die binom-Funktion mit neuem Namen, mit der zusätzlich addierten 1 kommt es hin! 
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:10 So 09.12.2007 | | Autor: | ycle |
Ich denke, eure Funktion ist falsch. Ich habe folgendes implementiert und erfolgreich auf Richtigkeit getestet:
countBinomCalls :: Int->Int->Int
countBinomCalls n k
| k==0 = 0
| n==k = 0
| otherwise = 2 + (countBinomCalls (n-1) (k)) + (countBinomCalls (n-1) (k-1))
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:21 So 09.12.2007 | | Autor: | Martin243 |
Hallo,
mit anderen Worten:
Der Funkionsaufruf "binom 10 0" ist keiner?
Deine Funktion sagt, dass man hier überhaupt keinen Funktionsaufruf braucht. Aber man braucht schon mindestens einen, um überhaupt irgendwie anzufangen...
Gruß
Martin
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:54 Mo 10.12.2007 | | Autor: | ycle |
Aber selbstverständlich. Danke!
Im Tutorium habe ich mri als Beispielergebnis für countBinomCalls aufgeschrieben, dass die Funktion für 4 über 1 = 6 ergeben soll und habe somit angenommen, dass Reihe n=0 im Pascalschen Dreieck quasi übergangen wird.
|
|
|
|
