生成长度为n的所有二进制字符串，其中子字符串“01”恰好出现两次

本文概述

C ++
Java
Python3
C#

给定一个整数?, 任务是生成所有可能的长度为二进制的字符串?其中包含" 01"作为子字符串恰好两次。
例子：

输入：N = 4
输出：0101" 0101"是唯一一个长度为4的二进制字符串, 其中包含的" 01"是子字符串的两倍。
输入：N = 5
输出：00101 01001 01010 01011 01101 10101

方法：这个问题可以解决使用回溯。为了生成二进制字符串, 我们实现了一个函数, 该函数一次生成每个位, 更新二进制字符串的状态(当前长度, 模式出现的次数)。然后递归调用该函数, 并根据二进制字符串的当前状态, 该函数将决定如何生成下一位或打印出二进制字符串(如果满足问题要求)。
对于这个问题，回溯策略看起来就像我们生成了一棵二叉树，每个节点的值可以是0或1。
例如，当N = 4时，树看起来如下:

文章图片
下面是上述方法的实现：
C ++

//C++ implementation of the approach #include < iostream> #include < stdlib.h> using namespace std; //Utility function to print the given binary string void printBinStr( int * str, int len) { for ( int i = 0; i < len; i++) { cout < < str[i]; } cout < < endl; }//This function will be called recursively //to generate the next bit for given //binary string according to its current state void generateBinStr( int * str, int len, int currlen, int occur, int nextbit) {//Base-case: if the generated binary string //meets the required length and the pattern "01" //appears twice if (currlen == len) {//nextbit needs to be0 because each time //we call the function recursively, //we call 2 times for 2 cases: //next bit is 0 or 1 //The is to assure that the binary //string is printed one time only if (occur == 2 & & nextbit == 0) printBinStr(str, len); return ; }//Generate the next bit for str //and call recursive if (currlen == 0) {//Assign first bit str[0] = nextbit; //The next generated bit will wither be 0 or 1 generateBinStr(str, len, currlen + 1, occur, 0); generateBinStr(str, len, currlen + 1, occur, 1); } else {//If pattern "01" occurrence is < 2 if (occur < 2) {//Set next bit str[currlen] = nextbit; //If pattern "01" appears then //increase the occurrence of pattern if (str[currlen - 1] == 0 & & nextbit == 1) { occur += 1; } generateBinStr(str, len, currlen + 1, occur, 0); generateBinStr(str, len, currlen + 1, occur, 1); //Else pattern "01" occurrence equals 2 } else {//If previous bit is 0 then next bit cannot be 1 if (str[currlen - 1] == 0 & & nextbit == 1) { return ; //Otherwise } else { str[currlen] = nextbit; generateBinStr(str, len, currlen + 1, occur, 0); generateBinStr(str, len, currlen + 1, occur, 1); } } } }//Driver code int main() {int n = 5; //Length of the resulting strings //must be at least 4 if (n < 4) cout < < -1; else { int * str = new int [n]; //Generate all binary strings of length n //with sub-string "01" appearing twice generateBinStr(str, n, 0, 0, 0); generateBinStr(str, n, 0, 0, 1); }return 0; }

Java

//Java implementation of the above approach class GFG {//Utility function to print the given binary string static void printBinStr( int [] str, int len) { for ( int i = 0 ; i < len; i++) { System.out.print(str[i]); } System.out.println(); }//This function will be called recursively //to generate the next bit for given //binary string according to its current state static void generateBinStr( int [] str, int len, int currlen, int occur, int nextbit) {//Base-case: if the generated binary string //meets the required length and the pattern "01" //appears twice if (currlen == len) {//nextbit needs to be 0 because each time //we call the function recursively, //we call 2 times for 2 cases: //next bit is 0 or 1 //The is to assure that the binary //string is printed one time only if (occur == 2 & & nextbit == 0 ) { printBinStr(str, len); } return ; }//Generate the next bit for str //and call recursive if (currlen == 0 ) {//Assign first bit str[ 0 ] = nextbit; //The next generated bit will wither be 0 or 1 generateBinStr(str, len, currlen + 1 , occur, 0 ); generateBinStr(str, len, currlen + 1 , occur, 1 ); } else //If pattern "01" occurrence is < 2 if (occur < 2 ) {//Set next bit str[currlen] = nextbit; //If pattern "01" appears then //increase the occurrence of pattern if (str[currlen - 1 ] == 0 & & nextbit == 1 ) { occur += 1 ; } generateBinStr(str, len, currlen + 1 , occur, 0 ); generateBinStr(str, len, currlen + 1 , occur, 1 ); //Else pattern "01" occurrence equals 2 } else //If previous bit is 0 then next bit cannot be 1 if (str[currlen - 1 ] == 0 & & nextbit == 1 ) { return ; //Otherwise } else { str[currlen] = nextbit; generateBinStr(str, len, currlen + 1 , occur, 0 ); generateBinStr(str, len, currlen + 1 , occur, 1 ); } }//Driver code public static void main(String[] args) { int n = 5 ; //Length of the resulting strings //must be at least 4 if (n < 4 ) { System.out.print(- 1 ); } else { int [] str = new int [n]; //Generate all binary strings of length n //with sub-string "01" appearing twice generateBinStr(str, n, 0 , 0 , 0 ); generateBinStr(str, n, 0 , 0 , 1 ); } } }//This code has been contributed by 29AjayKumar

