7

O código deve imprimir quantos dígitos tem o fatorial de N.

Estou tentando realizar um desafio simples de fatorial no site URI e quando submeto o código a resposta é sempre "Time limit exceeded", o limite é 1.00s e está dando 2.00s. Já pesquisei sobre o problema e tentei modificar o código para ficar mais rápido, porém o erro se repete. Segue os códigos que submeti:

N = int(input())
for i in range(1, N):
  N = (i * N)
print(len(str(N)))

Este também:

import math
N = input()
print(len(str(math.factorial(int(N)))))

Tentei usar o stdout.write mas deu "Presentation Error" apesar de ter executado também em 2.00s

import math
from sys import stdin, stdout
N = int(input())
for i in range(1, N):
  N = N * i
  stdout.flush()
N = len(str(N))
stdout.write(str(N))
import math
from sys import stdin, stdout
N = int(input())
for i in range(1, N):
  N = N * i
  stdout.flush()
N = len(str(math.factorial(N)))
stdout.write(str(N))

Gostaria de dicas de qual caminho seguir para melhor o tempo de execução e por que estas não deram certo.

5
  • Você mencionou o tempo gasto, mas não mencionou para qual valor de N esse tempo foi calculado. Quais os valores de N que você usou nos seus testes ?
    – Lacobus
    10/04/2020 às 22:42
  • @Lacobus Esse é um desafio do URI. Normalmente, o URI faz testes com um monte de entradas diferentes, e muitas delas são secretas para evitar que os algoritmos sejam desenvolvidos de forma a tentar burlá-las. Muitas das entradas que tipicamente explodem algoritmos feitos por iniciantes são coisas monstruosas e/ou números astronômicos. 10/04/2020 às 22:44
  • Eu editei a pergunta, os casos de testes são para 0 < N <= 10^8 10/04/2020 às 23:34
  • Vey, pergunta veya e n deve precisar mais, mas n! = Gamma(n+1) e Digits(i) = floor(log10(i))+1 = floor(log10(exp(1))*ln(i))+1 ~ floor(0.43429448190325182765*ln(i))+1, portanto Digits(n!) ~ floor(0.43429448190325182765*ln( Gamma(n+1) ))+1. Função em python que calcula ln(Gamma()) é scipy.special.gammaln.
    – RHER WOLF
    18/07/2020 às 0:49
  • Ou seja, simplesmente da import de math e scipy.special e usa a expressão math.floor( 1+0.43429448190325182765*scipy.special.gammaln(N+1) ) ou mesmo (pra não precisar calcular a constante) math.floor( 1+math.log10( math.exp(1) )*scipy.special.gammaln(N+1) ). É cálculo bem rápido.
    – RHER WOLF
    18/07/2020 às 0:54

5 Respostas 5

5

O problema é que o fatorial cresce muito rápido, e em pouco tempo você estará multiplicando números enormes, o que é bem demorado. Só para ter uma ideia, o fatorial de 108 (que é o limite máximo que você indicou) é um número com mais de 750 milhões de dígitos. Manipular números dessa grandeza não tem como ser rápido...

Então uma alternativa é calcular a quantidade de dígitos do fatorial, mas sem precisar calcular o valor do fatorial.

Uma forma de obter a quantidade de dígitos de um número é calcular o logaritmo na base 10, arredondar para baixo e somar 1.

Outro detalhe é que o log10(a * b) é igual a log10(a) + log10(b).

E como o fatorial de N é a multiplicação de todos os números inteiros entre 1 e N, podemos calcular o log10(N!) somando os logs de todos os números entre 1 e N. Ou seja:

  • log10(N!) é o mesmo que log10(1 * 2 * 3 * ... * N)
  • que por sua vez é o mesmo que log10(1) + log10(2) + log10(3) + ... + log10(N)

Então basta somar os logs de todos os números de 1 a N, arredondar para baixo e somar 1, para obter a quantidade de dígitos de N! (sem precisar calcular o valor do fatorial).

Ficaria assim:

from math import floor, log10

n = int(input())

res = 0
for i in range(1, n + 1):
  res += log10(i)

print(floor(res) + 1)

Ou ainda:

print(floor(sum(map(log10, range(1, n + 1)))) + 1)

Não testei no URI online, mas fiz um pequeno teste no qual as duas opções acima se mostraram bem mais rápidas que calcular o fatorial:

from math import floor, log10, factorial
from timeit import repeat

def log(n):
  res = 0
  for i in range(1, n + 1):
    res += log10(i)

  return floor(res) + 1

def log2(n):
  return floor(sum(map(log10, range(1, n + 1)))) + 1

def fact(n):
  return floor(log10(factorial(n))) + 1 

n = 200000
x = 1
r = 3
print (repeat ('log(n)', repeat=r, number=x, globals=globals()))
print (repeat ('log2(n)', repeat=r, number=x, globals=globals()))
print (repeat ('fact(n)', repeat=r, number=x, globals=globals()))

E quanto maior o N, maior a diferença entre as abordagens.

E faz sentido. Ao calcular o fatorial, você está multiplicando números cada vez maiores, enquanto que no método dos logaritmos estamos somando números pequenos (tudo bem que temos que calcular o logaritmo de todos os números, mas ainda sim compensa e é mais rápido).

1
  • 1
    Se eu não tivesse lido a sua resposta eu teria respondido errado. Obrigado. 11/04/2020 às 7:28
