Demostrar el número de adiciones del algoritmo del número de Fibonacci

Estoy estudiando para un examen final y tengo problemas con esta pregunta:

El siguiente algoritmo recursivo FIB toma como entrada un número entero norte ≥ 0 y devuelve el norte -ésimo número de Fibonacci F norte :

Algorithm FIB(n):

    if n = 0 or n = 1 then
        f = n
    else
        f = FIB(n-1) + FIB(n-2)
    endif
    return f

Dejar a norte Sea la cantidad de adiciones hechas por el algoritmo FIB(n), el número total de veces que el + -función en caso contrario se llama. Demuestra que para todos norte ≥ 0

a norte = F norte + 1 − 1.

Estoy pensando que debería usar la recurrencia para resolverlo, pero estoy completamente perdido. ¡Gracias de antemano!

Respuestas (3)

Informática FIB(0)ya FIB(1)no tiene añadidos, ya que vuelve n.

La informática FIB(n)tiene una adición, más tantas como FIB(n-1)y FIB(n-2)tenga.

Entonces tenemos

a norte = { 0 , norte ∈ { 0 , 1 } , a norte − 1 + 1 + a norte − 2 , norte > 1.

Ahora, usa la inducción matemática para comprobar que a norte = F norte + 1 − 1 y comenta si te quedas atascado.

¿Estoy en lo correcto con mi inducción? Lo hice en papel y subí una imagen: i.imgur.com/a9ZxNt7.jpg
@pyramid No. Primero, debe verificar a 0 y a 1 , porque la recursividad para a norte depende de los dos elementos anteriores ( a norte − 2 y a norte − 1 ). En segundo lugar, por a k + 1 vas de F k + 1 + 1 que desea probar, por lo que no puede usarlo. Más bien, pon a k + 1 = a ( k + 1 ) − 1 + 1 + a ( k + 1 ) − 2 (de la recursión) = a k + a k − 1 , luego use la suposición en a k y a k − 1 y ver que obtienes el resultado F ( k + 1 ) + 1 − 1 .
@VedranŠego. Gracias. ¿Puede explicar por qué tiene "1" parte en el segundo caso de definición por partes? Veo esa cantidad de adiciones para a 4 = F 4 + 1 − 1 , pero si calculamos F 4 + 1 sumas, encontramos que es 6 y no 4, entonces a 4 = 6 − 1 = 5 ≠ 4 . O quieres decir por F 4 + 1 es la suma final y no el número de adiciones?
@Avra, no te sigo. a[0..4] = [0, 0, 1, 2, 4]y F[0..5] = [0, 1, 1, 2, 3, 5], entonces a 4 = 4 = 5 − 1 = F 5 − 1 . En cuanto al "1" en el segundo caso: a norte − 1 es el número de adiciones en FIB(n-1), a norte − 2 es el número de adiciones en FIB(n-2), y el extra +1es luego sumar esos dos.

Si reemplazamos la rama "entonces" con

f = 1

entonces el número de adiciones no cambia, porque nunca hay ninguna dependencia de control en el valor devuelto.

Sin embargo, el algoritmo modificado calcula F norte + 1 en vez de F norte . Y la forma en que calcula F norte + 1 es sumando unos, y nunca usando un resultado intermedio más de una vez. Por lo tanto, las adiciones forman los nodos internos en un árbol binario 1en cada hoja, por lo que hay F norte + 1 hojas. El árbol binario tiene un nodo interno menos de los que tiene hojas, por lo que debe haber F norte + 1 − 1 adiciones

Mire su algoritmo y conviértalo en una función que calcule la cantidad de sumas realizadas.

Algoritmo nFIB(n):

if n = 0 or n = 1 then
    f = 0
else
    f = nFIB(n-1) + nFIB(n-2) + 1 (for the addition)
endif
return f

Entonces norte F I B ( norte ) = norte F I B ( norte − 1 ) + norte F I B ( norte − 2 ) + 1 y esto está bastante cerca de la F norte recurrencia excepto por eso " + 1 ".

Para deshacerse de eso (y se necesita algo de experiencia para ver rápidamente cómo hacerlo), cámbielo agregando 1 a ambos lados) para obtener norte F I B ( norte ) + 1 = norte F I B ( norte − 1 ) + 1 + norte F I B ( norte − 2 ) + 1 .

Por lo tanto norte F I B ( norte ) + 1 satisface la misma recurrencia que F norte pero posiblemente con un desplazamiento diferente, por lo que norte F I B ( norte ) − 1 = F norte + k para algunos k . Jugar da k = 1 , entonces norte F I B ( norte ) = F norte + 1 − 1 .

Demostrar el número de adiciones del algoritmo del número de Fibonacci
RespuestasAquíPolítica de privacidad1y, 1v