sábado, 18 de abril de 2015

Programação em C - Soma dos dígitos do fatorial de 100 (Project Euler Problem 20)

Olá pessoal, recentemente me deparei com o problema de calcular a soma dos dígitos do fatorial de números grandes. Em algumas linguagens isso é muito fácil de fazer bastando utilizar bibliotecas já prontas.

Em Python por exemplo você não precisa se preocupar com o tamanho do número, basta você calcular o fatorial normalmente ou mesmo utilizar a função "factorial" que já vem implementada no ponto para utilizar. Depois de calcular o fatorial, basta somar os dígitos.

Em Java por exemplo você poderia utilizar a classe BigInteger. Enfim, existem várias bibliotecas que podem lhe ajudar. O problema de calcular a soma dos dígitos de 100! está disponível no endereço:

https://projecteuler.net/problem=20

Mas como seria em C? Calcular o fatorial de 100 é inviável pois não é possível armazenar um número tão grande em um inteiro. Vamos fazer sem bibliotecas, na minha humilde opinião o interessante de projetos como o Project Euler é você encontrar uma forma (um algoritmo) que resolva o problema.

Vamos utilizar um vetor de inteiros onde serão guardados todos os dígitos do fatorial do número 100. Antes vamos fazer testes com exemplos pequenos com o 4 fatorial.

Lembrando que 4! = 4 * 3 * 2 * 1 = 24

O nosso vetor de inteiros incialmente irá conter somente zeros exceto para o primeiro elemento que conterá o número 1.

Em 4!, o 4, 3, 2 e 1 são fatores do fatorial de 4. Para cada fator (exceto o 1, pois já colocamos ele inicialmente no vetor que guardará os dígitos) nós iremos fazer uma multiplicação.

Inicialmente temos o nosso vetor de dígitos onde o primeiro elemento é 1:

digitos = [1, 0, 0, 0, 0, 0, ... ]

fator = 2

A variável "div" guardará a divisão do digito por 10, inicialmente ela é 0
div = 0

para todos os elementos do vetor de dígitos, faça:

i = 0
digito = digitos[i] = digitos[0] = 1
digito = digito * fator = 1 * 2 = 2
digito = digito + div = 2 + 0 = 2
digitos[i] = digitos[0] = digito % 10 = 2 % 10 = 2
div = digito / 10 = 2 / 10 = 0

Perceba que o "div" é 0, não vou continuar a execução pois não irá mudar mais nada, irei passar para o próximo fator.

Lembrando que o nosso vetor de dígitos está assim:
digitos = [2, 0, 0, 0, 0, 0, ... ]

fator = 3
div = 0

i = 0
digito = digitos[i] = digitos[0] = 2
digito = digito * fator = 2 * 3 = 6
digito = digito + div = 6 + 0 = 6
digitos[i] = digitos[0] = digito % 10 = 6 % 10 = 6
div = digito / 10 = 6 / 10 = 0

Perceba que o "div" é 0, não vou continuar a execução pois não irá mudar mais nada, irei passar para o próximo fator.

Lembrando que o nosso vetor de dígitos está assim:
digitos = [6, 0, 0, 0, 0, 0, ... ]

fator = 4
div = 0

i = 0
digito = digitos[i] = digitos[0] = 6
digito = digito * fator = 6 * 4 = 24
digito = digito + div = 24 + 0 = 24
digitos[i] = digitos[0] = digito % 10 = 24 % 10 = 4
div = digito / 10 = 24 / 10 = 2

Opa, "div" não é 0, então vou continuar mostrando a execução :)

i = 1
digito = digitos[i] = digitos[1] = 0
digito = digito * fator = 0 * 4 = 0
digito = digito + div = 0 + 2 = 2
digitos[i] = digitos[1] = digito % 10 = 2 % 10 = 2
div = digito / 10 = 2 / 10 = 0

Perceba que o "div" é 0, não vou continuar a execução pois não irá mudar mais nada, irei passar para o próximo fator.

Lembrando que o nosso vetor de dígitos está assim:
digitos = [4, 2, 0, 0, 0, 0, ... ]

Perceba que temos os dois dígitos do fatorial de 4 no vetor digitos: 4 e 2. Agora ficou fácil, basta somar todos os dígitos do vetor digitos para obter a soma dos dígitos do fatorial de um número.

Perceba que a multiplicação de um número por 10 ou por 100 por exemplo, não altera a soma dos dígitos, isso quer dizer que para calcular a soma dos dígitos do fatorial de 100, você não precisa ir até 100.

A implementação foi feita em C, veja o código:


Quaisquer dúvidas deixem nos comentários, até a próxima!


Nenhum comentário: