Letra B) 8 movimentos.
O estado inicial da pilha é:
q2 v5
q4 v4
q1 v3
q3 v2
q5 v1
A ordem que ele deseja no final da pilha é a seguinte:
q1 v5
q2 v4
q3 v3
q4 v2
q5 v1
Concorda que o q5 já está na posição ideal? Então ele não precisa ser alterado.Só com isso, já não precisaremos retirar toda a pilha e colocar novamente, pois teríamos 10 movimentos caso ocorresse este fluxo.Com o movimento apenas dos 4 elementos da pilha, retirando os mesmos e colocando os ímpares na pilha P2 e os pares na pilha P3, teremos a seguinte situação:
q5 v1 (p1)
q4, q2(p2)
q3, q1(p3)
Logo, retornando alternando pilha p2 e p3 sucessivamente ordenaremos a pilha final p1, de modo que atenda ao exercício e com apenas 8 movimentos.
q1 v5
q2 v4
q3 v3
q4 v2
q5 v1
A questão fala que tem uma pilha P1 com posições V1 a V5 e está preenchida respectivamente Q5, Q3, Q1, Q4, Q2 e têm duas pilas vazias P2 e P3
No resultado pede de v(5) a v(1) nas ordens os símbolos Q1, Q2, Q3, Q4, Q5, então Q1 deverá estar no TOPO, na posição v(5).
Inicialmente as pilas ficam assim
Pilha P1 P2 P3
V5 - Q2 V5 - V5 -
V4 - Q4 V5 - V4 -
V3 - Q1 V5 - V3 -
V2 - Q3 V5 - V2 -
V1 - Q5 V5 - V1 -
1ª movimentação tiramos Q2 da posição V5 da pilha P1 e e inserimos no topo da pilha P2 posição V5
Pilha P1 P2 P3
V5 - V1 - V5 -
V4 - Q4 V4 - V4 -
V3 - Q1 V3 - V3 -
V2 - Q3 V2 - V2 -
V1 - Q5 V5 - Q2 V1 -
2ª movimentação tiramos Q4 da posição V4 da pilha P1 e inserimos no topo da pilha P2
Pilha P1 P2 P3
V5 - V5 - V5 -
V4 - V4 - V4 -
V3 - Q1 V3 - V3 -
V2 - Q3 V2 - Q4 V2 -
V1 - Q5 V1 - Q2 V1 -
3ª movimentação tiramos Q1 da posição V3 da pilha P1 e inserimos no topo da pilha P3
Pilha P1 P2 P3
V5 - V5 - V5 -
V4 - V5 - V4 -
V3 - V5 - V3 -
V2 - Q3 V5 - Q4 V2 -
V1 - Q5 V5 - Q2 V1 - Q1
4ª movimentação tiramos Q3 da posição V2 da pilha P1 e inserimos no topo da pilha P3
Pilha P1 P2 P3
V5 - V5 - V5 -
V4 - V4 - V4 -
V3 - V3 - V3 -
V2 - V2 - Q4 V2 - Q3
V1 - Q5 V1 - Q2 V1 - Q1
5ª movimentação tiramos Q4 da posição V2 da P2 e inserimos no topo da pilha P1
Pilha P1 P2 P3
V5 - V5 - V5 -
V4 - V4 - V4 -
V3 - V3 - V3 -
V2 - Q4 V2 - V2 - Q3
V1 - Q5 V1 - Q2 V1 - Q1
6ª movimentação tiramos Q3 da posição V2 da pilha P3 e inserimos no topo da pilha P1
Pilha P1 P2 P3
V5 - V5 - V5 -
V4 - V4 - V4 -
V3 - Q3 V3 - V3 -
V2 - Q4 V2 - V2 -
V1 - Q5 V1 - Q2 V1 - Q1
7º movimentação tiramos Q2 da posição V1 da pilha P2 e inserimos no topo da pilha P1
Pilha P1 P2 P3
V5 - V5 - V5 -
V4 - Q2 V4 - V4 -
V3 - Q3 V3 - V3 -
V2 - Q4 V2 - V2 -
V1 - Q5 V1 - V1 - Q1
8ª movimentação tiramos Q1 da posição V1 da pilha P3 e inserimos no topo da na pilha P1
Pilha P1 P2 P3
V5 - Q1 V5 - V5 -
V4 - Q2 V4 - V4 -
V3 - Q3 V3 - V3 -
V2 - Q4 V2 - V2 -
V1 - Q5 V1 - V1 -