רצפים באורך נתון כאשר כל אלמנט גדול או שווה לפעמיים מקודמו  


רמת קושי קַל
נשאל לעתים קרובות אקסנצ'ר אמזון בעברית CodeNation פייסבוק Google פייפאל קוואלקום
הפרד ומשול תכנות דינמי

הבעיה "רצפים באורך נתון כאשר כל אלמנט הוא יותר או שווה לפעמיים מקודם" מספקת לנו שני מספרים שלמים m ו- n. פה m הוא המספר הגדול ביותר שיכול להתקיים ברצף ו הוא מספר האלמנטים שחייבים להיות ברצף הנדרש. יש תנאי נוסף המוטל על הרצף, כלומר כל אלמנט צריך להיות יותר או שווה לפעמיים לאלמנט הקודם. גלה את המספר הכולל של הרצפים כך שכל התנאים מתקיימים.

דוגמה  

n = 3, m = 6
4

הסבר

ישנם 4 רצפים שניתן לבצע בתנאים נתונים: (1, 2, 4), (1, 2, 5), (1, 2, 6), (1, 3, 6).

גישה  

הבעיה מבקשת מאיתנו למצוא את המספר הכולל של רצפים באורך נתון שבו כל אלמנט גדול או שווה לפעמיים מקודמו. פתרון נאיבי בעל מורכבות זמן גבוהה יכול להיות ליצור את כל רצפי האורך n. על האלמנטים לפעול לפי הסדר העולה והמספר המקסימלי לא יעלה על m. אבל פתרון יעיל יותר יכול היה להיות אם היינו משלבים את העובדה שכל אלמנט צריך להיות יותר או שווה לפעמיים הקודם. כך אנו יכולים לכתוב נוסחה רקורסיבית. אם נבחר אז אנחנו צריכים למצוא את הרצף עם אורך n-1 ואלמנט מקסימלי מ / 2. אחרת עלינו למצוא את הרצף באורך ואלמנט מקסימלי מ-1. אף על פי שגישה זו יעילה מעט יותר מזו שנדונה בעבר. זה גם גוזל זמן.

ראה גם
מצא אם תת-מערך הוא בצורת הר או לא

רצפים באורך נתון כאשר כל אלמנט גדול או שווה לפעמיים מקודמואורן

במקרים בהם יש לנו נוסחה רקורסיבית, אנו משתמשים תכנות דינמי. אנו פשוט נזכיר את האמור לעיל רקורסיבית פתרון עליו דנו. במקרה זה, יש לנו 2 מצבים. הראשון הוא המספר המרבי והשני הוא אורך הרצף.

קופונים  

קוד C ++ למציאת רצפים באורך נתון כאשר כל אלמנט גדול או שווה לפעמיים מקודמו

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n = 3, m = 6;
    int dp[m+1][n+1];
    memset(dp, 0, sizeof dp);
    for(int i=0;i<=m;i++)
        dp[i][0] = 1;
    int ans = 0;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            // we pick the current element
            dp[i][j] = dp[i/2][j-1];
            // we ignore the current element
            dp[i][j] += dp[i-1][j];
        }
    }
    cout<<dp[n][m];
}
4

קוד Java למציאת רצפים באורך נתון כאשר כל אלמנט גדול או שווה לפעמיים מקודמו

import java.util.*;
class Main{
  public static void main(String[] args)
  {
      int n = 3, m = 6;
      int dp[][] = new int[m+1][n+1];
      for(int i=0;i<=n;i++)
      	for(int j=0;j<=m;j++)
      		dp[i][j] = 0;
      for(int i=0;i<=m;i++)
          dp[i][0] = 1;
      for(int i=1;i<=m;i++){
          for(int j=1;j<=n;j++){
              // we pick the current element
              dp[i][j] = dp[i/2][j-1];
              // we ignore the current element
              dp[i][j] += dp[i-1][j];
          }
      };
    System.out.print("dp[n][m]");
  }
}
4

ניתוח מורכבות  

מורכבות זמן

O (N * M), מכיוון שהמצבים לבעיה הם אורך הרצף והמספר המרבי שניתן לשקול. לפיכך מורכבות הזמן היא פולינומית.

מורכבות בחלל

O (N * M), מכיוון שיצרנו טבלת DP דו-ממדית לאחסון תוצאות הביניים. מורכבות החלל היא גם פולינומית.