Wchodzenie po schodach

Poziom trudności Łatwo
Często zadawane pytania Adobe Amazonka Apple Bloomberg Expedia Goldman Sachs
Programowanie dynamiczneodwiedzajacy 72

Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że ​​trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.

Problem Statement

Problem „Wchodzenie po schodach” mówi, że masz klatkę schodową z n schodami. Jednocześnie możesz wspiąć się po jednym lub dwóch schodach. Ile jest sposobów, aby dostać się na szczyt schodów?

Przykład

3
3

Wyjaśnienie

Na szczyt można wejść na trzy sposoby.

1. 1 stopień + 1 stopień + 1 stopień

2. 1 stopień + 2 stopnie

3. 2 stopnie + 1 krok

Wchodzenie po schodachszpilka

Obraz przedstawia sposoby poruszania się.

Więc nasza odpowiedź to 3.

Podejście rekurencyjne

Możemy zaobserwować, że liczba dróg dotarcia do i-tego stopnia jest sumą liczby dróg dotarcia do (i-1) schodów i liczby dróg do osiągnięcia (i-2) schodów. Staje się więc nasze równanie rekurencyjne

ways(n) = ways(n-1) + ways(n-2)

Kod

Kod C ++ do wspinania się po schodach

#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

Kod Java do wspinania się po schodach

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

Analiza złożoności

Złożoność czasowa

O (2 ^ n), ponieważ w podejściu rekurencyjnym dla każdego stopnia mamy dwie możliwości: wchodzić po jednym stopniu na raz lub wchodzić po dwóch schodach naraz. Ponieważ sprawdzamy wszystkie możliwe przypadki, więc dla każdego schodów mamy 2 opcje i mamy łącznie n schodów, więc złożoność czasowa staje się złożona O (2 ^ n)

Złożoność przestrzeni

Na) ponieważ kompilator wymaga miejsca, aby użyć rekursji. Rekursja wymaga również stosu, a tym samym przechowywania, co tworzy tę przestrzeń O (n), ponieważ rekursja będzie prawie n głęboka.

Dynamiczne podejście do programowania

Podejście rekurencyjne obejmuje wielokrotne przeliczanie tych samych wartości. W tym celu używamy zapamiętywania, a kiedy obliczamy go dla jakiegoś wejścia, przechowujemy go w pliku zapamiętywanie stół. Kiedy potrzebujemy go później, nie obliczamy go ponownie i bezpośrednio używamy jego wartości z tabeli. Utrzymujemy tabelę sposobów [], gdzie sposoby [i] przechowują liczbę dróg do osiągnięcia i-tego stopnia. Zatem sposoby [n-1] to nasza odpowiedź.

Kod

Kod C ++ do wspinania się po schodach

#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

Kod Java do wspinania się po schodach

// 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

Analiza złożoności

Złożoność czasowa

O (m * n) tutaj m to liczba dróg, która dla tego problemu wynosi 2, an to liczba schodów.

Złożoność przestrzeni

Na) ponieważ używamy tablicy o rozmiarze n, w której każda pozycja przechowuje liczbę sposobów dotarcia do tej pozycji.

Wywiady dotyczące projektowania systemu pękania
Translate »