假设我们有 n 个元素，a1, a2, ..., an，排列成一个圆圈。即a2在a1和a3之间，a3在a2和a4之间，an在an-1和a1之间，以此类推。
每个元素的值可以是 1 或 0。如果对应的 ai 的值不同，则两种排列是不同的。例如，当 n=3 时，(1, 0, 0) 和 (0, 1, 0) 是不同的排列，即使它们在旋转或反射下可能是同构的。
因为有n个元素，每个元素可以取两个值，所以排列总数为2n。
这是问题:
有多少种可能的排列方式，使得没有两个相邻元素的值都为 1？如果有帮助，只考虑 n>3 的情况。
我在这里问有几个原因:
最佳答案
我们先问一个问题“没有两个连续的 1 的长度为 n 的 0-1 序列有多少个？”设答案为 A(n)。我们有 A(0)=1(空序列)，A(1)=2(“0”和“1”)，A(2)=3(“00”，“01”和“10”，但不是“11”)。
为了更容易编写递归，我们将 A(n) 计算为两个数字的总和:
B(n)，以 0 结尾的此类序列的数量，以及
C(n)，以 1 结尾的此类序列的数量。
然后 B(n) = A(n-1)(取任何长度为 n-1 的序列，并附加一个 0)
和 C(n) = B(n-1)(因为如果在位置 n 有一个 1，则在 n-1 处必须有一个 0。)
这给出了 A(n) = B(n) + C(n) = A(n-1) + B(n-1) = A(n-1) + A(n-2)。
现在应该很熟悉了:-)
A(n) 只是斐波那契数 Fn+2，其中斐波那契数列由 F0=0、F1=1 和 Fn+2= Fn+1+Fn 定义，n ≥ 0。
现在回答你的问题。我们将分别计算 a1=0 和 a1=1 的排列数。对于前者，a2 … an 可以是任何序列(没有连续的 1)，所以数字是 A(n-1)=Fn+1。对于后者，我们必须有 a2=0，然后 a3…an 是任何以 0 结尾的没有连续 1 的序列，即 B(n-2)=A(n-3)=Fn-1。
所以 答案是 Fn+1 + Fn-1。
实际上，我们可以比那个答案走得更远。请注意，如果您将答案称为 G(n)=Fn+1+Fn-1，则
G(n+1)=Fn+2+Fn，并且
G(n+2)=Fn+3+Fn+1，所以即使G(n)也满足与斐波那契数列相同的递归! [实际上，类似斐波那契数列的任何线性组合都会满足相同的循环，所以这并不奇怪。] 所以另一种计算答案的方法是使用:
G(2)=3
G(3)=4
对于 n≥4，G(n)=G(n-1)+G(n-2)。
现在你还可以使用 closed form Fn=(αn-βn)/(α-β)(其中 α 和 β 是 (1±√5)/2，x2-x-1=0 的根)，得到
G(n) = ((1+√5)/2)n + ((1-√5)/2)n。
[您可以忽略第二项，因为对于大 n，它非常接近 0，实际上 G(n) 是 最接近 ((1+√5)/2)n 的整数，对于所有 n≥2。]
关于algorithm - 安排数量，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/354640/