প্রথম এবং দ্বিতীয়ার্ধের বিটগুলির সমতুল্য সমান দৈর্ঘ্যের বাইনারি ক্রমগুলি গণনা করুন


কাঠিন্য মাত্রা মধ্যম
প্রায়শই জিজ্ঞাসা করা হয় 24 * 7 ইনোভেশন ল্যাব মর্দানী স্ত্রীলোক উপত্যকা জিই হেলথকেয়ার
ডায়নামিক প্রোগ্রামিং

সমস্যাটি "প্রথম এবং দ্বিতীয়ার্ধের বিটগুলির সমতুল্য সমান দৈর্ঘ্যের বাইনারি ক্রমগুলি গণনা করুন" আপনাকে জানায় যে আপনাকে একটি পূর্ণসংখ্যা দেওয়া হয়েছে। এখন আকার 2 * n এর বাইনারি সিকোয়েন্স তৈরির উপায়গুলির সন্ধান করুন যেমন প্রথমার্ধ এবং দ্বিতীয়ার্ধে সেট সংখ্যার সমান সংখ্যা রয়েছে।

প্রথম এবং দ্বিতীয়ার্ধের বিটগুলির সমতুল্য সমান দৈর্ঘ্যের বাইনারি ক্রমগুলি গণনা করুন

উদাহরণ

2
6

ব্যাখ্যা

বাইনারি সিকোয়েন্সগুলি হল 0000, 1001, 1010, 0110, 0101, 1111. সুতরাং মোট গণনা 1।

অভিগমন

নিষ্পাপ দৃষ্টিভঙ্গি

সমস্যাটি সমাধানের একটি উপায় পুনরাবৃত্তি ব্যবহার করা। সুতরাং, আমরা উভয় অর্ধে সেট করতে হবে বিট সংখ্যা ট্র্যাক করব। সুতরাং সমাধানটি 3 রাষ্ট্রীয় সমাধান is রাজ্যগুলি হ'ল বিটের সংখ্যা যা প্রথমার্ধে নির্ধারণ করা দরকার, দ্বিতীয়ার্ধে সেট করতে থাকা বিটের সংখ্যা, বিট বিড়াল সংখ্যা। একটি সাধারণ পুনরাবৃত্তি সমাধান নীচের কোডে দেখানো মত দেখতে হবে।

#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;
    }
}

সমাধানটি ঠিক আছে তবে অত্যন্ত অদক্ষ। এভাবে সময়ের জটিলতা উন্নতি করতে হবে। আমরা ব্যবহার করতে পারি ডায়নামিক প্রোগ্রামিং। তবে এখনও তিনটি রাজ্যের কারণে সময় জটিলতা হবে (N ^ 3)।

একটি ভাল পদ্ধতির

পুনরাবৃত্তির সূত্র পরিবর্তন এবং ব্যবহারের বিষয়ে চিন্তাভাবনা করা আরও ভাল পদ্ধতির হবে গতিশীল প্রোগ্রামিং সমস্যাটি সমাধান করতে. প্রথম এবং দ্বিতীয়ার্ধে বিটের সংখ্যা নির্ধারণের পরিবর্তে গণনা রাখুন। পার্থক্যটি ব্যবহার করে আমরা উভয় রাজ্যকে একক রাজ্যে হ্রাস করতে পারি। এখন আমাদের পুনরাবৃত্তির সূত্রটি পরিবর্তিত হয়েছে এবং তাই আমাদের সময়ের জটিলতা এবং স্পেস জটিলতা। আমরা একটি সমাধান লিখতে পারি যা ও (এন ^ 2) সময়ে চলতে পারে।

প্রথম এবং দ্বিতীয়ার্ধের বিটগুলির সমতুল্য সমান দৈর্ঘ্যের বাইনারি ক্রমগুলি গণনা করতে সি ++ কোড

#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

জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (এন ^ 2), কারণ সমস্যাটিতে এন ^ 2 বিভিন্ন রাজ্য ছিল। সুতরাং সময় জটিলতা বহুপদী।

স্পেস জটিলতা ity

ও (এন ^ 2), কারণ আমরা একটি 2D ডিপি অ্যারে তৈরি করেছি। সুতরাং স্থান জটিলতাও বহুপদী।

সেরা পন্থা

সমস্যার জন্য উত্তরটি গণনা করার জন্য দ্বিপদী সহগ ব্যবহার করা সর্বোত্তম পদ্ধতির। আমরা দুটি অংশকে স্বাধীন বলে বিবেচনা করতে পারি। তারপরে যদি তারা স্বাধীন হয় এবং আমাদের কেবল কিছু বিট সেট করতে হয়। এন বিটগুলির বাইরে আমাদের কে বিট সেট করতে হবে তা বিবেচনা করুন। সুতরাং আমরা কীভাবে এনসি কে * এনসিকে সমান তার বিভিন্ন পদ্ধতি লিখতে পারি। সুতরাং আমরা যদি k এর সমান 0 থেকে k সমান n এর মানটি গণনা করি। আমরা উত্তর খুঁজে পেতে হবে।

প্রথম এবং দ্বিতীয়ার্ধের বিটগুলির সমতুল্য সমান দৈর্ঘ্যের বাইনারি ক্রমগুলি গণনা করতে সি ++ কোড

#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

জটিলতা বিশ্লেষণ

সময় জটিলতা

চালু), কারণ আমরা এন পর্যন্ত একটি লুপ চালিয়েছি Thus সুতরাং অ্যালগরিদমের রৈখিক সময়ের জটিলতা রয়েছে।

স্পেস জটিলতা ity

ও (1), কারণ স্থান জটিলতা ধ্রুবক।