Question

Considere uma função

f: D = ℕ × ℕ* → ℕ

onde a cada par (x, y) ∈ D, f associa o valor do resto da divisão de x por y.

Escreva uma lei de formação recursiva para f.

f(x, y) = ____________

Answer 1

Olá Lukyo.


Considere uma função

f: D = ℕ × ℕ* → ℕ

onde a cada par (x, y) ∈ D, f associa o valor do resto da divisão de x por y.

Escreva uma lei de formação recursiva para f.

f(x, y) = ____________
___________________________

Em uma divisão de x por y, sendo x < y, o resto será x.

Para obtermos o resto de uma divisão de um número x por um número y para x ≥ y, basta multiplicarmos y por um inteiro k de forma que a diferença de x pelo produto ky seja menor que x.

Algebricamente ficaria:

$\mathsf{x - ky = r}$

r ∈ {0, 1, 2, ..., x - 1}

Onde r é o resto. 

Entretanto, como queremos uma relação de recorrência iremos considerar subtrações sucessivas pelo divisor y, para os casos em que x ≥ y.

Portanto, nossa relação de recorrência ficará da seguinte forma.


$\mathsf{f(x,y)=}\begin{cases}\mathsf{x,~se~x\ \textless \ y~}\\\mathsf{f(x-y,y),~se~x\geq y}\end{cases}$



Dúvidas? comente.