پہلے اور دوسرے نصف بٹس کی ایک ہی رقم کے ساتھ لمبائی بائنری ترتیب کو بھی گنیں


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے 24 * 7 انوویشن لیبز ایمیزون ڈیل GE صحت کا خیال
متحرک پروگرامنگ

مسئلہ "پہلے اور دوسرے نصف بٹس کی ایک ہی رقم کے ساتھ لمبائی بائنری سلسلوں کی گنتی کرو" یہ بتاتا ہے کہ آپ کو ایک عدد اعداد دی جاتی ہے۔ اب سائز 2 * n کے بائنری ترتیب کی تعمیر کے ل ways طریقے معلوم کریں جیسے پہلے نصف اور دوسرے نصف حصے میں ایک جیسے تعداد میں سیٹ بٹس ہوں۔

پہلے اور دوسرے نصف بٹس کی ایک ہی رقم کے ساتھ لمبائی بائنری ترتیب کو بھی گنیں

مثال کے طور پر

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) ہوگی۔

ایک بہتر نقطہ نظر

تکرار فارمولے اور استعمال کو تبدیل کرنے کے بارے میں سوچنے کے لئے ایک بہتر نقطہ نظر ہوگا متحرک پروگرامنگ مسئلے کو حل کرنے کے ل. بٹس کی تعداد کو پہلے اور دوسرے نصف حصے میں رکھنے کے بجائے گنتی رکھیں۔ ہم فرق کو استعمال کرتے ہوئے دونوں ریاستوں کو ایک ہی ریاست میں گھٹا سکتے ہیں۔ اب ہمارا بار بار چلنے والا فارمولا تبدیل ہوگیا ہے اور اسی طرح ہمارے وقت کی پیچیدگی اور جگہ کی پیچیدگی ہے۔ ہم ایک ایسا حل لکھ سکتے ہیں جو او (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

پہلے اور دوسرے نصف بٹس کی ایک ہی رقم کے ساتھ بھی لمبائی بائنری ترتیب گننے کے لئے جاوا کوڈ

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)، کیونکہ ہم نے 2D DP صف تیار کی ہے۔ اس طرح خلائی پیچیدگی بھی متعدد ہے۔

بہترین نقطہ نظر

مسئلے کے جواب کی گنتی کرنے کے لئے بہترین نقطہ نظر بائنومیئل کوفیفیئنٹس کا استعمال کرنا ہے۔ ہم دو حصوں کو خود مختار سمجھ سکتے ہیں۔ پھر اگر وہ آزاد ہیں اور ہمیں کچھ بٹس لگانا ہوں گے۔ غور کریں ہمیں 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

پہلے اور دوسرے نصف بٹس کی ایک ہی رقم کے ساتھ بھی لمبائی بائنری ترتیب گننے کے لئے جاوا کوڈ

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)، کیونکہ جگہ کی پیچیدگی مستقل ہے۔