Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Andrea Cipriani,
- #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);
- }
- // Procedure per il cacolo del coefficiente binomiale:
- // 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 coefficienteBinomiale3(k,n);
- 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;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement