(**
Objectivo do exercício:

ler um inteiro positivo n e ler um algarismo i (inteiro positivo entre 0 e 9) e
- calcular o número de algarismo de n
- calcular a soma dos algarismos de n
- calcular o numero de ocorrência de i em n

**)


(**
Comecemos pela acquisição dos dados úteis ao problema. A leitura dos dados...

A versão ingénua (optimista, confiando no bom senso do utilizador) pode ser simplesmente:

let n = read_int ()
let i = read_int ()

ou ainda 

let n,i = Scanf.scanf " %d %d" (fun a b -> a,b)

No entanto, vamos aplicar aqui alguns princípios básicos da programação defensiva (i.e. precaver-se do que pode acontecer, não confiar na origem dos dados): 

Ou seja repetir o processo de leitura de dados enquantos esses não respeitarem os requisitos a que estão sujeitos.
Usemos aqui uma função auxiliar e local de leitura de cada valor

**)

let n =
  (*ler_aux : função auxiliar e local à leitura de "n"
    enquanto o valor lido "tradicionalmente" (aux) não se enquadrar no requisito "ser inteiro positivo", então reiniciar o processo de leitura. 
    Case se enquadre, devolver simplesmente o valor aux 
  *)
  let rec ler_aux  () = 
    (let aux = read_int () in 
     if aux  < 0 
     then ler_aux () 
     else aux) 
  in  (*Estando a função definida,  invocar a função ler_aux*)
  ler_aux ()


(*De forma semelhante*)

let i = 
  let rec ler_i () = let aux = read_int () in if aux < 0 || aux > 9 then ler_i () else aux in
  ler_i ()



(**
Como percorrer os algarismos de um número, do primeiro ao último (ou - de forma semelhante -  do último ao primeiro)?

Se mantivermos o formato de n como sendo um inteiro (poderiamos ter lido n na forma de uma string, ou um vector dos seus algarismos)
então uma estratégia possível é percorrer estes algarismos recorrendo a divisão por 10 ou o resto da divisão por 10.

Assim (por exemplo)

13251432453  /  10 = 1325143245
13251432453 mod 10 = 3

A função "mod 10" dá-nos o algarismo das unidades
A função "/ 10" realiza um shift para a direita (remove o algarismo das unidades).

A combinação destas duas funções nos permitirá aceder de forma sequencial, da direita para a esquerda, aos algarismos do inteiro considerado.  
 
Por comodidade, definimos duas funções auxiliares

**)

let alga a = a mod 10

let next a = a / 10


(**
Iniciemos a resolução propriamente dita.
**)




(**
Somar os algarismos de um inteiro pode ser feito explorando e somando um a um os algarismos constituinte.
O caso de base (ou terminal) deste processo é quando a exploração se depara com o último algarismo (o da primeira posição à esquerda)
**)



let rec soma a = 
  if a < 10 then a
  else (alga a) + soma (next a)
 

(* um exemplo de execução pode ser:

soma 2341234 = (alga 2341234) + soma (next 2341234)
             = 4 + soma 234123
             = 4 + (alga 234123) + soma (next 234123)
             = 4 + 3 + soma 23412
             = 4 + 3 + (alga 23412) + soma (next 23412)
             = 4 + 3 + 2 + soma 2341
             = 4 + 3 + 2 + (alga 2341) + soma (next 2341)
             = 4 + 3 + 2 + 1 + soma 234
             = 4 + 3 + 2 + 1 + (alga 234) + soma (next 234)
             = 4 + 3 + 2 + 1 + 4 + soma 23
             = 4 + 3 + 2 + 1 + 4 + (alga 23) + soma (next 23)
             = 4 + 3 + 2 + 1 + 4 + 3 + soma 2
             = 4 + 3 + 2 + 1 + 4 + 3 + 2
             = 4 + 3 + 2 + 1 + 4 + 5
             = 4 + 3 + 2 + 1 + 9
             = 4 + 3 + 2 + 10
             = 4 + 3 + 12
             = 4 + 15 
             = 19


Claramente esta função não é recursiva terminal. Deixa o calculo das somas a espera do resultado da chamada recursiva.

Um informático é por natureza poupado. Se vê uma oportunidade de melhorar, poupar recursos computacionais, poupa.
(Em engenharia de software, esta tarefa é designada de "refactoring")
É o caso aqui....

Vamos transformar a função [soma] numa função recursiva terminal.
Esta nova versão da função procurará não deixa nenhum cálculo pendente.

Aqui a pista essencial é determinar que os calculos pendentes gerados devam ser realizados na chamada recursiva na forma de uma passagem parâmetros "inteligente".
Para tal precisamos de mais um parâmetro para a função [soma]...
Este parâmetro tem o papel de uma variável temporária que, no caso de um ciclo, actualizamos até esta conter o resultdo final pretendido.

Aquando da chamada inicial a função alterda deverá propor um valor inicial para este parâmetro suplementar (o valor inicial da variável temporária no caso de um ciclo)   
 *)


