숫자 문자열을 0으로 계산하려면 +/-를 추가하십시오.

숫자로 구성된 문자열이 주어지면 + 또는 - 부호를 추가하여 표현식 값을 0으로 만드십시오. 표현식을 리턴하십시오. 예를 들어 숫자 문자열을 0으로 계산하려면 +/-를 추가하십시오.

123 => 1 + 2-3 = 0

173,956 => 17 + 39-56 =

0 I가 아닌 이러한 문제를 해결하기 위해 어떠한 단서가없는 brute-force way.

의견이 있습니까?

당신은 예를 들어, 나무

로를 구조하는 경우 분명하게 재귀 적 방법을 사용하여 예를 들어 여러 가지 방법으로 그것을 해결할 수

출처

2012-10-18 StarPinkER

아마도 http://math.stackexchange.com이이 질문에 더 좋은 곳이 될 것입니다. – Uooo

동적 프로그래밍을 사용하여 해결 했습니까? – stackoverflowery

동적 프로그래밍을 시도했지만 최적의 하부 구조를 얻는 것이 약간 어렵습니다. – StarPinkER

이 검색 문제입니다. 솔루션 공간에서 검색을 수행해야합니다. '123'문자열에서 시작하여 '1'다음에 + 또는 - 기호를 추가 할 수 있으며 '1 + 23'또는 '1 - 23'이 표시됩니다. 모든 변형은 다음 문자 다음에 부호를 추가하여 더 멀리 나눌 수 있습니다. 결과적으로 가능한 모든 기호 추가는 트리 구조와 같은 솔루션 공간을 형성합니다. 알고리즘은이 구조에서 솔루션을 검색해야합니다. A *를 사용하여이 작업을 수행 할 수 있다고 생각합니다.

Anders K 솔루션 공간의 멋진 ASCII 그래프를 그리면 솔루션을 검색하면됩니다. 간단한 너비 우선 검색이나 깊이 우선 검색은 작업을 수행 할 수 있지만 솔루션 공간이 클 경우 느려질 것이라고 생각합니다.

또한 솔루션 공간의 속성을 이용하는보다 최적의 특정 솔루션을 찾을 수 있다고 생각합니다. 예를 들어 트리 구조입니다.

출처

2012-10-18 06:22:27 Lazin

고마워요,하지만 앤더스 케이가 하나의 지점을 놓친 것 같아요, 맞습니까? – StarPinkER

예. 그렇다면 솔루션 공간이 그래프가됩니다. – Lazin

숫자의 자리 (+|-) 후 두 개의 서로 다른 징후가있을 수 있기 때문에 :

 1 
    /\ 
     + - 
    / \ 
    2  2 
/\ /\ 
    + - + - 
    | | | | 
    3 3 3 3

출처

2012-10-18 06:21:51

숫자 문자열을 0으로 계산하려면 +/-를 추가하십시오.

답변

관련 문제