資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學r 與 r 次二項式係數乘積之和 (r * nCr)
問題要求我們確定 r 與 r 次二項式係數乘積的和 (r*nCr)。
二項式定理中作為係數的正數稱為二項式係數。可以使用帕斯卡三角形和一個簡單的公式來確定二項式係數。
二項式係數的公式為
$$\mathrm{n_{c_{r}}=\frac{n!}{(n-r)!r!}}$$
注意：0! 的值始終等於 1。
在這個等式中，n 和 r 可以是任何非負整數，並且 r 永遠不能大於 n。
這個問題的目標是計算 r 與 r 次二項式係數的乘積，並確定從 r=0 到 r=n 的所有乘積的總和，其中 n 是使用者輸入的任何正數。
讓我們通過幾個例子來研究這個問題
輸入
N=5
輸出
80
解釋：我們計算了 r 與 r 次二項式係數的所有乘積，並將它們加起來以獲得輸出，其中 r 的值範圍從 0 到 N（即 r>=0 且 r=N）。
對於 r=0，0 * $\mathrm{^5{C_{0}} = 0}$，使用上面提到的公式計算 $\mathrm{^5{C_{0}}}$ 的值。
對於 r=1，1 * $\mathrm{^5{C_{1}} = 5}$。
對於 r=2，2 * $\mathrm{^5{C_{2}} = 20}$，因為 $\mathrm{^5{C_{2}} = 10}$。
對於 r=3，3 * $\mathrm{^5{C_{3}} = 30}$。
對於 r=4，4 * $\mathrm{^5{C_{4}} = 20}$。
對於 r=5，5 * $\mathrm{^5{C_{5}} = 5}$。
上面列出了 r=0 到 r=5 的二項式係數及其各自的乘積 r 和 r 次係數。我們需要的輸出是 0+5+20+30+20+5=80，這是 r 與 r 次二項式係數乘積之和。
輸入
N=4
輸出
32
解釋：對於範圍 [0,4] 內的所有 r 值，r 與 r 次二項式係數乘積之和為：
$$\mathrm{\sum(r*^N{C_{r}})}$$ 對於所有 r >=0 且 r <=N
$$\mathrm{\sum(r*^N{C_{r}})=0*^4{C_{0}}+1*^4{C_{1}}+2*^4{C_{2}}+3*^4{C_{3}}+4*^4{C_{4}}}$$
$$\mathrm{= 0 + 4 + 12 + 12 + 4 = 32}$$
讓我們看看解決這個問題的方法。
方法一（帕斯卡三角形）
使用帕斯卡三角形解決這個問題的思路是得到所有需要的二項式係數的值。眾所周知，帕斯卡三角形描繪了二項式係數的值。帕斯卡三角形如下圖所示
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
可以使用相同的邏輯進一步擴充套件這個三角形。帕斯卡三角形中的每個值都代表從 n=0 開始的行中的二項式係數，並且每一行中的每個值都代表 $\mathrm{n_{c_{r}}}$，其中 r 的範圍是從 r=0 到 r=n。
我們將建立一個大小為 (N+1)*(N+1) 的矩陣，其中 N 是輸入中給出的任何正數，並將帕斯卡三角形的數值儲存在其中。使用動態規劃將帕斯卡三角形的數值儲存在矩陣中可以簡化這個過程。
如何在矩陣中儲存帕斯卡三角形的數值？
對於第一行，我們將 matrix[0][0] 儲存為 1，因為 $\mathrm{0_{c_{0}}= 1}$。對於 i=0 的其餘列，我們將儲存 0，因為在表示式 $\mathrm{^n{C_{r}}}$ 中，r 永遠不能大於 n。
對於每個 i>0 的值，將 matrix[i][0] 儲存為 1，因為 $\mathrm{^n{C_{0}}}$ 始終等於 1。
數學中二項式係數存在一個關係，即 $\mathrm{^n{C_{r}}=^{n-1}{C_{r-1}}+^{n-1}{C_{r}}}$。對於每個 i 和 j 的值，其中 0
透過這種方式，我們可以用帕斯卡三角形的數值填充矩陣，其中 matrix[i][j] 將代表 $\mathrm{^i{C_{j}}}$ 的值。
我們可以使用矩陣來計算 r 與 r 次二項式係數乘積之和。
為了使用這種方法來解決問題，我們必須遵循以下步驟
宣告一個大小為 (N+1)*(N+1) 的矩陣來儲存帕斯卡三角形的數值。
我們將建立一個函式，使用上述方法將帕斯卡三角形的數值儲存在矩陣中。
一旦數值儲存在矩陣中，我們就可以透過迭代 for 迴圈來簡單地得到 r 與 r 次二項式係數乘積之和。
在 for 迴圈中從 i=0 迭代到 i<=N，並將每次 i 與 i 次二項式係數的乘積新增到變數 sum 中。
儲存在變數 sum 中的值將是我們的輸出。
該方法的 C++ 程式碼為
示例
// C++ code for calculating sum of product of r and rth 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;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=8;
vector<vector<long long int>> mat(N+1,vector<long long int>(N+1,0));
//initialise a 2d vector to store values
pascaltriangle(N,mat); //calling the function to update values in mat
long long int sum=0; //variable to store sum of product of r and rth coefficients
for(int i=0;i<=N;i++){
sum = sum + (i * mat[N][i]); //mat[N][i] represents value of NCi
}
cout<<"The sum of product of r and rth binomial coefficients for N is "<<sum<<endl;
return 0;
}
輸出
The sum of product of r and rth binomial coefficients for N is 1024
時間複雜度：O(N^2)
空間複雜度：O(N^2)
方法二（使用直接公式）
我們將使用一個直接公式來計算 r 與 r 次二項式係數乘積之和，其中 r 的範圍為 [0,N]。我們將推匯出一個公式來計算這個和。
r 與 r 次二項式係數乘積之和可以表示為
$$\mathrm{\sum(r*^n{C_{r}})}$ $對於所有 r>=0 且 r <=N
所以我們需要找到
$$\mathrm{\sum(r*^n{C_{r}})}$$
我們可以將 r 寫成 $\mathrm{r_{C_{1}}}$，因為 $\mathrm{n_{C_{r}}}$ 始終等於 n，
$$\mathrm{\sum(^r{C_{1}}*^n{C_{r}} )}$$
使用公式 $\mathrm{^n{C_{r}}=\frac{n!}{(n-r)!r!}}$，我們可以將上述表示式寫成：
$$\mathrm{\sum(\frac{r!}{(r-1)!1!}*\frac{N!}{(N-r)!r!})=\sum(\frac{N!}{(N-r)!(r-1)!})=\sum N*(\frac{(N-1)!}{(N-r)!(r-1)!})}$$
因為 $\mathrm{{n-1}_{c_{r-1}}=\frac{(N-1)!}{(N-1-(r-1))!(r-1)!}}$，簡化後可以寫成 $\mathrm{\frac{(N-1)!}{(N-r)!(r-1)!}}$
所以用 $\mathrm{{n-1}_{C_{r-1}}}$ 替換 $\mathrm{\frac{(N-1)!}{(N-r)!(r-1)!}}$，表示式將為
$$\mathrm{N*\sum({n-1}_{C_{r-1}})=N*2^{N-1}(因為 \sum n_{c_{r}}=2^{N}，其中 0<=r <=N)}$$
可以使用公式 $\mathrm{N*2^{N-1}}$ 計算 r 與 r 次二項式係數乘積之和，其中 N 為某個正值。可以使用 C++ 中的 pow() 函式計算此表示式的值。
語法
int a=pow(2,N);
這將返回等於 $\mathrm{2^{N}}$ 的值給 a。
使用直接公式解決問題的 C++ 程式碼
示例
#include<bits/stdc++.h>
using namespace std;
//function to calculate sum of product of r and rth binomial coefficients
long long int sum(int N){
long long int ans=0; //to store the answer
ans = N * pow(2,(N-1)); //using direct formula derived
return ans; // return the answer
}
int main()
{
int N;
N=4;
cout<<"The sum of product of r and rth binomial coefficients is "<<sum(N)<<endl;
N=15;
cout<<"The sum of product of r and rth binomial coefficients is "<<sum(N)<<endl;
return 0;
}
輸出
The sum of product of r and rth binomial coefficients is 32 The sum of product of r and rth binomial coefficients is 245760
時間複雜度：O(log N)，因為 pow() 函式執行時間複雜度為 O(log N)。
空間複雜度：O(1)，因為我們沒有使用任何額外的空間。
結論
本文使用兩種不同的方法，利用多個 C++ 函式和庫，討論了在 C++ 中計算 r 與 r 次二項式係數乘積之和的主題。透過建立計算輸出的公式，我們能夠將解決問題的暴力方法轉換為有效的方法。
閱讀完這篇文章後，我希望您對這個問題有了很好的理解。
瀏覽量：179
