Página 1 de 1

Uma função... factorialmente desafiante!

MensagemEnviado: Terça Dez 15, 2009 5:11 pm
por Bruno Oliveira
Este problema é do projecteuler, e creio que deve envolver programação dinâmica, que por ser um conceito que eu não domino nem de perto (mas que gostava de aprender), decidi colocá-lo aqui:

Seja f(N) a função que para cada N que recebe, retorna os últimos 5 dígitos antes dos "trailing zeroes" em N! (os trailing zeroes, são a enorme sequência de zeros que existe a partir de determinada altura em N! e que vai até ao fim do número.)

Por exemplo:

20! = 2432902008176640000

Então:

f(20) = 17664

O objectivo é calcular f(1,000,000,000,000) :evil:

PS: A única coisa que consegui fazer foi calcular o número de 0s em 1,000,000,000,000!. Existem 249999999997 zeros seguidos.:shock:

Re: Uma função... factorialmente desafiante!

MensagemEnviado: Terça Dez 15, 2009 11:12 pm
por Ivo_Timóteo
Sinceramente não estou a ver o Project Euler a necessitar de DP... Creio que haja uma matematiquice que te ajude :)

Re: Uma função... factorialmente desafiante!

MensagemEnviado: Terça Dez 15, 2009 11:30 pm
por Bruno Oliveira
Só pensei no uso da programação dinâmica porque está mais que visto que é incomportável calcular 1,000,000,000,000!, portanto é mais que óbvio que deve haver uma maneira mais "Matemática" de abordar a questão, mas, caso seja viável resolver recorrendo a Programação Dinâmica gostava de ver.. :roll:

Re: Uma função... factorialmente desafiante!

MensagemEnviado: Quarta Dez 16, 2009 3:46 pm
por Tharis
Este problema aparece na USACO (sistema de treino americano) na secção onde estou actualmente. Não tem nada de difícil excepto descobrir o truque (ou como muito bem disse o Ivo, a "matematiquice") e aplicá-lo. De facto, demorei algum tempo a resolvê-lo e não o resolvi da maneira mais simples e eficiente... (Usei o que eles tentaram fazer com que não se usasse :P

Basicamente é descobrir como aparecem os 0s no final. Depois de saberem é só aplicarem o conceito. :P

Re: Uma função... factorialmente desafiante!

MensagemEnviado: Quarta Dez 16, 2009 4:08 pm
por ampat
Sim Bruno, acho que até já fizeste esse cálculo dos zeros (não para 1000000000000) este ano numa certa aula de Matemática... :D

Re: Uma função... factorialmente desafiante!

MensagemEnviado: Quarta Dez 16, 2009 5:37 pm
por Bruno Oliveira
Eh eh, pois já... :wink: