O‘ZBEKISTON RESPUBLIKASI RAQAMLI TEXNOLOGIYALAR VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI
AMALIY ISHI
TOSHKENT- 2023
Task 9. Zinapoya N zinadan iborat. Quyon bir sakrashda K dan ortiq qadam bosib o’ta olmaydi. K va N ning qiymatlari berilganda quyon zinapoyaning tepasiga necha xil yo’l bilan chiqishi mumkin.
Masalan, agar K=3 va N=4 bo’lsa, unda quyidagi yo’llar mavjud: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+ 3, 3+1. Demak, Output:
7 Input: K=2, N=7; Output: 21
def quyon_tepasiga_chiqish(K, N):
if K == 1:
return 1
if N == 1:
return 1
if N < K:
return 0
dp = [[0] * (N + 1) for _ in range(K + 1)]
for i in range(K + 1):
dp[i][0] = 1
for i in range(1, K + 1):
for j in range(1, N + 1):
dp[i][j] = dp[i][j - 1] + dp[i - 1][j]
return dp[K][N]
K = int(input("K ni kiriting: "))
N = int(input("N ni kiriting: "))
result = quyon_tepasiga_chiqish(K, N)
print("Output:", result)
def count_ways_to_top(K, N):
# Create a list to store the number of ways to reach each step
ways = [0] * (N + 1)
# Initialize the base cases
ways[0] = 1
ways[1] = 1
# Compute the number of ways for each step up to N
for i in range(2, N + 1):
for j in range(1, K + 1):
if i - j >= 0:
ways[i] += ways[i - j]
# Return the number of ways to reach the top
return ways[N]
# Test the function
K = 3
N = 4
print(count_ways_to_top(K, N)) # Output: 7
K = 2
N = 7
print(count_ways_to_top(K, N)) # Output: 21
|