相邻位计数

Question

这是来自spoj 的问题

对于n位x1,x2,x3,...,Xn的字符串,字符串的相邻位数(AdjBC(x))由下式给出:

X1*X2 + X2*X3 + X3*X4 + ... + Xn-1*Xn

它计算1位与另一个1位相邻的次数.例如:

AdjBC(011101101)= 3
AdjBC(111101101)= 4
AdjBC(010101010)= 0

问题是:编写一个程序,它将整数n和k作为输入,并返回满足AdjBC(x)= k的n位(2位中的2位)的位串数x.

我不知道如何解决这个问题.你能帮帮我解决这个问题吗？

谢谢

Answer 1

通常在组合问题中,有助于查看它产生的一组值.使用蛮力我计算了下表:

  k   0   1   2   3   4   5   6
n +----------------------------
1 |   2   0   0   0   0   0   0
2 |   3   1   0   0   0   0   0
3 |   5   2   1   0   0   0   0
4 |   8   5   2   1   0   0   0
5 |  13  10   6   2   1   0   0
6 |  21  20  13   7   2   1   0
7 |  34  38  29  16   8   2   1

第一列是熟悉的Fibonacci序列,并且满足递归关系 f(n, 0) = f(n-1, 0) + f(n-2, 0)

其他列满足递归关系 f(n, k) = f(n - 1, k) + f(n - 1, k - 1) + f(n - 2, k) - f(n - 2, k - 1)

有了这个,你可以做一些动态编程:

INPUT: n, k
row1 <- [2,0,0,0,...] (k+1 elements)
row2 <- [3,1,0,0,...] (k+1 elements)
repeat (n-2) times
  for j = k downto 1 do
    row1[j] <- row2[j] + row2[j-1] + row1[j] - row1[j-1]
  row1[0] <- row1[0] + row2[0]
  swap row1 and row2
return row2[k]

Answer 2

作为提示,您可以将其分为两种情况:数字以0结尾,数字以1结尾.

def f(n, k):
    return f_ending_in_0(n, k) + f_ending_in_1(n, k)

def f_ending_in_0(n, k):
    if n == 1: return k == 0
    return f(n - 1, k)

def f_ending_in_1(n, k):
    if n == 1: return k == 0
    return f_ending_in_0(n - 1, k) + f_ending_in_1(n - 1, k - 1)

这给出了正确的输出,但需要很长时间才能执行.您可以应用标准动态编程或记忆技术,以使其足够快地执行.