Algoritmo recursivo para encontrar os maiores elementos de uma lista

[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.

[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?

[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),)

[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.

[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 August 13, 2013 at 09:36 PM by Hercles

[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.

[Hercles]

mas tem um chamada externa ==> Chamada externa: maior1_maior2(1, n)

[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.

[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 August 14, 2013 at 03:13 PM by Hercles

[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.

[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

[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 August 14, 2013 at 04:10 PM by Hercles

[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 August 15, 2013 at 04:10 PM by thoga31

[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)

[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 August 15, 2013 at 05:00 PM by thoga31

[Hercles]

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

[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)