ספרו רצפים בינאריים באורך אפילו עם אותו סכום של ביטים במחצית הראשונה והשנייה  


רמת קושי בינוני
נשאל לעתים קרובות מעבדות חדשנות 24 * 7 אמזון בעברית Dell GE Healthcare
תכנות דינמי

הבעיה "ספרו רצפים בינאריים באורך אפילו עם סכום זהה של סיביות מחצית ראשונה ושניה" קובעת שקיבלתם מספר שלם. כעת גלה את מספר הדרכים לבניית רצף בינארי בגודל 2 * n כך שבמחצית הראשונה ובמחצית השנייה יש מספר זהה של סיביות.

ספרו רצפים בינאריים באורך אפילו עם אותו סכום של ביטים במחצית הראשונה והשנייהאורן

דוגמה  

2
6

הסבר

הרצפים הבינאריים הם 0000, 1001, 1010, 0110, 0101, 1111. לפיכך הספירה הכוללת היא 1.

גישה  

גישה נאיבית

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

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

int n;
int rec(int a, int b, int i){
    if(i == n)
        if(a == 0 && b == 0)
            return 1;
        else
            return 0;
    return rec(a-1, b-1, i+1) + rec(a-1, b, i+1) + rec(a, b-1, i+1) + rec(a, b, i+1);
}

int main(){
    int t;cin>>t;
    while(t--){
        cin>>n;
        int ans = 0;
        for(int i=0;i<=n;i++)
            ans += rec(i, i, 0);
        cout<<ans;
    }
}

הפיתרון הוא בסדר אבל הוא מאוד לא יעיל. כך כדי לשפר את מורכבות הזמן. אנחנו יכולים להשתמש תכנות דינמי. אך עדיין מורכבות הזמן תהיה O (N ^ 3) בגלל שלוש המדינות.

ראה גם
מצא אם יש תת-מערך עם סכום 0

גישה טובה יותר

גישה טובה יותר תהיה לחשוב על שינוי הנוסחה והשימוש הרקורסיבי תכנות דינמי לפתור את הבעיה. במקום לשמור על ספירת מספר הביטים שנקבעו במחצית הראשונה והשנייה. אנו יכולים להפחית את שתי המדינות למצב יחיד באמצעות ההבדל. כעת הנוסחה הרקורסיבית שלנו משתנה וכך מורכבות הזמן שלנו ומורכבות החלל. אנו יכולים לכתוב פיתרון שיכול לרוץ בזמן O (N ^ 2).

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

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

int n;
int rec(int diff, int i, vector<vector<int>> &dp){
    if(i == n)
        if(diff == 0)
            return 1;
        else
            return 0;
    if(dp[diff+n][i] != -1)
        return dp[diff+n][i];
    return dp[diff+n][i] = rec(diff+1, i+1, dp) + rec(diff-1, i+1, dp) + 2*rec(diff, i+1, dp);
}

int main(){
    cin>>n;
    vector<vector<int>> dp(2*n+2, vector<int>(n+1, -1));
    int ans = rec(0, 0, dp);
    cout<<ans;
}
6
924

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

import java.util.*;

class Main{
  static int n;
  static int rec(int diff, int i, int dp[][]){
      if(i == n)
          if(diff == 0)
              return 1;
          else
              return 0;
      if(dp[diff+n][i] != -1)
          return dp[diff+n][i];
      return dp[diff+n][i] = rec(diff+1, i+1, dp) + rec(diff-1, i+1, dp) + 2*rec(diff, i+1, dp);
  }
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
      n = sc.nextInt();
      int dp[][] = new int[2*n+2][n+1];
      for(int i=0;i<2*n+2;i++){
      	for(int j=0;j<n+1;j++)
      		dp[i][j] = -1;
      }
      int ans = rec(0, 0, dp);
      System.out.print(ans);
  }
}
6
924

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

מורכבות זמן

O (N ^ 2), בגלל שהיו N ^ 2 מצבים שונים בבעיה. לפיכך מורכבות הזמן היא פולינומית.

מורכבות בחלל

O (N ^ 2), כי יצרנו מערך DP דו-ממדי. לפיכך מורכבות החלל היא גם פולינומית.

ראה גם
גודל מערך משנה מקסימלי שווה ל- k

הגישה הטובה ביותר

הגישה הטובה ביותר היא להשתמש במקדמים בינומיים לחישוב התשובה לבעיה. אנו יכולים לראות בשני החצאים עצמאים. ואז אם הם עצמאיים ואנחנו פשוט צריכים להגדיר כמה סיביות. שקול שעלינו לקבוע ביטים k מתוך n ביטים. אז אנחנו יכולים פשוט לכתוב את מספר הדרכים לעשות את זה שווה ל- nCk * nCk. לכן אם נחשב ערך זה עבור k השווה ל- 0 ל- k השווה ל- n. היינו מוצאים את התשובה.

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

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

int main(){
    int n;cin>>n;
    int C = 1, answer = 1;
    for (int i = 1; i<=n ; i++)
    {
        C = (C * (n+1-i))/i;
        answer += (C*C);
    }
    cout<<answer;
}
6
924

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

import java.util.*;

class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int answer = 1, C = 1;
      for(int i = 1; i<=n; i++)
      {
          C = (C * (n+1-i))/i;
          answer += (C*C);
      }
      System.out.print(answer);
  }
}
6
924

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

מורכבות זמן

O (N) מכיוון שהפעלנו לולאה אחת עד N. לפיכך לאלגוריתם יש מורכבות זמן ליניארית.

מורכבות בחלל

O (1), כי מורכבות החלל קבועה.