数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究连续二项式系数乘积之和
问题陈述包括打印任何正数 N（将作为用户输入）的连续二项式系数乘积之和。
任何项的二项式展开式中的正系数称为二项式系数。这些二项式系数可以使用帕斯卡三角形或直接公式计算出来。计算二项式系数的公式
$$\mathrm{^nC_{r}=\frac{n!}{(n-r)!r!}}$$
其中，n 和 r 可以是任何正数，并且 r 绝不能大于 n。
注意：0! 的值始终等于 1。
在此问题中，我们将得到一个正数 N，我们的任务是找出连续二项式系数乘积之和，即 $\mathrm{\mathrm{^{i=N-1}{\sum_{i=0}}(^NC_{i}*^NC_{i+1})}}$
让我们通过一些示例来理解这个问题。
示例
输入
N=4
输出
56
解释 - 这里我们得到 N=4，我们需要找到连续二项式系数乘积之和，即 $\mathrm{^{i=N-1}{\sum_{i=0}}(^NC_{i}*^NC_{i+1})}$
对于 N=4，
$\mathrm{(^4C_{0}*^4C_{1})+(^4C_{1}*^4C_{2})+(^4C_{2}*^4C_{3})+(^4C_{3}*^4C_{4})}$
使用公式计算二项式系数的值，我们得到
(1*4)+(4*6)+(6*4)+(4*1)=4+24+24+4=56
总和为 56，这是我们需要的输出。
输入
N=1
输出
1
解释 - 输入中的 N 值为 1。我们需要找到从 i=0 到 i=N−1（即 0）的二项式系数乘积之和。
因此，所需的总和为，$\mathrm{^{i=N-1}{\sum_{i=0}}(^NC_{i}*^NC_{i+1})=(^1C_{0}*^1C_{1})=1*1=1}$
让我们了解用于查找任何数字 N 的连续二项式系数乘积之和的算法。
算法
如果我们为每种情况计算二项式系数的值，然后找到连续二项式系数乘积之和，则该过程可能会非常冗长。
我们将使用帕斯卡三角形的概念来计算作为输入给出的正数 N 的二项式系数的值。
帕斯卡三角形是一个三角形的数组，三角形中的每个值都代表二项式系数的值。帕斯卡三角形可以表示如下
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
可以使用相同的逻辑将三角形进一步扩展到无限。帕斯卡三角形中的每个数字都代表二项式系数的值，其中每一行都代表从 0 开始的 n，每一列都代表从 0 开始的 r，公式为 $\mathrm{^nC_{r}}$
我们将创建一个大小为 (N+1)*(N+1) 的二维矩阵来存储最多 N 的二项式系数的值，其中 N 将是输入中给定的正数。为了将帕斯卡三角形的值存储在二维矩阵中，我们将使用动态规划的概念。
以下步骤是将帕斯卡三角形的值存储在我们创建的二维矩阵中的指南
我们将 1 存储在 mat[0][0] 中，因为 $\mathrm{^0C_{0}}$ 等于 1。对于第一行的其余列索引，我们将保持值为 0，因为在公式 $\mathrm{^nC_{r}}$ 中 r 永远不能大于 n
在 for 循环中从 i=1 迭代到 i<N+1，因为我们需要 N 的二项式系数的值。
在每次迭代中，我们将 mat[i][0] 更新为 1，因为 $\mathrm{^nC_{0}}$ 始终等于 1
现在，我们将在一个嵌套的 for 循环中迭代，对于 i 的每个值从 j=1 到 j<N+1，以计算二项式系数 $\mathrm{^nC_{r}}$ 的值，其中 r 的范围从 0 到 n。
二项式系数之间存在一种关系，可以表示为 $\mathrm{^nC_{r}=^{n-1}C_{r-1}+^{n-1}C_{r}}$。对于 i 和 j 的每个值，其中 0<i,j<N+1 且 i 代表 n，j 代表二项式系数中的 r，mat[i][j] 的值将等于 mat[i−1][j−1]+mat[i−1][j]。
我们可以通过这种方式更新帕斯卡三角形直到 N。
一旦我们得到帕斯卡三角形，我们就可以简单地获取二项式系数的所需值来找到连续二项式系数乘积之和。
连续二项式系数乘积之和可以表示为 $\mathrm{^{i=N-1}{\sum_{i=0}}(^NC_{i}*^NC_{i+1})}$。因此，为了找到总和，我们可以简单地在 for 循环中从 i=0 迭代到 i<N（因为 i 的范围从 0 到 N−1）并计算 mat[N][i]*mat[N][i+1] 的乘积，并将其不断添加到总和中，这将给出我们所需的最终结果。
为了解决查找连续二项式系数乘积之和的问题，我们将在我们方法中实现上述算法。
方法
以下步骤是我们可以在我们的方法中实现上述算法以查找连续二项式系数乘积之和的步骤
为了找到总和，我们将创建一个函数。
我们将创建一个大小为 (N+1)*(N+1) 的二维向量，以在其内存储帕斯卡三角形的值。
在函数中，我们将按照算法中讨论的步骤，使用帕斯卡三角形的值更新二维向量。
向量更新后，我们将再次在 for 循环中迭代，以计算从 i=0 到 $\mathrm{i<N(^{i=N-1}{\sum_{i=0}}(^NC_{i}*^NC_{i+1}))}$ 的二项式系数的乘积。
我们将通过 mat[N][i]*mat[N][i+1] 在一个变量中不断更新二项式系数乘积之和。
我们将返回作为输出的变量，即所需的总和。
示例
// C++ code for calculating sum of product of consecutive binomial binomial coefficients for N
#include <bits/stdc++.h>
using namespace std;
//function to store values of Pascal's triangle in 2d matrix
void pascaltriangle(int N,vector<vector<long long int>>& mat){
mat[0][0]=1; //C(0,0)=1
for(int i=1;i<N+1;i++){ //iterating in matrix to update the values of Pascal's triangle
mat[i][0]=1; //nC0 is always equal to 1
for(int j=1;j<=i;j++){ //since r can never be greater than n in nCr
mat[i][j] = mat[i-1][j-1] + mat[i-1][j]; //nCr= (n-1)C(r-1) + (n-1)Cr
}
}
}
int main()
{
int N=18;
vector<vector<long long int>> mat(N+1,vector<long long int>(N+1,0));
//initialise a 2d vector to store values of pascal triangle
pascaltriangle(N,mat); //calling the function to update values in vector
long long int ans=0; //variable to store sum of product of consecutive binomial coefficients
for(int i=0;i<N;i++){
ans = ans + (mat[N][i]*mat[N][i+1]); // (NCi*NCi+1) for i>=0 and i<=N-1
}
cout<<"The sum of product of consecutive binomial coefficients for N is : "<<ans<<endl;
return 0;
}
输出
The sum of product of consecutive binomial coefficients for N is : 8597496600
时间复杂度 - O(N^2)，其中 N 是输入，因为我们在嵌套循环中迭代以更新大小为 (N+1)*(N+1) 的二维向量中的值。
空间复杂度 - O(N^2)，因为我们创建了一个大小为 (N+1)*(N+1) 的二维矩阵来存储帕斯卡三角形的值
结论
本文讨论了打印任何正数 N 的连续二项式系数乘积之和的问题。我们在方法中使用了帕斯卡三角形的概念来查找 N 的所有二项式系数的值，即 $\mathrm{^NC_{r}}$，其中 r 的范围从 0 到 N，并找到连续二项式系数的乘积并将其相加。
希望您在阅读本文后了解了我们用来解决此问题并在 C++ 中解决它的问题和算法。
156 次查看
