이진 문자열의 역전

길이가 n 인 이진 문자열에는 몇 개의 반전이 있습니까?이진 문자열의 역전

For example , n = 3 
000->0 
001->0 
010->1 
011->0 
100->2 
101->1 
110->2 
111->0 
So total inversions are 6

'전환'이란 무엇입니까? –

약간의 노력을 보여주십시오. 짐승 같은 솔루션을 만들 수 있습니까? – SergeyS

질문은 숙제처럼 보입니다. 그 이유는 나를 세부 사항을 생략하십시오. 당신은 할 수 있습니다

은 (Толя의 답변을 참조) recurrency 같은 문제를 해결
는 메이크업과 특성 방정식을 해결, 어떤 임의의 상수 (c1, c2와 가까운 공식과 솔루션을 얻을. .., cn); 사실상 당신은 단지 하나의 알 수 없게됩니다.
이 공식에 (예를 들어 f(1) = 0, f(3) = 6를) 몇 가지 알려진 솔루션을 넣고 모든 미지의 계수

당신이 가야의 마지막 대답은 (

f(n) = n*(n-1)*2**(n-3)

** 전원에 제기 의미입니다 2**(n-3)은 n-3 전력에서 2입니다. 재발행 등을 다루고 싶지 않은 경우에는 수식 으로 증명하면됩니다.

2017-01-05 11:48:49

쉽게 반복되는 기능입니다. n-1에 대한 답을 알고 있다고 가정합니다. 그리고 ato 이전의 모든 시퀀스 뒤에 0 또는 1을 첫 번째 문자로 추가합니다.

첫 번째 문자로 0을 추가하면 역전 횟수가 변경되지 않으므로 n-1과 같은 응답이됩니다.

첫 번째 문자에 1을 더하면 역전의 평균 수가 이전과 같을 것이고 여분의 역전은 이전의 모든 시퀀스에 대해 0으로 계산됩니다. 길이 n-1의 시퀀스에서 제로의 ANS 것들의

카운트가 될 것입니다 : 그들의

(n-1)*2^(n-1)

절반이 결과를 다음 줄 것이다 제로입니다

(n-1)*2^(n-2)

우리가 공식 다음과 같은 것을 의미 :

f(1) = 0 
f(n) = 2*f(n-1) + (n-1)*2^(n-2)

2017-01-05 11:29:03

조금 더 나아가'f (n) = n * (n-1) * 2^(n-3)'인 * close formula *를 얻을 수 있습니다. 한 사람이 성격 방정식을 푸는 것을 원하지 않는 경우에, 그/그녀는 단지 방정식으로 해를 증명할 수 있습니다. –

답변