quarta-feira, 30 de julho de 2014

3830. Soma

Olá meus amigos nerds, como é costume, estou aqui hoje para resolver nosso problema da semana. Infelizmente, o problema que vamos resolver é muito fácil, mas como nosso objetivo é resolver todos os problemas do spoj isso não importa muito. Não é mesmo?

Hoje vamos somar números, já que é isso que o problemas 3830. Soma nos pede para fazer. Mais especificamente, esse problema nos pede que, dada uma lista de N inteiros, encontre a soma de todos eles.

Fácil não, um simples for resolve...



Vamos brincar um pouco mais?  Será que é possível resolver esse problema se a tecla + do seu computador estivesse estragada? Certamente que sim, e é o que eu vou mostrar agora.

Modelagem


O segredo para resolver esse problema é lembrar que soma e subtração podem ser feitas usando se operações lógicas. Vamos dividir o nosso problema de somar em dois problemas:
  1. Somar sem considerar o vai 1
  2. Calcular e somar o vai 1
Vamos tentar somar dois números de 1 bit sem considerar o vai 1. Sejam a e b esses números:

a     b     a+b sem vai 1
1     1              0
1     0              1
0     1              1
0     0              0

É possível perceber que o resultado a+b é igual a 1 quando ou exclusivamente a ou ou exclusivamente b forem 1. Assim a soma sem se considerar o vai 1 pode ser feita como a xor b.

Calcular o vai 1 pode ser feito da mesma forma:

a     b     vai 1
1     1       1
1     0       0
0     1       0
0     0       0

Ou seja o vai 1 pode ser representado como a and b.

Pronto agora é só somar o a+b sem vai 1 com o vai 1. Opa, mas voltamos ao mesmo problema de antes. Para contornar esse empecilho, podemos usar recursão, como feito no pseudocódigo abaixo.

soma_recursivo(a, b)
    if (b == 0) return a //condição de parada
    somaSemVai1 = a xor b
    vai1 = a and b
    vai1 = vai1<<1 //o vai 1 sempre deve ser somado ao próximo bit
    return soma_recursivo(somaSemVai1, vai1)

Implementação




Nenhum comentário:

Postar um comentário