Ficha OCaml 2. Do familiar para o novo.Nível básicoEx. Digit Sum.Ex. Triângulo de Floyd.Nível MédioEx. Procura de número.Ex. Troca de variável, com poupança.Ex. Função de Rolling Hash para string.
Considere o seguinte programa C que calcula a soma dos dígitos de uma dado número.
xxxxxxxxxx
211// Um programa C que calcula a soma dos dígitos de um dado inteiro
2
3int getSum(int n)
4{
5 int sum = 0;
6 while (n)
7 {
8 sum += n % 10;
9 n /= 10;
10 }
11 return sum;
12}
13
14int main()
15{
16 int n;
17 printf("number? ");
18 scanf("%d",&n);
19 printf("\n digit sum= %d \n", getSum(n));
20 return 0;
21}
Proponha duas versões OCaml da função getSum
:
Uma versão iterativa, fiel a versão C, get_sum_iter : int -> int
.
Assim, get_sum_iter 3415 = 13
Uma versão recursiva get_sum_rec : int -> int
.
Assim, get_sum_rec 3415 = 13
O triângulo de Floyd é uma matriz triangular de números naturais. O seu nome se refere ao Robert Floyd.
É definido pelo preenchimento das linhas do triângulo com números consecutivos, começando com 1 no canto superior esquerdo. Assim o triângulo de Floyd com 5 linhas é:
xxxxxxxxxx
511
22 3
34 5 6
47 8 9 10
511 12 13 14 15
Um programa C que calcula este triângulo com um dado número de linhas é:
xxxxxxxxxx
251
2
3
4void print_triangle(int n)
5{
6 int value=1,i=0,line=0;
7 for (line=1;line<=n;line++)
8 {
9 for(i=0;i<line;i++)
10 printf("%4d",value++);
11 printf("\n");
12 }
13}
14
15int main(int argv,char ** argc) {
16 if (argv!= 2)
17 {
18 int n;
19 printf("número de linhas? ");
20 scanf(" %d",&n);
21 }
22 else print_triangle(atoi(argc[1]));
23
24return 0;
25}
Escreva a função OCaml print_triangle : int -> unit
que realize esta mesma tarefa. Assim:
xxxxxxxxxx
71print_triangle 5 = ()
2(*no stdin*)
31
42 3
54 5 6
67 8 9 10
711 12 13 14 15
Charles Babbage propôs um desafio de aritmética simples mas que pensava poder ser resolvido mais comodamente com máquinas se estas existissem, em particular se ele tivesse os meios de as construir.
Qual é o menor inteiro positivo cujo quadrado termina nos dígitos 269.696?
(Babbage, carta para Lord Bowden, 1837)
Ele achou que a resposta poderia ser 99.736, cujo quadrado é 9.947.269.696; mas ele não tinha certeza.
Obviamente ele resolveu o problema com papel e caneta, mas é tao mais prático, de facto usar um programa de computador.
xxxxxxxxxx
201
2
3
4
5int main() {
6 int current = 0,
7 square;
8
9 while (((square=current*current) % 1000000 != 269696) && (square<INT_MAX)) {
10 current++;
11 }
12
13 if (square > INT_MAX)
14 printf("Condition not satisfied before INT_MAX reached.");
15 else
16 printf ("The smallest number whose square ends in 269696 is %d\n", current);
17
18 return 0 ;
19}
20
Esta é uma solução em C (retirada do excelente site rosetta code, apesar deste exemplo aqui...).
Infelizmente este código tem alguns problemas escondidos.
babbage : unit -> int
que de um argumento unit
(o argumento vazio) calcula o inteiro pretendido pelo Charles Babbage . babbage_opt : unit -> int
.
Há uma forma simples de trocar o valor de duas variáveis numéricas, digamos x
e y
sem usar uma variável auxiliar.
x
1
2
3int main()
4{
5 int x,y;
6
7 printf("two numbers: ");
8 scanf(" %d %d", &x, &y);
9
10 printf("Before Swapping: x = %d, y = %d\n", x, y);
11
12 x = x + y;
13 y = x - y;
14 x = x - y;
15
16 printf("After Swapping: x = %d, y = %d\n", x, y);
17
18 return 0;
19}
20
Este pequeno programa C implementa esta ideia simples. Mas, sem devidos cuidados, é uma prenda envenenada.
Proponha uma versão OCaml na forma da função swap : int -> int -> unit
cujo esqueleto se mostra aqui e que lhe pedimos por completar:
xxxxxxxxxx
51let swap a b =
2 let x,y = ref a , ref b in
3 let () = Printf.printf "Before Swapping: x = %d, y = %d\n" !x !y in
4 (*Por completar*)
5 let () = Printf.printf "After Swapping: x = %d, y = %d\n" !x !y
Liste os potenciais problemas que este programa tem (tanto na versão C como na versão OCaml).
Proponha uma versão OCaml sem a parte envenenada, ou seja a função nice_swap : int -> int -> unit
. Caso seja necessário poderá lançar a exceção Failure "nice_swap"
Uma alternativa ao método proposto é usar o operador bitwise XOR para trocar para números. O operador XOR bit a bit avalia cada bit do resultado como 1 se os bits correspondentes dos dois operandos forem diferentes, caso contrário, avalia 0.
Sejam x
e y
dois valores inteiros, seja a
= x XOR y
. Agora a XOR y
será avaliado como x
e a XOR x
será avaliado como y
.
Uma solução em C pode ser:
xxxxxxxxxx
201
2
3int main()
4{
5 int xnum1, num2;
6
7 printf("two numbers: ");
8 scanf(" %d %d", &x, &y);
9
10 printf("Before Swapping: x = %d, y = %d\n", x, y);
11
12 x ^= y;
13 y ^= x;
14 x ^= y;
15
16 printf("After Swapping: x = %d, y = %d\n", x, y);
17
18 return 0;
19}
20
bitwise_swap : int -> int -> unit
.
Uma função de hash de uma string tem por objeto a conversão de uma string para um número inteiro que será intitulado como hash dessa string. Idealmente esta associação é única. Mas na prática duas strings podem ter o mesmo hash (fenômeno designado de colisão).
Uma boa função de hash é aquela em que a probabilidade em ter o mesmo hash para duas strings diferentes é residual ou é aquela para a qual é muito difícil saber que outra string tem uma colisão com uma dada string. Este tema será abordado com mais detalhe mais adiante nesta matéria e no curso.
Um caso particular de função de hash são as funções designadas de rolling hash. São funções auxiliares importantes em alguns algoritmos de processamento de texto. Por exemplo o algoritmo de procura de string em textos grandes conhecido por algoritmo Rabin-Karp para a procura em string usa uma função de rolling hash como função auxiliar.
Uma das funções Rollin Hash mais simples calcula uma hash para uma string da seguinte forma:
os valores e devem ser escolhidos cuidadosamente e onde os são os valores numéricos associados a cada letra considerada. Para o fim deste exercício, trabalharemos com strings constituídas exclusivamente por letras minúsculas, assim escolhemos e e o valor de 'a' é , o valor de 'b' é , etc.
Por exemplo
xxxxxxxxxx
161long long rollingHash(char *str,int length)
2{
3 // P and M
4 int p = 31;
5 int m = 1e9 + 9;
6 long long power_of_p = 1;
7 long long hash_val = 0;
8
9 // Loop to calculate the hash value by iterating over the elements of the string
10 for (int i = 0; i < length; i++) {
11 hash_val = (hash_val + (str[i] - 'a' + 1) * power_of_p) % m;
12 power_of_p = (power_of_p * p) % m;
13 }
14 return hash_val;
15}
16
Numa primeira versão, não tomaremos conta do tamanho dos inteiros manipulados, ou seja, vamos trabalhar com valores de tipo int
na esperança que estes sejam suficientes. Proponha uma versão OCaml desta função rollingHash : string -> int
(o tamanho de uma string pode ser calculado da própria string em OCaml, não é preciso fornecê-lo explicitamente).
Assim rolling_hash "hello" = 14222002
.
Pretendemos agora garantir este mesmo cálculo mas com base numa função recursiva
Assuma as definições seguintes:
xxxxxxxxxx
81let p = 31
2let m = 1_000_000_000 + 9
3let code c = Char.code c - Char.code 'a' + 1
4
5let rec rolling_hash_rec s i hval powerp =
6(*Por completar *)
7
8let rolling_hash s = rolling_hash_rec s 0 0 1
Complete a definição da função rolling_hash_rec
.
xxxxxxxxxx
31utop # rolling_hash "euqueroestarlaquandotutiveresdeolharparatrassemprequeroouvirsquiloqueguardasteparadizernofim";;
2
3- : int = 130515272
rolling_hash
(qualquer uma das duas acima referida) que recorra à aritmética de precisão arbitrária (módulo zarith
). A função esperada é: rollingHash_wide : string -> Z.t
xxxxxxxxxx
41utop # #require "zarith.top";;
2utop # rolling_hash_wide "temmilanosumahistoriadeviveranavegarhamilanosdememoriasacontaraicidadeabeiramarazul"
3;;
4- : Z.t = 728940700