Introdução à Programação OCaml |
O problema que segue foi proposto na edição 2017 como item inicial da avaliação da componente prática da aprendizagem da programação OCaml
A sequência de Perrin é uma sequência de inteiros naturais que tem uma história interessante. Sugerida em 1876, foi explicitamente definida por François Olivier Raoul Perrin em 1899.
Tem várias aplicações, em particular em teoria dos grafos. Mas recentemente tem sido usada para descobrir coordenadas de taxis em redes urbanas de forma confidencial 1.
A sequência define-se de forma simples como
|
A entrada deste exercício consiste numa linha onde consta o inteiro n para qual se pretende obter Pn.
Uma simples linha com o inteiro Pn.
n≤ 10000 |
Este limite é arbitrário mas já obriga saber tratar de grandes
números. Comece por usar o tipo int para garantir uma boa
implementação e teste com valores pequenos. Garantida esta parte, use
a seguir o tipo de dado num ou big_int
fornecidos no módulo
num (em particular
num
ou big_int).
44
236282
Apresentamos diferentes soluções possíveis nos ficheiros seguintes:
Procedeu-se a avaliação do tempo de execução das diferentes soluções
aqui apresentadas. Todos os tempos são em medidos em segundos. As
execuções foram single-threaded. o parâmetro n
varia de 10 até 2.107, valor a partir do qual nenhuma solução
apresenta um tempo razoável de cálculo.
n: | 10 | 20 | 30 | 40 | 50 | 60 | 65 | 70 | 75 | 80 | 85 | 90 |
naive | 0 | 0 | 0 | 0 | 0 | 0,05 | 0,23 | 0,93 | 3,8 | 15,52 | 63,93 | 262,52 |
hash | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
vect | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
terminal | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
matrix | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
n: | 100 | 104 | 105 | 2.105 | 5.105 | 106 | 2.106 | 5.106 | 107 | 2.107 |
naive | - | - | - | - | - | - | - | - | - | - |
hash | 0 | 0 | 0,3 | 1,07 | 10,5 | - | - | - | - | - |
vect | 0 | 0 | 0,24 | 0,91 | 7,39 | - | - | - | - | - |
terminal | 0 | 0 | 0,07 | 0,26 | 1,4 | 5,46 | 22,94 | 164,72 | - | - |
matrix | 0 | 0 | 0,01 | 0,03 | 0,23 | 0,85 | 3,38 | 21,21 | 84,8 | 343,43 |
O computador que serviu de base à execução dos testes de performance tem a seguinte especificação técnica:
Model Name: | Mac Pro |
Processor Name: | Quad-Core Intel Xeon E5 |
Processor Speed: | 3,7 GHz |
Number of Processors: | 1 |
Total Number of Cores: | 4 |
L2 Cache (per Core): | 256 KB |
L3 Cache: | 10 MB |
Memory: | 12 GB |
This document was translated from LATEX by HEVEA.