/*
 * Programmieren fuer Physiker, SS 2010
 *
 * Binomialkoeffizienten rekursiv/iterativ
 */

#include <iostream>
using namespace std ;

// kurze, aber langsame rekursive Version
// (viele Berechnungen werden mehrfach ausgefuehrt)
int bino( int n, int k)
{
    if (k==0 || k==n) return 1 ;
    return bino( n-1, k) + bino( n-1, k-1) ;
}

// Routine von Uebungsblatt 3, Aufg 9:
// berechne die Zeilen des Pascal-Dreiecks bis zur
// gewuenschten Zeile.
int bino_iter( int ziel_n, int k)
{
    const int nmax=50 ; // Anzahl von zu berechnenden Zeilen
    int zeile[nmax] ; // Speicher fuer die BinoKo der akt. Zeile

    for( int n=0; n<=ziel_n; n++)
    {
	// Randwerte setzen
	zeile[0] = zeile[n] = 1 ;
	// mittlere Werte per Rek.formel berechnen
	// rueckwaerts die Zeile fuellen verhinder ueberschreiben der Werte
	for( int k=n-1; k>0; k--)
	    zeile[k] += zeile[k-1] ;
    }
    return zeile[k] ;
}

int main()
{
    int n,k ;
    cout << "Binomialkoeffizienten rekursiv/iterativ" << endl ;
    cout << "n: " ;
    cin >> n ;
    cout << "k: " ;
    cin >> k ;
    cout << "Antwort (iterativ): " << bino_iter( n,k) << endl ;
    cout << "Antwort (rekursiv): " << bino( n,k) << endl ;
}