Henrique Rennó wrote:
Eu acredito que a função mod implementada em linguagens de programação
podem diferir em resultado. Acredito que isso deva ser um assunto bem
antigo, pois a função mod deve existir desde que as linguagens
começaram a ser implementadas.
Sim, isso é verdade. Em C, por exemplo, (-1)%2 = -1. Já em Python,
(-1)%2=1. Em Haskell tem os dois jeitos, você pode usar "rem" ou "mod".
Nesses casos é bom pegar a referência da linguagem que você está usando.
No caso específico da conversão de números, use o módulo dos dois lados
pra garantir o resultado não-negativo.
A conversão 1001(10) para base (-2) seria o problema de achar os
valores de N e A[i] (0 <= i <= N) para os quais a seguinte igualdade
seja verdadeira (na verdade termos com base elevada a valores > N
seriam 0, ou seja, A[j] = 0 para j > N):
1*(10)^3 + 0.(10)^2 + 0.(10)^1 + 1.(10)^0 = A[N]*(-2)^N +
A[N-1]*(-2)^(N-1) + A[N-2]*(-2)^(N-2) + ... + A[1]*(-2)^1 + A[0]*(-2)^0
Tá certinho, só faltou dizer que 0<=A[i]<abs(N)
Não é difícil continuar daqui, basta notar que você pode isolar um
(-2)^1 no lado direito:
x = (A[N]*(-1)^(N-1)+.....+A[1]*(-2)^0) * (-2)^1 + A[0]*(-2)^0
x - A[0] = (A[N]*(-1)^(N-1)+.....+A[1]*(-2)^0) * (-2)
Ou seja (x-A[0]) precisa ser um múltiplo de (-2), o que justifica a
passagem na conversão. O algoritmo então fica:
1. Ache A[0] tal que 0<=A[0]<abs(N) e (x-A[0]) seja múltiplo de (-2)
2. Calcule (x-A[0])/(-2) = A[N]*(-1)^(N-1)+.....+A[1]*(-2)^0
3. Você reduziu o problema ao caso anterior, itere até acabar.
--
Ricardo Bittencourt
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================
