Visualizzazione dei risultati da 1 a 5 su 5

Discussione: [C]grandi numeri

  1. #1
    Utente di HTML.it
    Registrato dal
    Oct 2012
    Messaggi
    53

    [C]grandi numeri

    Ciao a tutti!
    Ho la necessità di realizzare un programmino che mi calcoli il coefficiente binomiale di due numeri ( http://it.wikipedia.org/wiki/Coefficiente_binomiale ).
    Il mio problema è che tipo di dato usare, visto che il fattoriale di un numero abbastanza basso, come per esempio 15 vale troppo!
    15! = 1 307 674 368 000
    Un intero non basta, un long int nemmeno...avete idee?
    Intanto vi posto il codice se volete provare!
    codice:
    /***************************/
    /*Inclusione delle librerie*/
    /***************************/
    
    #include <stdio.h>
    #include <stdlib.h>
    
    /******************************/
    /*Dichiarazione delle funzioni*/
    /******************************/
    long int fattoriale(long int num);
    int calcola_coeff_bin(int nodi_sottografo, int nodi);
    
    /*********************************/
    /*Definizione della funzione main*/
    /*********************************/
    
    int main()
    {
        int n,k,ris;
        printf("Inserisci N...\n");
        scanf("%d", &n);
        printf("Inserisci K...\n");
        scanf("%d", &k);
        calcola_coeff_bin(k,n);
    }
    
    /***************************************/
    /*Definizione della funzione fattoriale*/
    /***************************************/
    /*funzione che calcola il fattoriale di un numero*/
    long int fattoriale(long int num)
    {
        int fatt;
        
        if(num == 0)
            fatt = 1;
        else
            fatt = num * fattoriale (num - 1);
        return (fatt);
    }
    
    
    /**********************************************/
    /*Definizione della funzione calcola_coeff_bin*/
    /**********************************************/
    /*funzione che calcola il coefficiente binomiale*/
    int calcola_coeff_bin(int k, int n)
    {
        int coefficiente,
            tmp1, tmp2, tmp3;
            
    
        tmp1 = fattoriale(n);
        printf("Fattoriale n: %d\n", tmp1);
        tmp2 = fattoriale(k);
        printf("Fattoriale k: %d\n", tmp2);
        tmp3 = fattoriale(n - k);
        printf("Fattoriale (n - k): %d\n", tmp3);
        coefficiente = tmp1/(tmp2 * tmp3);
        printf("Coefficiente binomiale: %d\n", coefficiente);
        return(coefficiente);
        
    }

  2. #2
    Utente di HTML.it
    Registrato dal
    Dec 2009
    Messaggi
    613
    Da C99 esiste il tipo long long che è almeno 64 bit, che ad esempio è sufficiente per il numero da te citato. Se non ti è sufficiente nemmeno quello e non vuoi perdere precisione suppongo tu debba affidarti ad una libreria.

    Se lo scopo è calcolare il coefficiente binomiale assicurati di utilizzare l'algoritmo più adatto, sulla pagina di Wikipedia inglese ce ne sono alcuni, magari riesci ad ottenere il risultato manipolando numeri più piccoli.

  3. #3
    Utente di HTML.it L'avatar di Scara95
    Registrato dal
    Jul 2009
    residenza
    Zimella (VR)
    Messaggi
    2,590
    Come detto da @Kaamos è preferibile cambiare algoritmo, in ogni caso, se mai ti dovesse servire una libreria che gestisca numeri di grande dimensione GNU MP potrebbe fare al tuo caso...
    "Quid enim est, quod contra vim sine vi fieri possit?" - Cicerone, Ad Familiares

  4. #4
    Utente di HTML.it
    Registrato dal
    Oct 2012
    Messaggi
    53
    Che algoritmo mi consigliate?

  5. #5
    http://en.wikipedia.org/wiki/Binomia...cative_formula
    la formula con tutti i fattoriali è la peggiore, dato che ti ritrovi con numeri enormi a numeratore e denominatore che hanno numerosi fattori comuni, con questa (terza da sinistra) dovresti avere numeratore e denominatore più "sotto controllo". Inoltre se è accettabile avere un risultato approssimato puoi usare l'espressione più a destra, effettuando la divisione (con i double) per ciascun fattore.
    Amaro C++, il gusto pieno dell'undefined behavior.

Permessi di invio

  • Non puoi inserire discussioni
  • Non puoi inserire repliche
  • Non puoi inserire allegati
  • Non puoi modificare i tuoi messaggi
  •  
Powered by vBulletin® Version 4.2.1
Copyright © 2024 vBulletin Solutions, Inc. All rights reserved.