Лагічная праблема дужак


Узровень складанасці Жорсткі
Часта пытаюцца ў амазонка LinkedIn Microsoft
Дынамічнае праграмаванне

Пастаноўка праблемы

«Булевая праблема дужак» сцвярджае, што нам даецца паслядоўнасць праўдзівага і ілжывага, а паміж імі - некаторыя лагічныя аператары (І, АБО, XOR). Нам трэба знайсці колькасць спосабаў уключэння дадзенай паслядоўнасці ў дужкі, каб уся паслядоўнасць атрымала TRUE. У дадзенай задачы лагічнай дужкі мы будзем называць "True", выкарыстоўваючы "T", і False, выкарыстоўваючы "F".

Прыклад

Symbol Sequence = {T,T}

Operator Sequence = {|}
1

Тлумачэнне: Гэта банальны прыклад, які прыведзены тут толькі для таго, каб пачаць працу з праблемай. Такім чынам, існуе толькі адзін спосаб увядзення ў дужкі паслядоўнасці. Гэта (Y | T).

Лагічная праблема дужак

Symbol Sequence = {T, F, F}

Operator Sequence = {^, |}
2

Тлумачэнне: Тут мы можам заключыць у круглыя ​​дужкі зададзеную паслядоўнасць сімвалаў двума спосабамі. Два шляхі: (T ^ (F | F)) і ((T ^ F) | F).

Падыход да праблемы лагічнай дужкі

«Булевая праблема дужак» сцвярджае, што нам трэба знайсці колькасць спосабаў уключэння ў сімвал паслядоўнасці сімвалаў з выкарыстаннем зададзеных аператараў, каб паслядоўнасць ацэньвала яе ў сапраўдную. Такім чынам, для гэтага мы створым два 2D-масівы, адзін для захоўвання колькасці спосабаў уключэння ў дужкі сегмента паслядоўнасці ад i да j, што прывядзе да ісціны. Падобным чынам іншы 2D-масіў пазначае тое ж самае, але сегмент прыводзіць да ілжывага. Пры вырашэнні нам трэба вырашаць падзадачы некалькі разоў. Такім чынам, мы спрабуем выкарыстоўваць Дынамічнае праграмаванне для вырашэння гэтай праблемы.

Праблема падобная на Задача множання матрычных ланцугоў, дзе спачатку мы вырашаем меншыя падзадачы (i, e, меншыя адрэзкі). І аб'яднаўшы вынік, мы знаходзім адказ на першапачатковую праблему. Так як мы выкарыстоўваем Дынамічнае праграмаванне падыход, у нас павінны быць некаторыя базавыя выпадкі. Асноўныя выпадкі - гэта адрэзкі даўжыні = 1. Такім чынам, мы запоўнім матрыцу T і матрыцу F адпаведна. Калі мы вырашаем вялікія падзадачы, аб'ядноўваючы меншыя. Мы будзем прытрымлівацца пэўных правілаў, якія наступныя.

Лагічная праблема дужак

код

Код C ++ для праблемы лагічнай дужкі

#include<bits/stdc++.h>
using namespace std; 

