• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

BlodyGrl

Fibonacci com iteração

22 mensagens neste tópico

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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. ;)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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. ;)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

:wallbash: OMFG!

Eu não sei fazer a identação AQUI, no fórum!  ;):P:):P:)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

AH! :P

Eu normalmente copio a indentação que já existe e colo onde é preciso. ;)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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:

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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? ;)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Já que a última linha não faz nada o que está lá a fazer? ;)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu acho que nao vai retornar nada, considerando que o objectivo e apenas apagar o máximo.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

A última linha retorna o valor que removeste para poderes fazer:

print "Removi o valor ", asdf.delMax(), " da heap."

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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

0

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