Considere un círculo con n puntos en la circunferencia donde n es par . Cuente el número de formas en que podemos conectar estos puntos de manera que no haya dos líneas de conexión que se crucen entre sí y cada punto esté conectado exactamente con otro punto. Cualquier punto se puede conectar con cualquier otro punto.
Consider a circle with 4 points.
1
2 3
4
In above diagram, there are two
non-crossing ways to connect
{{1, 2}, {3, 4}} and {{1, 3}, {2, 4}}.
Note that {{2, 3}, {1, 4}} is invalid
as it would cause a cross
Ejemplos:
Input : n = 2 Output : 1 Input : n = 4 Output : 2 Input : n = 6 Output : 5 Input : n = 3 Output : Invalid n must be even.
Necesitamos dibujar n/2 líneas para conectar n puntos. Cuando dibujamos una línea, dividimos los puntos en dos conjuntos que deben conectarse. Cada conjunto debe estar conectado dentro de sí mismo. A continuación se muestra la relación de recurrencia para el mismo.
Let m = n/2
// For each line we draw, we divide points
// into two sets such that one set is going
// to be connected with i lines and other
// with m-i-1 lines.
Count(m) = ∑ Count(i) * Count(m-i-1)
where 0 <= i < m
Count(0) = 1
Total number of ways with n points
= Count(m) = Count(n/2)
Si echamos un vistazo más de cerca a la recurrencia anterior, en realidad es recurrencia de números catalanes . Así que la tarea se reduce a encontrar el n/2′ número catalán.
A continuación se muestra la implementación basada en la idea anterior.
C++
// C++ program to count number of ways to connect n (where n
// is even) points on a circle such that no two connecting
// lines cross each other and every point is connected with
// one other point.
#include <iostream>
using namespace std;
// A dynamic programming based function to find nth
// Catalan number
unsigned long int catalanDP(unsigned int n)
{
// Table to store results of subproblems
unsigned long int catalan[n + 1];
// Initialize first two values in table
catalan[0] = catalan[1] = 1;
// Fill entries in catalan[] using recursive formula
for (int i = 2; i <= n; i++) {
catalan[i] = 0;
for (int j = 0; j < i; j++)
catalan[i] += catalan[j] * catalan[i - j - 1];
}
// Return last entry
return catalan[n];
}
// Returns count of ways to connect n points on a circle
// such that no two connecting lines cross each other and
// every point is connected with one other point.
unsigned long int countWays(unsigned long int n)
{
// Throw error if n is odd
if (n & 1) {
cout << "Invalid";
return 0;
}
// Else return n/2'th Catalan number
return catalanDP(n / 2);
}
// Driver program to test above function
int main()
{
cout << countWays(6) << " ";
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// C program to count number of ways to connect n (where n
// is even) points on a circle such that no two connecting
// lines cross each other and every point is connected with
// one other point.
#include <stdio.h>
// A dynamic programming based function to find nth
// Catalan number
unsigned long int catalanDP(unsigned int n)
{
// Table to store results of subproblems
unsigned long int catalan[n + 1];
// Initialize first two values in table
catalan[0] = catalan[1] = 1;
// Fill entries in catalan[] using recursive formula
for (int i = 2; i <= n; i++) {
catalan[i] = 0;
for (int j = 0; j < i; j++)
catalan[i] += catalan[j] * catalan[i - j - 1];
}
// Return last entry
return catalan[n];
}
// Returns count of ways to connect n points on a circle
// such that no two connecting lines cross each other and
// every point is connected with one other point.
unsigned long int countWays(unsigned long int n)
{
// Throw error if n is odd
if (n & 1) {
printf("Invalid");
return 0;
}
// Else return n/2'th Catalan number
return catalanDP(n / 2);
}
// Driver program to test above function
int main()
{
printf("%ld", countWays(6));
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java program to count number of ways to connect n (where
// n is even) points on a circle such that no two connecting
// lines cross each other and every point is connected with
// one other point.
import java.io.*;
class GFG {
// A dynamic programming based function to find nth
// Catalan number
static int catalanDP(int n)
{
// Table to store results of subproblems
int[] catalan = new int[n + 1];
// Initialize first two values in table
catalan[0] = catalan[1] = 1;
// Fill entries in catalan[] using recursive formula
for (int i = 2; i <= n; i++) {
catalan[i] = 0;
for (int j = 0; j < i; j++)
catalan[i]
+= catalan[j] * catalan[i - j - 1];
}
// Return last entry
return catalan[n];
}
// Returns count of ways to connect n points on a circle
// such that no two connecting lines cross each other
// and every point is connected with one other point.
static int countWays(int n)
{
// Throw error if n is odd
if (n < 1) {
System.out.println("Invalid");
return 0;
}
// Else return n/2'th Catalan number
return catalanDP(n / 2);
}
// Driver Code
public static void main(String[] args)
{
System.out.println(countWays(6) + " ");
}
}
// This code is contributed by Aditya Kumar (adityakumar129)
Python3
# Python3 program to count number
# of ways to connect n (where n
# is even) points on a circle such
# that no two connecting lines
# cross each other and every point
# is connected with one other point.
# A dynamic programming based
# function to find nth Catalan number
def catalanDP(n):
# Table to store results
# of subproblems
catalan = [1 for i in range(n + 1)]
# Fill entries in catalan[]
# using recursive formula
for i in range(2, n + 1):
catalan[i] = 0
for j in range(i):
catalan[i] += (catalan[j] *
catalan[i - j - 1])
# Return last entry
return catalan[n]
# Returns count of ways to connect
# n points on a circle such that
# no two connecting lines cross
# each other and every point is
# connected with one other point.
def countWays(n):
# Throw error if n is odd
if (n & 1):
print("Invalid")
return 0
# Else return n/2'th Catalan number
return catalanDP(n // 2)
# Driver Code
print(countWays(6))
# This code is contributed
# by sahilshelangia
C#
// C# program to count number
// of ways to connect n (where
// n is even) points on a circle
// such that no two connecting
// lines cross each other and
// every point is connected with
// one other point.
using System;
class GFG
{
// A dynamic programming
// based function to find
// nth Catalan number
static int catalanDP(int n)
{
// Table to store
// results of subproblems
int []catalan = new int [n + 1];
// Initialize first
// two values in table
catalan[0] = catalan[1] = 1;
// Fill entries in catalan[]
// using recursive formula
for (int i = 2; i <= n; i++)
{
catalan[i] = 0;
for (int j = 0; j < i; j++)
catalan[i] += catalan[j] *
catalan[i - j - 1];
}
// Return last entry
return catalan[n];
}
// Returns count of ways to
// connect n points on a circle
// such that no two connecting
// lines cross each other and
// every point is connected
// with one other point.
static int countWays(int n)
{
// Throw error if n is odd
if (n < 1)
{
Console.WriteLine("Invalid");
return 0;
}
// Else return n/2'th
// Catalan number
return catalanDP(n / 2);
}
// Driver Code
static public void Main ()
{
Console.WriteLine(countWays(6) + " ");
}
}
// This code is contributed
// by M_kit
PHP
<?php
// PHP program to count number of
// ways to connect n (where n is
// even) points on a circle such
// that no two connecting lines
// cross each other and every
// point is connected with one
// other point.
// A dynamic programming based
// function to find nth Catalan number
function catalanDP($n)
{
// Table to store results
// of subproblems Initialize
// first two values in table
$catalan[0] = $catalan[1] = 1;
// Fill entries in catalan[]
// using recursive formula
for ($i = 2; $i <= $n; $i++)
{
$catalan[$i] = 0;
for ($j = 0; $j < $i; $j++)
$catalan[$i] += $catalan[$j] *
$catalan[$i - $j - 1];
}
// Return last entry
return $catalan[$n];
}
// Returns count of ways to connect
// n points on a circle such that
// no two connecting lines cross
// each other and every point is
// connected with one other point.
function countWays($n)
{
// Throw error if n is odd
if ($n & 1)
{
echo "Invalid";
return 0;
}
// Else return n/2'th
// Catalan number
return catalanDP($n / 2);
}
// Driver Code
echo countWays(6) , " ";
// This code is contributed by aj_36
?>
Javascript
<script>
// javascript program to count number of
// ways to connect n (where n is
// even) points on a circle such
// that no two connecting lines
// cross each other and every
// point is connected with one
// other point.
// A dynamic programming based
// function to find nth Catalan number
function catalanDP(n)
{
// Table to store results
// of subproblems Initialize
// first two values in table
let catalan = []
catalan[0] = catalan[1] = 1;
// Fill entries in catalan[]
// using recursive formula
for (let i = 2; i <= n; i++)
{
catalan[i] = 0;
for (let j = 0; j < i; j++)
catalan[i] += catalan[j] *
catalan[i - j - 1];
}
// Return last entry
return catalan[n];
}
// Returns count of ways to connect
// n points on a circle such that
// no two connecting lines cross
// each other and every point is
// connected with one other point.
function countWays(n)
{
// Throw error if n is odd
if (n & 1)
{
document.write("Invalid");
return 0;
}
// Else return n/2'th
// Catalan number
return catalanDP(n / 2);
}
// Driver Code
document.write(countWays(6) + " ");
// This code is contributed by _saurabh_jaiswal
</script>
Producción :
5
Complejidad del tiempo: O(n 2 )
Espacio auxiliar: O(n)
Este artículo es una contribución de Shivam Agrawal . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo 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.
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