Броји бинарне секвенце једнаке дужине са истим збиром прве и друге половине битова  


Ниво тешкоће Средњи
Често питани у 24 * 7 лабораторија за иновације амазонка Шумовита долина ГЕ Хеалтхцаре
Динамичко програмирање

Проблем „Броји бинарне секвенце парне дужине са истим збиром прве и друге половине битова“ наводи да сте добили цео број. Сада сазнајте број начина за конструисање бинарног низа величине 2 * н тако да прва половина и друга половина имају исти број постављених битова.

Броји бинарне секвенце једнаке дужине са истим збиром прве и друге половине битоваПин

Пример  

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) због три стања.

Види такође
Пронађите да ли постоји подред са 0 збиром

Бољи приступ

Бољи приступ биће размишљање о промени рекурзивне формуле и употребе динамичко програмирање за решавање проблема. Уместо да се броји број битова који се поставља у првом и другом полувремену. Помоћу разлике можемо обе државе свести у једно стање. Сада је наша рекурзивна формула промењена, а тиме и наша временска сложеност и сложеност простора. Можемо написати решење које може да се покрене за О (Н ^ 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 различита стања. Стога је временска сложеност полиномна.

Сложеност простора

О (Н ^ 2), јер смо креирали 2Д ДП низ. Стога је сложеност простора такође полином.

Види такође
Збир подмреже максималне величине једнак је к

Најбољи приступ

Најбољи приступ је коришћење биномних коефицијената за израчунавање одговора на проблем. Ове две половине можемо сматрати независним. Онда ако су независни и једноставно морамо да поставимо неке битове. Узмите у обзир да треба да поставимо к битова од н битова. Тако можемо једноставно написати број начина за то који је једнак нЦк * нЦк. Дакле, ако израчунамо ову вредност за к једнако 0 до к једнако н. Пронашли бисмо одговор.

Ц ++ код за бројање бинарних секвенци парне дужине са истим збиром прве и друге половине битова

#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

Анализа сложености

Сложеност времена

НА), јер смо водили једну петљу до Н. Дакле, алгоритам има линеарну временску сложеност.

Сложеност простора

О (1), јер је сложеност простора константна.