Dado un entero positivo N . Cuente el número total de conjuntos ordenados de cualquier tamaño de modo que los números consecutivos no estén presentes en el conjunto y todos los números sean <= N.
Conjunto ordenado: arrays en las que todos los números son distintos y se tiene en cuenta el orden de los elementos, por ejemplo, {1, 2, 3} es diferente de {1, 3, 2}.
Ejemplos:
Entrada: N = 3
Salida: 5
Explicación:
Los conjuntos ordenados son:
{1}, {2}, {3}, {1, 3}, {3, 1}Entrada: N = 6
Salida: 50
Enfoque ingenuo:
- Usaremos Recursion para resolver este problema. Si obtenemos un conteo digamos C del conjunto ordenado donde los elementos están en orden ascendente/descendente y el tamaño del conjunto es S, entonces el conteo total para este tamaño será
- . Haremos esto para cada conjunto ordenado de tamaños distintos.
- Iterar en todos los tamaños de conjuntos ordenados y para cada tamaño encontrar el conteo de conjuntos ordenados y multiplicar por factorial de tamaño (S!). En cada paso recursivo, tenemos dos opciones:
- Incluya el elemento actual x y muévase a la siguiente posición con el elemento máximo que se puede incluir ahora como x – 2.
- No incluya el elemento actual x y quédese en la posición actual con el elemento máximo que se puede incluir ahora como x – 1.
- Entonces la relación recursiva es:
countSets(x, pos) = countSets(x-2, pos-1) + countSets(x-1, pos)
C++
// C++ program to Count the number of
// ordered sets not containing
// consecutive numbers
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the count
// of ordered set for a given size
int CountSets(int x, int pos)
{
// Base cases
if (x <= 0) {
if (pos == 0)
return 1;
else
return 0;
}
if (pos == 0)
return 1;
int answer = CountSets(x - 1, pos)
+ CountSets(x - 2, pos - 1);
return answer;
}
// Function returns the count
// of all ordered sets
int CountOrderedSets(int n)
{
// Prestore the factorial value
int factorial[10000];
factorial[0] = 1;
for (int i = 1; i < 10000; i++)
factorial[i] = factorial[i - 1] * i;
int answer = 0;
// Iterate all ordered set sizes and find
// the count for each one maximum ordered
// set size will be smaller than N as all
// elements are distinct and non consecutive
for (int i = 1; i <= n; i++) {
// Multiply ny size! for all the
// arrangements because sets are ordered
int sets = CountSets(n, i) * factorial[i];
// Add to total answer
answer = answer + sets;
}
return answer;
}
// Driver code
int main()
{
int N = 3;
cout << CountOrderedSets(N);
return 0;
}
Java
// Java program to count the number
// of ordered sets not containing
// consecutive numbers
class GFG{
// Function to calculate the count
// of ordered set for a given size
static int CountSets(int x, int pos)
{
// Base cases
if (x <= 0)
{
if (pos == 0)
return 1;
else
return 0;
}
if (pos == 0)
return 1;
int answer = CountSets(x - 1, pos) +
CountSets(x - 2, pos - 1);
return answer;
}
// Function returns the count
// of all ordered sets
static int CountOrderedSets(int n)
{
// Prestore the factorial value
int []factorial = new int[10000];
factorial[0] = 1;
for(int i = 1; i < 10000; i++)
factorial[i] = factorial[i - 1] * i;
int answer = 0;
// Iterate all ordered set sizes and find
// the count for each one maximum ordered
// set size will be smaller than N as all
// elements are distinct and non consecutive
for(int i = 1; i <= n; i++)
{
// Multiply ny size! for all the
// arrangements because sets are ordered
int sets = CountSets(n, i) * factorial[i];
// Add to total answer
answer = answer + sets;
}
return answer;
}
// Driver code
public static void main(String[] args)
{
int N = 3;
System.out.print(CountOrderedSets(N));
}
}
// This code is contributed by sapnasingh4991
Python3
# Python3 program to count the number of # ordered sets not containing # consecutive numbers # Function to calculate the count # of ordered set for a given size def CountSets(x, pos): # Base cases if (x <= 0): if (pos == 0): return 1 else: return 0 if (pos == 0): return 1 answer = (CountSets(x - 1, pos) + CountSets(x - 2, pos - 1)) return answer # Function returns the count # of all ordered sets def CountOrderedSets(n): # Prestore the factorial value factorial = [1 for i in range(10000)] factorial[0] = 1 for i in range(1, 10000, 1): factorial[i] = factorial[i - 1] * i answer = 0 # Iterate all ordered set sizes and find # the count for each one maximum ordered # set size will be smaller than N as all # elements are distinct and non consecutive for i in range(1, n + 1, 1): # Multiply ny size! for all the # arrangements because sets are ordered sets = CountSets(n, i) * factorial[i] # Add to total answer answer = answer + sets return answer # Driver code if __name__ == '__main__': N = 3 print(CountOrderedSets(N)) # This code is contributed by Samarth
C#
// C# program to count the number
// of ordered sets not containing
// consecutive numbers
using System;
class GFG{
// Function to calculate the count
// of ordered set for a given size
static int CountSets(int x, int pos)
{
// Base cases
if (x <= 0)
{
if (pos == 0)
return 1;
else
return 0;
}
if (pos == 0)
return 1;
int answer = CountSets(x - 1, pos) +
CountSets(x - 2, pos - 1);
return answer;
}
// Function returns the count
// of all ordered sets
static int CountOrderedSets(int n)
{
// Prestore the factorial value
int []factorial = new int[10000];
factorial[0] = 1;
for(int i = 1; i < 10000; i++)
factorial[i] = factorial[i - 1] * i;
int answer = 0;
// Iterate all ordered set sizes and find
// the count for each one maximum ordered
// set size will be smaller than N as all
// elements are distinct and non consecutive
for(int i = 1; i <= n; i++)
{
// Multiply ny size! for all the
// arrangements because sets are ordered
int sets = CountSets(n, i) * factorial[i];
// Add to total answer
answer = answer + sets;
}
return answer;
}
// Driver code
public static void Main(String[] args)
{
int N = 3;
Console.Write(CountOrderedSets(N));
}
}
// This code is contributed by sapnasingh4991
Javascript
<script>
// Javascript program to count the number
// of ordered sets not containing
// consecutive numbers
// Function to calculate the count
// of ordered set for a given size
function CountSets(x , pos)
{
// Base cases
if (x <= 0) {
if (pos == 0)
return 1;
else
return 0;
}
if (pos == 0)
return 1;
var answer = CountSets(x - 1, pos) +
CountSets(x - 2, pos - 1);
return answer;
}
// Function returns the count
// of all ordered sets
function CountOrderedSets(n) {
// Prestore the factorial value
var factorial = Array(10000).fill(0);
factorial[0] = 1;
for (i = 1; i < 10000; i++)
factorial[i] = factorial[i - 1] * i;
var answer = 0;
// Iterate all ordered set sizes and find
// the count for each one maximum ordered
// set size will be smaller than N as all
// elements are distinct and non consecutive
for (i = 1; i <= n; i++) {
// Multiply ny size! for all the
// arrangements because sets are ordered
var sets = CountSets(n, i) * factorial[i];
// Add to total answer
answer = answer + sets;
}
return answer;
}
// Driver code
var N = 3;
document.write(CountOrderedSets(N));
// This code contributed by umadevi9616
</script>
Producción:
5
Complejidad del tiempo: O(2 N )
Enfoque eficiente:
- En el enfoque recursivo, estamos resolviendo subproblemas varias veces, es decir, sigue la propiedad de superposición de subproblemas en la programación dinámica . Entonces podemos usar una tabla de memorización o caché para que la solución sea eficiente.
C++
// C++ program to Count the number
// of ordered sets not containing
// consecutive numbers
#include <bits/stdc++.h>
using namespace std;
// DP table
int dp[500][500];
// Function to calculate the count
// of ordered set for a given size
int CountSets(int x, int pos)
{
// Base cases
if (x <= 0) {
if (pos == 0)
return 1;
else
return 0;
}
if (pos == 0)
return 1;
// If subproblem has been
// solved before
if (dp[x][pos] != -1)
return dp[x][pos];
int answer = CountSets(x - 1, pos)
+ CountSets(x - 2, pos - 1);
// Store and return answer to
// this subproblem
return dp[x][pos] = answer;
}
// Function returns the count
// of all ordered sets
int CountOrderedSets(int n)
{
// Prestore the factorial value
int factorial[10000];
factorial[0] = 1;
for (int i = 1; i < 10000; i++)
factorial[i] = factorial[i - 1] * i;
int answer = 0;
// Initialise the dp table
memset(dp, -1, sizeof(dp));
// Iterate all ordered set sizes and find
// the count for each one maximum ordered
// set size will be smaller than N as all
// elements are distinct and non consecutive.
for (int i = 1; i <= n; i++) {
// Multiply ny size! for all the
// arrangements because sets
// are ordered.
int sets = CountSets(n, i) * factorial[i];
// Add to total answer
answer = answer + sets;
}
return answer;
}
// Driver code
int main()
{
int N = 3;
cout << CountOrderedSets(N);
return 0;
}
Java
// Java program to count the number
// of ordered sets not containing
// consecutive numbers
import java.util.*;
class GFG{
// DP table
static int [][]dp = new int[500][500];
// Function to calculate the count
// of ordered set for a given size
static int CountSets(int x, int pos)
{
// Base cases
if (x <= 0)
{
if (pos == 0)
return 1;
else
return 0;
}
if (pos == 0)
return 1;
// If subproblem has been
// solved before
if (dp[x][pos] != -1)
return dp[x][pos];
int answer = CountSets(x - 1, pos) +
CountSets(x - 2, pos - 1);
// Store and return answer to
// this subproblem
return dp[x][pos] = answer;
}
// Function returns the count
// of all ordered sets
static int CountOrderedSets(int n)
{
// Prestore the factorial value
int []factorial = new int[10000];
factorial[0] = 1;
for(int i = 1; i < 10000; i++)
factorial[i] = factorial[i - 1] * i;
int answer = 0;
// Initialise the dp table
for(int i = 0; i < 500; i++)
{
for(int j = 0; j < 500; j++)
{
dp[i][j] = -1;
}
}
// Iterate all ordered set sizes and find
// the count for each one maximum ordered
// set size will be smaller than N as all
// elements are distinct and non consecutive.
for(int i = 1; i <= n; i++)
{
// Multiply ny size! for all the
// arrangements because sets
// are ordered.
int sets = CountSets(n, i) * factorial[i];
// Add to total answer
answer = answer + sets;
}
return answer;
}
// Driver code
public static void main(String[] args)
{
int N = 3;
System.out.print(CountOrderedSets(N));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to count the number # of ordered sets not containing # consecutive numbers # DP table dp = [[-1 for j in range(500)] for i in range(500)] # Function to calculate the count # of ordered set for a given size def CountSets(x, pos): # Base cases if (x <= 0): if (pos == 0): return 1 else: return 0 if (pos == 0): return 1 # If subproblem has been # solved before if (dp[x][pos] != -1): return dp[x][pos] answer = (CountSets(x - 1, pos) + CountSets(x - 2, pos - 1)) # Store and return answer to # this subproblem dp[x][pos] = answer return answer # Function returns the count # of all ordered sets def CountOrderedSets(n): # Prestore the factorial value factorial = [0 for i in range(10000)] factorial[0] = 1 for i in range(1, 10000): factorial[i] = factorial[i - 1] * i answer = 0 # Iterate all ordered set sizes and find # the count for each one maximum ordered # set size will be smaller than N as all # elements are distinct and non consecutive. for i in range(1, n + 1): # Multiply ny size! for all the # arrangements because sets # are ordered. sets = CountSets(n, i) * factorial[i] # Add to total answer answer = answer + sets return answer # Driver code if __name__=="__main__": N = 3 print(CountOrderedSets(N)) # This code is contributed by rutvik_56
C#
// C# program to count the number
// of ordered sets not containing
// consecutive numbers
using System;
class GFG{
// DP table
static int [,]dp = new int[500, 500];
// Function to calculate the count
// of ordered set for a given size
static int CountSets(int x, int pos)
{
// Base cases
if (x <= 0)
{
if (pos == 0)
return 1;
else
return 0;
}
if (pos == 0)
return 1;
// If subproblem has been
// solved before
if (dp[x,pos] != -1)
return dp[x, pos];
int answer = CountSets(x - 1, pos) +
CountSets(x - 2, pos - 1);
// Store and return answer to
// this subproblem
return dp[x, pos] = answer;
}
// Function returns the count
// of all ordered sets
static int CountOrderedSets(int n)
{
// Prestore the factorial value
int []factorial = new int[10000];
factorial[0] = 1;
for(int i = 1; i < 10000; i++)
factorial[i] = factorial[i - 1] * i;
int answer = 0;
// Initialise the dp table
for(int i = 0; i < 500; i++)
{
for(int j = 0; j < 500; j++)
{
dp[i, j] = -1;
}
}
// Iterate all ordered set sizes and find
// the count for each one maximum ordered
// set size will be smaller than N as all
// elements are distinct and non consecutive.
for(int i = 1; i <= n; i++)
{
// Multiply ny size! for all the
// arrangements because sets
// are ordered.
int sets = CountSets(n, i) * factorial[i];
// Add to total answer
answer = answer + sets;
}
return answer;
}
// Driver code
public static void Main(String[] args)
{
int N = 3;
Console.Write(CountOrderedSets(N));
}
}
// This code is contributed by sapnasingh4991
Javascript
<script>
// JavaScript program to Count the number
// of ordered sets not containing
// consecutive numbers
// DP table
var dp = Array.from(Array(500), ()=>Array(500));
// Function to calculate the count
// of ordered set for a given size
function CountSets(x, pos)
{
// Base cases
if (x <= 0) {
if (pos == 0)
return 1;
else
return 0;
}
if (pos == 0)
return 1;
// If subproblem has been
// solved before
if (dp[x][pos] != -1)
return dp[x][pos];
var answer = CountSets(x - 1, pos)
+ CountSets(x - 2, pos - 1);
// Store and return answer to
// this subproblem
return dp[x][pos] = answer;
}
// Function returns the count
// of all ordered sets
function CountOrderedSets(n)
{
// Prestore the factorial value
var factorial = Array(10000).fill(0);
factorial[0] = 1;
for (var i = 1; i < 10000; i++)
factorial[i] = factorial[i - 1] * i;
var answer = 0;
// Initialise the dp table
dp = Array.from(Array(500), ()=>Array(500).fill(-1));
// Iterate all ordered set sizes and find
// the count for each one maximum ordered
// set size will be smaller than N as all
// elements are distinct and non consecutive.
for (var i = 1; i <= n; i++) {
// Multiply ny size! for all the
// arrangements because sets
// are ordered.
var sets = CountSets(n, i) * factorial[i];
// Add to total answer
answer = answer + sets;
}
return answer;
}
// Driver code
var N = 3;
document.write( CountOrderedSets(N));
</script>
Producción:
5
Complejidad temporal: O(N 2 )