2012/10/3 terence thirteen peterdirich...@gmail.com
Em 3 de outubro de 2012 06:12, ennius enn...@bol.com.br escreveu:
Caros Colegas, Gostaria de obter, se possível for, demonstração do
teorema abaixo, em que divisão quer dizer divisão euclidiana, n é inteiro,
D e d são inteiros positivos. Teorema: O quociente da divisão de n por
Dd é igual ao quociente da divisão de q por d, sendo q o quociente da
divisão de n por D.
O quociente de x por y é [x/y], parte inteira da divisão.
Você quer que [n/Dd] = [[n/D]/d]
Eu tenho boas razões para pensar que isso não é verdadeiro, pelo menosnão
sem impor alguma restrição a D e d.
Isso é verdadeiro.
[n/Dd] = [[n/D]/d] sse d[n/Dd] = d[[n/D]/d]
(para d != 0)
d[[n/D]/d] = [n/D] - [n/D]%d, onde a%b é o resto de a na divisão por b.
De modo similar
d[n/Dd] = d[(n/D)/d] = (n/D) - (n/D)%d
Note que o resto aqui é especial aqui, pq carrega também a mantissa do
número. (n/D)%d = ([n/D] + m)%d = [n/D]%d + m, onde m é a mantissa, ou seja
a parte fracionária do número.
Assim fica claro que (n/D) - (n/D)%d = [n/D] - [n/D]%d
Isso é um exercício do Art of Computer Programming do Knuth.
--
[]'s
Lucas
