Как интерпретировать код для подсчета путей, чтобы добраться до n-й ступени? - PullRequest
Новая
       12

Как интерпретировать код для подсчета путей, чтобы добраться до n-й ступени?

0 голосов
/ 28 сентября 2019

Я пытаюсь интерпретировать этот код от geeksforgeeks: 

def fib(n): 
    if n <= 1: 
        return n 
    return fib(n-1) + fib(n-2) 

def countWays(s): 
    return fib(s + 1) 

s = 4
print "Number of ways = ", 
print countWays(s)

Кажется, я не могу получить правильный ответ, когда подставляю числа в функцию.Вот мой мыслительный процесс: 

def countWays(s): 
    return fib(4 + 1) #5

#this goes into fib(n). 5 is not less than or equal to n so I skip to the else statement:

fib(5-1) + fib(5-2) 

#fib(4) + fib(3) since these are still not less than or equal to n I input 
#them into the function again.

 fib(4-1) + fib(3-2) 

#fib(3) + fib(1) now that one of the n is less than or equal to n, 
#I return n and get 4 (3+1). The answer is supposed to be 5.

1 Ответ

0 голосов
/ 28 сентября 2019

Проверьте это так: 

# Python 3
def fib(n): 
    print(f'Fib: {n}')
    if n <= 1:
        print('End')
        return n
    else:
        print(f'Send: {n-1} and {n-2}')
    return fib(n-1) + fib(n-2) 

def countWays(s): 
    return fib(s + 1) 

s = 4
print("Number of ways = ")
print(countWays(s))

Результаты 

Fib: 5           # A
Send: 4 and 3    # A.B and A.C
Fib: 4           # A.B
Send: 3 and 2    # A.B.1 and A.B.2
Fib: 3           # A.B.1
Send: 2 and 1    # A.B.1.1 and A.B.1.2
Fib: 2           # A.B.1.1
Send: 1 and 0    # A.B.1.1.1 and A.B.1.1.2
Fib: 1           # A.B.1.1.1
End              # (END) A.B.1.1.1       -> 1
Fib: 0           # A.B.1.1.2
End              # (END) A.B.1.1.2       -> 0
Fib: 1           # A.B.1.2
End              # (END) A.B.1.2         -> 1
Fib: 2           # A.B.2
Send: 1 and 0    # A.B.2.1 and A.B.2.2
Fib: 1           # A.B.2.1
End              # (END) A.B.2.1         -> 1
Fib: 0           # A.B.2.2
End              # (END) A.B.2.2         -> 0
Fib: 3           # A.C
Send: 2 and 1    # A.C.1 and A.C.2
Fib: 2           # A.C.1
Send: 1 and 0    # A.C.1.1 and A.C.1.2
Fib: 1           # A.C.1.1
End              # (END) A.C.1.1         -> 1
Fib: 0           # A.C.1.2
End              # (END) A.C.1.2         -> 0
Fib: 1           # A.C.2
End              # (END) A.C.2           -> 1
5                                     # 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1

А теперь подставьте 

>>> print(fib(5))
Fib: 5
Send: 4 and 3
Fib: 4
...
Fib: 1
End
5

Тот же результат.

...