Troca de valor entre variáveis: mesmo exercícios simples possuem muitas formas diferentes de resolver

Escrevo para apresentar a soluções algorítmicas para um problema apresentam uma grande variação. Logicamente os problemas mais simples possuem menor quantidade possível de variação, mas trago aqui um exercício tradicional introdutório de programação para discutir essa questão.

Enunciado: elabore um algoritmo que, dado dois valores, troque o conteúdo de um pelo do outro.

Acredito que a primeira tentativa dos iniciantes com programação seja similar a que mostro a seguir. Nela, simplesmente é feita a atribuição de x em y e de y em x. Olhando o resultado é possível verificar que a solução não funciona (o resultado da execução mostra: x=5 e y=5). Isso porque, na atribuição feita na linha 5, o valor de x é perdido pois ele é sobrescrito com o valor de y.

#include <stdio.h>
int main() {
    int x=1, y=5;

    x = y; //x recebe 5
    y = x; //y recebe 5, pois x recebeu 5 antes

    printf("x=%i e y=%i", x, y);

    return 0;
}

A forma mais comum de resolver esse problema envolve definir uma variável auxiliar que armazena o valor de x antes dele ser sobrescrito e depois utiliza o valor armazenado dessa variável. O resultado dessa solução é mostrado no código a seguir.

#include <stdio.h>
int main() {
    int x=1, y=5, aux;

    aux = x; //aux recebe 1
    x = y;   //x recebe 5
    y = aux; //y recebe 1

    printf("x=%i e y=%i", x, y);

    return 0;
}

Uma melhoria, pelo menos considerando que ela economiza a variável temporária é mostrada a seguir.

#include <stdio.h>
int main() {
    int x=1, y=5;
 
    x = x + y; // x recebe 1+5 = 6
    y = x - y; // y recebe 6-5 = 1
    x = x - y; // x recebe 6-1 = 5
 
    printf("x=%i e y=%i", x, y);
 
    return 0;
}

Embora as duas soluções apresentas possuam a mesma complexidade de tempo (a complexidade delas é O(1)), a segunda solução não exige qualquer variável adicional para a troca.

As operações aritméticas utilizadas (soma e subtração) poderiam ser substituídas por multiplicação e divisão, conforme mostrado a seguir. Essa opção não altera a complexidade da solução, apenas aplica outros cálculos e mostra outra forma de aplicar o mesmo princípio.

    x = x * y; // x recebe 1*5 = 5
    y = x / y; // y recebe 5/5 = 1
    x = x / y; // x recebe 5/1 = 5

A solução utilizando multiplicação e divisão, embora tenha o mesmo desempenho da opção com soma e subtração, não recomendo a utilização. Veja que ela apresenta problema se o valor de y for zero (geraria uma divisão por zero, o que não é permitido). Sendo assim, é mais seguro utilizar a opção com soma e subtração.

Uma outra solução envolve o uso de um operador bitwise, no caso, o bitwise XOR (veja mais sobre os operadores bitwise em http://www.galirows.com.br/meublog/programacao/operadores-bitwise-cpp/). Com esse operador, o par de bits comparados precisa que apenas e exclusivamente um deles seja 1. No caso da primeira operação, somente o segundo bit (da esquerda para a direita) é exclusivo 1 e por isso o valor obtido no cálculo.

    //x: 0001 | y: 0101
    x = x ^ y; // x recebe 0001^0101 = 0100
    y = x ^ y; // y recebe 0100^0101 = 0001
    x = x ^ y; // x recebe 0100^0001 = 0101

Observe que essa sequência de cálculo é baseada nos bits e não deve ser observada sua correspondência com valores decimais. Por exemplo, o valor binário 0100 é o número 4 em decimal, o qual não faz muito sentido no cálculo.

Por fim, foram apresentadas algumas formas de resolver um mesmo problema, trazendo inclusive uma forma pouco usual, que é a utilização de operadores bitwise. Nunca se contente com apenas a primeira solução encontrada pois ela pode não ser a melhor delas (no caso, a primeira exigia o uso adicional de uma variável) e sempre pense bem o conjunto de testes que será utilizado para a valiar sua solução (no caso visto, a solução com a operação de divisão não pode ter o zero como denominador).

Share

Deixe um comentário

O seu endereço de e-mail não será publicado.

Esse site utiliza o Akismet para reduzir spam. Aprenda como seus dados de comentários são processados.