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:
- Somar sem considerar o vai 1
- 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)
Nenhum comentário:
Postar um comentário