Hercles Posted August 12, 2013 at 12:23 PM Report #521504 Posted August 12, 2013 at 12:23 PM 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 Posted August 12, 2013 at 03:28 PM Report #521523 Posted August 12, 2013 at 03:28 PM 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 Posted August 12, 2013 at 08:05 PM Author Report #521552 Posted August 12, 2013 at 08:05 PM 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 Posted August 13, 2013 at 10:49 AM Report #521593 Posted August 13, 2013 at 10:49 AM 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 Posted August 13, 2013 at 09:26 PM Author Report #521658 Posted August 13, 2013 at 09:26 PM (edited) 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 Posted August 14, 2013 at 02:41 PM Report #521747 Posted August 14, 2013 at 02:41 PM 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!
Hercles Posted August 14, 2013 at 02:49 PM Author Report #521750 Posted August 14, 2013 at 02:49 PM mas tem um chamada externa ==> Chamada externa: maior1_maior2(1, n)
thoga31 Posted August 14, 2013 at 02:57 PM Report #521752 Posted August 14, 2013 at 02:57 PM 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!
Hercles Posted August 14, 2013 at 03:07 PM Author Report #521753 Posted August 14, 2013 at 03:07 PM (edited) 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 Posted August 14, 2013 at 03:22 PM Report #521754 Posted August 14, 2013 at 03:22 PM 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!
Hercles Posted August 14, 2013 at 03:54 PM Author Report #521756 Posted August 14, 2013 at 03:54 PM 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 Posted August 14, 2013 at 04:08 PM Author Report #521758 Posted August 14, 2013 at 04:08 PM (edited) 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 Posted August 15, 2013 at 04:07 PM Report #521807 Posted August 15, 2013 at 04:07 PM (edited) 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 Knowledge is free!
Hercles Posted August 15, 2013 at 04:45 PM Author Report #521811 Posted August 15, 2013 at 04:45 PM 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 Posted August 15, 2013 at 04:58 PM Report #521812 Posted August 15, 2013 at 04:58 PM (edited) 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 Knowledge is free!
Hercles Posted August 15, 2013 at 07:02 PM Author Report #521824 Posted August 15, 2013 at 07:02 PM Entendi.. tive uma ideia que fiz aqui rabiscando alguns papeis... vou baixar o pascal pra tentar ver se roda.
Hercles Posted September 8, 2013 at 10:50 PM Author Report #523866 Posted September 8, 2013 at 10:50 PM 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)
Recommended Posts
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 accountSign in
Already have an account? Sign in here.
Sign In Now