حتی د لمړۍ او دوهم نیمې بټس مساوي حجم سره د دوه لمریز بائنری ترتیبونو شمیرل


مشکل کچه منځني
په مکرر ډول دننه پوښتل کیږي 24 * 7 د بدعت لیبونه ترلاسه کړئ Amazon Dell په روبل روغتيا
متحرک برنامې

ستونزه "د لمړي او دوهم نیمایی بټونو ورته مجموعې سره حتی د اوږدوالي دوه ثانیو حسابونه حساب کړئ" په ګوته کوي چې تاسو ته یو بشپړ انفرادي درکړل شوی. اوس د 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) وخت کې پرمخ وړلی شو.

د لومړۍ او دویمې نیمې بټس ورته مقدار سره حتی اوږدوالی دوه لمریز ترتیبونو د شمیرلو لپاره 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 سرنی رامینځته کړی. پدې توګه د ځای پیچلتیا هم ډیری پولی ده.

غوره چلند

غوره لاره د ستونزې لپاره د ځواب محاسبه کولو لپاره د بایومینل کوفیفینټونو کارول دي. موږ کولی شو دوه برخې نیمه خپلواک وګ considerو. بیا که دوی خپلواک وي او موږ باید په ساده ډول ځینې ټوټې وټاکو. په پام کې ونیسئ موږ اړتیا لرو چې د n بټونو څخه k k ټوټې تنظیم کړو. نو موږ کولی شو په ساده ډول د هغه کولو لارو تعداد ولیکو چې د nCk * nCk سره مساوي دي. پدې توګه که چیرې موږ دا ارزښت د k لپاره له 0 څخه تر k مساوي برابر کړو. موږ به ځواب وموم.

د لومړۍ او دویمې نیمې بټس ورته مقدار سره حتی اوږدوالی دوه لمریز ترتیبونو د شمیرلو لپاره 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)، ځکه چې د ځای پیچلتیا مستقل ده.