Programação Competitiva

O laço de repetição for é muitas vezes escrito de forma automática conforme a estrutura a seguir.

for (i = 0; i < n; i++) {
    //faz algo
}

Embora essa estruturação seja válida para muitos problemas, vale a pena avaliar se o valor inicial não pode ser maior, se a condição de parada pode ser diferente ou se o incremento também não pode ser maior. Essas questões podem economizar processamento.

Por exemplo, imagine um código para mostrar os números inteiros ímpares no intervalo entre zero e 10. O resultado da execução serão os valores: 1 3 5 7 9.

int main() {
    int i;

    for (i=0; i <= 10; i++) {
        if (i % 2 == 1) {
            printf("%d ", i);
        }
    }

    return 0;
}

O laço de repetição do código acima faz com que a variável i assuma cada um dos valores do intervalo entre zero e dez. Ou seja, a variável i irá assumir cada um dos 10 valores possíveis do intervalo e o laço de repetição irá executar seu bloco 10 vezes.

Veja que, embora o intervalo de valores seja entre zero e dez, o primeiro número ímpar é o número 1, enquanto o último número ímpar é o 9. Sendo assim, modificando o valor inicial e a condição de parada do código não alterarão o resultado do algoritmo e será possível diminuir o processamento. O código com a alteração é mostrado a seguir.

int main() {
    int i;

    for (i=1; i < 10; i++) {
        if (i % 2 == 1) {
            printf("%d ", i);
        }
    }

    return 0;
}

Com a modificação no valor inicial, o algoritmo irá começar a avaliação diretamente com o primeiro valor ímpar possível do intervalo (pulando o valor zero). Com a modificação na condição de parada, o algoritmo não irá continuar avaliando valores depois do último valor ímpar possível. Com isso, o laço de repetição reduziu a quantidade de vezes que o bloco executa para 8 vezes (eram 10 vezes anteriormente).

Veja também que os valores ímpares sempre ocorrem com incremento de dois e dois. Com isso, alterando o incremento da variável de controle do for, podemos ter mais uma diminuição do processamento. O código com a modificação no incremento é mostrado a seguir, fazendo a variável i ser incrementada de duas em duas unidades.

int main() {
    int i;

    for (i=1; i < 10; i=i+2) {
        if (i % 2 == 1) {
            printf("%d ", i);
        }
    }

    return 0;
}

Com essa modificação no código, a variável i assumirá os valores 1, 3, 5, 7 e 9 durante a execução do código (apenas e exatamente os valores que são ímpares no intervalo entre zero e dez). Com isso, a estrutura de repetição irá executar seu bloco apenas 5 vezes (metade do que era executado na primeira versão do código).

Outra melhoria que agora pode ser feita no código é dispensar o uso do desvio condicional, uma vez que todos os números que a variável i pode assumir sempre passarão no teste da estrutura if. O código final com essa modificação é mostrado a seguir.

int main() {
    int i;

    for (i=1; i < 10; i=i+2) {
        printf("%d ", i);
    }

    return 0;
}

Com a remoção do desvio condicional, 5 testes desnecessários deixaram de ser feito, uma vez que o teste sempre seria verdadeiro e o printf precisaria ser feito.

Veja como é importante pensar e repensar seu código a fim de otimizar sua execução. Na primeira versão do código o laço de repetição executa 10 vezes e faz 10 testes para mostrar os 5 valores possíveis do intervalo. Na última versão do código, o laço de repetição executa 5 vezes e nenhum teste é necessário para mostrar exatamente os mesmos 5 valores do intervalo.