SOGO論壇

標題: C++註解 [列印本頁]

作者: 無所謂的愛 時間: 2010-11-24 19:14:10 標題: C++註解

#include <iostream>

using namespace std;

int Bin(int n, int k) {
if (n==k||k==0) {
return 1;
} else {
return Bin(n-1, k)+Bin(n-1, k-1);
}
}

int main()
{
int N, K, n,r,i;
cout << "請輸入N:";
cin >> N;
cout << "請輸入K:";
cin >> K;

// 二項式係數
cout << "C(N,K)=" << Bin(N,K);

// 巴斯卡三角形

for (n=0;n<=N;n++) {
for (r=0;r<=n;r++) {
long nCr = 1;
for(i=1;i<=r;i++) {
nCr = nCr * (n-i+1)/i;

}
cout << nCr;
}
cout << "\n";
}

system ("pause");
return 0 ;
}

有些地方不太清楚,有大大可以幫我註解一下嗎?感恩

作者: regist 時間: 2011-3-9 16:49:10

先看選取法：
int Bin(int n, int k) {
if (n==k||k==0) {
return 1;
} else {
return Bin(n-1, k)+Bin(n-1, k-1);
}
}

表示： C(N, K) , 即 N 個相異物選取 K 個，有幾個選法，
由於 n 個相異物選取 n 個物件只有一種選法，(即全選)
且 n 個相異物選取 0 個物件也只有一種選法，(即全不選)
所以遞迴終止條件為：
if (n==k||k==0) {
return 1;
}
否則 C(N, K) = C(N-1, K) + C(N-1, K-1)：
else {
return Bin(n-1, k)+Bin(n-1, k-1);
}
註：考慮某一物件 a，則 C(N, K) 有兩種選法：
即 a 物件必不選的取法 + a 物件必選的取法
即 a 物件必不選的取法相當於剩下的 N-1 件相異物再挑選 K 件的取法有 C(N-1, K)
a 物件必選的取法相當於剩下的 N-1 件相異物再挑選 K-1 件的取法有 C(N-1, K)
所以 C(N, K) = C(N-1, K) + C(N-1, K-1)

作者: regist 時間: 2011-3-9 17:07:09

巴斯卡三角形：
1
1,1
1,2,1
1,3,3,1
1,4,6,4,1

相當於：
C(0,0)
C(1,0), C(1,1)
C(2,0), C(2,1), C(2,2)
C(3,0), C(3,1), C(3,2), C(3,3)
...................

又 C(n,k)
= n! / (k!*(n-k)!)
= n*(n-1)*(n-2)*....*(k+1) / (n-k)!
= n*(n-1)*(n-2)*....*(k+1) / 1*2*3*...*(n-k)
= (n/1)*((n-1)/2)*((n-2)/3)*...((k+1)/(n-k))

程式 main 中：
int N, K, n,r,i;
cout << "請輸入N:";
cin >> N;
cout << "請輸入K:";
cin >> K;

// 二項式係數
cout << "C(N,K)=" << Bin(N,K); //只是印出 C(N,K) 的值

for (n=0;n<=N;n++) { // 決定印出幾層的巴斯卡三角形
for (r=0;r<=n;r++) { // 決定印出該層巴斯卡三角形的每個 C(N,K) 數值
long nCr = 1;
for(i=1;i<=r;i++) {
// 計算 C(N,K) 值，
//如上所推理的：C(n,k) = (n/1)*((n-1)/2)*((n-2)/3)*...((k+1)/(n-k))
//第一個數:n/1 為 (n-1+1)/1，第二個數：(n-1)/2 為 (n-2+1)/2
//第三個數：(n-2)/3 為 (n-3+1)/3.....
//依此類推，第i個數： (n-i+1)/i
//C(n,k)為第一個數*第二個數*....*第i個數，所以為累乘
nCr = nCr * (n-i+1)/i;

}
cout << nCr;
}
cout << "\n";
}

system ("pause");
return 0 ;

歡迎光臨 SOGO論壇 (https://oursogo.com/)