Chase The Limit

Kita mengetahui bahwa nCk = n!/k!(n-k)!. dengan itu maka kita hanya memerlukan 2 buah fungsi, yaitu fungsi faktorial, dan fungsi nCk itu sendiri sehingga menjadi seperti ini.

1
2
3
4
5
6
7
8
9

int fac(int n) {
	int res = 1;
	for(int i=2; i<=n; i++) res*=i;
	return res;
}
 
int nCk(int n,int k) {
	return (fac(n)/(fac(k)*fac(n-k)));
}

Ya, semudah itu ! tapi bagaimana jika situasi yang kita hadapi adalah n dan k nya bisa sangat besar (melebihi 100)? tentu saja cara di atas sudah tidak dapat kita gunakan lagi. Karena 100! itu pun sudah sangat besar. FYI 100! adalah

93,326,215,443,944,152,681,699,238,856,266,700,490, 715,968,264,381,621,468,592,963,895,217,599,993,229, 915,608,941,463,976,156,518,286,253,697,920,827,223, 758,251,185,210,916,864,000,000,000,000,000,000,000,000

Jadi bagaimana untuk menghitung nCk ketika n dan k adalah bilangan yang lebih besar dari 100?

Pertama, kita dapat menggunakan pembagian dengan GCD terlebih dahulu, baru dikalikan (Kodenya bisa langsung dilihat dibawah).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

typedef long long LL;
int GCD(int a,int b) {
	return (b==0) ? a : GCD(b,a%b);
}
void GCDdiv(LL &a, LL &b) {
	LL div = GCD(a,b);
	a/=div, b/=div;
}
LL C(int n, int k) {
	LL num=1,den=1,mul,div,i;
	if (k>n/2) k = n-k; // C(4,3) = C(4,1) * Kamu bisa buktikan sendiri :) *
	for(i=k; i>0; i--) {
		mul = n-k+1, div = i;
		GCDdiv(mul,div);
		GCDdiv(num,div);
		GCDdiv(mul,den);
		num *= mul;
		den *= div;
	}
	return num/den;
}

Dengan kode diatas, tentu saja jika hasilnya masih muat dalam batas integer 64, hasil itu ttp dapat dikalkulasi dengan aman.

- Felix J

Pages: 1 2