Matemática

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) = ____________


Answers

Generic placeholder image

raphaelinhasil

Reply

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 [latex]\mathsf{x = qy + r}[/latex] 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 [latex]\mathsf{x=qy+r}\\\\\\\mathsf{x=\underbrace{\mathsf{y+y+...+y}}+r}\\\mathsf{\qquad~\quad _{(q~vezes)}}[/latex] Subtraia y em ambos os lados [latex]\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)}}[/latex] 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: [latex]\mathsf{q-(q-1)=q-q+1=1}[/latex] 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. [latex]\mathsf{f(x,y)=}\begin{cases}\mathsf{0,~se~x\ \textless \ y}\\\mathsf{f(x-y,y)+1,~se~x\geq y}\end{cases}[/latex] Dúvidas? comente.

Leave a Answer


Please use only default html tags.