Página 1 de 1

Ordenação de números

MensagemEnviado: Sexta Jan 08, 2010 1:10 pm
por Bruno Oliveira
Mais um problema de treino pitónico! :lol: (depois de um exame de 2h30 de C++, sabe tão bem estar "livre" daquela cadeira e poder voltar ao Python! :P )

(Novamente, à semelhança do problema dos números trimórficos, este problema é para ser resolvido pelos newbies. Os pitonistas de serviço, como o Tharis, o Ivo, etc, poderão achá-lo desnecessário e até um pouco idiota, mas será certamente um óptimo desafio para os newbies)

Problema:

Desde o "nascimento" da computação, um dos problemas que causou (e, que, provavelmente ainda hoje causará) uma grande agitação entre os programadores/aficionados da programação, é um problema que tem um enunciado simples, e que, na prática, também tem uma solução simples (mas que não é uma das mais eficientes que por aí andam, obviamente.). Falo do problema de ordenação. O seu enunciado pode ser algo do género:

Dada uma lista de números inteiros fora de ordem, ordená-los por ordem crescente.

Desde miúdos que aprendemos a fazer isso na escola, mas verão que desenvolver um algoritmo, por mais simples que seja, para resolver computacionalmente este problema, não é assim tão simples. :roll:

Nota: o algoritmo que eu desenvolvi para este programa é muito simples e só funciona (em tempo "útil") para listas muito pequenas, com, no máximo, cerca de 5000 números... A ideia não é desenvolver um mergesort ou quicksort, que são populares, mas sim conseguir pensar numa maneira totalmente diferente e criar um algoritmo mais personalizado, para realizar a tarefa em mãos... Uma dica: usem listas!! :P

Re: Ordenação de números

MensagemEnviado: Sexta Jan 08, 2010 8:37 pm
por joao_moreira
Já consegui fazer um programa de 11 linhas... Não ponho aqui o código nem digo para já como fiz para deixar outros newbies a pensar. :D
Obrigado pelo exercício. :wink:

Re: Ordenação de números

MensagemEnviado: Sexta Jan 08, 2010 9:50 pm
por jap
:lol:

E já agora, a propósito: conseguem implementar o algoritmo Quicksort numa só linha pitónica?

Desafio! :mock:

Re: Ordenação de números

MensagemEnviado: Sexta Jan 08, 2010 11:57 pm
por Bruno Oliveira
Hmm... Numa só linha tenho de pensar... lá vêm as lambda functions ao barulho :lol:

Vou tentar arranjar um tempo no meio do meu estudo de Análise, para pensar sobre esse desafio :wink: . É desta que domino as lambda functions!!

Re: Ordenação de números

MensagemEnviado: Sábado Jan 09, 2010 12:09 am
por jap
Bruno Oliveira Escreveu:Hmm... Numa só linha tenho de pensar... lá vêm as lambda functions ao barulho :lol:

Vou tentar arranjar um tempo no meio do meu estudo de Análise, para pensar sobre esse desafio :wink: . É desta que domino as lambda functions!!


Não quero sentir-me culpado por prejudicar o teu estudo de Análise! :whistle:

Re: Ordenação de números

MensagemEnviado: Sábado Jan 09, 2010 12:15 am
por Tharis
jap Escreveu::lol:

E já agora, a propósito: conseguem implementar o algoritmo Quicksort numa só linha pitónica?

Desafio! :mock:


Código: Seleccionar Todos
qsort = lambda l: l if len(l) <= 1 else qsort([i for i in l[1:] if i < l[0]]) + [l[0]] + qsort([i for i in l[1:] if i >= l[0]])


;) Não resisti ao one line challenge! :D

Re: Ordenação de números

MensagemEnviado: Sábado Jan 09, 2010 12:17 am
por Bruno Oliveira
jap Escreveu:
Bruno Oliveira Escreveu:Hmm... Numa só linha tenho de pensar... lá vêm as lambda functions ao barulho :lol:

Vou tentar arranjar um tempo no meio do meu estudo de Análise, para pensar sobre esse desafio :wink: . É desta que domino as lambda functions!!


Não quero sentir-me culpado por prejudicar o teu estudo de Análise! :whistle:


Não tem problema prof. , para o Python e para o Quark há sempre um tempinho :wink: , de qualquer forma, o Tharis não resistiu :lol: , parece que as lambda functions vão ser adiadas novamente... :roll:

Re: Ordenação de números

MensagemEnviado: Sábado Jan 09, 2010 12:31 am
por jap
Tharis Escreveu:
jap Escreveu::lol:

E já agora, a propósito: conseguem implementar o algoritmo Quicksort numa só linha pitónica?

Desafio! :mock:


Código: Seleccionar Todos
qsort = lambda l: l if len(l) <= 1 else qsort([i for i in l[1:] if i < l[0]]) + [l[0]] + qsort([i for i in l[1:] if i >= l[0]])


;) Não resisti ao one line challenge! :D


Muito bem! :hands:

Re: Ordenação de números

MensagemEnviado: Domingo Jan 10, 2010 11:41 am
por Bruno Oliveira
Bem, e como o Tharis já fez o one-liner, posso deixar aqui o meu método original, que usa duas listas.

A ideia é ir à lista dada pelo utilizador, procurar o valor minimo que ela tem, e adicioná-lo a uma outra lista. Após o valor minimo estar na nova lista, remove-se o valor minimo da antiga, e assim sucessivamente, até o tamanho da lista original ser 0.

Achei bastante interessante, pois não é nada de muito elaborado, é fácil de perceber e de escrever e usando o psyco funciona com listas até 10 000 números. Cá está então, o muito simples, código que mete por ordem uma lista de números:

Código: Seleccionar Todos
"""

Program that receives an unsorted list as user input, and returns as output
the list sorted in ascending order.

Bruno @2010 Having fun with Python.

"""

L = input('Input an unsorted list of real numbers: ')
J = []
while len(L) > 0:
    J.append(min(L))
    L.remove(min(L))
if len(L)==0:
    print "The sorted list is: ", J


:)

Re: Ordenação de números

MensagemEnviado: Domingo Jan 10, 2010 2:04 pm
por Tharis
O algoritmo que descreveste é o Bubble Sort.

No entanto, o código que apresentaste está errado. Vê lá o que tens mal. ;)

Re: Ordenação de números

MensagemEnviado: Domingo Jan 10, 2010 3:56 pm
por Bruno Oliveira
Corrigido :P

Re: Ordenação de números

MensagemEnviado: Segunda Jan 18, 2010 10:11 pm
por Francisco_Lopes
E para um newbie que não sabe mesmo nada de programação, por onde começa? :D

Re: Ordenação de números

MensagemEnviado: Segunda Jan 18, 2010 11:15 pm
por Bruno Oliveira
Bem, estar a postar isto aqui fica um bocado off-topic... mas, no problem :wink: .

Se não souberes nada de programação e quiseres começar a aprender Python, tanto para te divertires por aqui, como para desenvolveres as tuas capacidades de raciocino algorítmico, diria que tens um problema complicado entre mãos...Porque o que não falta por aí são livros e tutoriais excelentes. :P

Recomendo muito vivamente, qualquer dos links disponibilizados pelo prof. jap, que são excelentes e creio que, constantemente actualizados por serem afinal de contas, a documentação oficial... E, se calhar, numa opinião mais pessoal, não posso deixar de te referir o livro intitulado "How to think like a computer scientist: Learning with Python" do Engº Civil empregado na Google, Allen B. Downey :D É um excelente livro e tem os fundamentos explicados de uma forma que ainda não encontrei em mais lado nenhum, creio que te tornarás um excelente programmer se te guiares por esse livro :wink:

Abraço

Re: Ordenação de números

MensagemEnviado: Terça Jan 19, 2010 6:26 pm
por Tharis
@Bruno Oliveira, tudo o que mencionaste está correcto e o que não falta são livros e tutoriais 5*, mas eu sou apologista do "learn and use".

Escrevendo a minha história com o Python em alguns caracteres: depois de decidir aprender Python, devorei uns bons livros de +-500 páginas e quando chegou a altura de fazer algo simples, não conseguia. Então, comecei a ler código de outros coders e a resolver desafios. Só posso dizer, valeu-me mais a segunda parte que ler todos os livros de Python do mundo. Claro que depois uma pessoa precisa sempre de uma referência particular a uma biblioteca ou paradigma, etc, mas para quem está a aprender, nada que um bom sistema de tutorial e desafio para isso.

@Francisco_Lopes, portanto, recomendo-te um projecto do DEI da UC (mais uma vez a UC está de Parabéns! :hands: ) que é o DEI Academy.


Cumprimentos
Tharis

Re: Ordenação de números

MensagemEnviado: Domingo Fev 07, 2010 3:35 pm
por RicardoCampos
Eu recomendo www.projecteuler.net/ com um tutorial de suporte.