题目53：对于1≤n≤100，C(n,r)有多少超过100万？

欧拉计划

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, .

In general,

,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: .

How many, not necessarily distinct, values of   ，for 1 ≤ n ≤ 100, are greater than one-million?

题目：

从五个数 12345 中选出三个数一共有十种方法:

123, 124, 125, 134, 135, 145, 234, 235, 245, and 345

在组合数学中我们用 来表示.

概括来说：

，其中 r ≤ n, n! = n×(n-1)×...×3×2×1, 并且 0! = 1.

n = 23 时产生第一个超过一百万的数： .

对于 ,  1 ≤ n ≤ 100，有多少超过 100 万的值？包括重复的在内。

QingXin

原先的C（n，r）公式还有另外一种写法，为C（n，r）=n*（n-1）*（n-2）*……（n-r+1）/[1*2*3……*r]，而且C（n，r）=C（n，n-r），是对称的。另外，n固定时，r从1到n取值，一定是中间高，两边低的。基于此，可以得到结果，4075。
程序采用对数进行加法运算，代替阶乘，加快运算速度。

import math

log_catlog = [math.log10(x) for x in range(1,101)]
num = 0
for n in range(23,101):
    i,logsum = 0,0
    while logsum <6:
        i+=1
        logsum = log_catlog[n-i] - log_catlog[i-1] + logsum
    num_n = n - 2 * i +1
    num+=num_n
print(num)

jerryxjr1220

直接用阶乘算，速度也还可以，1秒内出结果。
4075
[Finished in 0.8s]

def Cnr(n,r):
        if n == 1 or n == 0: return 1
        if r == 0: return 1
        Fn, Fr, Fnr = 1,1,1
        for i in range(1,n+1):
                Fn *= i
        for j in range(1,r+1):
                Fr *= j
        for k in range(1,(n-r+1)):
                Fnr *= k 
        return int(Fn/Fr/Fnr)

count = 0
for n in range(1,101):
        for r in range(int(n/2)+1):
                if Cnr(n,r) > 1000000:
                        if n % 2 == 1:
                                count += 2*(int(n/2)-r+1)
                        else:
                                count += 2*(int(n/2)-r)+1
                        break
print (count)

愤怒的大头菇

def Jc(x,y):
    temp = 1
    tmp = 1
    tg = 1
    for i in range(1,x+1):
        temp *= i
    for i in range(1,y+1):
        tmp *= i
    for i in range(1,x-y+1):
        tg *= i
    return int(temp/(tmp*tg))
count = 0
for i in range(1,101):
    for j in range(1,101):
        if Jc(i,j) > 1000000:
            count += 1
print(count)

结果：4075

芒果加黄桃

# encoding:utf-8
# 对于1<=n<=100,C(n,r)有所少超过100万的值
from time import time
from math import factorial
def euler052(N=1000000):
    count = 0
    for n in range(23, 101):
        for r in range(0, n + 1):
            if factorial(n) / factorial(r) / factorial(n - r) > 1000000:
                count += 1
                #print(n, r)
    print(count)
if __name__ == '__main__':
    start = time() 
    euler052()
    print('cost %.6f sec' % (time() - start))

4075
cost 0.020002 sec

渡风

此代码使用matlab编程
Problem53所用时间为： 0.040387秒
Problem53的答案为： 4075

%% Problem53.m
% 最后编辑时间：17-06-15 10:48
% 问题：1<= n <= 100,C(n,r)有多少个数超过100万
%事实上可以先求出小于等于100w的数，然后用总数减去之
% Problem53所用时间为： 0.040387秒
% Problem53的答案为： 4075

function Output = Problem53()
tic
AllNum = 100*(100+1)/2 + 100 ; %1 -2,2 -3,.....100 - 101
Total = 0;
for ii = 1:100
    for jj = 0:ii %从0开始
        if nchoosek(ii,jj) <= 1000000
            Total = Total + 1;
        else
            Total = Total + jj ; %由于从0开始，在jj处大于100w，前有jj个数大于100w
            break
        end
    end
end

Output = AllNum - Total;
                  
toc
disp('此代码使用matlab编程')
disp(['Problem53所用时间为： ',num2str(toc),'秒'])
disp(['Problem53的答案为： ',num2str(Output)])
end

najin

用的matlab
结果是：
        4075

时间已过 0.005218 秒。
>>

k往事如烟k

4075

def fac(n):
    product = 1
    for i in range(1, n+1):
        product *= i
    return product

count = 0
for n in range(1, 101):
    for r in range(1, 101):
        combinatorics = fac(n)/(fac(r)*fac(n-r))
        if combinatorics >= 1000000:
            count += 1

print(count)

王小召

结果是：4075
用时：0.1092007 秒

from math import factorial
import time


def cal_result():
    count = 0
    for n in range(23, 101):
        for r in range(n-1, 0, -1):
            if factorial(n)/(factorial(r)*factorial(n-r)) >= 1000000:
                count += 1
    return count

print("结果是：{}\n用时：{} 秒".format(cal_result(), time.process_time()))

永恒的蓝色梦想

借用了一下3L大佬的一部分逻辑

from time import process_time as t
t1=t()
from math import factorial as f
count=0
for n in range(23,100+1):
  for r in range(1,n+1):
    if (1 if n in(0,1)or r==0 else f(n)/(f(r)*f(n-r)))>1000000:count+=1
