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

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

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

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

eu pensei numa, não sei se faz sentido e estou agora a tentar codifica-la:
1-procuramos um elemento maior que 0
2-adicionamos esse elemento à variavel 'soma'.
3-repetimos os passos 1 e 2, até chegarmos ao fim do vector.
4-output soma

o que achas? é mais directo que a força bruta...
última vez editado por ruifm s Domingo Fev 12, 2012 10:39 pm, editado 1 vez no total
"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 ruifm em Domingo Fev 12, 2012 10:03 pm

já está, e funciona. Acho que está bem.
"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 10:14 pm

É, sem dúvida, mais directo, porque só percorres o vector uma vez :)

Mas, infelizmente, não funciona :(

Ora repara no caso de exemplo que eu dei no ínicio deste tópico:

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

A maior soma de um subvector deste vector é dada por:

[4, −1, 2, 1]

que tem um número negativo, pelo que somar apenas os números maiores que 0 (positivos) não resolve da forma pedida o problema.

Uma dica: Utiliza duas variáveis:

Uma para manter o valor da soma até um dado elemento; outra que armazenará o resultado total, que será obviamente a maior de todas as somas parciais até um dado elemento!
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 Bruno Oliveira em Domingo Fev 12, 2012 10:16 pm

ruifm Escreveu:já está, e funciona. Acho que está bem.


Obrigado pelo teu código Rui, mas como disse acima, não está correcto, pois o que o teu código está a fazer é somar apenas os elementos positivos do vector, que não serão necessariamente contíguos, daí a dificuldade do problema :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

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

Mensagempor ruifm em Domingo Fev 12, 2012 10:30 pm

ahhhh teem de ser contiguos!
acho que isso simplifica as coisas. pera ai que ja faco um update ao codigo
"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 ruifm em Domingo Fev 12, 2012 10:39 pm

já está :D


EDIT: ahh reparei agora que uso a tal brute force...bem, acho que o meu PC não se importa :lol:
EDIT2: o nº de vezes que percorro o vector corresponde ao nº de elementos deste. não é muito... até fica eficiente
"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 Segunda Fev 13, 2012 9:55 am

ruifm Escreveu:EDIT2: o nº de vezes que percorro o vector corresponde ao nº de elementos deste. não é muito... até fica eficiente


Não necessariamente, pois imagina que o subvector cuja soma é máxima tem 10 componentes (por exemplo). Assim, estás a percorrer todos os subvectores com 1,2,3...,9 componentes em vão, pois o subvector com máxima soma tem 10 componentes.

Terás uma solução mais eficiente quando conseguires apanhar o subvector cuja soma é máxima percorrendo o vector apenas uma vez, e isso é possível fazer!! :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: Clássico: Encontrar o maior subvector cuja soma é maxima

Mensagempor ruifm em Segunda Fev 13, 2012 2:46 pm

Bruno Oliveira Escreveu:
ruifm Escreveu:EDIT2: o nº de vezes que percorro o vector corresponde ao nº de elementos deste. não é muito... até fica eficiente


Não necessariamente, pois imagina que o subvector cuja soma é máxima tem 10 componentes (por exemplo). Assim, estás a percorrer todos os subvectores com 1,2,3...,9 componentes em vão, pois o subvector com máxima soma tem 10 componentes.

Terás uma solução mais eficiente quando conseguires apanhar o subvector cuja soma é máxima percorrendo o vector apenas uma vez, e isso é possível fazer!! :P

o que estás a sugerir, é que há uma forma de descobrir o numero de componentes do subvector com a maior soma, antes de o percorrer? e é dessa forma que so procuramos somas com os subvectores com esse numero de elementos?
A minha solução pela brute force esta certa?
"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 Segunda Fev 13, 2012 6:55 pm

Não a corri, mas o teu programa não faz o que se pretende... :roll:

Vou dar-te um exemplo do que seria usar o brute force no vector de exemplo:

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

Subvectores com 2 componentes:

[-2,1]
[1,-3]
[-3,4]
[4,-1]
(...)
[-5,4]

Subvectores com 3 componentes:

[-2,1,-3]
[1,-3,4]
[-3,4,-1]
(...)
[1,-5,4]

etc para N componentes... Como vês existem demasiados subvectores a considerar usando o Brute force...

Uma maneira melhor será percorrer o vector uma só vez. Assim:

Primeira suposição para a max soma = 0

1: -2 (como é < 0, a max soma é 0, começamos a contagem na próxima componente, com max soma = 0)
2: 1 = 1 (como é > 0, a max soma é 1, será somada à prox componente)
3: 1+(-3) = -2 (como é <0, a max soma volta a ser 0, começamos a contagem na prox componente, com max soma = 0)
4: 4 = 4 (como é > 0, max soma é 4, será somada à prox componente)
5: 4-1 = 3 (como é > 0, max soma é 3, será somada à prox componente)
6: 3+2 = 5 (como é >0, somamos à prox componente)
7: 5+1 = 6 (...)
8: 6-5 = 1 (...)
9: 1+4 = 5 (FIM DO VECTOR)

Max subsoma encontrada = 6, é o resultado pretendido
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 Segunda Fev 13, 2012 11:19 pm

Bruno Oliveira Escreveu:Não a corri, mas o teu programa não faz o que se pretende... :roll:

Vou dar-te um exemplo do que seria usar o brute force no vector de exemplo:

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

Subvectores com 2 componentes:

[-2,1]
[1,-3]
[-3,4]
[4,-1]
(...)
[-5,4]

Subvectores com 3 componentes:

[-2,1,-3]
[1,-3,4]
[-3,4,-1]
(...)
[1,-5,4]

etc para N componentes... Como vês existem demasiados subvectores a considerar usando o Brute force...

Uma maneira melhor será percorrer o vector uma só vez. Assim:

Primeira suposição para a max soma = 0

1: -2 (como é < 0, a max soma é 0, começamos a contagem na próxima componente, com max soma = 0)
2: 1 = 1 (como é > 0, a max soma é 1, será somada à prox componente)
3: 1+(-3) = -2 (como é <0, a max soma volta a ser 0, começamos a contagem na prox componente, com max soma = 0)
4: 4 = 4 (como é > 0, max soma é 4, será somada à prox componente)
5: 4-1 = 3 (como é > 0, max soma é 3, será somada à prox componente)
6: 3+2 = 5 (como é >0, somamos à prox componente)
7: 5+1 = 6 (...)
8: 6-5 = 1 (...)
9: 1+4 = 5 (FIM DO VECTOR)

Max subsoma encontrada = 6, é o resultado pretendido

acho que o teu algoritmo tem uma falha:
se TODOS os elementos do vector forem negativos...
a max soma será sempre inferior a 0, e percorreras o vector sem considerar soma nenhuma, não chegando a um resultado. a tua suposição para max soma = 0 não permite generalizar para qualquer vector. De resto parece muito bom e eficaz :D
"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 Segunda Fev 13, 2012 11:24 pm

O caso em que não existem elementos positivos é, de facto, um caso que este algoritmo não cobre, mas, como é um caso particular, o resultado será o elemento do vector cujo valor absoluto for menor... Concordas? :wink:

De resto, este algoritmo destaca-se mesmo pela sua rapidez de execução e racíocino "à programação dinâmica".

Explicarei melhor o que quero dizer com a frase acima, quando tiver tempo, hopefully, até ao final da semana!! :wink:

Cumprimentos,
Bruno
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 Segunda Fev 13, 2012 11:51 pm

Bruno Oliveira Escreveu:O caso em que não existem elementos positivos é, de facto, um caso que este algoritmo não cobre, mas, como é um caso particular, o resultado será o elemento do vector cujo valor absoluto for menor... Concordas? :wink:

De resto, este algoritmo destaca-se mesmo pela sua rapidez de execução e racíocino "à programação dinâmica".

Explicarei melhor o que quero dizer com a frase acima, quando tiver tempo, hopefully, até ao final da semana!! :wink:

Cumprimentos,
Bruno

hmmm faz sentido.
também é facil. basta criar um if statement para esse caso, e aí a maxima soma é apenas o maior valor do vector!
Quando tiver tempo, passo o algoritmo para python para treinar
"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 Segunda Fev 13, 2012 11:59 pm

Bom, sugeri tomar o módulo e achar o menor valor, apenas porque calhou, no mystery there! Na realidade, podemos tomar os elementos todos negativos, tal como eles estão no vector e achar o maior deles (que será o que tem menor valor absoluto).
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 Bruno Oliveira em Terça Fev 14, 2012 9:57 am

Para um problema ser resolvido usando o conceito de Programação Dinâmica, é obrigatório que apresente duas características: overlapping subproblems e optimal substructure, que como veremos adiante são características que o nosso (muito) simples problema tem.

[*] Overlapping subproblems

A ideia da Programação Dinâmica consiste em resolver um problema, subdividindo-o em subproblemas mais simples, relacionados com o problema original. Quando estes problemas se sobrepõem, podemos utilizar Programação Dinâmica para resolver o problema original. Quando poder ser aplicado, este método é muito mais rápido do que outros metódos passíveis de serem utilizados para resolver o problema original.

Exemplo: A sequência de Fibonacci

A relação recursiva que rege a geração da sequência de Fibonacci, é do tipo:

F_n = F_{n-1} + F_{n-2} , com F_1 = 1 e F_2 = 1

Se implementares a relação recursiva acima, verás que para calculares F(40) já demorarás um tempo muito considerável (quando no PE te pedem qual o primeiro número de Fibonacci a exceder 1000 dígitos de comprimento, esta fórmula levaria anos a terminar...)

Isto acontece, pois se desenvolveres a relação recursiva verás que estás a recalcular imensos valores que já tens calculados, o que faz da relação acima uma relação muito ineficaz...

Quando um problema exibe uma estrutura semelhante (a necessidade de recalcular valores já calculados) diz-se que ele exibe a propriedade de overlapping subproblems. Veremos oportunamente uma maneira de contornar este problema...

[*] Optimal Substructure

Um problema diz-se que exibe optimal substructure, se a solução para o problema original, contém todas as soluções óptimas para os subproblemas. Esta propriedade percebe-se facilmente através do nosso exemplo do vector:

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

A solução para o problema original, tem no caso acima 4 componentes (assinaladas a bold).

Se olharmos com atenção, vemos que as 4 componentes, formam entre si, as soluções óptimas para subvectores com uma (4), duas (4-1) e três componentes (4-1+2) respectivamente.

Assim, o nosso problema apresenta de facto as duas características necessárias à aplicação de um algoritmo de programação dinâmica.

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 Terça Fev 14, 2012 9:56 pm

acho que a grande maioria dos problemas do PE apresenta pelo menos a 1ª caracteristica (overlaping subproblems).
não sei se é isso mas acabo sempre por dividir o problema principal em problemas mais pequenos que estao inter-relacionados.

quanto à segunda caracteristica, eu não sei bem se se aplica a este problema da maior soma de um sub vector. Aplica-se para ESTE vector.
Mas para outro vector, com outros valores ou outra ordem penso que já não seria. Imagina que adicionavas um novo elemento ao vector:

vector=[−2, 1, −3, 4, −1, 2, 1, −5, 4]
vector.append(1)

seria adicionado 1, no final do vector.
vector=[−2, 1, −3, 4, −1, 2, 1, −5, 4,1]

a soluçao com 4 componentes é a mesma, mas a soluçao com 2 elementos já não (seria [4,1] em vez de [4,-1] anterior).
ou estou a fazer alguma coisa mal?
"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

AnteriorPróximo

Voltar para Pitónica

Quem está ligado

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