Dado un entero K. La tarea es Imprimir toda la string binaria de tamaño K (número dado).
Ejemplos:
Input : K = 3 Output : 000 , 001 , 010 , 100 , 101 Input : K = 4 Output :0000 0001 0010 0100 0101 1000 1001 1010
La idea detrás de eso es SI la string termina con ‘1’, entonces solo ponemos ‘0’ al final. SI la string termina en ‘0’, ponemos ‘0’ y ‘1’ al final de la string para generar una nueva string.
A continuación se muestra el algoritmo
K : size of string
First We Generate All string starts with '0'
initialize n = 1 .
GenerateALLString ( K , Str , n )
a. IF n == K
PRINT str.
b. IF previous character is '1' :: str[n-1] == '1'
put str[n] = '0'
GenerateAllString ( K , str , n+1 )
c. IF previous character is '0' :: str[n-1] == '0'
First We Put zero at end and call function
PUT str[n] = '0'
GenerateAllString ( K , str , n+1 )
PUT str[n] = '1'
GenerateAllString ( K , str , n+1 )
Second Generate all binary string starts with '1'
DO THE SAME PROCESS
A continuación se muestra la implementación recursiva:
C++
// C++ program to Generate
// all binary string without
// consecutive 1's of size K
#include<bits/stdc++.h>
using namespace std ;
// A utility function generate all string without
// consecutive 1'sof size K
void generateAllStringsUtil(int K, char str[], int n)
{
// Print binary string without consecutive 1's
if (n == K)
{
// Terminate binary string
str[n] = '\0' ;
cout << str << " ";
return ;
}
// If previous character is '1' then we put
// only 0 at end of string
//example str = "01" then new string be "010"
if (str[n-1] == '1')
{
str[n] = '0';
generateAllStringsUtil (K , str , n+1);
}
// If previous character is '0' than we put
// both '1' and '0' at end of string
// example str = "00" then
// new string "001" and "000"
if (str[n-1] == '0')
{
str[n] = '0';
generateAllStringsUtil(K, str, n+1);
str[n] = '1';
generateAllStringsUtil(K, str, n+1) ;
}
}
// Function generate all binary string without
// consecutive 1's
void generateAllStrings(int K )
{
// Base case
if (K <= 0)
return ;
// One by one stores every
// binary string of length K
char str[K];
// Generate all Binary string
// starts with '0'
str[0] = '0' ;
generateAllStringsUtil ( K , str , 1 ) ;
// Generate all Binary string
// starts with '1'
str[0] = '1' ;
generateAllStringsUtil ( K , str , 1 );
}
// Driver program to test above function
int main()
{
int K = 3;
generateAllStrings (K) ;
return 0;
}
Java
// Java program to Generate all binary string without
// consecutive 1's of size K
import java.util.*;
import java.lang.*;
public class BinaryS {
// Array conversion to String--
public static String toString(char[] a) {
String string = new String(a);
return string;
}
static void generate(int k, char[] ch, int n) {
// Base Condition when we
// reached at the end of Array**
if (n == k) {
// Printing the Generated String**
// Return to the previous case*
System.out.print(toString(ch)+" ");
return;
}
// If the first Character is
//Zero then adding**
if (ch[n - 1] == '0') {
ch[n] = '0';
generate(k, ch, n + 1);
ch[n] = '1';
generate(k, ch, n + 1);
}
// If the Character is One
// then add Zero to next**
if (ch[n - 1] == '1') {
ch[n] = '0';
// Calling Recursively for the
// next value of Array
generate(k, ch, n + 1);
}
}
static void fun(int k) {
if (k <= 0) {
return;
}
char[] ch = new char[k];
// Initializing first character to Zero
ch[0] = '0';
// Generating Strings starting with Zero--
generate(k, ch, 1);
// Initialized first Character to one--
ch[0] = '1';
generate(k, ch, 1);
}
public static void main(String args[]) {
int k = 3;
//Calling function fun with argument k
fun(k);
//This code is Contributed by Praveen Tiwari
}
}
Python3
# Python3 program to Generate all binary string # without consecutive 1's of size K # A utility function generate all string without # consecutive 1'sof size K def generateAllStringsUtil(K, str, n): # print binary string without consecutive 1's if (n == K): # terminate binary string print(*str[:n], sep = "", end = " ") return # if previous character is '1' then we put # only 0 at end of string # example str = "01" then new string be "000" if (str[n-1] == '1'): str[n] = '0' generateAllStringsUtil (K, str, n + 1) # if previous character is '0' than we put # both '1' and '0' at end of string # example str = "00" then new string "001" and "000" if (str[n-1] == '0'): str[n] = '0' generateAllStringsUtil(K, str, n + 1) str[n] = '1' generateAllStringsUtil(K, str, n + 1) # function generate all binary string without # consecutive 1's def generateAllStrings(K): # Base case if (K <= 0): return # One by one stores every # binary string of length K str = [0] * K # Generate all Binary string starts with '0' str[0] = '0' generateAllStringsUtil (K, str, 1) # Generate all Binary string starts with '1' str[0] = '1' generateAllStringsUtil (K, str, 1) # Driver code K = 3 generateAllStrings (K) # This code is contributed by SHUBHAMSINGH10
C#
// C# program to Generate
// all binary string without
// consecutive 1's of size K
using System;
class GFG {
// Array conversion to String--
static string toString(char[] a) {
string String = new string(a);
return String;
}
static void generate(int k, char[] ch, int n) {
// Base Condition when we
// reached at the end of Array**
if (n == k) {
// Printing the Generated String**
// Return to the previous case*
Console.Write(toString(ch)+" ");
return;
}
// If the first Character is
//Zero then adding**
if (ch[n - 1] == '0') {
ch[n] = '0';
generate(k, ch, n + 1);
ch[n] = '1';
generate(k, ch, n + 1);
}
// If the Character is One
// then add Zero to next**
if (ch[n - 1] == '1') {
ch[n] = '0';
// Calling Recursively for the
// next value of Array
generate(k, ch, n + 1);
}
}
static void fun(int k)
{
if (k <= 0)
{
return;
}
char[] ch = new char[k];
// Initializing first character to Zero
ch[0] = '0';
// Generating Strings starting with Zero--
generate(k, ch, 1);
// Initialized first Character to one--
ch[0] = '1';
generate(k, ch, 1);
}
// Driver code
static void Main()
{
int k = 3;
//Calling function fun with argument k
fun(k);
}
}
// This code is contributed by divyeshrabadiya07.
Javascript
<script>
// Javascript implementation
// A utility function generate all string without
// consecutive 1'sof size K
function generateAllStringsUtil(K, str, n)
{
// Print binary string without consecutive 1's
if (n == K)
{
// Terminate binary string
str[n] = '\0' ;
document.write(str.join("") + " ");
return ;
}
// If previous character is '1' then we put
// only 0 at end of string
//example str = "01" then new string be "010"
if (str[n-1] == '1')
{
str[n] = '0';
generateAllStringsUtil (K , str , n+1);
}
// If previous character is '0' than we put
// both '1' and '0' at end of string
// example str = "00" then
// new string "001" and "000"
if (str[n-1] == '0')
{
str[n] = '0';
generateAllStringsUtil(K, str, n+1);
str[n] = '1';
generateAllStringsUtil(K, str, n+1) ;
}
}
// Function generate all binary string without
// consecutive 1's
function generateAllStrings(K )
{
// Base case
if (K <= 0)
return ;
// One by one stores every
// binary string of length K
var str = new Array(K);
// Generate all Binary string
// starts with '0'
str[0] = '0' ;
generateAllStringsUtil ( K , str , 1 ) ;
// Generate all Binary string
// starts with '1'
str[0] = '1' ;
generateAllStringsUtil ( K , str , 1 );
}
/* Driver code */
var K = 3;
generateAllStrings(K);
// This is code is contributed
// by shivani
</script>
Producción
000 001 010 100 101
Este problema se resuelve mediante el uso de un árbol de recurrencia que tiene dos posibilidades 0 o 1 al igual que la selección de elementos en una subsecuencia.
Por lo tanto, también podemos implementar el enfoque anterior utilizando una array booleana.
C++14
#include <bits/stdc++.h>
using namespace std;
void All_Binary_Strings(bool arr[],int num,int r)
{
if(r==num)
{
for(int i=0;i<num;i++)
cout<<arr[i];
cout<<" ";
return;
}
else if(arr[r-1])
{
arr[r]=0;
All_Binary_Strings(arr,num,r+1);
}
else
{
arr[r]=0;
All_Binary_Strings(arr,num,r+1);
arr[r]=1;
All_Binary_Strings(arr,num,r+1);
}
}
void print(bool a[],int& num)
{
a[0]=0;
All_Binary_Strings(a,num,1);
a[0]=1;
All_Binary_Strings(a,num,1);
}
//driver's code
int main()
{
int n=2;
bool a[n];
print(a,n);
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
class GFG {
static void All_Binary_Strings(int arr[],int num,int r)
{
if(r == num)
{
for(int i = 0; i < num; i++)
System.out.print(arr[i]);
System.out.print(" ");
return;
}
else if(arr[r-1] == 1)
{
arr[r] = 0;
All_Binary_Strings(arr,num,r+1);
}
else
{
arr[r] = 0;
All_Binary_Strings(arr,num,r+1);
arr[r] = 1;
All_Binary_Strings(arr,num,r+1);
}
}
static void print(int a[],int num)
{
a[0] = 0;
All_Binary_Strings(a,num,1);
a[0] = 1;
All_Binary_Strings(a,num,1);
}
// Driver code
public static void main(String args[])
{
int n = 2;
int a[] = new int[n];
print(a,n);
}
}
// This code is contributed by shinjanpatra.
Python3
def All_Binary_Strings(arr,num,r): if(r == num): for i in range(num): print(arr[i],end="") print(end=" ") return elif(arr[r-1]): arr[r] = 0 All_Binary_Strings(arr, num, r + 1) else: arr[r] = 0 All_Binary_Strings(arr,num,r+1) arr[r] = 1 All_Binary_Strings(arr,num,r+1) def Print(a,num): a[0] = 0 All_Binary_Strings(a,num,1) a[0] = 1 All_Binary_Strings(a,num,1) # driver's code n = 2 a = [False for i in range(n)] Print(a,n) # This code is contributed by shinjanpatra
C#
// C# program to Generate
// all binary string without
using System;
public static class GFG {
public static void All_Binary_Strings(int[] arr,
int num, int r)
{
if (r == num) {
for (int i = 0; i < num; i++) {
Console.Write(arr[i]);
}
Console.Write(" ");
return;
}
else if (arr[r - 1] == 1) {
arr[r] = 0;
All_Binary_Strings(arr, num, r + 1);
}
else {
arr[r] = 0;
All_Binary_Strings(arr, num, r + 1);
arr[r] = 1;
All_Binary_Strings(arr, num, r + 1);
}
}
public static void print(int[] a, ref int num)
{
a[0] = 0;
All_Binary_Strings(a, num, 1);
a[0] = 1;
All_Binary_Strings(a, num, 1);
}
// driver's code
public static void Main()
{
int n = 2;
int[] a = new int[n];
print(a, ref n);
}
}
// This code is contributed by Aarti_Rathi
Javascript
<script>
function All_Binary_Strings(arr,num,r)
{
if(r == num)
{
for(let i = 0; i < num; i++)
document.write(arr[i]);
document.write(" ");
return;
}
else if(arr[r-1])
{
arr[r] = 0;
All_Binary_Strings(arr, num, r + 1);
}
else
{
arr[r] = 0;
All_Binary_Strings(arr,num,r+1);
arr[r] = 1;
All_Binary_Strings(arr,num,r+1);
}
}
function print(a,num)
{
a[0] = 0;
All_Binary_Strings(a,num,1);
a[0] = 1;
All_Binary_Strings(a,num,1);
}
// driver's code
let n=2;
let a = new Array(n).fill(false);
print(a,n);
// This code is contributed by shinjanpatra
</script>
Producción
00 01 10
El enfoque anterior también se puede resolver usando una string. No tiene ningún efecto sobre la complejidad, pero el manejo, la impresión y el funcionamiento de strings son sencillos.
C++14
#include <bits/stdc++.h>
using namespace std;
void All_Binary_Strings(string str,int num)
{
int len=str.length();
if(len==num)
{
cout<<str<<" ";
return;
}
else if(str[len-1]=='1')
All_Binary_Strings(str+'0',num);
else
{
All_Binary_Strings(str+'0',num);
All_Binary_Strings(str+'1',num);
}
}
void print(int& num)
{
string word;
word.push_back('0');
All_Binary_Strings(word,num);
word[0]='1';
All_Binary_Strings(word,num);
}
//driver's code
int main()
{
int n=4;
print(n);
return 0;
}
Python3
def All_Binary_Strings(str,num): Len = len(str) if(Len == num): print(str,end = " ") return elif(str[Len - 1]=='1'): All_Binary_Strings(str+'0',num) else: All_Binary_Strings(str+'0',num) All_Binary_Strings(str+'1',num) def Print(num): word = "" word += '0' All_Binary_Strings(word,num) word = '1' All_Binary_Strings(word,num) # Driver's code n = 4 Print(n) # This code is contributed by shinjanpatra.
Javascript
<script>
function All_Binary_Strings(str,num)
{
let len = str.length;
if(len == num)
{
document.write(str," ");
return;
}
else if(str[len - 1]=='1')
All_Binary_Strings(str+'0',num);
else
{
All_Binary_Strings(str+'0',num);
All_Binary_Strings(str+'1',num);
}
}
function print(num)
{
let word = "";
word += '0';
All_Binary_Strings(word,num);
word = '1';
All_Binary_Strings(word,num);
}
// driver's code
let n = 4;
print(n);
// This code is contributed by shinjanpatra.
</script>
Producción
0000 0001 0010 0100 0101 1000 1001 1010
Complejidad de tiempo: O(2^n)
Espacio auxiliar: O(n)
Este artículo es una contribución de Nishant Singh . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA