Descreva um algoritmo que use apenas proposições que substitua o trio
em
. Qual é o menor número de proposições necessárias?
Passo 1
O enunciado pede um algoritmo que, usando apenas atribuições (proposições do tipo “variável := expressão”), transforme o triplo
em
. Esse é um problema de rotação cíclica de três variáveis e vamos precisar entender quantas atribuições mínimas são necessárias.
Passo 2
Uma solução clássica usa uma variável auxiliar
. A ideia é:
Aqui fazemos quatro atribuições e ao final obtemos exatamente
.
Passo 3
Para ver que não dá para usar menos de quatro atribuições, note que:
- Na primeira atribuição você precisa guardar algum valor original antes que ele seja perdido por uma sobreposição.
- Após salvar esse valor, ainda restam três deslocamentos (colocar
em , em e o valor salvo em ). - Cada um desses deslocamentos exige uma atribuição distinta, e não há como combinar duas delas numa só sem usar atribuições simultâneas ou expressões que leiam e escrevam várias variáveis de uma vez.
Logo, precisamos de 1 atribuição para salvar e 3 para redistribuir, totalizando pelo menos 4.
Resposta
O menor número de proposições necessárias é 4. Por exemplo: