Pancake Sort 1

Páginas: 4 (786 palavras) Publicado: 6 de junho de 2015
Pancake Sort

Caio César Ponte Silva
Jonathan Nascimento Madeira

História
 No ano de 1975 ,o matemático Jacob E Goodman
estava em casa dobrando toalhas para ajudar sua
esposa. A pilha final ficouum pouco
desorganizada, então ele decidiu reempilhar as
toalhas dobradas por ordem de tamanho , a
menor toalha dobrada ficaria no topo e a maior
no fim da pilha , de modo que ele foi forçado a
viraralgumas toalhas , avaliar a situação , em
seguida , virar mais uma vez algumas outras
toalhas , e assim por diante.
 Durante a tentativa de organizar a pilha de
toalhas, um problema curioso cruzou suamente :
“Quantos flips (viradas) precisaria, no pior caso,
para organizar as toalhas?”, então Goodman
enviou o problema para o American

Definição do Problema
 O Problema da Ordenação de Panquecastem como
objetivo organizar uma pilha desordenada de panquecas
em ordem de tamanho, dadas panquecas de diâmetros
diferentes;
 Ou seja, temos que organizar uma pilha de panquecas de
tamanhos variadosde forma que a menor fique no topo da
pilha, a segunda menor fique logo abaixo dela, e assim
sucessivamente até que a maior fique na parte inferior;
 Para isso, uma espátula pode ser inserida emqualquer
lugar da pilha e usada para virar todas as panquecas
acima dela;
 Virada ou flip consiste em inserir a espátula entre duas
panquecas e então “virar” (inverter) as panquecas da

 Ao contráriode algoritmos de ordenação tradicional,
que tenta resolver com o menor número de
comparações possíveis, o objetivo desse algoritmo é
ordenar a sequência em poucas viradas possível.

A figura mostra aespátula se posicionando
entre duas panquecas e fazendo um flip.

emplificação da quantidade de flips no Pancake S

0 FLIP

1 FLIP

2 FLIPS

3 FLIPS

figura mostra os 6 arranjos possíveis para umapilha de 3 panquec
a 3 panquecas o número máximo de flips são 3.

A tabela seguinte mostra o número de panquecas n
por pilha e o número de flips que necessitam:

Algoritmo
Pancake-Sort(s)
Para i ←...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • sort
  • sort
  • Merge Sort, Quick Sort e Heap Sort
  • Quick sort e shell sort
  • Heap Sort
  • selection sort
  • Radix sort
  • count sort

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!