Mündəricat
Problem bəyanat
“Pilləkənlərə qalxmaq” problemi sizə n pilləkənli pilləkən verildiyini bildirir. Bir anda ya bir pilləkən, ya da iki pilləkən qalxa bilərsiniz. Nərdivanın zirvəsinə çatmağın neçə yolu var?
misal
3
3
Izahat
Zirvəyə qalxmağın üç yolu var.
1. 1 addım + 1 addım + 1 addım
2. 1 addım + 2 addım
3. 2 addım + 1 addım
Şəkildə hərəkət etmə yolları göstərilir.
Buna görə cavabımız 3-dür.
Rekursiv yanaşma
Pilləkənə çatmağın sayının (i-1) pilləkənə və (i-2) pilləyə çatmağın sayının cəmidir. Beləliklə rekursiv tənliyimiz olur
ways(n) = ways(n-1) + ways(n-2)
Kodu
Nərdivanlara çıxmaq üçün C ++ kodu
#include <bits/stdc++.h>
using namespace std;
// A recursive function used by countWays
int countWaysUtil(int n, int m)
{
if (n <= 1)
{
return n;
}
int res = 0;
for(int i = 1; i <= m && i <= n; i++)
{
res += countWaysUtil(n - i, m);
}
return res;
}
// Returns number of ways to reach s'th stair
int countWays(int s, int m)
{
return countWaysUtil(s + 1, m);
}
// Driver code
int main()
{
int s = 4, m = 2;
cout << "Nuber of ways = " << countWays(s, m);
return 0;
}
5
Pilləkənlərə çıxmaq üçün Java kodu
class stairs {
// A recursive function used by countWays
static int countWaysUtil(int n, int m)
{
if (n <= 1)
return n;
int res = 0;
for (int i = 1; i <= m && i <= n; i++)
res += countWaysUtil(n - i, m);
return res;
}
// Returns number of ways to reach s'th stair
static int countWays(int s, int m)
{
return countWaysUtil(s + 1, m);
}
/* Driver program to test above function */
public static void main(String args[])
{
int s = 4, m = 2;
System.out.println("Number of ways = "
+ countWays(s, m));
}
}
5
Mürəkkəblik təhlili
Zamanın mürəkkəbliyi
O (2 ^ n), çünki hər pilləkən üçün rekursiv yanaşmada iki seçimimiz var: bir dəfəyə bir pilləyə qalxmaq və ya eyni anda iki pilləyə qalxmaq. Mümkün olan bütün halları yoxladığımız üçün hər pilləkən üçün 2 seçimimiz var və cəmi n pilləkənimiz var, beləliklə zaman mürəkkəbliyi yaranır O (2 ^ n)
Kosmik Mürəkkəblik
O (n) çünki kompilyator tərəfindən rekursiyadan istifadə etmək üçün yer tələb olunur. Rekursiya ayrıca yığını və bu O (n) boşluğunu saxlamağı tələb edir, çünki rekursiya demək olar ki, n dərin olacaqdır.
Dinamik Proqramlaşdırma Yanaşması
Rekursiv yanaşma eyni dəyərlərin təkrar hesablanmasını əhatə edir. Bunun üçün xatirədən istifadə edirik və müəyyən bir giriş üçün hesabladığımızda onu saxlayırıq xatirə masa. Daha sonra ehtiyac duyduğumuz zaman yenidən hesablamırıq və birbaşa dəyərini cədvəldən istifadə edirik. Cədvəl yollarını saxlayırıq [] burada yollar [i] nərdivana çatmağın sayını saxlayır. Yəni yollar [n-1] bizim cavabımızdır.
Kodu
Nərdivanlara çıxmaq üçün C ++ kodu
#include <stdio.h>
// A recursive function used by countWays
int countWaysUtil(int n, int m)
{
int res[n];
res[0] = 1;
res[1] = 1;
for (int i = 2; i < n; i++) {
res[i] = 0;
for (int j = 1; j <= m && j <= i; j++)
res[i] += res[i - j];
}
return res[n - 1];
}
// Returns number of ways to reach s'th stair
int countWays(int s, int m)
{
return countWaysUtil(s + 1, m);
}
// Driver program to test above functions
int main()
{
int s = 4, m = 2;
printf("Number of ways = %d", countWays(s, m));
return 0;
}
5
Pilləkənlərə çıxmaq üçün Java kodu
// Java program to count number of ways
// to reach n't stair when a person
// can climb 1, 2, ..m stairs at a time
class stairs {
// A recursive function used by countWays
static int countWaysUtil(int n, int m)
{
int res[] = new int[n];
res[0] = 1;
res[1] = 1;
for (int i = 2; i < n; i++) {
res[i] = 0;
for (int j = 1; j <= m && j <= i; j++)
res[i] += res[i - j];
}
return res[n - 1];
}
// Returns number of ways to reach s'th stair
static int countWays(int s, int m)
{
return countWaysUtil(s + 1, m);
}
// Driver method
public static void main(String[] args)
{
int s = 4, m = 2;
System.out.println("Number of ways = "
+ countWays(s, m));
}
}
5
Mürəkkəblik təhlili
Zamanın mürəkkəbliyi
O (m * n) burada m bu problem üçün 2 olan yolların sayı və n pilləkənlərin sayıdır.
Kosmik Mürəkkəblik
O (n) çünki hər mövqenin bu mövqeyə çatmağın sayını saxladığı n ölçülü bir sıra istifadə edirik.
