Question

Python programming

1. Use 0 and 1 only to complete the function that outputs how many N-long sequence are in total.

Condition
1) Starts with zero and ends with zero
2) Zero does not exist twice in a row.
3) 1 does not exist three times in a row.
4) N is a natural number.

- A sequence that satisfies the conditions.
ex) 010, 0110, 01010

- A sequence that does not meet the conditions.

ex) 0100, 01110, 01100110

Need two answer. One is with recursion function and the other is Dynamic programming

thank you

Answer 1

Python recursion code :

# using recursion...

def n_long_sequence(n,li,str):
if(n == 1):
if str[-1] == '1':
li.append(str+'0')
return li

if(n>1 and str[-1] == '1' and (len(str)>=2 and str[-2] == '1')):
n_long_sequence(n-1,li,str+'0')
return li
elif(n>1 and str[-1] == '1'):
n_long_sequence(n-1,li,str+'0')
n_long_sequence(n-1,li,str+'1')
return li
else:
n_long_sequence(n-1,li,str+'1')
return li
  
  
  

if __name__ == '__main__':
n = int(input())
output = n_long_sequence(n-1,[],'0')
print(*output,sep='\n')
print("Number of %d"%n+" bit long sequences is : %d"%len(output))