工学1号馆

home

« | 返回首页 | »

Project Euler 53–Combinatoric selections

By Wu Yudong on August 20, 2018

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?


组合数选择

从五个数12345中选择三个恰好有十种方式,分别是:

123、124、125、134、135、145、234、235、245和345
在组合数学中,我们记作:\(C_{5}^{3}=10\)。

一般来说,\(C_{n}^{r}=\frac{n!}{r!(n-r)!}\)

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

直到n = 23时,才出现了超出一百万的组合数: \(C_{23}^{10}= 1144066\) .

若数值相等形式不同也视为不同,对于1 ≤ n ≤ 100,有多少个组合数\(C_{n}^{r}\)超过一百万?

//(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;
}

 

如果文章对您有帮助,欢迎点击下方按钮打赏作者

Comments

No comments yet.
To verify that you are human, please fill in "七"(required)