3

Você pode usar a fórmula de Kamenetsky para se calcular a quantidade de digitos contidos no fatorial de N, veja só:

def kamenetsky(n):
    if n < 0:
        return 0
    if n <= 1:
        return 1
    x = (n * log10(n / e)) + (log10(2 * pi * n) / 2.0)
    return floor(x) + 1

Para efeito de comparação dos algoritmos testados, sugiro a implementação de uma função capaz de mensurar o tempo de processamento gasto por cada um deles:

from timeit import default_timer

def teste( func, n, cont=1000 ):
    inicio = default_timer()
    for i in range(cont):
        func(n)
    fim = default_timer()
    total = fim - inicio
    return (total / cont) * (10**6) # Tempo em microsegundos 

Testando:

from math import log10, floor, factorial, pi, e
from timeit import default_timer

def teste( func, n, cont=1000 ):
    inicio = default_timer()
    for i in range(cont):
        func(n)
    fim = default_timer()
    total = fim - inicio
    return (total / cont) * (10**6)

def f1(n):
    for i in range(1, n):
        n = i * n
    return len(str(n))

def f2(n):
    n = factorial(n)
    return len(str(n))

def f3(n):
    if n < 0:
        return 0
    if n <= 1:
        return 1
    x = (n * log10(n / e) + log10(2 * pi * n) / 2.0)
    return floor(x) + 1

N = 100
print('f1(): {:.3f} uS'.format(teste(f1, N)))
print('f2(): {:.3f} uS'.format(teste(f2, N)))
print('f3(): {:.3f} uS'.format(teste(f3, N)))

Saída:

f1(): 7.629 uS
f2(): 1.796 uS
f3(): 0.678 uS
2

Esta questão se refere ao problema de número "3096", cujo título é "overflow", disponibilizado por URI Online Judge (maratona online de programação).

Veja aqui a íntegra do enunciado.

A questão enfatiza que, em muitos casos onde é necessário calcular o fatorial de um número, cujo resultado possui um número muito grande de algarismos, possivelmente pode resultar em um overflow.

Observe que a questão diz que o programa deve suportar valores N, tais que, 1<= N <= 10^8, isto é, deve suportar valores entre 1 e 100000000. Agora, imagine o quanto de recursos computacionais um programa usaria se tivesse de calcular o fatorial de 100000000?

Pra começar, o número total de dígitos de 100000000! é 756570557. Para melhorar a legibilidade podemos dividir em milhares e deixa-lo da seguinte forma 756.570.557,ou seja, o número total de dígitos resultante do fatorial de 100.000.000 é setecentos e cinquenta e seis milhões, quinhentos e setenta mil, quinhentos e cinquenta e sete.

Como é muito demorado se obter o valor correto para fatoriais de grandes valores, o problema nos pede para calcular apenas o número de dígitos do possível fatorial.

Na matemática, podemos sim, calcular o número de dígitos do resultado do fatorial sem mesmo ter calculado o fatorial desse número. Para isso basta utilizar a fórmula de Kamenetsky.

Para implementarmos esta fórmula corretamente na questão do Uri, com todas as restrições que nos é enfatizada, devemos escrever o seguinte código...

from math import log10, e, pi, floor

n = int(input())

num_digitos = floor((n * log10(n / e)) + (log10(2 * pi * n) / 2.0)) + 1
print('{}'.format(num_digitos))

Veja aqui o funcionamento do algoritmo.

Observe que, quando executamos este programa, a tela do console fica limpa, aguardando a digitação do valor de N. Após digitarmos o valor de N e, em seguida, pressionarmos Enter, o programa conclui a tarefa.

Este código já foi testado, submetido e devidamente aprovado, na maratona que me referir no início do poste, sob linguagem de programação Python 3.

Só para constar, este programa levou apenas 0.028 s para ser executado no site URI.

0
1

Você pode computar o fatorial de um número usando a Função Gamma de Ramanujan que é semelhante ao Gamma de Stirling, porém é mais precisa:

função Gamma de Ramanujan

Função Gamma ou Γ é a extensão da função factorial para o conjunto dos números reais e complexos. A função Gamma é definida para todos os complexos exceto os inteiros negativos.

Como o domínio estabelecido pelo AP [0, 10⁸⁰] é de extensão maior que sys.float_info.max usei a biblioteca Mpmath que é uma biblioteca Python para aritmética de ponto flutuante de precisão arbitrária.

A implementação para computar o a quantidade de dígitos de um fatorial fica assim:

#No comentário foi definido o domínio [0, 10 ^ 80] então usei mpmath 
from mpmath import log10, pi, e, sqrt

def gamma(x):
  return int(log10(sqrt(pi)*(x/e)**x * (((8*x + 4)*x + 1)*x + 1/30.)**(1./6.))) + 1

Teste no Repl.it: https://repl.it/repls/RelievedJaggedLogins

-5

Manda a pergunta se esse código não lhe ajudar.

num = int(input('Numero: '))
for i in range(1, num):
  num = i * num
#Mostrando o fatorial do numero digitado
print(num)
#Essa varivel converte o valor int para string
converte = str(num)
#Aqui ele mostra o tamanho da string
print(len(converte))
1
  • É o primeiro que testei, só que com nomes de variáveis diferentes. 10/04/2020 às 23:32

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .