Nərdivanlara qalxmaq

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Çiy kərpic Amazon alma Bloomberg Expedia Goldman Sachs
Dinamik proqramlaşdırmaBaxılıb 27

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

Nərdivanlara qalxmaqPin

Şə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.

Translate »