Логикалық парездеу проблемасы


Күрделілік дәрежесі қиын
Жиі кіреді Amazon LinkedIn Microsoft
Динамикалық бағдарламалау

Проблемалық мәлімдеме

«Логикалық парездеу мәселесі» бізге шын және жалған, ал олардың арасында кейбір логикалық операторлар (AND, OR, XOR) реті берілгенін айтады. Біз берілген тізбекті жақшаға айналдырудың бірнеше жолын табуымыз керек, сонда бүкіл тізбек ШЫН мәнге айналады. Берілген логикалық жақшалау мәселесінде біз «Т» -мен True және «F» арқылы жалғанға сілтеме жасаймыз.

мысал

Symbol Sequence = {T,T}

Operator Sequence = {|}
1

Түсініктеме: бұл маңызды емес мысал, мұнда тек проблеманың не туралы екенін бастау үшін көрсетілген. Сонымен, (Y | T) тізбекті жақшалаудың жалғыз әдісі бар.

Логикалық парездеу проблемасы

Symbol Sequence = {T, F, F}

Operator Sequence = {^, |}
2

Түсініктеме: Мұнда біз берілген символдар тізбегін екі жолмен жақшаға аламыз. Екі жол (T ^ (F | F)) және ((T ^ F) | F).

Логикалық жақшаға айналдыру мәселесінің әдісі

«Логикалық жақшалау мәселесі» бізге берілген операторларды пайдаланып, символдар тізбегін жақшаға айналдырудың бірнеше тәсілін табу керек, сондықтан оны реттік деңгей шындыққа айналдырады. Сонымен, бұл үшін 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)

Мұнда біз ішкі сегментті шындыққа айналдыратындай етіп жақшаға айналдырудың бірнеше жолын сақтау үшін 2D Dp массивін қолдандық. Ал екіншісі жалғанға арналған. Осылайша, бізге O (N ^ 2) полиномдық кеңістіктің күрделілігі беріледі.