Падлічыце двайковыя паслядоўнасці з роўнай даўжынёй з аднолькавай сумай першай і другой паловы бітаў


Узровень складанасці серада
Часта пытаюцца ў 24 * 7 інавацыйныя лабараторыі амазонка Dell GE Healthcare
Дынамічнае праграмаванне

У задачы «Падлічыць бінарныя паслядоўнасці нават роўнай даўжыні з аднолькавай сумай першай і другой паловы бітаў» гаворыцца, што вам дадзена цэлае лік. Цяпер высветліце колькасць спосабаў пабудовы двайковай паслядоўнасці памерам 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

Код Java для падліку двайковых паслядоўнасцей з роўнай даўжынёй з аднолькавай сумай першай і другой паловы бітаў

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. Такім чынам, касмічная складанасць таксама мнагачленная.

Лепшы падыход

Лепшы падыход - выкарыстанне бінаміальных каэфіцыентаў для вылічэння адказу на задачу. Мы можам лічыць дзве паловы незалежнымі. Тады, калі яны незалежныя, і нам проста трэба ўсталяваць некалькі бітаў. Падумайце, нам трэба ўсталяваць k бітаў з n бітаў. Такім чынам, мы можам проста запісаць колькасць спосабаў зрабіць гэта роўным nCk * nCk. Такім чынам, калі мы вылічым гэтае значэнне для k, роўнага 0, каб k роўна n. Мы б знайшлі адказ.

Код 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

Код Java для падліку двайковых паслядоўнасцей з роўнай даўжынёй з аднолькавай сумай першай і другой паловы бітаў

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), таму што касмічная складанасць пастаянная.