# 工学1号馆

home

## Project Euler 53–Combinatoric selections

Wu Yudong    August 20, 2018     欧拉计划   433

Combinatoric selections

There are exactly ten ways of selecting three from five, 12345:

123, 124, 125, 134, 135, 145, 234, 235, 245, and 345
In combinatorics, we use the notation, $$C_{5}^{3}=10$$.

In general,

$$C_{n}^{r}=\frac{n!}{r!(n-r)!}$$, where r ≤ n, n! = n×(n−1)×…×3×2×1, and 0! = 1.

It is not until n = 23, that a value exceeds one-million: $$C_{23}^{10}= 1144066$$ .

How many, not necessarily distinct, values of $$C_{n}^{r}$$, for 1 ≤ n ≤ 100, are greater than one-million?

123、124、125、134、135、145、234、235、245和345

，其中r ≤ n，n! = n×(n−1)×…×3×2×1，且0! = 1。

//（Problem 53）Combinatoric selections
// Completed on Fri, 14 Feb 2014, 07:20
// Language: C11
//
// 版权所有（C）wu yudong
// 博客地址：http://www.wuyudong.com

#include<stdio.h>
#include<math.h>

long long combinatoric(int n, int r)   //计算组合数的函数
{
int i;
long long s = 1;
if(r > n / 2) r = n - r;
for(i = n; i >= n - r + 1; i--) {
s *= i;
}
for(i = 1; i <= r; i++) {
s /= i;
}
return s;
}

int main()
{
int i, j, s;
s = 0;
for(i = 23; i <= 100; i++) {
j = 3;
while(combinatoric(i, j) < 1000000) j++;
if(i % 2) {
s += (i / 2 - j + 1) * 2;   //利用组合数的对称性，分奇偶两种情况
} else {
s += (i / 2 - j) * 2 + 1;
}
}
printf("%d\n", s);
return 0;
}