முதல் மற்றும் இரண்டாம் பாதி பிட்களின் ஒரே தொகையுடன் கூட நீள பைனரி காட்சிகளை எண்ணுங்கள்


சிரமம் நிலை நடுத்தர
அடிக்கடி கேட்கப்படுகிறது 24 * 7 கண்டுபிடிப்பு ஆய்வகங்கள் அமேசான் டெல் GE ஹெல்த்கேர்
டைனமிக் புரோகிராமிங்

“முதல் மற்றும் இரண்டாம் பாதி பிட்களின் ஒரே தொகையுடன் கூட நீள பைனரி காட்சிகளை எண்ணுங்கள்” என்ற சிக்கல் உங்களுக்கு ஒரு முழு எண் கொடுக்கப்பட்டுள்ளது என்று கூறுகிறது. 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) ஆக இருக்கும்.

ஒரு சிறந்த அணுகுமுறை

ஒரு சிறந்த அணுகுமுறை சுழல்நிலை சூத்திரத்தையும் பயன்பாட்டையும் மாற்றுவதைப் பற்றி சிந்திக்க வேண்டும் டைனமிக் நிரலாக்க சிக்கலை தீர்க்க. முதல் மற்றும் இரண்டாம் பாதியில் அமைக்க வேண்டிய பிட்களின் எண்ணிக்கையை எண்ணுவதற்கு பதிலாக. வேறுபாட்டைப் பயன்படுத்தி இரு மாநிலங்களையும் ஒரே மாநிலமாகக் குறைக்க முடியும். இப்போது எங்கள் சுழல்நிலை சூத்திரம் மாற்றப்பட்டுள்ளது, எனவே எங்கள் நேர சிக்கலானது மற்றும் விண்வெளி சிக்கலானது. O (N ^ 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), ஏனெனில் சிக்கலில் N ^ 2 வெவ்வேறு மாநிலங்கள் இருந்தன. இதனால் நேர சிக்கலானது பல்லுறுப்புக்கோவை.

விண்வெளி சிக்கலானது

ஓ (என் ^ 2), ஏனெனில் நாங்கள் 2D டிபி வரிசையை உருவாக்கியுள்ளோம். இதனால் விண்வெளி சிக்கலானது பல்லுறுப்புக்கோவையாகும்.

சிறந்த அணுகுமுறை

சிக்கலுக்கான பதிலைக் கணக்கிட பைனோமியல் குணகங்களைப் பயன்படுத்துவதே சிறந்த அணுகுமுறை. இரண்டு பகுதிகளையும் நாம் சுயாதீனமாக கருதலாம். அவர்கள் சுயாதீனமாக இருந்தால், நாங்கள் சில பிட்களை அமைக்க வேண்டும். நாம் n பிட்களில் இருந்து k பிட்களை அமைக்க வேண்டும் என்பதைக் கவனியுங்கள். எனவே nCk * nCk க்கு சமமான வழிகளின் எண்ணிக்கையை நாம் வெறுமனே எழுதலாம். எனவே இந்த மதிப்பை k க்கு 0 க்கு சமமாக 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

சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (என்), N வரை ஒற்றை வளையத்தை இயக்கியுள்ளோம். இதனால் வழிமுறை நேரியல் நேர சிக்கலைக் கொண்டுள்ளது.

விண்வெளி சிக்கலானது

ஓ (1), ஏனெனில் விண்வெளி சிக்கலானது நிலையானது.