题目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。
程序采用对数进行加法运算，代替阶乘，加快运算速度。

1. import math
   
2. 
   
3. log_catlog = [math.log10(x) for x in range(1,101)]
   
4. num = 0
   
5. for n in range(23,101):
   
6.     i,logsum = 0,0
   
7.     while logsum <6:
   
8.         i+=1
   
9.         logsum = log_catlog[n-i] - log_catlog[i-1] + logsum
   
10.     num_n = n - 2 * i +1
    
11.     num+=num_n
    
12. print(num)

复制代码

jerryxjr1220

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

1. def Cnr(n,r):
   
2.         if n == 1 or n == 0: return 1
   
3.         if r == 0: return 1
   
4.         Fn, Fr, Fnr = 1,1,1
   
5.         for i in range(1,n+1):
   
6.                 Fn *= i
   
7.         for j in range(1,r+1):
   
8.                 Fr *= j
   
9.         for k in range(1,(n-r+1)):
   
10.                 Fnr *= k
    
11.         return int(Fn/Fr/Fnr)
    
12. 
    
13. count = 0
    
14. for n in range(1,101):
    
15.         for r in range(int(n/2)+1):
    
16.                 if Cnr(n,r) > 1000000:
    
17.                         if n % 2 == 1:
    
18.                                 count += 2*(int(n/2)-r+1)
    
19.                         else:
    
20.                                 count += 2*(int(n/2)-r)+1
    
21.                         break
    
22. print (count)

复制代码

愤怒的大头菇

1. def Jc(x,y):
   
2.     temp = 1
   
3.     tmp = 1
   
4.     tg = 1
   
5.     for i in range(1,x+1):
   
6.         temp *= i
   
7.     for i in range(1,y+1):
   
8.         tmp *= i
   
9.     for i in range(1,x-y+1):
   
10.         tg *= i
    
11.     return int(temp/(tmp*tg))
    
12. count = 0
    
13. for i in range(1,101):
    
14.     for j in range(1,101):
    
15.         if Jc(i,j) > 1000000:
    
16.             count += 1
    
17. print(count)

复制代码

结果：4075

芒果加黄桃

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

复制代码

4075
cost 0.020002 sec

渡风

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

1. %% Problem53.m
   
2. % 最后编辑时间：17-06-15 10:48
   
3. % 问题：1<= n <= 100,C(n,r)有多少个数超过100万
   
4. %事实上可以先求出小于等于100w的数，然后用总数减去之
   
5. % Problem53所用时间为： 0.040387秒
   
6. % Problem53的答案为： 4075
   
7. 
   
8. function Output = Problem53()
   
9. tic
   
10. AllNum = 100*(100+1)/2 + 100 ; %1 -2,2 -3,.....100 - 101
    
11. Total = 0;
    
12. for ii = 1:100
    
13.     for jj = 0:ii %从0开始
    
14.         if nchoosek(ii,jj) <= 1000000
    
15.             Total = Total + 1;
    
16.         else
    
17.             Total = Total + jj ; %由于从0开始，在jj处大于100w，前有jj个数大于100w
    
18.             break
    
19.         end
    
20.     end
    
21. end
    
22. 
    
23. Output = AllNum - Total;
    
24.                   
    
25. toc
    
26. disp('此代码使用matlab编程')
    
27. disp(['Problem53所用时间为： ',num2str(toc),'秒'])
    
28. disp(['Problem53的答案为： ',num2str(Output)])
    
29. end
    

复制代码

najin

用的matlab
结果是：
        4075

时间已过 0.005218 秒。
>>

k往事如烟k

4075

1. def fac(n):
   
2.     product = 1
   
3.     for i in range(1, n+1):
   
4.         product *= i
   
5.     return product
   
6. 
   
7. count = 0
   
8. for n in range(1, 101):
   
9.     for r in range(1, 101):
   
10.         combinatorics = fac(n)/(fac(r)*fac(n-r))
    
11.         if combinatorics >= 1000000:
    
12.             count += 1
    
13. 
    
14. print(count)

复制代码

王小召

结果是：4075
用时：0.1092007 秒

1. from math import factorial
   
2. import time
   
3. 
   
4. 
   
5. def cal_result():
   
6.     count = 0
   
7.     for n in range(23, 101):
   
8.         for r in range(n-1, 0, -1):
   
9.             if factorial(n)/(factorial(r)*factorial(n-r)) >= 1000000:
   
10.                 count += 1
    
11.     return count
    
12. 
    
13. print("结果是：{}\n用时：{} 秒".format(cal_result(), time.process_time()))

复制代码

永恒的蓝色梦想

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

1. from time import process_time as t
   
2. t1=t()
   
3. from math import factorial as f
   
4. count=0
   
5. for n in range(23,100+1):
   
6.   for r in range(1,n+1):
   
7.     if (1 if n in(0,1)or r==0 else f(n)/(f(r)*f(n-r)))>1000000:count+=1
   
8. 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.
利用同行递推式

                               
登录/注册后可看大图

以及组合数的对称性

                               
登录/注册后可看大图

1. #include<iostream>
   
2. using namespace std;
   
3. 
   
4. const int M = 1e6;
   
5. 
   
6. int main(){
   
7.   int ans = 0;
   
8. 
   
9.   for (int n = 23;n <= 100;n++){
   
10.     int cur_C = 1;  //C(23,0) = 1
    
11.     int pre_C;
    
12.     for (int m = 1;m <= n;m++){
    
13.       pre_C = cur_C;
    
14.       cur_C = pre_C * (n-m+1) / m;        //递推式
    
15.       if (cur_C > M)  {ans += n - 2*m + 1;//从n到n-m的组合数个数
    
16.         break;
    
17.       }
    
18.     }
    
19.   }
    
20.   cout << ans << endl;
    
21.   return 0;
    
22. }
    

复制代码

4444567

写的有点啰嗦……
4075
0.09194111824035645

1. from time import time
   
2. def jc(n):#递归
   
3.     if n==1 or n==0:
   
4.         return 1
   
5.     else:
   
6.         return n*jc(n-1)
   
7. t = time()
   
8. a = 0
   
9. b = 0
   
10. for n in range(23,101):
    
11.     if n%2 == 0:
    
12.         for i in range(0,int(n/2) +1):
    
13.             s = jc(n)/jc(i)/jc(n-i)
    
14.             if s >1000000:
    
15.                 #i到n/2 +1都符合，差值乘以2再加1
    
16.                 #返回一个数值，累加
    
17.                 a += ((int(n/2) - i)*2+1)
    
18.                 break
    
19.                
    
20.                
    
21.     else:
    
22.         for i in range(0,int(n/2)):
    
23.             s = jc(n)/jc(i)/jc(n-i)
    
24.             if s >1000000:
    
25.                 #i到n/2 都符合，差值乘以2
    
26.                 #返回一个数值，累加
    
27.                 b += (int((n+1)/2) - i)*2
    
28.                 break
    
29.                
    
30.    
    
31. print(a+b)
    
32. print(time()-t)

复制代码

4444567

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

改一丢丢……

1. from time import time
   
2. def jc(n):#递归
   
3.     if n==1 or n==0:
   
4.         return 1
   
5.     else:
   
6.         return n*jc(n-1)
   
7. t = time()
   
8. a = 0
   
9. for n in range(23,101):  
   
10.     for i in range(0,int(n/2) +1):
    
11.         s = jc(n)/jc(i)/jc(n-i)
    
12.         if s >1000000:
    
13.             #i到n/2 +1都符合，差值乘以2再加1
    
14.             #返回一个数值，累加
    
15.             a += (n+1 - 2*i)
    
16.             break
    
17.    
    
18. print(a)
    
19. print(time()-t)

复制代码

a1351468657

1. #include <stdio.h>
   
2. 
   
3. long long int fact(int);
   
4. int combination(int n, int r);
   
5. long long int fact(int num)//阶乘
   
6. {
   
7.         int i;
   
8.         long long j = num;
   
9.         for (i = num - 1; i > 0; i--)
   
10.         {
    
11.                 j *= i;
    
12.         }
    
13.         return j;
    
14. }
    
15. 
    
16. int combination(int n, int r)//组合
    
17. {
    
18.         int i, j;
    
19.         long long int k = 1;
    
20.         j = n - r;
    
21.         for (i = n; i > j; i--)
    
22.         {
    
23.                 k *= i;
    
24.         }
    
25.         return (k / fact(r));
    
26. }
    
27. main()
    
28. {
    
29.         int i, j, k, count = 4;//n = 23有四个超过1000000的
    
30. 
    
31.         for (i = 24; i < 101; i++)
    
32.         {
    
33.                 for (j = 1; j < i; j++)
    
34.                 {
    
35.                         if (combination(i, j) >= 1000000)
    
36.                         {
    
37.                                 k = i - j;
    
38.                                 k = k - j + 1;//n = i是超过一百万的个数
    
39.                                 count += k;
    
40.                                 goto Label;
    
41.                         }
    
42.                 }
    
43.         Label:continue;
    
44.         }
    
45.         printf("%d", count);
    
46. }
    

复制代码

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)即可。

1. /*
   
2. 答案：4075
   
3. */
   
4. #include <iostream>
   
5. #include <cmath>
   
6. using namespace std;
   
7. 
   
8. double d[101];
   
9. 
   
10. int main(void)
    
11. {
    
12.   for (int i = 2; i <= 100; ++i)
    
13.     d[i] = d[i - 1] + log10((double)i);
    
14.   int nCount = 0;
    
15.   for (int n = 1; n <= 100; ++n)
    
16.   {
    
17.     for (int r = 0; r <= n; ++r)
    
18.     {
    
19.       double x = d[n] - d[r] - d[n - r];
    
20.       if (x >= 6.0)
    
21.         ++nCount;
    
22.     }
    
23.   }
    
24.   cout << nCount << endl;
    
25.   return 0;
    
26. }

复制代码

B1tetheDust

1. import time as t
   
2. 
   
3. start = t.perf_counter()
   
4. 
   
5. 
   
6. def factorial(x):
   
7.     factl = x
   
8.     for i_factorail in range(1, x):
   
9.         factl *= i_factorail
   
10. 
    
11.     return factl
    
12. 
    
13. 
    
14. count = 0
    
15. r = 9
    
16. for n in range(23, 101):
    
17.     while True:
    
18.         Cnr = factorial(n) / (factorial(r) * factorial(n - r))
    
19.         if Cnr > 1e6:
    
20.             count += (n - 2 * r + 1)
    
21.             r -= 1
    
22.             break
    
23.         else:
    
24.             r += 1
    
25. 
    
26. print(count)
    
27. print("It costs %f s" % (t.perf_counter() - start))
    

复制代码

4075
It costs 0.001272 s