Dado un número n, cree una array de tamaño 2n tal que la array contenga 2 instancias de cada número del 1 al n, y la cantidad de elementos entre dos instancias de un número i sea igual a i. Si tal configuración no es posible, imprima lo mismo.
Ejemplos:
Input: n = 3
Output: res[] = {3, 1, 2, 1, 3, 2}
Input: n = 2
Output: Not Possible
Input: n = 4
Output: res[] = {4, 1, 3, 1, 2, 4, 3, 2}
Recomendamos encarecidamente minimizar el navegador y probarlo usted mismo primero.
Una solución es retroceder. La idea es simple, colocamos dos instancias de n en un lugar, luego recurrimos para n-1. Si la recurrencia es exitosa, devolvemos verdadero, de lo contrario retrocedemos e intentamos colocar n en una ubicación diferente. A continuación se muestra la implementación de la idea.
C++
// A backtracking based C++ Program to fill
// two instances of all numbers from 1 to n
// in a specific way
#include <bits/stdc++.h>
using namespace std;
// A recursive utility function to fill
// two instances of numbers from 1 to n
// in res[0..2n-1]. 'curr' is current value of n.
bool fillUtil(int res[], int curr, int n)
{
// If current number becomes 0,
// then all numbers are filled
if (curr == 0)
return true;
// Try placing two instances of 'curr' at
// all possible locations till solution is found
int i;
for (i = 0; i < 2 * n - curr - 1; i++)
{
// Two 'curr' should be placed at
// 'curr+1' distance
if (res[i] == 0 && res[i + curr + 1] == 0)
{
// Place two instances of 'curr'
res[i] = res[i + curr + 1] = curr;
// Recur to check if the above placement
// leads to a solution
if (fillUtil(res, curr - 1, n))
return true;
// If solution is not possible,
// then backtrack
res[i] = res[i + curr + 1] = 0;
}
}
return false;
}
// This function prints the result for
// input number 'n' using fillUtil()
void fill(int n)
{
// Create an array of size 2n and
// initialize all elements in it as 0
int res[2 * n], i;
for (i = 0; i < 2 * n; i++)
res[i] = 0;
// If solution is possible,
// then print it.
if (fillUtil(res, n, n))
{
for (i = 0; i < 2 * n; i++)
cout << res[i] << " ";
}
else
cout << "Not Possible";
}
// Driver Code
int main()
{
fill(7);
return 0;
}
// This code is contributed
// by SHUBHAMSINGH8410
C
// A backtracking based C Program to fill two instances of all numbers
// from 1 to n in a specific way
#include <stdio.h>
#include <stdbool.h>
// A recursive utility function to fill two instances of numbers from
// 1 to n in res[0..2n-1]. 'curr' is current value of n.
bool fillUtil(int res[], int curr, int n)
{
// If current number becomes 0, then all numbers are filled
if (curr == 0) return true;
// Try placing two instances of 'curr' at all possible locations
// till solution is found
int i;
for (i=0; i<2*n-curr-1; i++)
{
// Two 'curr' should be placed at 'curr+1' distance
if (res[i] == 0 && res[i + curr + 1] == 0)
{
// Place two instances of 'curr'
res[i] = res[i + curr + 1] = curr;
// Recur to check if the above placement leads to a solution
if (fillUtil(res, curr-1, n))
return true;
// If solution is not possible, then backtrack
res[i] = res[i + curr + 1] = 0;
}
}
return false;
}
// This function prints the result for input number 'n' using fillUtil()
void fill(int n)
{
// Create an array of size 2n and initialize all elements in it as 0
int res[2*n], i;
for (i=0; i<2*n; i++)
res[i] = 0;
// If solution is possible, then print it.
if (fillUtil(res, n, n))
{
for (i=0; i<2*n; i++)
printf("%d ", res[i]);
}
else
puts("Not Possible");
}
// Driver program
int main()
{
fill(7);
return 0;
}
Java
// A backtracking based C++ Program to fill
// two instances of all numbers from 1 to n
// in a specific way
import java.io.*;
class GFG
{
// A recursive utility function to fill
// two instances of numbers from 1 to n
// in res[0..2n-1]. 'curr' is current value of n.
static boolean fillUtil(int res[], int curr, int n)
{
// If current number becomes 0,
// then all numbers are filled
if (curr == 0)
return true;
// Try placing two instances of 'curr' at
// all possible locations till solution is found
int i;
for (i = 0; i < 2 * n - curr - 1; i++)
{
// Two 'curr' should be placed at
// 'curr+1' distance
if (res[i] == 0 && res[i + curr + 1] == 0)
{
// Place two instances of 'curr'
res[i] = res[i + curr + 1] = curr;
// Recur to check if the above placement
// leads to a solution
if (fillUtil(res, curr - 1, n))
return true;
// If solution is not possible,
// then backtrack
res[i] = res[i + curr + 1] = 0;
}
}
return false;
}
// This function prints the result for
// input number 'n' using fillUtil()
static void fill(int n)
{
// Create an array of size 2n and
// initialize all elements in it as 0
int res[] = new int[2 * n];
int i;
for (i = 0; i < 2 * n; i++)
res[i] = 0;
// If solution is possible,
// then print it.
if (fillUtil(res, n, n))
{
for (i = 0; i < 2 * n; i++)
System.out.print(res[i] + " ");
}
else
System.out.print("Not Possible");
}
// Driver Code
public static void main (String[] args)
{
fill(7);
}
}
// This code is contributed by ajit
Python3
# A backtracking based Python3 Program
# to fill two instances of all numbers
# from 1 to n in a specific way
def fillUtil(res, curr, n):
# A recursive utility function to fill
# two instances of numbers from 1 to n
# in res[0..2n-1]. 'curr' is current value of n.
# If current number becomes 0,
# then all numbers are filled
if curr == 0:
return True
# Try placing two instances of 'curr' at all
# possible locations till solution is found
for i in range(2 * n - curr - 1):
# Two 'curr' should be placed
# at 'curr+1' distance
if res[i] == 0 and res[i + curr + 1] == 0:
# Place two instances of 'curr'
res[i] = res[i + curr + 1] = curr
# Recur to check if the above
# placement leads to a solution
if fillUtil(res, curr - 1, n):
return True
# If solution is not possible,
# then backtrack
res[i] = 0
res[i + curr + 1] = 0
return False
def fill(n):
# This function prints the result
# for input number 'n' using fillUtil()
# Create an array of size 2n and
# initialize all elements in it as 0
res = [0] * (2 * n)
# If solution is possible, then print it.
if fillUtil(res, n, n):
for i in range(2 * n):
print(res[i], end = ' ')
print()
else:
print("Not Possible")
# Driver Code
if __name__ == '__main__':
fill(7)
# This code is contributed by vibhu4agarwal
C#
// A backtracking based C# Program to fill
// two instances of all numbers from 1 to n
// in a specific way
using System;
class GFG
{
// A recursive utility function to fill
// two instances of numbers from 1 to n
// in res[0..2n-1]. 'curr' is current value of n.
static bool fillUtil(int []res, int curr, int n)
{
// If current number becomes 0,
// then all numbers are filled
if (curr == 0)
return true;
// Try placing two instances of 'curr' at
// all possible locations till solution is found
int i;
for (i = 0; i < 2 * n - curr - 1; i++)
{
// Two 'curr' should be placed at
// 'curr+1' distance
if (res[i] == 0 && res[i + curr + 1] == 0)
{
// Place two instances of 'curr'
res[i] = res[i + curr + 1] = curr;
// Recur to check if the above placement
// leads to a solution
if (fillUtil(res, curr - 1, n))
return true;
// If solution is not possible,
// then backtrack
res[i] = res[i + curr + 1] = 0;
}
}
return false;
}
// This function prints the result for
// input number 'n' using fillUtil()
static void fill(int n)
{
// Create an array of size 2n and
// initialize all elements in it as 0
int []res=new int[2 * n];
int i;
for (i = 0; i < (2 * n); i++)
res[i] = 0;
// If solution is possible,
// then print it.
if (fillUtil(res, n, n))
{
for (i = 0; i < 2 * n; i++)
Console.Write (res[i] + " ");
}
else
Console.Write ("Not Possible");
}
// Driver Code
static public void Main ()
{
fill(7);
}
}
// This code is contributed by ajit
Javascript
<script>
// A backtracking based Javascript Program to fill
// two instances of all numbers from 1 to n
// in a specific way
// A recursive utility function to fill
// two instances of numbers from 1 to n
// in res[0..2n-1]. 'curr' is current value of n.
function fillUtil(res, curr, n)
{
// If current number becomes 0,
// then all numbers are filled
if (curr == 0)
return true;
// Try placing two instances of 'curr' at
// all possible locations till solution is found
let i;
for (i = 0; i < 2 * n - curr - 1; i++)
{
// Two 'curr' should be placed at
// 'curr+1' distance
if (res[i] == 0 && res[i + curr + 1] == 0)
{
// Place two instances of 'curr'
res[i] = res[i + curr + 1] = curr;
// Recur to check if the above placement
// leads to a solution
if (fillUtil(res, curr - 1, n))
return true;
// If solution is not possible,
// then backtrack
res[i] = res[i + curr + 1] = 0;
}
}
return false;
}
// This function prints the result for
// input number 'n' using fillUtil()
function fill(n)
{
// Create an array of size 2n and
// initialize all elements in it as 0
let res=new Array(2 * n);
let i;
for (i = 0; i < (2 * n); i++)
res[i] = 0;
// If solution is possible,
// then print it.
if (fillUtil(res, n, n))
{
for (i = 0; i < 2 * n; i++)
document.write(res[i] + " ");
}
else
document.write("Not Possible");
}
fill(7);
// This code is contributed by divyeshrabadiya07.
</script>
Producción:
7 3 6 2 5 3 2 4 7 6 5 1 4 1
La solución anterior puede no ser la mejor solución posible. Parece que hay un patrón en la salida. Estoy buscando una mejor solución de otros geeks.
Este artículo es una contribución de Asif . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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