string - 二进制字符串中的反转

Question

长度为 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

Answer 1

这个问题看起来像一个家庭作业，这就是为什么让我省略细节。你可以：

1. 以递归方式解决问题（请参阅Толя的答案）
2. 组成并求解特征方程，得到解为具有任意常数（, , ..., ）的闭式；事实上，你只会得到一个未知常数。c1c2cn
3. 将一些已知解（例如f(1) = 0，f(3) = 6）代入公式，找出所有未知系数

你应该得到的最终答案是

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

其中**意味着上台（2**(n-3)掌权2）n-3。如果您不想处理 recurrency 之类的东西，您可以通过归纳证明公式。

Answer 2

这是简单的循环功能。假设我们知道 n-1 的答案。在所有之前的序列之后，我们添加 0 或 1 作为第一个字符。

如果我们添加 0 作为第一个字符，这意味着反转计数不会改变：因此答案将与 n-1 相同。

如果我们将 1 作为第一个字符添加，则意味着反转计数将与以前相同，并且将在所有先前的序列中添加额外的反转等于 0 的计数。

长度序列中的零和一的计数n-1将是：

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

其中一半是零，它将给出以下结果

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

这意味着我们有以下公式：

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