Q9.11 count the number of ways of parenthesizing the expression

Q:Given a boolean expression consisting of the symbols 0,1, &,/, and A, and a desired boolean result value result, implement a function to count the number of ways of parenthesizing the expression such that it evaluates to result.
A:문제에 귀착해서 현재 문제와 하위 문제의 관계를 찾습니다.
표현식에 괄호를 붙여 하위 문제로 구분합니다.
예를 들어 f(1&0&1|1,true) = f(1&0&1|1),true)+f(1&0)&(1|1),true)+f(1&0&1)|1,true).이 예를 통해 구분 규칙을 정리하고 문제를 두 부분으로 나눌 수 있다. i와 n-i, 그 중에서 i는 1과 0의 개수를 가리키고, n은 전체 표현식에서 1과 0의 개수를 가리키며, i=1, 2...n-1.
더 나아가 진가표를 다시 이용하면 전체 개수를 구할 수 있다.

#include 
#include 
#include 
using namespace std;

typedef map mi;

int placeParen(string exp, int result, int start, int end, mi &Map){
	int key = result*200 + start*7 + end*3;
	if (Map.count(key))
		return Map[key];
	if (start == end) {
		if (exp[start] == '1' && result == 1)
			return 1;
		else if (exp[start] == '0' && result == 0)
			return 1;
		return 0;
	}
	int c=0;
	if (result) {
		for (int i = start + 1; i < end; i+=2) {
			char op = exp[i];
			if (op == '&')
				c += placeParen(exp, 1, start, i-1, Map) * placeParen(exp, 1, i+1, end, Map);
			else if (op == '|') {
				c += placeParen(exp, 1, start, i-1, Map) * placeParen(exp, 0, i+1, end, Map);
				c += placeParen(exp, 0, start, i-1, Map) * placeParen(exp, 1, i+1, end, Map);
				c += placeParen(exp, 1,start, i-1, Map) * placeParen(exp, 1, i+1, end, Map);
			}
			else if (op == '^' ) {
				c += placeParen(exp, 1, start, i-1, Map) * placeParen(exp, 0, i+1, end, Map);
				c += placeParen(exp, 0, start, i-1, Map) * placeParen(exp, 1, i+1, end, Map);
			}
		}
	}
	else{
		for (int i = start + 1; i < end; i+=2) {
			char op = exp[i];
			if (op == '&') {
				c += placeParen(exp, 0, start, i-1, Map) * placeParen(exp, 1, i+1, end, Map);
				c += placeParen(exp, 1, start, i-1, Map) * placeParen(exp, 0, i+1, end, Map);
				c += placeParen(exp, 0, start, i-1, Map) * placeParen(exp, 0, i+1, end, Map);
			}
			else if (op == '|')
				c += placeParen(exp, 0, start, i-1, Map) * placeParen(exp, 0, i+1, end, Map);
			else if (op == '^' ) {
				c += placeParen(exp, 1, start, i-1, Map) * placeParen(exp, 1, i+1, end, Map);
				c += placeParen(exp, 0, start, i-1, Map) * placeParen(exp, 0, i+1, end, Map);
			}
		}
	}
	Map[key] = c;
	return c;
}

int main(){
	mi Map;
	string s = "1&0&1|1";
	cout<

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

슬 래 그 기초: Hawtein 학 Cracking the coding 인터뷰 비교 (3)

제목 은 isSubstring 함 수 를 한 번 사용 하면 s2 가 s1 의 회전 문자열 인지 판단 할 수 있 습 니 다. 하위 문자열 관계 가 전혀 존재 하지 않 기 때 문 입 니 다.문 자 를 계속 회전 시 킨 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

Q9.11 count the number of ways of parenthesizing the expression

좋은 웹페이지 즐겨찾기