عد متواليات ثنائية الطول بنفس مجموع بتات النصف الأول والثاني  


مستوى الصعوبة متوسط
كثيرا ما يطلب في 24 * 7 معامل ابتكار أمازون ديل جنرال إلكتريك للرعاية الصحية
البرمجة الديناميكية

توضح مشكلة "عد المتواليات الثنائية ذات الطول الزوجي بنفس مجموع النصف الأول والثاني من البتات" أنك تحصل على عدد صحيح. اكتشف الآن عدد الطرق لإنشاء تسلسل ثنائي بالحجم 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

تحليل التعقيد

تعقيد الوقت

يا (N ^ 2) ، نظرًا لوجود حالات مختلفة لـ N ^ 2 في المشكلة. وبالتالي فإن تعقيد الوقت هو متعدد الحدود.

تعقيد الفضاء

يا (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. وبالتالي فإن الخوارزمية لها تعقيد زمني خطي.

تعقيد الفضاء

يا (1)، لأن تعقيد الفضاء ثابت.