Clássico: Encontrar o maior subvector cuja soma é maxima

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

Clássico: Encontrar o maior subvector cuja soma é maxima

Mensagempor Bruno Oliveira em Terça Jan 17, 2012 2:02 pm

Considere-se um dado vector:

[−2, 1, −3, 4, −1, 2, 1, −5, 4]

Vemos que o subvector que tem a maior soma é:
[4, -1, 2, 1]

cuja soma é 6.

A vossa tarefa é escrever um programa em python que permita calcular a máxima soma existente num dado vector.

Boa programação,
Bruno

PS: Este problema vai servir para introduzir um paradigma de programação que tem vindo a tornar-se mais normalizado devido à sua frequente aparição em concursos de algoritmia, mas que é bastante complexo, e que é o de Programação Dinâmica.
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: Clássico: Encontrar o maior subvector cuja soma é maxima

Mensagempor filipematos em Terça Jan 17, 2012 3:31 pm

Mas para um vector com esse número de coordenadas e sub vector com 4 coordenadas ou com as que forem?
"If I have seen further than others, it is by standing upon the shoulders of giants" - Isaac Newton

“We build too many walls and not enough bridges.” - Isaac Newton
filipematos
down-Quark!
down-Quark!
 
Mensagens: 280
Registado: Sábado Jun 25, 2011 4:48 pm
Localização: Lisboa

Re: Clássico: Encontrar o maior subvector cuja soma é maxima

Mensagempor Bruno Oliveira em Terça Jan 17, 2012 3:39 pm

Obviamente, quero a solução do problema mais geral, em que o vector onde se vai procurar a solução tem n coordenadas e o sub-vector terá k coordenadas.

Dada uma sequência de n números [v_1, v_2, \cdots, v_n], quero saber qual a sub-sequência de k números dessa sequência cuja soma é máxima.
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: Clássico: Encontrar o maior subvector cuja soma é maxima

Mensagempor filipematos em Terça Jan 17, 2012 4:22 pm

Foi o que eu pensei :) Muito em, vou trabalhar nisso!!! Postarei aqui o código quando o conseguir :)
"If I have seen further than others, it is by standing upon the shoulders of giants" - Isaac Newton

“We build too many walls and not enough bridges.” - Isaac Newton
filipematos
down-Quark!
down-Quark!
 
Mensagens: 280
Registado: Sábado Jun 25, 2011 4:48 pm
Localização: Lisboa

Re: Clássico: Encontrar o maior subvector cuja soma é maxima

Mensagempor Bruno Oliveira em Terça Jan 17, 2012 4:29 pm

Seria interessante que não o postasses logo, pois, este problema foi aqui postado por mim com dois própositos:

1. Trazer mais gente para o Python :inocent:

2. Introduzir o conceito de Programação Dinâmica que eu próprio também estou a aprender

Reparei que a Adriana também veio ler o tópico. :)

Seria interessante e muito mais útil para todos (eu incluído) que discutissem aqui entre vocês algumas formas de abordar este problema (não necessariamente por programação dinâmica) e que descobrissem alguns aspectos interessantes sobre ele. O papel e o lápis são sempre os vossos melhores aliados nestes casos ;)

Discutam todas as formas possíveis de resolver a questão, conjecturem sobre a validade e eficiência das mesmas, e no fim, irão aprender uma técnica de design de algoritmos espectacular!! :)

Bom brainstorming!!
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: Clássico: Encontrar o maior subvector cuja soma é maxima

Mensagempor filipematos em Terça Jan 17, 2012 4:31 pm

Excelente ideia :) É só as pessoas começarem a aparecer para se puder discutir :)
"If I have seen further than others, it is by standing upon the shoulders of giants" - Isaac Newton

“We build too many walls and not enough bridges.” - Isaac Newton
filipematos
down-Quark!
down-Quark!
 
Mensagens: 280
Registado: Sábado Jun 25, 2011 4:48 pm
Localização: Lisboa

Re: Clássico: Encontrar o maior subvector cuja soma é maxima

Mensagempor Bruno Oliveira em Terça Jan 17, 2012 4:35 pm

Exacto :)

Eu posso estar aqui para ajudar, se mais ninguém aparecer... :wink:

Mas gostaria que mais gente se envolvesse... aprender sozinho um assunto tão interessante como programação devia ser considerado crime!!! :P

PS: Obrigado Quark! por existires e me dares liberdade de expressão "geek" :lol:
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: Clássico: Encontrar o maior subvector cuja soma é maxima

Mensagempor Tharis em Terça Jan 17, 2012 11:23 pm

@Bruno Oliveira, não vejo razão para que cada um coloque aqui a sua solução. Se o problema é outros poderem ver e ficarem influenciados, existe a tag spoiler para isso. Quem quiser meter o código sob spoiler, coloque o código, seleccione-o e depois clique no botão spoiler (ao pé do bold, italic, ...).

Btw, bom problema para começar DP. ;)
Avatar do utilizador
Tharis
up-Quark!
up-Quark!
 
Mensagens: 387
Registado: Quinta Out 23, 2008 4:26 pm

Re: Clássico: Encontrar o maior subvector cuja soma é maxima

Mensagempor Bruno Oliveira em Quarta Jan 18, 2012 12:45 am

Eu disse isso mais por experiência própria visto que eu vou logo abrir o spoiler :mrgreen:

Mas sim, creio que o problema é interessante para introduzir DP :) No entanto, e ainda para mim, partir deste problema para outros mais "mascarados" (no sentido de mais floreados, como os de competições de algoritmia) ainda é algo que não domino... :evil:
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: Clássico: Encontrar o maior subvector cuja soma é maxima

Mensagempor jap em Quarta Jan 18, 2012 5:33 pm

Thks! :hands:

Bom desafio!
BTW, dentro em breve iremos (re)animar a secção Pitónica, com algumas novidades. Stay tuned!
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: Clássico: Encontrar o maior subvector cuja soma é maxima

Mensagempor Bruno Oliveira em Quarta Jan 18, 2012 5:47 pm

Excelente!!! :D

Entretanto, uns desafios deste género são sempre interessantes! :D
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: Clássico: Encontrar o maior subvector cuja soma é maxima

Mensagempor ruifm em Sexta Fev 10, 2012 11:09 pm

Bruno Oliveira Escreveu:Obviamente, quero a solução do problema mais geral, em que o vector onde se vai procurar a solução tem n coordenadas e o sub-vector terá k coordenadas.

Dada uma sequência de n números [v_1, v_2, \cdots, v_n], quero saber qual a sub-sequência de k números dessa sequência cuja soma é máxima.


eu não percebi bem o objectivo. É para generalizar o problema?
É para criar uma função a que dados todos os valores do vector, e dado o valor de k ( nº de coordenadas para o subvector), essa função retorna o subvector cuja soma é máxima?
isso até parece simples :XD
"Everything is determined, the beginning as well as the end, by forces over which we have no control." - Albert Einstein
Avatar do utilizador
ruifm
down-Quark!
down-Quark!
 
Mensagens: 205
Registado: Segunda Jan 16, 2012 12:04 am
Localização: Lisboa - IST

Re: Clássico: Encontrar o maior subvector cuja soma é maxima

Mensagempor Bruno Oliveira em Domingo Fev 12, 2012 8:50 pm

Rui, não é assim tão simples não! :lol:

A tua função deve receber apenas um vector como argumento e retornar um número como output, em que o número é a máxima soma de um (qualquer) nº de elementos contíguos do vector. Deu para perceber? :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: Clássico: Encontrar o maior subvector cuja soma é maxima

Mensagempor ruifm em Domingo Fev 12, 2012 9:24 pm

Temos de sequenciar todas as somas possiveis e achar a maxima?
"Everything is determined, the beginning as well as the end, by forces over which we have no control." - Albert Einstein
Avatar do utilizador
ruifm
down-Quark!
down-Quark!
 
Mensagens: 205
Registado: Segunda Jan 16, 2012 12:04 am
Localização: Lisboa - IST

Re: Clássico: Encontrar o maior subvector cuja soma é maxima

Mensagempor Bruno Oliveira em Domingo Fev 12, 2012 9:37 pm

Assim seria fácil... :P

Apesar dessa ser uma solução possível (é a solução chamada de força bruta ou brute force), gostaria que pensasses(m) numa forma mais directa e que não envolva sequenciar todas as somas possíveis :wink:
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

Próximo

Voltar para Pitónica

Quem está ligado

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

cron