let rec soma_aux a acc =
if a < 10 then (acc+a)
else soma_aux (next a) (acc + (alga a))

let soma n = soma_aux n 0

(*
soma 324121 = soma_aux 324121 0
            = soma_aux 32412 1
            = soma_aux 3241 3
            = soma_aux 324 4
            = soma_aux 32 8
            = soma_aux 3 10
            = 13
*)


(**
Como calcular o número de algarismos de um determinado inteiro positivo n?
De forma muito semelhante à soma...

Aproveitemos aqui para definir uma versão recursiva terminal
**)

let rec conta_aux a acc =
if a < 10 then (acc+1)
else conta_aux (next a) (acc + 1)

let conta n = conta_aux n 0


(*
conta 324121 = conta_aux 324121 0
             = conta_aux 32412 1
             = conta_aux 3241 2
             = conta_aux 324 3
             = conta_aux 32 8
             = conta_aux 3 5
             = 6

Muito melhor, não?



Tentemos agora calcular o produto dos algarismos de um inteiro positivo
*)

(* uma primeira versão*)
let rec mult a = 
  if a < 10 then a
  else (alga a) * mult (next a)
 
(* uma versão recursiva terminal*)
let rec mult_aux a acc =
if a < 10 then (acc*a)
else mult_aux (next a) (acc * (alga a))

let mult n = mult_aux n 1


(* Outra qualidade intrínseca de um programador é ser preguiçoso constructivo. 
Procura nunca repetir a mesma tarefa.

No nosso caso, vemos perfeitamente que as três funções até agora escritas partilham a 
mesma estrutura algorítmica, o mesmo caso de base, quer na versão recursiva quer na versão recursiva terminal.

Ser preguiçoso neste caso é escrever uma função para o padrão algorítmico principal e 
permitir que várias instâncias deste padrão possam ser definidas a custa dos parâmetros da função

De froma geral o padrão para as operações que fizemos sobre o inteiro é:

let rec  operação a = 
  if a < 10 then "algo sobre a" 
  else  "algo sobre (alga a) e  operação (next a)";;

Nos três casos que vimos:
"algo sobre a" foi "a" ou então "1"

"algo sobre (alga a) e  operação (next a)" foi a soma, a função sucessor e finalmente a multiplicação.

Estas diferenças no padrão algorítmico podem tomar a forma de funções parâmetros: 

*)

let rec oper f r a = 
if a < 10 then r a
else f (alga a) (oper f r (next a))


let soma n = oper (+) (fun a -> a) n

let mult n = oper ( * ) (fun a -> a) n

let conta n = oper (fun a b -> 1 + b) (fun a -> 1) n 


(** 
O ideal, no fundo, é ser poupado e preguiçoso.
**) 



let rec oper f a acc =
if a < 10 then (f a acc)
else oper f (next a) (f (alga a) acc)


let soma a = oper (+) a 0 
let mult a =  oper ( * ) a 1
let conta a = oper (fun a b -> 1 + b) a 0 

(* Vejamos então como resolver a ultima alínea *)


(* originalmente podemos escrever a função desta forma*)
let rec algarismo_i a i =
if a <10 then 
  (if a =i then 1 else 0)
else  
  (if (alga a) = i then 1 else 0) + algarismo_i (next a) i

  

(* Vejamos então se a função oper é suficientemente flexível para expressar a ultima alínea*)

let algarismo_i n i = oper (fun a b -> if a=i then 1+b else b) n 0


(**
Ser mesmo poupado é calcular os tres valores de uma só vez (num só percurso de n).
A função seguinte implementa tal solução.

Com tal, precisa então de três acumuladores que arquivarão os três valores por devolver 
no fim dos percurso dos algarismos.
**)


let rec count x y acc1 acc2 acc3 = 
  if x < 10 then 
    ((if (x=y) then 1 else 0) + acc1,(acc2+x),(acc3+1))
  else
    count (next x) y ((if (alga x) = y then 1 else 0) + acc1) (acc2+(alga x)) (acc3+1)





(**
Por último....melhor ainda
**)

let count n i = oper (fun a (acc1,acc2,acc3) -> ((if (a = i) then 1 else 0) + acc1,(acc2+ a),(acc3+1)))  n (0,0,0)




(*finalmente: chamar a função e mostrar o resultado*)

let pp_res = fun (x,y,z) ->  Printf.printf "%d\n%d\n%d\n" x y z


let () = pp_res (count n i)

This document was generated using caml2html