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

the function start with

def Recursion(N):

the parameter is just N

thank you

Answer 1

Recursion Code:-

def solve(N,zero,one,x):
   if N==0:
       return 1
   ans=0
   if zero<1 and N!=x and N!=1:
       ans+=solve(N-1,zero+1,0,x)
   if one<2:
       ans+=solve(N-1,0,one+1,x)
   return ans
      
  
def Recursion(N):
   N=N-2
   return solve(N,0,0,N)
  
print(Recursion(9))

OUTPUT :- (For N=9)

Dynamic Programming Code:-

a =100
b =3
c =2
dp = [[ [-1 for col in range(a)] for col in range(b)] for row in range(c)]

def solve(N,zero,one,x):
   if N==0:
       return 1
   ans=0
   if dp[N][zero][one] != -1:
       return dp[N][zero][one]
   if zero<1 and N!=x and N!=1:
       ans+=solve(N-1,zero+1,0,x)
   if one<2:
       ans+=solve(N-1,0,one+1,x)
   dp[N][zero][one]=ans
   return ans
      
  
def Recursion(N):
   N=N-2
   return solve(N,0,0,N)
  
print(Recursion(9))

OUTPUT :- (For N=9)