ಮೊದಲ ಮತ್ತು ದ್ವಿತೀಯಾರ್ಧದ ಒಂದೇ ಮೊತ್ತದೊಂದಿಗೆ ಇನ್ನೂ ಉದ್ದದ ಬೈನರಿ ಅನುಕ್ರಮಗಳನ್ನು ಎಣಿಸಿ


ತೊಂದರೆ ಮಟ್ಟ ಮಧ್ಯಮ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ 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;
    }
}

ಪರಿಹಾರವು ಉತ್ತಮವಾಗಿದೆ ಆದರೆ ಹೆಚ್ಚು ಅಸಮರ್ಥವಾಗಿದೆ. ಹೀಗಾಗಿ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯನ್ನು ಸುಧಾರಿಸಲು. ನಾವು ಬಳಸಬಹುದು ಡೈನಾಮಿಕ್ ಪ್ರೊಗ್ರಾಮಿಂಗ್. ಆದರೆ ಇನ್ನೂ ಮೂರು ರಾಜ್ಯಗಳ ಕಾರಣದಿಂದಾಗಿ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು ಒ (ಎನ್ ^ 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), ಏಕೆಂದರೆ ನಾವು 2 ಡಿ ಡಿಪಿ ರಚನೆಯನ್ನು ರಚಿಸಿದ್ದೇವೆ. ಹೀಗಾಗಿ ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆಯು ಬಹುಪದೀಯವಾಗಿದೆ.

ಅತ್ಯುತ್ತಮ ಅಪ್ರೋಚ್

ಸಮಸ್ಯೆಯ ಉತ್ತರವನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡಲು ದ್ವಿಪದ ಗುಣಾಂಕಗಳನ್ನು ಬಳಸುವುದು ಉತ್ತಮ ವಿಧಾನವಾಗಿದೆ. ನಾವು ಎರಡು ಭಾಗಗಳನ್ನು ಸ್ವತಂತ್ರವೆಂದು ಪರಿಗಣಿಸಬಹುದು. ನಂತರ ಅವರು ಸ್ವತಂತ್ರರಾಗಿದ್ದರೆ ಮತ್ತು ನಾವು ಕೆಲವು ಬಿಟ್‌ಗಳನ್ನು ಹೊಂದಿಸಬೇಕಾಗುತ್ತದೆ. ನಾವು n ಬಿಟ್‌ಗಳಿಂದ k ಬಿಟ್‌ಗಳನ್ನು ಹೊಂದಿಸಬೇಕಾಗಿದೆ ಎಂದು ಪರಿಗಣಿಸಿ. ಆದ್ದರಿಂದ ನಾವು ಅದನ್ನು ಮಾಡಲು nCk * nCk ಗೆ ಸಮಾನವಾದ ಮಾರ್ಗಗಳ ಸಂಖ್ಯೆಯನ್ನು ಬರೆಯಬಹುದು. ಹೀಗೆ ನಾವು ಈ ಮೌಲ್ಯವನ್ನು 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

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್), ಏಕೆಂದರೆ ನಾವು N ವರೆಗೆ ಒಂದೇ ಲೂಪ್ ಅನ್ನು ಓಡಿಸಿದ್ದೇವೆ. ಹೀಗೆ ಅಲ್ಗಾರಿದಮ್ ರೇಖೀಯ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯನ್ನು ಹೊಂದಿರುತ್ತದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (1), ಏಕೆಂದರೆ ಸ್ಥಳದ ಸಂಕೀರ್ಣತೆ ಸ್ಥಿರವಾಗಿರುತ್ತದೆ.