Python3

# Python3 implementation of the approach# Utility function to print the # given binary string def printBinStr(string, length):for i in range ( 0 , length): print (string[i], end = "")print ()# This function will be called recursively # to generate the next bit for given # binary string according to its current state def generateBinStr(string, length, currlen, occur, nextbit):# Base-case: if the generated binary # string meets the required length and # the pattern "01" appears twice if currlen = = length:# nextbit needs to be 0 because each # time we call the function recursively, # we call 2 times for 2 cases: # next bit is 0 or 1 # The is to assure that the binary # string is printed one time only if occur = = 2 and nextbit = = 0 : printBinStr(string, length) return# Generate the next bit for # str and call recursive if currlen = = 0 : # Assign first bit string[ 0 ] = nextbit# The next generated bit will # either be 0 or 1 generateBinStr(string, length, currlen + 1 , occur, 0 ) generateBinStr(string, length, currlen + 1 , occur, 1 )else :# If pattern "01" occurrence is < 2 if occur < 2 : # Set next bit string[currlen] = nextbit# If pattern "01" appears then # increase the occurrence of pattern if string[currlen - 1 ] = = 0 and nextbit = = 1 : occur + = 1generateBinStr(string, length, currlen + 1 , occur, 0 ) generateBinStr(string, length, currlen + 1 , occur, 1 )# Else pattern "01" occurrence equals 2else :# If previous bit is 0 then next bit cannot be 1 if string[currlen - 1 ] = = 0 and nextbit = = 1 : return# Otherwiseelse : string[currlen] = nextbit generateBinStr(string, length, currlen + 1 , occur, 0 ) generateBinStr(string, length, currlen + 1 , occur, 1 )# Driver code if __name__ = = "__main__" :n = 5# Length of the resulting strings # must be at least 4 if n < 4 : print ( - 1 ) else : string = [ None ] * n# Generate all binary strings of length n # with sub-string "01" appearing twice generateBinStr(string, n, 0 , 0 , 0 ) generateBinStr(string, n, 0 , 0 , 1 )# This code is contributed by Rituraj Jain

//C# implementation of the above approach using System; class GFG {//Utility function to print the given binary string static void printBinStr( int [] str, int len) { for ( int i = 0; i < len; i++) { Console.Write(str[i]); } Console.Write( "\n" ); }//This function will be called recursively //to generate the next bit for given //binary string according to its current state static void generateBinStr( int [] str, int len, int currlen, int occur, int nextbit) {//Base-case: if the generated binary string //meets the required length and the pattern "01" //appears twice if (currlen == len) {//nextbit needs to be 0 because each time //we call the function recursively, //we call 2 times for 2 cases: //next bit is 0 or 1 //The is to assure that the binary //string is printed one time only if (occur == 2 & & nextbit == 0) { printBinStr(str, len); } return ; }//Generate the next bit for str //and call recursive if (currlen == 0) {//Assign first bit str[0] = nextbit; //The next generated bit will wither be 0 or 1 generateBinStr(str, len, currlen + 1, occur, 0); generateBinStr(str, len, currlen + 1, occur, 1); } else //If pattern "01" occurrence is < 2 if (occur < 2) {//Set next bit str[currlen] = nextbit; //If pattern "01" appears then //increase the occurrence of pattern if (str[currlen - 1] == 0 & & nextbit == 1) { occur += 1; } generateBinStr(str, len, currlen + 1, occur, 0); generateBinStr(str, len, currlen + 1, occur, 1); //Else pattern "01" occurrence equals 2 } else //If previous bit is 0 then next bit cannot be 1 if (str[currlen - 1] == 0 & & nextbit == 1) { return ; //Otherwise } else { str[currlen] = nextbit; generateBinStr(str, len, currlen + 1, occur, 0); generateBinStr(str, len, currlen + 1, occur, 1); } }//Driver code public static void Main(String[] args) { int n = 5; //Length of the resulting strings //must be at least 4 if (n < 4) { Console.Write(-1); } else { int [] str = new int [n]; //Generate all binary strings of length n //with sub-string "01" appearing twice generateBinStr(str, n, 0, 0, 0); generateBinStr(str, n, 0, 0, 1); } } }//This code is contributed by Princi Singh

【生成长度为n的所有二进制字符串，其中子字符串“01”恰好出现两次】输出如下：