Ajuda C [RESOLVIDO]

1. Ajuda C [RESOLVIDO]

BellCoutinho
(usa Arch Linux)

Enviado em 18/09/2018 - 13:02h

Pessoal quando em digito números 45 e 6, aparece esse erro "Floating point exception (core dumped)". Como eu resolvo esse problema?

Meu código:



#include <stdio.h>



int factorial(const int);

int combinations(const int, const int);



int main(void) {



    int students, group1;



    printf("Digite o número de estudantes: ");

    scanf("%d", &students);



    printf("Informe a quantidade de estudantes do primeiro grupo: ");

    scanf("%d", &group1);



    printf("O número de combinações possíveis é %d\n", combinations(students, group1));

    return 0;

}



int factorial(const int number)

{

    int fact = 1;



    for (int counter = 2; counter <= number; counter++) {

        fact *= counter;

    }



    return fact;

}



int combinations(const int n, const int k) {

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

}

Desde de já obrigado.

0 0

Quote

2. MELHOR RESPOSTA

paulo1205
(usa Ubuntu)

Enviado em 18/09/2018 - 13:47h

Já tentou calcular a fatorial de 45? É o seguinte valor:

119622220865480194561963161495657715064383733760000000000

Na maioria dos PCs, um int tem 32 bits, e representa números positivos e negativos. Assim sendo, o maior valor possível para um int é 2147483647.

Como você pode ver, um int não consegue armazenar a fatorial de nenhum número maior que 12 (13! já dá 6227020800, que requer 33 bits).

O que acontece quando você tenta calcular algo como fatorial de 45 é que os bits mais à esquerda e que não cabem no número vão sendo descartados. No fim das contas, haverá tantos bits descartados e tantas múltiplicações por fatores pares que só vão sobrar bits com valor zero.

Desse modo, você terá de mudar a forma de calcular sua combinação. Para isso, é útil lembrar que x!/y!, com x>=y, é a mesma coisa que x*(x-1)*(x-2)*...*(y+1).

EDIT: Uma maneira ainda melhor é inverter os fatores, calculando (y+1)*(y+2)*(y+3)*...*(x-1)*x, porque os valores intermediários das multiplicações que forem sendo feitas à esquerda serão menores dessa forma. Isso é particularmente útil se você lembrar que existe uma outra coisa para dividir (também sucessivamente crescente) essa conta.

EDIT2: Outra coisa que ajuda é lembrar que C(n, p) é idêntico a C(n, n-p). Desse modo, você pode fazer com que sua função possa sempre trabalhar com os menores valores possíveis no numerador.

1 0

Quote

3. Re: Ajuda C

paulo1205
(usa Ubuntu)

Enviado em 18/09/2018 - 14:47h

Outra forma de fazer, recursiva, é pelo Triângulo de Pascal: C(n, p)=C(n-1, p-1)+C(n-1, p), sendo que C(n, 0)=1 e C(n, p)=0 para todo p<0 ou p>n.

Como no Triângulo de Pascal ainda vale a relação C(n, n-p)=C(n, p), de modo que é possível reduzir a profundidade e a largura da recursividade quando p>n/2.

0 0

Quote

4. Re: Ajuda C [RESOLVIDO]

phoemur
(usa Debian)

Enviado em 18/09/2018 - 18:28h

https://pt.wikipedia.org/wiki/Coeficiente_binomial

Tem diversas formas de achar o Coeficiente binomial, utilizando dynamic programming, etc...

Em C++17 eu gosto assim, pois a integral de Euler de primeiro tipo (função std::beta) foi adicionada à biblioteca à partir do ano passado, no header <cmath>



int binomialCoeff(int n, int k) 

{ 

    return std::round(1.0 / ((n+1)*std::beta(n-k+1,k+1)));

}

Agora em C eu uso assim, que é mais ou menos o que o Paulo falou:



int binomialCoeff(int n, int k) 

{ 

    int res = 1; 

  

    // C(n, k) = C(n, n-k) 

    if ( k > n - k ) 

        k = n - k; 

  

    // [n * (n-1) *---* (n-k+1)] / [k * (k-1) *----* 1] 

    for (int i = 0; i < k; ++i) 

    { 

        res *= (n - i); 

        res /= (i + 1); 

    } 

  

    return res; 

}

Eu não gosto das soluções recursivas ou de Dynamic Programming porque tem complexidade quadrática O(n*k), enquanto as anteriores tem complexidade linear O(k).

Mas se tiver curiosidade dá uma olhada aqui que é interessante:
https://www.geeksforgeeks.org/binomial-coefficient-dp-9/

Abraços
______________________
https://github.com/phoemur

0 0

Quote