print(f'运行结果：{count}\n运行时间：{t()-t1}s')

运行结果：4075
运行时间：0.015625s

debuggerzh

4075

Process returned 0 (0x0)   execution time : 0.047 s
Press any key to continue.
利用同行递推式

                               
登录/注册后可看大图

以及组合数的对称性

                               
登录/注册后可看大图

#include<iostream>
using namespace std;

const int M = 1e6;

int main(){
  int ans = 0;

  for (int n = 23;n <= 100;n++){
    int cur_C = 1;  //C(23,0) = 1
    int pre_C;
    for (int m = 1;m <= n;m++){
      pre_C = cur_C;
      cur_C = pre_C * (n-m+1) / m;        //递推式
      if (cur_C > M)  {ans += n - 2*m + 1;//从n到n-m的组合数个数
        break;
      }
    }
  }
  cout << ans << endl;
  return 0;
}

4444567

写的有点啰嗦……
4075
0.09194111824035645

from time import time
def jc(n):#递归
    if n==1 or n==0:
        return 1
    else:
        return n*jc(n-1)
t = time()
a = 0
b = 0
for n in range(23,101):
    if n%2 == 0:
        for i in range(0,int(n/2) +1):
            s = jc(n)/jc(i)/jc(n-i)
            if s >1000000:
                #i到n/2 +1都符合，差值乘以2再加1
                #返回一个数值，累加
                a += ((int(n/2) - i)*2+1)
                break
                
                
    else:
        for i in range(0,int(n/2)):
            s = jc(n)/jc(i)/jc(n-i)
            if s >1000000:
                #i到n/2 都符合，差值乘以2
                #返回一个数值，累加
                b += (int((n+1)/2) - i)*2
                break
                
    
print(a+b)
print(time()-t)

4444567

4444567 发表于 2020-10-25 10:39
写的有点啰嗦……
4075
0.09194111824035645

改一丢丢……

from time import time
def jc(n):#递归
    if n==1 or n==0:
        return 1
    else:
        return n*jc(n-1)
t = time()
a = 0
for n in range(23,101):  
    for i in range(0,int(n/2) +1):
        s = jc(n)/jc(i)/jc(n-i)
        if s >1000000:
            #i到n/2 +1都符合，差值乘以2再加1
            #返回一个数值，累加
            a += (n+1 - 2*i)
            break
   
print(a)
print(time()-t)

a1351468657

#include <stdio.h>

long long int fact(int);
int combination(int n, int r);
long long int fact(int num)//阶乘
{
        int i;
        long long j = num;
        for (i = num - 1; i > 0; i--)
        {
                j *= i;
        }
        return j;
}

int combination(int n, int r)//组合
{
        int i, j;
        long long int k = 1;
        j = n - r;
        for (i = n; i > j; i--)
        {
                k *= i;
        }
        return (k / fact(r));
}
main()
{
        int i, j, k, count = 4;//n = 23有四个超过1000000的

        for (i = 24; i < 101; i++)
        {
                for (j = 1; j < i; j++)
                {
                        if (combination(i, j) >= 1000000)
                        {
                                k = i - j;
                                k = k - j + 1;//n = i是超过一百万的个数
                                count += k;
                                goto Label;
                        }
                }
        Label:continue;
        }
        printf("%d", count);
}

4075

ft215378

#对于1≤n≤100，C(n,r)有多少超过100万
from time import *

#求阶乘
def factorial(num):
    res = 1
    if num == 0:
        return 1
    else:
        for i in range(num, 1, -1):
            res *= i
    return res


def calc(n):
    result = []
    calc = 0
    for r in range(1, n+1):
        calc = factorial(n)//(factorial(r)*factorial(n-r))
        if calc > 1000000:
            #print(calc)
            result.append(calc)
    return True, len(result)

s = time()
n = 23
count = 0
while True:
    if calc(n):
        count += calc(n)[1]
    n += 1
    if n > 100:
        break
e = time()
#'''
print(count)
print("用时%.4f秒" % (e-s))
4075
用时0.1562秒

guosl

这题前面的几位都做得太复杂了，直接用双精度数和函数log10(x)即可。

/*
答案：4075
*/
#include <iostream>
#include <cmath>
using namespace std;

double d[101];

int main(void)
{
  for (int i = 2; i <= 100; ++i)
    d[i] = d[i - 1] + log10((double)i);
  int nCount = 0;
  for (int n = 1; n <= 100; ++n)
  {
    for (int r = 0; r <= n; ++r)
    {
      double x = d[n] - d[r] - d[n - r];
      if (x >= 6.0)
        ++nCount;
    }
  }
  cout << nCount << endl;
  return 0;
}

B1tetheDust

import time as t

start = t.perf_counter()


def factorial(x):
    factl = x
    for i_factorail in range(1, x):
        factl *= i_factorail

    return factl


count = 0
r = 9
for n in range(23, 101):
    while True:
        Cnr = factorial(n) / (factorial(r) * factorial(n - r))
        if Cnr > 1e6:
            count += (n - 2 * r + 1)
            r -= 1
            break
        else:
            r += 1

print(count)
print("It costs %f s" % (t.perf_counter() - start))

4075
It costs 0.001272 s