Esta foi a mensagem dele:
Esta foi a mensagem dele:
Re: Tratamento de "becos sem saída" no EP1
"Você identificou uma questão crucial, mas escolheu uma solução (backtracking) que não é a melhor. Aqui é importante distinguir entre o caso geral do problema do troco e o caso particular que aparece no EP1.
No caso geral do problema do troco, nem a quantidade de tipos de moedas nem o valor de cada moeda são conhecidos de antemão. O programa deveria ler esses dados. Ele seria, portanto, suficientemente genérico para lidar com qualquer sistema monetário. Nessa formulação geral, o problema do troco é computacionalmente difícil. (De fato, é possível provar que esse problema é NP-difícil.) Note que uma solução para o problema do troco é um algoritmo com duas propriedades: (1) sempre que for houver troco, o algoritmo deve encontrá-lo, e (2) o troco encontrado deve usar o menor número possível de moedas. A técnica de "backtracking", aplicada ao problema geral do troco, produz uma solução parcial, que tem a propriedade (1) mas não a propriedade (2). Existe outra técnica, chamada "programação dinâmica", que produz uma solução com as duas propriedades.
No caso específico do EP1, entretanto, não é necessário usar nada disso! Como os valores das moedas são conhecidos de antemão (e são valores "razoáveis", no sentido de que eles têm só dois probleminhas), é possível explorar o conhecimento desses valores para criar um algoritmo simples que tem as propriedades (1) e (2). Esse algoritmo pode ser obtido modificando-se a solução "gulosa" (a que escolhe sempre a moeda de maior valor) de modo a contornar os tais dois probleminhas. E quais são os probleminhas? Bom, o que atrapalha a solução "gulosa" é a existência de algum par de cédulas ou moedas tais que nenhuma delas é múltipla da outra. Ou seja, os dois probleminhas são os pares (25, 10) e (500, 200). Note que o primeiro desses pares está na raiz do beco sem saída descrito em sua mensagem."
Re: Tratamento de "becos sem saída" no EP1
É claro que não espero que vocês saibam o que é "Prolog", "backtracking", "programação dinâmica", ou "NP-difícil". Vocês aprenderão essas coisas no devido tempo. (Não vai ser em MAC0110!) Da conversa acima, entretanto, deve ficar claro que a aplicação da estratégia gulosa ao problema do troco (escolher sempre a maior cédula ou moeda) só funciona bem para sistemas monetários nos quais os valores das cédulas/moedas maiores são sempre múltiplos dos das cédulas/moedas menores. Essa estratégia leva a "becos sem saída" quando aplicada cegamente a outros sistemas monetários, como por exemplo o do EP1. Deve também ficar clara uma sugestão para evitar "becos sem saída" no EP1: alterar um pouco a estratégia gulosa, para que em algumas situações bem específicas não seja escolhida a cédula/moeda de maior valor. Aqui o desafio é caracterizar precisamente que situações bem específicas são essas. (Dica: a modificação na estratégia gulosa deve ser pequena!)
Reverbel
as entradas saum:
105 centavos de saldo, 1 nota de 1, 1 moeda de 25, 8 moedas de 10.
205 centavos de saldo, 1 nota de 2, 1 nota de 1, 1 moeda de 50, 1 moeda de 25 e 3 moedas de 10.
e também há um problema ao se tentar usar 2 moedas de 25 por vez na entrada como no caso:
saldo de 55 centavos, 2 moedas de 25, 3 moedas de 10.
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAHHHHHHHHHHHHHHHHH!!!!!!!!!!
A cada vez que eu termino o EP, aparece aqui alguém dizendo que encontrou mais um enrosco a ser corrigido. Será que isso é algum tipo de pegadinha?! Continuação do trote, talvez?
A melhor parte dessa história toda é que o EP precisa ser entregue daquí a dois dias. (Não quero nem pensar no que vai aparecer nesse fórum quando faltar apenas uma hora para o encerramento do prazo de entrega...)
Professor, realmente espero que o senhor dê uma (boa) dica de como devemos resolver esses problemas, ou ao menos diga que na correção não irá usar entradas tão "malvadas" quanto as que foram aqui postadas.
Mais uma vez peço desculpas caso meu post tenha parecido ofensivo ou inapropriado, mas não pude deixar de manifestar minha perplexidade (com uma pontinha de desespero) perante à essa situação.
Abraços,
Vinícius
Logo agora q eu resolvo o problema dos pares (R$ 5,00 e R$ 2,00) aparece mais esse caso!!
Também peço desculpas se de alguma forma meu post ofendeu a alguém, foi somente um desabafo.. hehe
Abraços,
Toshi
Acho que esse reply não foi muito apropriado, mas foi um desabafo tbm hahaha xD
505 centavos de saldo, uma nota de 5, duas notas de 2, uma moeda de 50, uma moeda de 25 e três moedas de 10;
1005 centavos de saldo, uma nota de 10, uma nota de 5, duas notas de 2, uma moeda de 50, uma moeda de 25 e três moedas de 10.
Não é difícil alterar a "solução gulosa" para fazê-la funcionar corretamente também nesses casos. (Eu acabei de fazer isso com a minha solução, que estava entrando nesses becos sem saída.) O que é muito difícil é ter certeza que ninguém vai aparecer com outros casos de becos sem saída. É bem provável que existam outros!
Levando isso em conta, estou tomando as seguintes decisões sobre a correção do EP1:
(1) Uma parte pequena (no máximo 10%) da nota do EP1 dependerá do tratamento de "becos sem saída".
(2) Para efeito dessa parte da nota serão considerados apenas os casos de becos sem saída já identificados e já divulgados neste fórum.
(3) A identificação de casos adicionais de becos sem saída e o tratamento correto desses casos no EP1 é opcional. Quem não fizer isso não perderá nada em termos de nota. Quem fizer, ganhará um bônus na nota do EP1. O bônus valerá no máximo 1 ponto e servirá apenas para compensar algum outro ponto que tenha sido perdido por qualquer motivo (ou seja, o bônus não fará a nota passar de 10).
Quem achar outros casos de becos sem saída pode divulgar seus achados neste fórum, que o tratamento dos casos novos não vai ser exigido de ninguém!
Reverbel
Obrigado por responder e acredito que realmente essa seja a melhor solução para o problema que estamos enfrentando.
Abraços,
Vinícius.
nossa,,,,entao eh muito mais dificil arruma esse problema....
eu n sei c issu ajuda, mas tenho qse certeza que,, em TDOS ESSES casos que a "estrategia gulosa" n da certo, o troco remanescente(akele q deveria ser 0, mas n foi) fika, no final, igual ao valor de uma cedula(10, 5, 2, 1, 0.5, 0.25, 0.1, 0.05) que nao estah disponivel em caixa.
de qq forma que eu tente resolver o problema aki, sempre aparece umas excessoes,,
Isso ocorre naquela parte que a pessoa introduz 2 notas de 1 real e uma moeda de 50. Dae não é efetuada a venda por falta de troco, e qndo a pessoa pede o dinheiro de volta, o programa do enunciado devolve as 2 notas de 1 e a moeda, e o meu programa devolve uma nota de 2 e a moeda.
Acho que isso pode estar ocorrendo com seus programas tbm. Será que tem algum problema??
Até!
Me corrigi ae c eu tive errado, mas acho que o programa do enunciado tbm devolve 1xMoeda de 2 reais e 1xMoeda de 0.50 centavos.
Talvez vc esteja vendo uma versao antiga do enunciado: o professor alterou o pdf um pouco. Acho que quando o ep foi bolado inicialmente, se a pessoa nao comprasse nda, a maquina devolveria as mesmas cedulas que ela colocou(para que a maquina nao seja usada para trocar dinheiro :P ). Mas agora nao existe mais essa condiçao, entao nessa versao que to vendo agora do pdf, eh devolvido pro usuario 1xMoeda de 2 reais e 1xMoeda de 0.50 centavos.
Re: Tratamento de "becos sem saída" no EP1
Eu não tinha visto o pdf atualizado ^^
ehhee
Mas o caso mais interessante é o de 55 centavos. É diferente do caso que você apontou, pois aqui eu tenho uma moeda de 50, e no seu caso não tem. Se temos moedas de 50, 25 e 10 o primeiro beco sem saída seria usar a moeda de 50, e o segundo seria usar as duas de 25.
Testei o algoritmo recursivo que implementei com todos as situações problema levantadas por você, pelo professor e por mim, e funcionou sempre. Aguardo ansiosamente nossas discussões sobre a solução amanhã de manhã.
Boa sorte para todos!
Luciano
======= Estado inicial =======
caixa (total = 1205):
10,00 5,00 2,00 1,00 0,50 0,25 0,10 0,05
0 1 3 0 1 1 3 0
======= Trocar 30 =======
0 0 0 0 0 0 3 0
======= Trocar 55 =======
0 0 0 0 0 1 3 0
======= Trocar 80 =======
0 0 0 0 1 0 3 0
======= Trocar 680 =======
0 0 3 0 1 0 3 0
PS. Estive afastado da discussão pois fui ao FISL em Porto Alegre, onde por sinal encontrei o Rodrigo, nosso monitor.
esses "becos" serao testados? pq eu posso fazer dos dois primeiros e acaberem testando os outros...pq mesmo que tirem ponto pq nao fiz da do de 105 centavos 205 e 55 sempre vai ter algum gênio(...=)...) que vai descobrir outro problema, nao?? e o que garante que esse outro problema nao sera utilizado no teste dos programas????ate segunda alguem vai inventar outro aí alguns ...eu pelo menos.... vao ficar na duvida "sera que vao testar isso de verdade??"
pq nao adianta resolvermos um, dois, cinco...nao sei quem vai corrigir...mas a pergunta é para essa pessoa "quais 'problemas' voce vai testar???se alguem postar outro hj(sabado) ou domingo você vai testar este problema tb??? pq se for eu soh vou terminar mesmo segunda feira...."
esse post nao eh para ser levado no tom da ignorancia ou da impaciencia e nem da "to com preguica de fazer" mas eh que nao quero perder ponto a toa...
sem mais...=)...
Re: Tratamento de "becos sem saída" no EP1
Re: Tratamento de "becos sem saída" no EP1
Eu ainda não escrevi nada para o forum, mas cá estou para falar uma coisa.
FIco de fora só lendo o que o pessoal escreve e vendo o sofrimento de cada um que entrou a sério na ideia de fazer o Ep1. Infelizmente acho que se tornou neurotica a busca por erros. Não sei quanto a todos que me leem, mas eu aprendi muito fazendo o ep e agora me sinto bem em algo que me sentia inseguro. Pensem como vocês fizeram muita coisa e no tempo que gastaram. Calma a todos!
(acho que mandei uma mensagem só para o Igor...foi mal)
Re: Tratamento de "becos sem saída" no EP1
Re: Tratamento de "becos sem saída" no EP1
Como o professor já falou que os próximos "becos sem saída" contariam apenas como bônus, vou postar o que eu achei já que não vai prejudicar niguém ; ]
O método guloso também falha quado se tem:
troco: R$ 6,00
Caixa: 1 nota de R$ 5,00; 3 notas de R$ 2,00; 20 moedas de R$ 0,05.
O erro está no fato desse método entregar a nota de cinco reais e as vinte moedas de cinco centavos. Notem que qual quer outra combinação de moedas cuja soma seja igual ou maior a R$ 1,00 também resulta nesse erro.
Boa sorte, pessoal!
Abraços,
Vinícius
Re: Tratamento de "becos sem saída" no EP1
Agora que já acabou o tempo para entregar o EP
vou comentar isso ae hehehe...
esse meu if ficou com 32 linhas... porque eu tive que colocar todas as combinações de moedas que poderiam formar 1 real... :P
Re: Tratamento de "becos sem saída" no EP1
Outras situações só serão levadas em conta para efeito do bonus de 1 ponto, como eu disse nesta mensagem.