資料結構
網路
關係型資料庫管理系統 (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 次檢視
