N adet basamağa sahip bir merdivende, en alt noktadan üst noktaya her seferinde en fazla bir veya iki adım atarak kaç farklı şekilde ulaşabileceğimizi bulacağız.
Örneğin yadaki resim için 3 adet çözüm vardır.
Daha fazla örnek;
Input: n = 1
Output: 1
Sadece 1 adımda ulaşılır
Input: n = 2
Output: 2
İki farklı adımda ulaşılır: (1, 1) ve (2)
Input: n = 4
Output: 5
(1, 1, 1, 1), (1, 1, 2), (2, 1, 1), (1, 2, 1), (2, 2)
Basit olarak rekürsif olarak çözebilir. yol(n) = yol(n-1) + yol(n-2)
. Aslında yandaki formulun fibonacci formulu olduğu çok belli.
def recursion(n):
if n <= 1:
return n
return recursion(n - 1) + recursion(n - 2)
def solve(n):
return recursion(n + 1)
if __name__ == '__main__':
n = 4
print(solve(n))
Yukarıdaki çözüm O(2^n) zaman karmaşasına sahiptir. Tabi çok daha efektif çözmenin yollarını şurada daha önce belirttim.
Problemin genelleştirilmiş hali
Örneğin kişinin m adıma kadar hakkı olsun. m=4 için kişi her bir anda 1, 2, 3 veya 4 adım atabilir.
yol(n, m) = yol(n-1, m) + yol(n-2, m) + ... yol(n-m, m)
def calculate(n, m):
if n <= 1:
return n
res = 0
i = 1
while i <= m and i <= n:
res += calculate(n - i, m)
i += 1
return res
def solve_gen(n, m):
return calculate(n + 1, m)
if __name__ == '__main__':
basamak = 4
adim = 2
print(solve_gen(basamak, adim))
Comments
comments powered by Disqus