int waysToParenthesize(string symbolSequence, string operatorSequence) 
{
    int n = symbolSequence.size();
  int T[n][n], F[n][n];
  memset(T, 0 ,sizeof T);
  memset(F, 0, sizeof F);
  
  //base case 
  for(int i=0;i<n;i++)
        if(symbolSequence[i] == 'T')
            T[i][i] = 1, F[i][i] = 0;
        else
            T[i][i] = 0, F[i][i] = 1;

    // Now solve the subproblems in bottom up manner
  for(int len=2;len<=n;len++)
  {
    for(int i=0;i<=n-len;i++) 
    {
        int j = i+len-1;
      T[i][j] = F[i][j] = 0;
      
      //Index of placing brackets
      for(int k=i;k<j;k++)
      {
        int waysik = T[i][k] + F[i][k]; 
        int wayskj = T[k+1][j] + F[k+1][j]; 
        if(operatorSequence[k] == '&') 
        { 
          T[i][j] += T[i][k]*T[k+1][j]; 
          F[i][j] += (waysik*wayskj - T[i][k]*T[k+1][j]); 
        } 
        else if(operatorSequence[k] == '|')
        { 
          F[i][j] += F[i][k]*F[k+1][j]; 
          T[i][j] += (waysik*wayskj - F[i][k]*F[k+1][j]); 
        } 
        else if(operatorSequence[k] == '^') 
        { 
          T[i][j] += F[i][k]*T[k+1][j] + T[i][k]*F[k+1][j]; 
          F[i][j] += T[i][k]*T[k+1][j] + F[i][k]*F[k+1][j]; 
        }
      } 
    } 
  }
  return T[0][n-1]; 
} 

int main() 
{
    string symbolSequence="";
    string operatorSequence="";
    cin>>symbolSequence>>operatorSequence;
    cout<<waysToParenthesize(symbolSequence, operatorSequence)<<endl;
} 
TTFT
|&^
4

Код Java для праблемы лагічнай дужкі

import java.util.*;

class Main{
    
    static int waysToParenthesize(String symbolSequence, String operatorSequence) 
    {
        int n = symbolSequence.length();
    	int T[][] = new int[n][n];
    	int F[][] = new int[n][n];
    	for(int i=0;i<n;i++){
    	    for(int j=0;j<n;j++){
    	        T[i][j] = 0;
    	        F[i][j] = 0;
    	    }
    	}
    	
    	//base case
    	for(int i=0;i<n;i++){
            if(symbolSequence.charAt(i) == 'T'){
                T[i][i] = 1;
                F[i][i] = 0;
            }
            else{
                T[i][i] = 0;
                F[i][i] = 1;   
            }
    	}
    
        // Now solve the subproblems in bottom up manner
    	for(int len=2;len<=n;len++)
    	{
    		for(int i=0;i<=n-len;i++) 
    		{
    		    int j = i+len-1;
    			T[i][j] = 0;
    			F[i][j] = 0;
    			
    			//Index of placing brackets
    			for(int k=i;k<j;k++)
    			{
    				int waysik = T[i][k] + F[i][k]; 
    				int wayskj = T[k+1][j] + F[k+1][j]; 
    				if(operatorSequence.charAt(k) == '&') 
    				{ 
    					T[i][j] += T[i][k]*T[k+1][j]; 
    					F[i][j] += (waysik*wayskj - T[i][k]*T[k+1][j]); 
    				} 
    				else if(operatorSequence.charAt(k) == '|')
    				{ 
    					F[i][j] += F[i][k]*F[k+1][j]; 
    					T[i][j] += (waysik*wayskj - F[i][k]*F[k+1][j]); 
    				} 
    				else if(operatorSequence.charAt(k) == '^') 
    				{ 
    					T[i][j] += F[i][k]*T[k+1][j] + T[i][k]*F[k+1][j]; 
    					F[i][j] += T[i][k]*T[k+1][j] + F[i][k]*F[k+1][j]; 
    				}
    			} 
    		} 
    	}
    	return T[0][n-1]; 
    } 
    
    
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        String symbolSequence = sc.next();
        String operatorSequence = sc.next();
    	int ans = waysToParenthesize(symbolSequence, operatorSequence);
    	System.out.println(ans);
    }
}
TTFT
|&^
4

Аналіз складанасці

Складанасць часу: O (N ^ 3)

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

Касмічная складанасць: O (N ^ 2)

Тут мы выкарысталі 2 2D Dp масівы, адзін для захоўвання колькасці спосабаў укласці ў падрабрынкі такі сегмент, каб ён прывёў да ісціны. А другі за Ілжывы. Такім чынам, мы атрымліваем шматзначную прасторавую складанасць O (N ^ 2).