Uma função... factorialmente desafiante!

Secção dedicada à linguagem de programação favorita dos quarkianos: Python!

Uma função... factorialmente desafiante!

Mensagempor Bruno Oliveira em Terça Dez 15, 2009 5:11 pm

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:
e^{ix}=cos x + i\,sin x
Avatar do utilizador
Bruno Oliveira
top-Quark!
top-Quark!
 
Mensagens: 1553
Registado: Quarta Nov 14, 2007 10:19 pm
Localização: Lisboa

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

Mensagempor Ivo_Timóteo em Terça Dez 15, 2009 11:12 pm

Sinceramente não estou a ver o Project Euler a necessitar de DP... Creio que haja uma matematiquice que te ajude :)
Avatar do utilizador
Ivo_Timóteo
charm-Quark!
charm-Quark!
 
Mensagens: 579
Registado: Quarta Nov 15, 2006 7:25 pm
Localização: V. N. Gaia

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

Mensagempor Bruno Oliveira em Terça Dez 15, 2009 11:30 pm

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:
e^{ix}=cos x + i\,sin x
Avatar do utilizador
Bruno Oliveira
top-Quark!
top-Quark!
 
Mensagens: 1553
Registado: Quarta Nov 14, 2007 10:19 pm
Localização: Lisboa

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

Mensagempor Tharis em Quarta Dez 16, 2009 3:46 pm

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
Avatar do utilizador
Tharis
up-Quark!
up-Quark!
 
Mensagens: 387
Registado: Quinta Out 23, 2008 4:26 pm

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

Mensagempor ampat em Quarta Dez 16, 2009 4:08 pm

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
ampat
bottom-Quark!
bottom-Quark!
 
Mensagens: 68
Registado: Sábado Dez 13, 2008 10:50 am
Localização: IST, Lisboa / Oeiras

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

Mensagempor Bruno Oliveira em Quarta Dez 16, 2009 5:37 pm

Eh eh, pois já... :wink:
e^{ix}=cos x + i\,sin x
Avatar do utilizador
Bruno Oliveira
top-Quark!
top-Quark!
 
Mensagens: 1553
Registado: Quarta Nov 14, 2007 10:19 pm
Localização: Lisboa


Voltar para Pitónica

Quem está ligado

Utilizadores a navegar neste fórum: Nenhum utilizador registado e 2 visitantes

cron