Jump to content
Hercles

Algoritmo recursivo para encontrar os maiores elementos de uma lista

Recommended Posts

Hercles

Escreva um algoritmo recursivo para encontrar os dois maiores elementos de uma lista com n elementos, baseado no seguinte princípio: divide-se a lista ao meio e encontrase recursivamente os dois maiores elementos de cada uma das metades; a seguir, combinase as duas soluções parciais na solução final.

Share this post


Link to post
Share on other sites
pwseo

Hercles,

O enunciado que escreveste já descreve precisamente o que tens que fazer. Se estás à espera que te resolvam o exercício, não será aqui que encontrarás resposta. Mas se começares a tentar resolver tu e fores colocando dúvidas válidas, serás ajudado sempre que possível.

Já começaste a resolver?

Share this post


Link to post
Share on other sites
Hercles

Sim. uma função, mas quando tento fazer ele fica iratarivo. Será que posso usar max1 e max2?

funcao maior1_ maiorr2(i, j)
 se i = j entao
   retornar (V [i], V [i])
 senao
   se j = i + 1 entao
     retornar (MAX(V [i], V [j]),MIN(V [i], V [j]))
   senao
     meio = (i + j)/2
     (maior1,maior2) = maiormaior(i,meio)
     (maior2,maiorr2) = maior1 maoir(meio + 1, j)
     retornar (MAX(maior1,maior2),)

Edited by Rui Carlos
Tags CODE / indentação

Share this post


Link to post
Share on other sites
pwseo

Isso está um pouco confuso, não é verdade? Consegues explicar-me o que se está a passar nesse pseudo-código que escreveste? Eu não percebi, e vou aguardar que o expliques antes de explorarmos o que está mal nele.

E mais uma vez, quando colocas código no fórum, esse código é para ser colocado nas tags apropriadas, como podes ver nesta secção da ajuda. Já foste avisado para isso mais que uma vez, e no entanto continuo a ver os teus posts editados pela moderação por esse motivo.

Share this post


Link to post
Share on other sites
Hercles
Chamada externa: maior1_maior2(1, n)
// quando a função for chamada ela vai com o primeiro indice que 1 até o tamanho da lista (n)


funcao maior1_ maior2(i, j)

se i = j entao					 //aqui se i que vale 1 for iqual a j então a lista só tem 1 elemento
retornar (V [i], V [i])			 //aqui vai retornar tanto pra maior1 e maior2 o unico elemento da lista
senao

se j = i + 1 entao				 // senão j = 2 a lista tem dois elemento
retornar (MAX(V [i], V [j]),MIN(V [i], V [j]))	 // aqui vai retornar o maior1 e maior2 destes dois elementos


senao								 // se a lista não for conposta de 1 e nem 2 elementos meio vai receber o
									 // tamanho da lista dividido por 2, ou seja vai ficar com a metade
meio = (i + j)/2


(maior1,maior1b) = maior1_maior2(i,meio)	 // aqui chama a função e coloca o valor 1 em maior1 e o valor da metade da lista em maior1b

(maior2,maior2b) = maior1_maio2b(meio + 1, j) // aqui chama a função e coloca o 1º depois da metade da lista em maior2 e no maior2b o idice do ultimo vetor


antes de chegar aqui deveria ter mais alguam coisa


retornar (MAX(maior1,maior2),MAx(maior2,menor2b))


.

Edited by Hercles

Share this post


Link to post
Share on other sites
thoga31

se j = i + 1 entao                               // senão j = 2 a lista tem dois elemento
retornar (MAX(V [i], V [j]),MIN(V [i], V [j]))   // aqui vai retornar o maior1 e maior2 destes dois elementos

Mentira, aqui nada te garante que j seja igual a 2. j é simplesmente igual a i + 1. Se i for 10, j terá de ser 11. Lê bem o código que escreves.

Eu acho que tens de repensar muito bem esse teu algoritmo. pega em caneta e papel e começa a testar e a ver que algoritmo corresponde ao teu raciocínio.


Knowledge is free!

Share this post


Link to post
Share on other sites
thoga31

Um bom procedimento em Pascal não recebe por argumentos os índices da array, recebe sim a própria array. Por isso, primeiro que nada, o cabeçalho deveria ser algo como:

funcao maior1_maior2(lista)

E tens todo o algoritmo para rever.


Knowledge is free!

Share this post


Link to post
Share on other sites
Hercles

poxa mas a função vai retornar 2 números... o 1º maior e o 2º maior

no caso do pascal não seria: funcao maior1_maior2(i,j: integer):integer; mas eu só querendo escrever o algoritmo.

Edited by Hercles

Share this post


Link to post
Share on other sites
thoga31

Que confusão que estás a fazer...

Afinal os argumentos da função são índices ou os 2 elementos maiores? Resposta: os índices.

O que eu estou a dizer: em Pascal não se passa por argumento os índices, passa-se directamente a array.

Problema: como é que a função retorna os dois valores maiores?

Resposta: ou devolves uma estrutura que possua 2 números (array[1..2] ou record) ou então essa estrutura ou 2 variáveis são passadas por referência.

Traduzindo em Pascal, estas seriam algumas opções:

type // por boa prática, declara-se o tipo:
    TLista = array of integer;

    // Caso se prefira usar uma estrutura para devolver os maiores elementos, eis duas hipóteses:
    TParMaior = array[1..2] of integer;
    TParMaior = record
       m1, m2 : integer;
    end;

(* Hipóteses para a função... *)

function maiores(lista : TLista) : TParMaior;
procedure maiores(lista : TLista; var m : TParMaior);
procedure maiores(lista : TLista; var m1, m2 : integer);

