[ create a new paste ] login | about

Link: http://codepad.org/jr3RnmOj    [ raw code | output | fork ]

C, pasted on Mar 29:
/*
	12345から3つ選ぶ選び方は10通りである.

	123, 124, 125, 134, 135, 145, 234, 235, 245, 345.
	組み合わせでは, 以下の記法を用いてこのことを表す: 5C3 = 10.

	一般に, r <= n について nCr = n!/(r!(n-r)!) である. 
	ここで, n! = n×(n-1)×...×3×2×1, 0! = 1 と階乗を定義する.

	n = 23 になるまで, これらの値が100万を超えることはない: 23C10 = 1144066.

	1 <= n <= 100 について, 100万を超える nCr は何通りあるか?
*/

#include <stdio.h>

#define MILLIION	1000000

int memo[101][101];

int combination(int n, int r) {

	if( n < r ) return 0;
	if( n == r || r <= 0 ) return 1;
	if( memo[n][r] != 0 ) return memo[n][r];

	return combination(n - 1, r) + combination(n - 1, r - 1);
}

int main(void) {
	int n, r;
	int cnt = 0, rslt = 0;
	int tmp;

	for( n = 23; n <= 100; n++ ) {
		cnt = 0;
		for( r = 0; r <= n / 2; r++ ) {
			tmp = combination(n, r);
			memo[n][r] = tmp;
			if( tmp < MILLIION ) {
				cnt++;
			} else {
				rslt += (n + 1) - cnt * 2;
				break;
			}
		}
	}

	printf("%d\n", rslt);

	return 0;
}


Output:
1
4075


Create a new paste based on this one


Comments: