Como detectar a ordem da pilha?

8

Tomamos a sequência de números inteiros de 1 para n, e os empurramos para uma pilha, um por um, em ordem. Entre cada push, podemos optar por exibir qualquer número de itens da pilha (de 0 ao tamanho atual da pilha).

Sempre que extrairmos um valor da pilha, imprimi-lo-emos.

Por exemplo, 1,2,3é impresso quando o fazemos push, pop, push, pop, push, pop.3,2,1vem de push, push, push, pop, pop, pop.

Contudo, 3,1,2 não é uma impressão possível, porque não é possível ter 3 impresso seguido por 1, sem ver 2 entre.

Pergunta: Como podemos detectar pedidos impossíveis como3,1,2?

De fato, com base em minha observação, saí em uma solução potencial. Mas o problema é que não posso provar que minha observação está completa.

O programa que escrevi com a seguinte lógica:

Quando o valor atual menos o próximo valor for maior que 1, um valor entre atual e o próximo não poderá aparecer após o próximo. Por exemplo, se current = 3 e next = 1, o valor entre current (3) e next (1) é 2 que não pode aparecer após next (1), portanto3,1,2 viola a regra.

Isso cobre todos os casos?

Eterno
fonte

Respostas:

6

Não consegui entender exatamente sua abordagem (parece correta), mas existe uma regra simples para pedidos impossíveis: o pedido é impossível Euff Há sim umaEu,umaj,umak de tal modo que umaEu>umak>umaj e Eu<j<k. Para talumaEu,umaj,umak dizemos triplo ruim.

Por quê? Primeiro, você deve provar que, se houver um triplo ruim, a sequência é impossível, mas isso é simples, e eu o deixarei como exercício (o número do meio não pode aparecer mais cedo que o maior, exceto que o menor aparece antes de todos).

Segundo, você deve provar que todas as ordens impossíveis têm pelo menos um triplo ruim. Suponha que você tenha uma sequência sem nenhum triplo ruim; você pode encontrar a ordem de empurrar e saltar para que não seja uma sequência impossível. Para reconstruir as ordens push e pop, use apenas uma abordagem ingênua (a operação é pop enquanto você itera sobre números consecutivos), mas, para uma prova formal (por simplicidade), você pode usar a indução, assumir por todas as seqüências de comprimentomse não houver triplo ruim, não serão impossíveis. Para sequência de comprimenton, você pode definir operações como pop (iniciar do final da sequência) e, ao encontrar números consecutivos crescentes, agora você tem uma sequência de comprimento mcom m<n, sem triplo ruim, para que você possa reconstruir o push e o pop nessa sequência, então a original não era impossível. O início da indução é a sequência de comprimento 3.


fonte