时间戳

首页 > 解决方案 > 描述一种递归算法来打印所有不包含任何连续 1 的 N 位二进制字符串

algorithm - 描述一种递归算法来打印所有不包含任何连续 1 的 N 位二进制字符串

问题描述

我找到了一个给出连续 1 的解决方案，但我找不到二进制字符串中不包含连续 1 的任何内容，有人可以帮我吗？

标签： algorithmrecursionbinary

解决方案

从空字符串递归。在每次调用时，决定在基本字符串的最后一个字符上附加什么。当字符串达到所需大小时终止。

    def recurse(base,n):
        #termination criteria
        if len(base)==n:`
            print(base)
    
        #You can add '0' or '1' if the base string ends with '0' or is empty  
        #and recurse. There is no issue having consecutive zeroes.
    
        elif base== "" or base[-1]=="0" :
            recurse(base+"0",n)
            recurse(base+"1",n)
      
        #To prevent consecutive '1's, append '0' only to the base string ending 
        #with '0'
    
        elif base[-1]=="1":
            recurse(base+"0",n)
    n=int(input())
    recurse("",n)

对于 n=5，输出为：

00000 00001 00010 00100 00101 01000 01001 01010 10000 10001 10010 10100 10101

推荐阅读