Colocada a questão dos argumentos da função, o meu conselho é pensares bem no algoritmo. Não estás longe da solução, mas tens de melhorar tudo.

Nota: apesar de ser pseudocódigo, este deverá reflectir minimamente o que vai ser a função, pelo que, para mim, esse cabeçalho é simplesmente algo a ser refeito.


Knowledge is free!

Share this post


Link to post
Share on other sites
Hercles

a questão pede o algoritmo, pensar em pascal é bom porque posso testar... mas o que entendi eu vou passar é a posição aonde esta o elemento maior1 e maior2, ou seja o indice de aonde eles estão. V seria uma variavel global do tipo Array

Share this post


Link to post
Share on other sites
Hercles

você concorda comigo se o array só tiver um elemento. Então o 1º maior e 2º maior vai ter o mesmo valor ou eu posso mandar uma mensagem dizendo "Só há um elemento, não é possivel informar quem é o maior"

você concorda comigo se o array só tiver 2 elementos. Então é so comparar e retorna "i" como o 1º maior e "j" como o 2º maior.

agora qdo o array tiver mais de 2 elementos eu preciso dividir o array ao meio comparar a primeira metade do array e descobrir la quem é o 1º maior e 2º maior, depois fazer a mesma coisa com a segunda medade do array.

bom até aqui eu vou ter 4 resultado que só vou poder ficar com 2, o 1º maior e 2º maior. o problema de tornar RECURSIVO é descobrir estes 4 valores e depois 2 valores usando o que eu escrevi em azul

bom isso é o que eu acho, ninguém me explicou nada... pode ser que eu esteja errado! :):) :)

Edited by Hercles

Share this post


Link to post
Share on other sites
thoga31

bom isso é o que eu acho, ninguém me explicou nada...

Portanto, nós a darmos sugestões para começares a melhorar a tua função, e tu dizes que não explicamos nada. Já experimentaste começar a pensar e implementar o que tenho vindo a dizer para começares a melhorar?

Conselho: ouve mais e melhor, nós não falamos ao acaso. ;)

a questão pede o algoritmo, pensar em pascal é bom porque posso testar... mas o que entendi eu vou passar é a posição aonde esta o elemento maior1 e maior2, ou seja o indice de aonde eles estão. V seria uma variavel global do tipo Array

Espera lá, estás a dizer que passas como argumentos os índices onde estão os elementos maiores? Isso não bate certo com o que tens dito e feito. Tens de te explicar melhor. "Passar" refere-se à passagem de argumentos a uma função, e "retornar" refere-se ao valor devolvido pela função.

Também podes testar o algoritmo em Pascal. Eu resolvi o teu problema em Pascal para testar o meu algoritmo e funcionou.

De seguida, uma função não deve devolver nem escrever nenhuma mensagem de erro, o bloco que invoca a função é que deverá lidar com esses erros.

Concordo contigo acerca das arrays com 2 elementos, ainda ninguém disse nada acerca disso.

Acerca da recursividade, o teu algoritmo inicial não está longe da solução. Aliás, estás muito perto.

Aquilo com que não concordo é os argumentos que passas para a função - tu passas 2 índices para a função, e não há qualquer referência da array. Devias passar por argumento única e exclusivamente a array "V". A chamada externa não é algo que se indique num algoritmo, nem em qualquer LP. A função deveria receber uma array, com uma dimensão qualquer, e devolver os 2 elementos maiores, e não deveria receber índices - onde está a array no meio disto?

Dica: usar a função "length(array)" - devolve o tamanho de uma array em Pascal, podes usar este princípio no teu algoritmo com algo como "tamanho(V)".

Desta forma, teria assim o cabeçalho:

funcao maiores(V : lista de inteiro):

E mais à frente, terias coisas como:

meio = tamanho(V) DIV 2;

Em suma: não estás longe da solução, mas o caminho para ela passa por uma total reconstrução do cabeçalho da função e, por conseguinte, do corpo da função. Mais, a recursividade não está mal.

Edited by thoga31

Knowledge is free!

Share this post


Link to post
Share on other sites
Hercles

meio = tamanho(V) DIV 2; aqui vc usou o div porque o primeiro índice do vetor é zero? eu estava usando meio := (i+j) sendo i passado como 1 na chamada externa e j o valor de total de n (vetor)

Share this post


Link to post
Share on other sites
thoga31

Eu já entendi a "chamada externa", a qual já te disse que não deve existir. Esquece os índices passados pelos argumentos, esses argumentos devem ir à vida. O argumento deve ser a própria array.

Usei DIV porque se a array tiver um nº ímpar de elemento a divisão "normal" ia-me dar um índice fraccionário, e só existem índices inteiros - DIV retorna a parte inteira da divisão. Não é por mais nada.

Começa a implementar as sugestões, daí até à solução final é um instante.

EDIT: tópico movido para a secção correcta.

Edited by thoga31

Knowledge is free!

Share this post


Link to post
Share on other sites
Hercles

Entendi.. tive uma ideia que fiz aqui rabiscando alguns papeis... vou baixar o pascal pra tentar ver se roda.

Share this post


Link to post
Share on other sites
Hercles

Resposta:

função dois_maiores(i, j)
 se
 i = j então
   retornar (V [i], V [i])
 senão
 se
 j = i + 1 então
   retornar ( MAX(V [i],V [j]), MIN(V [i]; V [j]))
 senão
   meio= (i + j)/2
   (maior1, segMaior1) = dois_maiores(i, meio)
   (maior2,segMaior2) = dois_maiores(meio + 1, j)
   aux1:= MAX(maior1, maior2)
   aux2:= MAX(MIN(maior1, maior2), MAX(segMaior1, segMaior2))
   retornar (aux1,aux2)

Edited by Rui Carlos
Tags code + formatação

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.