Página 1 de 3

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

MensagemEnviado: Terça Jan 17, 2012 2:02 pm
por Bruno Oliveira
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.

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

MensagemEnviado: Terça Jan 17, 2012 3:31 pm
por filipematos
Mas para um vector com esse número de coordenadas e sub vector com 4 coordenadas ou com as que forem?

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

MensagemEnviado: Terça Jan 17, 2012 3:39 pm
por Bruno Oliveira
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.

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

MensagemEnviado: Terça Jan 17, 2012 4:22 pm
por filipematos
Foi o que eu pensei :) Muito em, vou trabalhar nisso!!! Postarei aqui o código quando o conseguir :)

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

MensagemEnviado: Terça Jan 17, 2012 4:29 pm
por Bruno Oliveira
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!!

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

MensagemEnviado: Terça Jan 17, 2012 4:31 pm
por filipematos
Excelente ideia :) É só as pessoas começarem a aparecer para se puder discutir :)

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

MensagemEnviado: Terça Jan 17, 2012 4:35 pm
por Bruno Oliveira
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:

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

MensagemEnviado: Terça Jan 17, 2012 11:23 pm
por Tharis
@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. ;)

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

MensagemEnviado: Quarta Jan 18, 2012 12:45 am
por Bruno Oliveira
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:

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

MensagemEnviado: Quarta Jan 18, 2012 5:33 pm
por jap
Thks! :hands:

Bom desafio!
BTW, dentro em breve iremos (re)animar a secção Pitónica, com algumas novidades. Stay tuned!

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

MensagemEnviado: Quarta Jan 18, 2012 5:47 pm
por Bruno Oliveira
Excelente!!! :D

Entretanto, uns desafios deste género são sempre interessantes! :D

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

MensagemEnviado: Sexta Fev 10, 2012 11:09 pm
por ruifm
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

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

MensagemEnviado: Domingo Fev 12, 2012 8:50 pm
por Bruno Oliveira
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:

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

MensagemEnviado: Domingo Fev 12, 2012 9:24 pm
por ruifm
Temos de sequenciar todas as somas possiveis e achar a maxima?

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

MensagemEnviado: Domingo Fev 12, 2012 9:37 pm
por Bruno Oliveira
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: