Uma função... factorialmente desafiante!

[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 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.)

Por exemplo:



Então:



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.

[Ivo_Timóteo]

Sinceramente não estou a ver o Project Euler a necessitar de DP... Creio que haja uma matematiquice que te ajude

[Bruno Oliveira]

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..

[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

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

[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...

[Bruno Oliveira]

Eh eh, pois já...