Ir para o conteúdo
  • Revista PROGRAMAR: Já está disponível a edição #57 da revista programar. Faz já o download aqui!

BlodyGrl

Fibonacci com iteração

Mensagens Recomendadas

BlodyGrl    0
BlodyGrl

Bem, o que eu gostava era que vocês me ajudassem a fazer o fibonacci com iteração (i.é, sem recursão).

Deixo aqui a minha tentativa falhada e peço que me digam onde está o erro (tenho um palpite que seja na linha 10 mas sem 100% de certeza) e como o corrigir, por favor.

O que este programa faz é a soma do elemento mais o anterior e não das somas dos anteriores.  ;)

Agradecida.  :P

def fibonaccib(x):
    a=1
    b=range(1,x+1)
    if type(x)!= int:
        return "O elemento que inseriu nao e um numeral inteiro!"
    elif x==0 | x==1:
        a=1
    else:
        for i in b:
           a= b[x-1] + b[x-2]
    return a

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
djthyrax    11
djthyrax

Fazes uma lista dos números da sequencia até a x assim:

x = 5000 #o limite de valor
listaFib = [1, 1, 2] #precomputadados
while listaFib[-1] <= x:
    listaFib.append(listaFib[-1] + listaFib[-2])

O listaFib.apppend() cria um novo elemento na lista, ou seja, no primeiro while, o listaFib passa de [1,1,2] para [1,1,2,3], e por aí fora. Os indexes negativos são relativos ao final da lista (o -1 é o último elemento, -2 o anterior, -3 o anterior, etc etc).

Btw, o if que tens para o tipo não deveria ser feito assim IMO, mas sim levantando uma excepção, mas só posso opinar mais sabendo o que deste. ;)

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
BlodyGrl    0
BlodyGrl

Acho que estás a usar uma notação que desconheço...  :-[ Além de que acho que me estás a dar uma lista dos números e eu só quero número certo...

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
djthyrax    11
djthyrax

Ah, tu queres o elemento x da sequencia? É só mudar a condição para len(listaFib) <= x

Estou a usar listas, se não deste, diz que eu explico-te de outra maneira ;)

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
BlodyGrl    0
BlodyGrl

Eu dei listas mas não percebo é a tua notação do índice ser -1... O índice das listas não começa em 0? :hmm:

E depois ainda não aprendi a definir as listas fora da função (isso só em Haskall  ;)).

É assim não é? :P

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
djthyrax    11
djthyrax

O -1 tem a ver com índices relativos. Fazer -1 ou len(lista)-1 é a mesma coisa.

Listas são igual seja numa função ou fora dela, só tens a questão do scope, mas ao teu nível ainda não interessa isso. ;)

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
BlodyGrl    0
BlodyGrl

def fibonaccib(x):
listaFib = [1, 1, 2]
while len(listaFib) <= x:
    listaFib.append(listaFib[-1] + listaFib[-2])
return listaFib[-1]

É assim não é?  :) Obrigado!

Sim, já sei... Eu é que estava distraída com isso dos negativos. ;)

Mas quanto ao caso do [1,1,2] não sabia é que o Python tinha já essas listas no computador, era isso que queria dizer. :P

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
djthyrax    11
djthyrax

Tens a identação mal, falta-te um nível a partir do def (e eu enganei-me na lista acho, deve ser [1, 2] e não [1, 1, 2], alguém que verifique isto):

def fibonaccib(x):
    listaFib = [1, 2]
    while len(listaFib) <= x:
        listaFib.append(listaFib[-1] + listaFib[-2])
    return listaFib[-1]

Mas sim, já apanhaste isso. ;)

Em relação ao python ter a lista no computador, tu é que estás a definir uma lista que [1, 2], poupas fazer isto:

listaFib = []
listaFib.append(1)
listaFib.append(2)

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
BlodyGrl    0
BlodyGrl

Eu não sei fazer a identação aqui...  ;)

Eu acho que deve mesmo ser [1,1,2] porque fib(1)=1 e fib(2)=1... Podes é não ter o 2 porque o 2 já é a soma dos 2 uns anteriores...

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
BlodyGrl    0
BlodyGrl

;) Bom truque! Mais uma dúvida... Desta vez sobre árvores, maxHeaps...

Eu não percebo muito bem porque é que o comando delMax é assim. Alguém me podia explicar sff? :P

    def delMax(self):
        retval = self.Q[1]
        self.Q[1] = self.Q[self.n]
        b=self.Q.pop()
        self.n -= 1
        self.insert1(1)
        return retval

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
djthyrax    11
djthyrax

Ui, objectos. Bem, ele vai buscar à variável Q da instância iniciada o elemento 1 e guarda-a numa variável temporal para depois retornar o valor. Depois, esse elemento 1 passa a ser igual ao elemento n (parece-me que seja o último indice da lista pelo resto do código), tira fora o último elemento da lista para a variável b, diminiu o n (porque tem menos 1 elemento a lista), e o método insert1 não faço ideia para o que serve.

Para ser mais concreto, só vendo a class inteira.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
BlodyGrl    0
BlodyGrl

class MaxHeap:
    def __init__(self):
        self.Q=[None]
        self.n=0
        
    def insert1(self,i):
        while i > 1 and self.Q[i] > self.Q[i/2]:
            self.Q[i/2],self.Q[i] = self.Q[i],self.Q[i/2]
            
    def insert(self,item):
        self.Q.append(item)
        self.n += 1
        self.insert1(self.n)
        
    def findMax(self):
        return self.Q[1]
    
    def delMax(self):
        retval = self.Q[1]
        self.Q[1] = self.Q[self.n]
        b=self.Q.pop()
        self.n -= 1
        self.insert1(1)
        return retval

    def isEmpty(self):
        return self.n==0

    def size(self):
        return self.n

Dúvidas:Porque é que ele define o valor de retval e depois tens mais 4 linhas que nem sequer lhes vai alterar o resultado?

Porque é que ele vai definir o b se depois nem sequer o usa?

Estou a ficar confusa.  :bored:

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
djthyrax    11
djthyrax

Bem, o delMax vai apagar o valor máximo da heap e retorna-o.  (O 1º elemento, que neste caso, não é o 0 mas sim o 1, porque tens uma lista cujo primeiro elemento é sempre o None, penso que para o aluno não fazer a confusão de os indices começarem no 0).

Na 1a linha ele vai buscar o valor máximo e guarda-o para o retornar. Na segunda e 3a linha ele vai buscar o último elemento da heap e mete-o no inicio (a 3a linha é para o apagar no fim). Na 4a linha, diminui a variável que te indica o tamanho da heap, e a chamada ao insert1() não te vai fazer nada, uma vez que o i > 1 no while não vai ser True (caso satisfazesse, o insert1() ia ordenar a heap). Na última, retorna o valor máximo que tinha ido buscar no início.

Queres que explique o resto? ;)

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
djthyrax    11
djthyrax

Isso não invalida que não seja útil. Mas sim, podes tirar se não te faz diferença (mas se não tirares, também não te perturba). :P

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora


×

Aviso Sobre Cookies

Ao usar este site você aceita a nossa Política de Privacidade