Re: [obm-l] Conversão de Números em Base Negativa

[Ricardo Bittencourt <ricbit@xxxxxxxxxxxx>]

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