Question

Considere uma função

f: D = ℕ × ℕ* → ℕ

onde a cada par (x, y) ∈ D, f associa o valor do quociente da divisão inteira 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 quociente da divisão inteira de x por y.

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

f(x, y) = ____________

_____________________


Para representarmos a divisão de um número x por y, podemos utilizar o algoritmo da divisão

x    |_y_
r       q


x = Dividendo
y = Divisor
r = Resto
q = Quociente


Onde o dividendo é igual ao produto do quociente pelo divisor mais o resto.

Escrevendo esse algoritmo em linguagem matemática

$\mathsf{x = qy + r}$

Em casos de uma divisão de x por y onde x < y, o quociente é 0.

Como queremos uma relação de recorrência, iremos usar a expressão acima para criar uma

$\mathsf{x=qy+r}\\\\\\\mathsf{x=\underbrace{\mathsf{y+y+...+y}}+r}\\\mathsf{\qquad~\quad _{(q~vezes)}}$

Subtraia y em ambos os lados

$\mathsf{x-y=\underbrace{\mathsf{y+y+...+y}}+r-y}\\\mathsf{\qquad\qquad~\quad _{(q~vezes)}}\\\\\mathsf{x-y=\underbrace{\mathsf{y+y+...+y}}+r}\\\mathsf{\qquad\qquad~_{(q-1~vezes)}}$

Se fazermos a diferença entre o quociente da divisão de x por y pelo quociente da divisão de x - y por y, obtémos:

$\mathsf{q-(q-1)=q-q+1=1}$

Obteremos sempre 1 unidade. Portanto, o quociente da divisão de x por y é uma unidade maior que o quociente de x - y por y.

Então teremos a seguinte relação de recorrência.

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



Dúvidas? comente.