以下の条件を満たす任意の桁数のパターンが、フィボナッチ数列に似ていることに気付いたのでまとめておきます。
目次
条件
・長さnのビットストリングの全パターン中の00を含まないビット文字列の数を$S_n$とする。
この条件を満たす$S_n$について、$S_n = S_{n-1} + S_{n-2} , \forall n \in\mathbb{N}^+$をとなることを確かめます。
ビット列の再帰生成プログラム
再帰を使用して、任意のnに対応する全ビット配列を出力するプログラムを作成します。
def r_bt(n:int,s:str,a:int,l:list=[]) -> list[str]:
if n == 0:
return []
else:
if len(s+"1") == a:
l += [s+"1"]
l += [s+"0"]
r_bt(n-1,s+"1",a,l)
r_bt(n-1,s+"0",a,l)
return l
def generate_bitstrings(n:int) -> list[str]:
bit_strings = r_bt(n,"",n)
for i in bit_strings:
print(i)
return bit_strings
generate_bitstrings(4)
>>>
1111
1110
1101
1100
1011
1010
1001
1000
0111
0110
0101
0100
0011
0010
0001
0000検証
上記の関数を使用して、条件を満たすビット列のみをカウントする関数を作成して、数列が成り立つことを確認します。
def is_valid(string:str) -> bool:
for i in range(len(string)-1):
if string[i] == "0" and string[i+1] == "0":
return False
return True
def count_bt(bit_strings:list[str]) -> int:
counter:int = 0
for i in bit_strings:
if is_valid(i):
counter += 1
return counter
if __name__ == '__main__':
for i in range(3,20):
bit_string_i = [j for j in generate_bitstrings(i) if len(j) == i]
print(count_bt(bit_string_i))
>>>
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
