Descreva um algoritmo que use apenas proposições que substitua o trio (x, y, z) em (y, z, x). 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 (x,y,z) em (y,z,x). 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 t. A ideia é:
t := x;\quad x := y;\quad y := z;\quad z := t.
Aqui fazemos quatro atribuições e ao final obtemos exatamente (x,y,z)=(y,z,x).

Passo 3

Para ver que não dá para usar menos de quatro atribuições, note que:
  1. Na primeira atribuição você precisa guardar algum valor original antes que ele seja perdido por uma sobreposição.
  2. Após salvar esse valor, ainda restam três deslocamentos (colocar y em x, z em y e o valor salvo em z).
  3. 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:
t := x;\quad x := y;\quad y := z;\quad z := t.

Exercícios de Livros Relacionados