Dado un entero positivo n . La tarea es encontrar el término de coeficiente máximo en todos los coeficientes binomiales.
La serie de coeficientes binomiales es
n C 0 , n C 1 , n C 2 , …., n C r , …., n C n-2 , n C n-1 , n C n
la tarea es encontrar el valor máximo de n C r .
Ejemplos:
Input : n = 4 Output : 6 4C0 = 1 4C1 = 4 4C2 = 6 4C3 = 1 4C4 = 1 So, maximum coefficient value is 6. Input : n = 3 Output : 3
Método 1: (Fuerza bruta)
La idea es encontrar todo el valor de la serie de coeficientes binomiales y encontrar el valor máximo en la serie.
A continuación se muestra la implementación de este enfoque:
C++
// CPP Program to find maximum binomial coefficient
// term
#include<bits/stdc++.h>
using namespace std;
// Return maximum binomial coefficient term value.
int maxcoefficientvalue(int n)
{
int C[n+1][n+1];
// Calculate value of Binomial Coefficient in
// bottom up manner
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= min(i, n); j++)
{
// Base Cases
if (j == 0 || j == i)
C[i][j] = 1;
// Calculate value using previously
// stored values
else
C[i][j] = C[i-1][j-1] + C[i-1][j];
}
}
// finding the maximum value.
int maxvalue = 0;
for (int i = 0; i <= n; i++)
maxvalue = max(maxvalue, C[n][i]);
return maxvalue;
}
// Driven Program
int main()
{
int n = 4;
cout << maxcoefficientvalue(n) << endl;
return 0;
}
Java
// Java Program to find
// maximum binomial
// coefficient term
import java.io.*;
class GFG
{
// Return maximum binomial
// coefficient term value.
static int maxcoefficientvalue(int n)
{
int [][]C = new int[n + 1][n + 1];
// Calculate value of
// Binomial Coefficient
// in bottom up manner
for (int i = 0; i <= n; i++)
{
for (int j = 0;
j <= Math.min(i, n); j++)
{
// Base Cases
if (j == 0 || j == i)
C[i][j] = 1;
// Calculate value
// using previously
// stored values
else
C[i][j] = C[i - 1][j - 1] +
C[i - 1][j];
}
}
// finding the
// maximum value.
int maxvalue = 0;
for (int i = 0; i <= n; i++)
maxvalue = Math.max(maxvalue, C[n][i]);
return maxvalue;
}
// Driver Code
public static void main (String[] args)
{
int n = 4;
System.out.println(maxcoefficientvalue(n));
}
}
// This code is contributed by ajit
Python3
# Python3 Program to find # maximum binomial # coefficient term # Return maximum binomial # coefficient term value. def maxcoefficientvalue(n): C = [[0 for x in range(n + 1)] for y in range(n + 1)]; # Calculate value of # Binomial Coefficient in # bottom up manner for i in range(n + 1): for j in range(min(i, n) + 1): # Base Cases if (j == 0 or j == i): C[i][j] = 1; # Calculate value # using previously # stored values else: C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]); # finding the maximum value. maxvalue = 0; for i in range(n + 1): maxvalue = max(maxvalue, C[n][i]); return maxvalue; # Driver Code n = 4; print(maxcoefficientvalue(n)); # This code is contributed by mits
C#
// C# Program to find maximum binomial coefficient
// term
using System;
public class GFG {
// Return maximum binomial coefficient term value.
static int maxcoefficientvalue(int n)
{
int [,]C = new int[n+1,n+1];
// Calculate value of Binomial Coefficient in
// bottom up manner
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= Math.Min(i, n); j++)
{
// Base Cases
if (j == 0 || j == i)
C[i,j] = 1;
// Calculate value using previously
// stored values
else
C[i,j] = C[i-1,j-1] + C[i-1,j];
}
}
// finding the maximum value.
int maxvalue = 0;
for (int i = 0; i <= n; i++)
maxvalue = Math.Max(maxvalue, C[n,i]);
return maxvalue;
}
// Driven Program
static public void Main ()
{
int n = 4;
Console.WriteLine(maxcoefficientvalue(n));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP Program to find
// maximum binomial
// coefficient term
// Return maximum binomial
// coefficient term value.
function maxcoefficientvalue($n)
{
// Calculate value of
// Binomial Coefficient in
// bottom up manner
for ($i = 0; $i <= $n; $i++)
{
for ($j = 0; $j <= min($i, $n); $j++)
{
// Base Cases
if ($j == 0 || $j == $i)
$C[$i][$j] = 1;
// Calculate value
// using previously
// stored values
else
$C[$i][$j] = $C[$i - 1][$j - 1] +
$C[$i - 1][$j];
}
}
// finding the maximum value.
$maxvalue = 0;
for ($i = 0; $i <= $n; $i++)
$maxvalue = max($maxvalue, $C[$n][$i]);
return $maxvalue;
}
// Driver Code
$n = 4;
echo maxcoefficientvalue($n), "\n";
// This code is contributed by aj_36
?>
Javascript
<script>
// JavaScript Program to find
// maximum binomial
// coefficient term
// Returns value of
// Binomial Coefficient
// C(n, k)
function binomialCoeff(n, k)
{
let C = new Array(n+1);
// Loop to create 2D array using 1D array
for (let i = 0; i < C.length; i++) {
C[i] = new Array(2);
}
// Calculate value of
// Binomial Coefficient
// in bottom up manner
for (let i = 0; i <= n; i++)
{
for (let j = 0;
j <= Math.min(i, k); j++)
{
// Base Cases
if (j == 0 || j == i)
C[i][j] = 1;
// Calculate value using
// previously stored values
else
C[i][j] = C[i - 1][j - 1] +
C[i - 1][j];
}
}
return C[n][k];
}
// Return maximum
// binomial coefficient
// term value.
function maxcoefficientvalue(n)
{
// if n is even
if (n % 2 == 0)
return binomialCoeff(n, n / 2);
// if n is odd
else
return binomialCoeff(n, (n + 1) / 2);
}
// Driver Code
let n = 4;
document.write(maxcoefficientvalue(n));
// This code is contributed by avijitmondal1998..
</script>
Producción:
6
Método 2: (usando fórmula)
Prueba,
Expansión de (x + y) n son:
n C 0 x n y 0 , n C 1 x n-1 y 1 , n C 2 x n-2 y 2 , …., n C r x n-r y r , … ., n C n-2 x 2 y n-2 , n C n-1 x 1 y n-1 , n C n x 0y n
Entonces, poniendo x = 1 y y = 1, obtenemos el coeficiente binomial,
n C 0 , n C 1 , n C 2 , …., n C r , …., n C n-2 , n C n- 1 , n C n
Sea el término ti +1 que contiene el mayor valor en (x + y) n . Por lo tanto,
t r+1 >= t r
n C r x n-r y r >= n C r-1x n-r+1 y r-1
Poniendo x = 1 y y = 1,
n C r >= n C r-1
n C r / n C r-1 >= 1
(usando n C r / n C r -1 = (n-r+1)/r)
(n-r+1)/r >= 1
(n+1)/r – 1 >= 1
(n+1)/r >= 2
(n+ 1)/2 >= r
Por lo tanto, r debe ser menor que igual a (n+1)/2.
Y r debe ser entero. Entonces, obtenemos un coeficiente máximo para r igual a:
(1) n/2, cuando n es par.
(2) (n+1)/2 o (n-1)/2, cuando n es impar.
C++
// CPP Program to find maximum binomial coefficient term
#include<bits/stdc++.h>
using namespace std;
// Returns value of Binomial Coefficient C(n, k)
int binomialCoeff(int n, int k)
{
int C[n+1][k+1];
// Calculate value of Binomial Coefficient
// in bottom up manner
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= min(i, k); j++)
{
// Base Cases
if (j == 0 || j == i)
C[i][j] = 1;
// Calculate value using previously
// stored values
else
C[i][j] = C[i-1][j-1] + C[i-1][j];
}
}
return C[n][k];
}
// Return maximum binomial coefficient term value.
int maxcoefficientvalue(int n)
{
// if n is even
if (n%2 == 0)
return binomialCoeff(n, n/2);
// if n is odd
else
return binomialCoeff(n, (n+1)/2);
}
// Driven Program
int main()
{
int n = 4;
cout << maxcoefficientvalue(n) << endl;
return 0;
}
Java
// Java Program to find
// maximum binomial
// coefficient term
import java.io.*;
class GFG
{
// Returns value of
// Binomial Coefficient
// C(n, k)
static int binomialCoeff(int n,
int k)
{
int [][]C = new int[n + 1][k + 1];
// Calculate value of
// Binomial Coefficient
// in bottom up manner
for (int i = 0; i <= n; i++)
{
for (int j = 0;
j <= Math.min(i, k); j++)
{
// Base Cases
if (j == 0 || j == i)
C[i][j] = 1;
// Calculate value using
// previously stored values
else
C[i][j] = C[i - 1][j - 1] +
C[i - 1][j];
}
}
return C[n][k];
}
// Return maximum
// binomial coefficient
// term value.
static int maxcoefficientvalue(int n)
{
// if n is even
if (n % 2 == 0)
return binomialCoeff(n, n / 2);
// if n is odd
else
return binomialCoeff(n, (n + 1) / 2);
}
// Driver Code
public static void main(String[] args)
{
int n = 4;
System.out.println(maxcoefficientvalue(n));
}
}
// This code is contributed
// by akt_mit
Python3
# Python3 Program to find # maximum binomial # coefficient term # Returns value of # Binomial Coefficient C(n, k) def binomialCoeff(n, k): C=[[0 for x in range(k+1)] for y in range(n+1)] # Calculate value of # Binomial Coefficient # in bottom up manner for i in range(n+1): for j in range(min(i,k)+1): # Base Cases if (j == 0 or j == i): C[i][j] = 1; # Calculate value # using previously # stored values else: C[i][j] = C[i - 1][j - 1] + C[i - 1][j]; return C[n][k]; # Return maximum binomial # coefficient term value. def maxcoefficientvalue(n): # if n is even if (n % 2 == 0): return binomialCoeff(n, int(n / 2)); # if n is odd else: return binomialCoeff(n, int((n + 1) / 2)); # Driver Code if __name__=='__main__': n = 4; print(maxcoefficientvalue(n)); # This code is contributed by mits
C#
// C# Program to find maximum binomial
// coefficient term
using System;
public class GFG {
// Returns value of Binomial Coefficient
// C(n, k)
static int binomialCoeff(int n, int k)
{
int [,]C = new int[n+1,k+1];
// Calculate value of Binomial
// Coefficient in bottom up manner
for (int i = 0; i <= n; i++)
{
for (int j = 0;
j <= Math.Min(i, k); j++)
{
// Base Cases
if (j == 0 || j == i)
C[i,j] = 1;
// Calculate value using
// previously stored values
else
C[i,j] = C[i-1,j-1] +
C[i-1,j];
}
}
return C[n,k];
}
// Return maximum binomial coefficient
// term value.
static int maxcoefficientvalue(int n)
{
// if n is even
if (n % 2 == 0)
return binomialCoeff(n, n/2);
// if n is odd
else
return binomialCoeff(n, (n + 1) / 2);
}
// Driven Program
static public void Main ()
{
int n = 4;
Console.WriteLine(maxcoefficientvalue(n));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP Program to find
// maximum binomial
// coefficient term
// Returns value of
// Binomial Coefficient C(n, k)
function binomialCoeff($n, $k)
{
$C[$n + 1][$k + 1] = array(0);
// Calculate value of
// Binomial Coefficient
// in bottom up manner
for ($i = 0; $i <= $n; $i++)
{
for ($j = 0;
$j <= min($i, $k); $j++)
{
// Base Cases
if ($j == 0 || $j == $i)
$C[$i][$j] = 1;
// Calculate value
// using previously
// stored values
else
$C[$i][$j] = $C[$i - 1][$j - 1] +
$C[$i - 1][$j];
}
}
return $C[$n][$k];
}
// Return maximum binomial
// coefficient term value.
function maxcoefficientvalue($n)
{
// if n is even
if ($n % 2 == 0)
return binomialCoeff($n, $n / 2);
// if n is odd
else
return binomialCoeff($n,
($n + 1) / 2);
}
// Driver Code
$n = 4;
echo maxcoefficientvalue($n), "\n";
// This code is contributed by m_kit
?>
Javascript
<script>
// Javascript Program to find
// maximum binomial
// coefficient term
// Returns value of
// Binomial Coefficient
// C(n, k)
function binomialCoeff(n, k)
{
let C = new Array(n + 1);
for(let i = 0; i <= n; i++)
{
C[i] = new Array(k + 1);
}
// Calculate value of
// Binomial Coefficient
// in bottom up manner
for(let i = 0; i <= n; i++)
{
for(let j = 0; j <= Math.min(i, k); j++)
{
// Base Cases
if (j == 0 || j == i)
C[i][j] = 1;
// Calculate value using
// previously stored values
else
C[i][j] = C[i - 1][j - 1] +
C[i - 1][j];
}
}
return C[n][k];
}
// Return maximum
// binomial coefficient
// term value.
function maxcoefficientvalue(n)
{
// If n is even
if (n % 2 == 0)
return binomialCoeff(n, n / 2);
// If n is odd
else
return binomialCoeff(n, (n + 1) / 2);
}
// Driver Code
let n = 4;
document.write(maxcoefficientvalue(n));
// This code is contributed by suresh07
</script>
Producción:
6