Ordenação de números

Secção dedicada à linguagem de programação favorita dos quarkianos: Python!

Ordenação de números

Mensagempor Bruno Oliveira em Sexta Jan 08, 2010 1:10 pm

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
e^{ix}=cos x + i\,sin x
Avatar do utilizador
Bruno Oliveira
top-Quark!
top-Quark!
 
Mensagens: 1553
Registado: Quarta Nov 14, 2007 10:19 pm
Localização: Lisboa

Re: Ordenação de números

Mensagempor joao_moreira em Sexta Jan 08, 2010 8:37 pm

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:
João Moreira

Quark! 2009/2010
OIbF 2010, Panamá
Caloiro ET - D.E.T. - U.A.
Avatar do utilizador
joao_moreira
bottom-Quark!
bottom-Quark!
 
Mensagens: 74
Registado: Quarta Dez 09, 2009 10:48 pm
Localização: Aveiro

Re: Ordenação de números

Mensagempor jap em Sexta Jan 08, 2010 9:50 pm

:lol:

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

Desafio! :mock:
José António Paixão
Departamento de Física da FCTUC
Avatar do utilizador
jap
Site Admin
Site Admin
 
Mensagens: 6790
Registado: Quinta Nov 09, 2006 9:34 pm
Localização: Univ. de Coimbra

Re: Ordenação de números

Mensagempor Bruno Oliveira em Sexta Jan 08, 2010 11:57 pm

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!!
e^{ix}=cos x + i\,sin x
Avatar do utilizador
Bruno Oliveira
top-Quark!
top-Quark!
 
Mensagens: 1553
Registado: Quarta Nov 14, 2007 10:19 pm
Localização: Lisboa

Re: Ordenação de números

Mensagempor jap em Sábado Jan 09, 2010 12:09 am

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:
José António Paixão
Departamento de Física da FCTUC
Avatar do utilizador
jap
Site Admin
Site Admin
 
Mensagens: 6790
Registado: Quinta Nov 09, 2006 9:34 pm
Localização: Univ. de Coimbra

Re: Ordenação de números

Mensagempor Tharis em Sábado Jan 09, 2010 12:15 am

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
Avatar do utilizador
Tharis
up-Quark!
up-Quark!
 
Mensagens: 387
Registado: Quinta Out 23, 2008 4:26 pm

Re: Ordenação de números

Mensagempor Bruno Oliveira em Sábado Jan 09, 2010 12:17 am

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:
e^{ix}=cos x + i\,sin x
Avatar do utilizador
Bruno Oliveira
top-Quark!
top-Quark!
 
Mensagens: 1553
Registado: Quarta Nov 14, 2007 10:19 pm
Localização: Lisboa

Re: Ordenação de números

Mensagempor jap em Sábado Jan 09, 2010 12:31 am

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:
José António Paixão
Departamento de Física da FCTUC
Avatar do utilizador
jap
Site Admin
Site Admin
 
Mensagens: 6790
Registado: Quinta Nov 09, 2006 9:34 pm
Localização: Univ. de Coimbra

Re: Ordenação de números

Mensagempor Bruno Oliveira em Domingo Jan 10, 2010 11:41 am

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


:)
última vez editado por Bruno Oliveira s Domingo Jan 10, 2010 3:56 pm, editado 2 vezes no total
e^{ix}=cos x + i\,sin x
Avatar do utilizador
Bruno Oliveira
top-Quark!
top-Quark!
 
Mensagens: 1553
Registado: Quarta Nov 14, 2007 10:19 pm
Localização: Lisboa

Re: Ordenação de números

Mensagempor Tharis em Domingo Jan 10, 2010 2:04 pm

O algoritmo que descreveste é o Bubble Sort.

No entanto, o código que apresentaste está errado. Vê lá o que tens mal. ;)
Avatar do utilizador
Tharis
up-Quark!
up-Quark!
 
Mensagens: 387
Registado: Quinta Out 23, 2008 4:26 pm

Re: Ordenação de números

Mensagempor Bruno Oliveira em Domingo Jan 10, 2010 3:56 pm

Corrigido :P
e^{ix}=cos x + i\,sin x
Avatar do utilizador
Bruno Oliveira
top-Quark!
top-Quark!
 
Mensagens: 1553
Registado: Quarta Nov 14, 2007 10:19 pm
Localização: Lisboa

Re: Ordenação de números

Mensagempor Francisco_Lopes em Segunda Jan 18, 2010 10:11 pm

E para um newbie que não sabe mesmo nada de programação, por onde começa? :D
Avatar do utilizador
Francisco_Lopes
bottom-Quark!
bottom-Quark!
 
Mensagens: 75
Registado: Domingo Jun 07, 2009 7:23 pm
Localização: Instituto Superior Técnico, Lisboa

Re: Ordenação de números

Mensagempor Bruno Oliveira em Segunda Jan 18, 2010 11:15 pm

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
e^{ix}=cos x + i\,sin x
Avatar do utilizador
Bruno Oliveira
top-Quark!
top-Quark!
 
Mensagens: 1553
Registado: Quarta Nov 14, 2007 10:19 pm
Localização: Lisboa

Re: Ordenação de números

Mensagempor Tharis em Terça Jan 19, 2010 6:26 pm

@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
Avatar do utilizador
Tharis
up-Quark!
up-Quark!
 
Mensagens: 387
Registado: Quinta Out 23, 2008 4:26 pm

Re: Ordenação de números

Mensagempor RicardoCampos em Domingo Fev 07, 2010 3:35 pm

Eu recomendo www.projecteuler.net/ com um tutorial de suporte.
\emph{Ricardo Campos}\in \delta \bigcap q\overline{q}
O Matemático-Físico de 2008
Avatar do utilizador
RicardoCampos
top-Quark!
top-Quark!
 
Mensagens: 1280
Registado: Sexta Jun 01, 2007 3:49 pm
Localização: Figueira da Foz/Coimbra/DMUC/DFUC, Paris... E agora Zurique!


Voltar para Pitónica

Quem está ligado

Utilizadores a navegar neste fórum: Nenhum utilizador registado e 1 visitante