Quark! • Vendo Tópico - Uma função... factorialmente desafiante!
Uma função... factorialmente desafiante!
por 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 a função que para cada N que recebe, retorna os últimos 5 dígitos antes dos "trailing zeroes" em (os trailing zeroes, são a enorme sequência de zeros que existe a partir de determinada altura em e que vai até ao fim do número.)
O objectivo é calcular f(1,000,000,000,000)
PS: A única coisa que consegui fazer foi calcular o número de 0s em 1,000,000,000,000!. Existem 249999999997 zeros seguidos.
Re: Uma função... factorialmente desafiante!
por 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
por 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 , 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..
por 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
Basicamente é descobrir como aparecem os 0s no final. Depois de saberem é só aplicarem o conceito.
por 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...