//Andrea Cipriani, esercizio per il corso di teoria dei grafi a.a 2010/2011

#include <stdio.h>

int count = 0; // Variabile globale per il conto di chiamate a procedure date dalla ricorsività

int main(void){
    unsigned int n,k,scelta,risultato;
    printf("Calcolo del coefficiente binomiale, \n");
    printf("Inserire primo parametro n\n");
    scanf("%d",&n);
    printf("n = %d\n",n);
    printf("Inserire secondo parametro k\n");
    scanf("%d",&k);
    printf("k = %d\n",k);
    printf("Scegliere il modo in cui calcolare il coefficiente binomiale\n");
    printf("1 - Procedura ricorsiva inefficiente -\n");
    printf("2 - Procedura iterativa inefficiente -\n");
    printf("3 - Procedura iterativa efficiente -\n");
    scanf("%d",&scelta);
    switch(scelta){
        case 1:
            risultato = coefficienteBinomiale1(n,k);
            break;
        case 2:
            risultato = coefficienteBinomiale2(n,k);
            printf("Attenzione ai probabili overflow nei calcoli dei fattoriali\n");
            break;
        case 3:
            risultato = coefficienteBinomiale3(n,k);
            break;
    }
    printf("%d binomiale %d = %d , chiamate a procedura = %d\n",n,k,risultato,count);
    return 0;
}

// Procedura per il calcolo ricorsivo del fattoriale di un intero n

unsigned long int factorial(int n)
 {
    count++;
    if (n<=1)
        return(1);
    else
        n=n*factorial(n-1);
    return(n);
}

// Procedura ricorsiva inefficiente:

 int coefficienteBinomiale1(int n, int k) {
    count++;
     if( k > n )
        return 0;
    if (k==0 || k==n)
        return 1;
    return coefficienteBinomiale1(n-1,k-1)+coefficienteBinomiale1(n-1,k);
}

//Soluzione iterativa inefficiente

 int coefficienteBinomiale2(int n , int k ){

    return (int) ( factorial(n) / ( factorial(k) * factorial(n-k) ) );
}

//Soluzione iterativa efficiente ( tempi di calcolo lineari, al variare di k )

int coefficienteBinomiale3(int n, int k){

    int i , risultato = 1;

    if ( k > n )
        return 0;
    if (k == 0 || k == n )
        return 1;

    //Calcolo n * (n-1)... *(n-k+1)  /(n-k)! risparmiando  moltiplicazioni

    for ( i=0; i < k ; i++){
        count++;
        risultato = risultato * (n - i);
    risultato = risultato / (i + 1);
     }

    return risultato;

}