dúvida - lab4 !!!!

[eduarda-nicoletto]

Olá, pessoal

Estou aguardando a monitoria das 16h, porém, se alguém puder me ajudar antes, agradeço muito pois quero terminar o lab4 o quanto antes!

Eu entendi o que deve ser feito e tenho uma noção de como fazer usando pilha. Mas essa noção de como fazer não está sendo suficiente para avançar. Acredito que estou tendo um erro de lógica e não no código em si. Alguém poderia desenvolver o passo a passo de como resolvo esse lab? Estou a mais de dois dias fazendo apenas isso e não consigo avançar, e sinceramente, a esse ponto estou desesperada pois a entrega é hoje.

[luizsimioni]

Estou com o mesmo problema. Ontem na monitoria o PED me explicou um algoritimo que funciona, mais não sei se consegui entender, vou explicar aqui oque eu entendi, mais acho que esta errado pois meu código não ta funcionando para alguns casos. Pega uma lista vazia e compara o primeiro elemento dela com o primeiro elemento da listadedados, (pode ser pilha, tanto faz), se o elemento da lista vazia é maior que o da listadedados você o substitui pelo da listadedados, caso não seja maior vc adiciona o elemento da listadedados no proximo indice da lista vazia. Quando vc faz a substituição vc retira 1 do n que vc pegou pelo scanf. Vai fazendo isso até a lista acabar ou n=0. Caso você terminou a lista e n não for igual a zero vc pega a lista vazia e faz o mesmo procedimento mais comparando o ultimo elemento com o penultimo assim sucessivamente. Não sei se está certo.

[iagoac]

Um método simples é você explorar todas as permutações com k dígitos do número recebido na entrada. Você pode utilizar uma pilha para saber o dígito que já foi considerado ou não foi considerado nestas permutações (se está na pilha é porquê já foi considerado).
Você pode trabalhar com a pilha como se ela fosse uma estrutura de backtraking.

O objetivo é inspecionar todas as possíveis permutações e salvar a menor delas.

[iagoac]

Existem diversos exemplos de como se fazer isto na Internet.
Aqui vocês podem conferir um código em Python que realiza tal tarefa. Entretanto, ele considera que N = k, sendo que neste lab, N > k.

[luizsimioni]

O senhor consegue me dizer se eu entendi corretamente o algoritimo que o o PED me explicou que eu descrevi acima? eu já implementei o código e da erro em alguns testes.

[iagoac]

@LuizluHenrique está difícil dizer, pois sua explicação está falha.

Pega uma lista vazia e compara o primeiro elemento dela com o primeiro elemento da lista de dados.

Se a lista é vazia, como podemos comparar o primeiro elemento dela?
Lista de dados???

Quando vc faz a substituição vc retira 1 do n que vc pegou pelo scanf. Vai fazendo isso até a lista acabar ou n=0

Isto aqui realmente me parece estar certo.

Caso você terminou a lista e n não for igual a zero vc pega a lista vazia e faz o mesmo procedimento mais comparando o ultimo elemento com o penultimo assim sucessivamente.

Isto aqui também me parece estar certo. Você vai acabar fazendo uma comparação de todos contra todos. A complexidade e o tempo gasto serão superiores ao método que eu descrevi pouco acima, mas acredito que funcione.

[eduarda-nicoletto]

Acho que entendi. Meu raciocínio está correto: Crio duas listas, uma com os dados de entrada e outra que tem a quantidade de posições da saída. Pego a lista de saída e para cada posição vou fixando um número da entrada que esteja entre a posição do número anterior e fim da lista de entrada. Assim, crio todas as permutações e vou sempre salvando a menor. Faz sentido?

[iagoac]

Faz sentido. E, caso você substitua suas estruturas por pilhas, a implementação fica mais simples.

[eduarda-nicoletto]

Você diz a lista de saída, a de entrada ou as duas?

[iagoac]

As duas

[eduarda-nicoletto]

Verdade! Muito muito obrigada, vou tentar!

[eduarda-nicoletto]

Professor, fui na monitoria e acabei optando por seguir a lógica do PED, que simplifica o algoritmo. De qualquer forma, consegui!! Muito obrigada!