Dado un entero positivo N , la tarea es contar todas las posibles strings binarias distintas de longitud N de modo que no haya unos consecutivos.
Ejemplos:
Entrada: N = 5
Salida: 5
Explicación:
Los enteros no negativos <= 5 con sus correspondientes representaciones binarias son:
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
Entre ellos, solo el 3 tiene dos 1 consecutivos. Por lo tanto cuenta requerida = 5Entrada: N = 12
Salida: 8
Enfoque de programación dinámica: Ya se ha discutidoun enfoque de programación dinámica en este artículo .
Enfoque: En este artículo, se analiza un enfoque que utiliza el concepto de digit-dp .
- Similar al problema digit-dp, aquí se crea una tabla tridimensional para almacenar los valores calculados. Se supone que el N < 2 31 – 1, y el rango de cada número es solo 2 (O 0 o 1). Por lo tanto, las dimensiones de la mesa se toman como 32 x 2 x 2 .
- Después de construir la tabla, el número dado se convierte en una string binaria .
- Luego, se itera el número. Para cada iteración:
- Compruebe si el dígito anterior es un 0 o un 1.
- Si es un 0, entonces el número actual puede ser un 0 o un 1.
- Pero si el número anterior es 1, entonces el número actual tiene que ser 0 porque no podemos tener dos 1 consecutivos en la representación binaria.
- Ahora, la tabla se llena exactamente como el problema digit-dp .
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to count number of
// binary strings without consecutive 1’s
#include <bits/stdc++.h>
using namespace std;
// Table to store the solution of
// every sub problem
int memo[32][2][2];
// Function to fill the table
/* Here,
pos: keeps track of current position.
f1: is the flag to check if current
number is less than N or not.
pr: represents the previous digit
*/
int dp(int pos, int fl, int pr, string& bin)
{
// Base case
if (pos == bin.length())
return 1;
// Check if this subproblem
// has already been solved
if (memo[pos][fl][pr] != -1)
return memo[pos][fl][pr];
int val = 0;
// Placing 0 at the current position
// as it does not violate the condition
if (bin[pos] == '0')
val = val + dp(pos + 1, fl, 0, bin);
// Here flag will be 1 for the
// next recursive call
else if (bin[pos] == '1')
val = val + dp(pos + 1, 1, 0, bin);
// Placing 1 at this position only if
// the previously inserted number is 0
if (pr == 0) {
// If the number is smaller than N
if (fl == 1) {
val += dp(pos + 1, fl, 1, bin);
}
// If the digit at current position is 1
else if (bin[pos] == '1') {
val += dp(pos + 1, fl, 1, bin);
}
}
// Storing the solution to this subproblem
return memo[pos][fl][pr] = val;
}
// Function to find the number of integers
// less than or equal to N with no
// consecutive 1’s in binary representation
int findIntegers(int num)
{
// Convert N to binary form
string bin;
// Loop to convert N
// from Decimal to binary
while (num > 0) {
if (num % 2)
bin += "1";
else
bin += "0";
num /= 2;
}
reverse(bin.begin(), bin.end());
// Initialising the table with -1.
memset(memo, -1, sizeof(memo));
// Calling the function
return dp(0, 0, 0, bin);
}
// Driver code
int main()
{
int N = 12;
cout << findIntegers(N);
return 0;
}
Java
// Java program to count number of
// binary Strings without consecutive 1’s
class GFG{
// Table to store the solution of
// every sub problem
static int [][][]memo = new int[32][2][2];
// Function to fill the table
/* Here,
pos: keeps track of current position.
f1: is the flag to check if current
number is less than N or not.
pr: represents the previous digit
*/
static int dp(int pos, int fl, int pr, String bin)
{
// Base case
if (pos == bin.length())
return 1;
// Check if this subproblem
// has already been solved
if (memo[pos][fl][pr] != -1)
return memo[pos][fl][pr];
int val = 0;
// Placing 0 at the current position
// as it does not violate the condition
if (bin.charAt(pos) == '0')
val = val + dp(pos + 1, fl, 0, bin);
// Here flag will be 1 for the
// next recursive call
else if (bin.charAt(pos) == '1')
val = val + dp(pos + 1, 1, 0, bin);
// Placing 1 at this position only if
// the previously inserted number is 0
if (pr == 0) {
// If the number is smaller than N
if (fl == 1) {
val += dp(pos + 1, fl, 1, bin);
}
// If the digit at current position is 1
else if (bin.charAt(pos) == '1') {
val += dp(pos + 1, fl, 1, bin);
}
}
// Storing the solution to this subproblem
return memo[pos][fl][pr] = val;
}
// Function to find the number of integers
// less than or equal to N with no
// consecutive 1’s in binary representation
static int findIntegers(int num)
{
// Convert N to binary form
String bin = "";
// Loop to convert N
// from Decimal to binary
while (num > 0) {
if (num % 2 == 1)
bin += "1";
else
bin += "0";
num /= 2;
}
bin = reverse(bin);
// Initialising the table with -1.
for(int i = 0; i < 32; i++){
for(int j = 0; j < 2; j++){
for(int l = 0; l < 2; l++)
memo[i][j][l] = -1;
}
}
// Calling the function
return dp(0, 0, 0, bin);
}
static String reverse(String input) {
char[] a = input.toCharArray();
int l, r = a.length - 1;
for (l = 0; l < r; l++, r--) {
char temp = a[l];
a[l] = a[r];
a[r] = temp;
}
return String.valueOf(a);
}
// Driver code
public static void main(String[] args)
{
int N = 12;
System.out.print(findIntegers(N));
}
}
// This code is contributed by sapnasingh4991
Python3
# Python program to count number of # binary strings without consecutive 1’s # Table to store the solution of # every sub problem memo=[[[-1 for i in range(2)] for j in range(2)] for k in range(32)] # Function to fill the table ''' Here, pos: keeps track of current position. f1: is the flag to check if current number is less than N or not. pr: represents the previous digit ''' def dp(pos,fl,pr,bin): # Base case if (pos == len(bin)): return 1; # Check if this subproblem # has already been solved if (memo[pos][fl][pr] != -1): return memo[pos][fl][pr]; val = 0 # Placing 0 at the current position # as it does not violate the condition if (bin[pos] == '0'): val = val + dp(pos + 1, fl, 0, bin) # Here flag will be 1 for the # next recursive call elif (bin[pos] == '1'): val = val + dp(pos + 1, 1, 0, bin) # Placing 1 at this position only if # the previously inserted number is 0 if (pr == 0): # If the number is smaller than N if (fl == 1): val += dp(pos + 1, fl, 1, bin) # If the digit at current position is 1 elif (bin[pos] == '1'): val += dp(pos + 1, fl, 1, bin) # Storing the solution to this subproblem memo[pos][fl][pr] = val return val # Function to find the number of integers # less than or equal to N with no # consecutive 1’s in binary representation def findIntegers(num): # Convert N to binary form bin="" # Loop to convert N # from Decimal to binary while (num > 0): if (num % 2): bin += "1" else: bin += "0" num //= 2 bin=bin[::-1]; # Calling the function return dp(0, 0, 0, bin) # Driver code if __name__ == "__main__": N = 12 print(findIntegers(N))
C#
// C# program to count number of
// binary Strings without consecutive 1’s
using System;
public class GFG{
// Table to store the solution of
// every sub problem
static int [,,]memo = new int[32,2,2];
// Function to fill the table
/* Here,
pos: keeps track of current position.
f1: is the flag to check if current
number is less than N or not.
pr: represents the previous digit
*/
static int dp(int pos, int fl, int pr, String bin)
{
// Base case
if (pos == bin.Length)
return 1;
// Check if this subproblem
// has already been solved
if (memo[pos,fl,pr] != -1)
return memo[pos,fl,pr];
int val = 0;
// Placing 0 at the current position
// as it does not violate the condition
if (bin[pos] == '0')
val = val + dp(pos + 1, fl, 0, bin);
// Here flag will be 1 for the
// next recursive call
else if (bin[pos] == '1')
val = val + dp(pos + 1, 1, 0, bin);
// Placing 1 at this position only if
// the previously inserted number is 0
if (pr == 0) {
// If the number is smaller than N
if (fl == 1) {
val += dp(pos + 1, fl, 1, bin);
}
// If the digit at current position is 1
else if (bin[pos] == '1') {
val += dp(pos + 1, fl, 1, bin);
}
}
// Storing the solution to this subproblem
return memo[pos,fl,pr] = val;
}
// Function to find the number of integers
// less than or equal to N with no
// consecutive 1’s in binary representation
static int findints(int num)
{
// Convert N to binary form
String bin = "";
// Loop to convert N
// from Decimal to binary
while (num > 0) {
if (num % 2 == 1)
bin += "1";
else
bin += "0";
num /= 2;
}
bin = reverse(bin);
// Initialising the table with -1.
for(int i = 0; i < 32; i++){
for(int j = 0; j < 2; j++){
for(int l = 0; l < 2; l++)
memo[i,j,l] = -1;
}
}
// Calling the function
return dp(0, 0, 0, bin);
}
static String reverse(String input) {
char[] a = input.ToCharArray();
int l, r = a.Length - 1;
for (l = 0; l < r; l++, r--) {
char temp = a[l];
a[l] = a[r];
a[r] = temp;
}
return String.Join("",a);
}
// Driver code
public static void Main(String[] args)
{
int N = 12;
Console.Write(findints(N));
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// JavaScript program to count number of
// binary strings without consecutive 1’s
// Table to store the solution of
// every sub problem
var memo = Array.from(Array(32), ()=>Array(2));
for(var i =0;i<32;i++)
{
for(var j =0; j<2; j++)
{
memo[i][j] = new Array(2).fill(-1);
}
}
// Function to fill the table
/* Here,
pos: keeps track of current position.
f1: is the flag to check if current
number is less than N or not.
pr: represents the previous digit
*/
function dp(pos, fl, pr, bin)
{
// Base case
if (pos == bin.length)
return 1;
// Check if this subproblem
// has already been solved
if (memo[pos][fl][pr] != -1)
return memo[pos][fl][pr];
var val = 0;
// Placing 0 at the current position
// as it does not violate the condition
if (bin[pos] == '0')
val = val + dp(pos + 1, fl, 0, bin);
// Here flag will be 1 for the
// next recursive call
else if (bin[pos] == '1')
val = val + dp(pos + 1, 1, 0, bin);
// Placing 1 at this position only if
// the previously inserted number is 0
if (pr == 0) {
// If the number is smaller than N
if (fl == 1) {
val += dp(pos + 1, fl, 1, bin);
}
// If the digit at current position is 1
else if (bin[pos] == '1') {
val += dp(pos + 1, fl, 1, bin);
}
}
// Storing the solution to this subproblem
return memo[pos][fl][pr] = val;
}
// Function to find the number of integers
// less than or equal to N with no
// consecutive 1’s in binary representation
function findIntegers(num)
{
// Convert N to binary form
var bin = "";
// Loop to convert N
// from Decimal to binary
while (num > 0) {
if (num % 2)
bin += "1";
else
bin += "0";
num =parseInt(num/2);
}
bin = bin.split('').reverse().join('')
// Calling the function
return dp(0, 0, 0, bin);
}
// Driver code
var N = 12;
document.write( findIntegers(N));
</script>
Producción:
8
Complejidad de tiempo: O(L * log(N))
- O(log(N)) para convertir el número de decimal a binario.
- O(L) para llenar la tabla, donde L es la longitud de la forma binaria.
Espacio Auxiliar: O(32 * 2 * 2)