题目53：对于1≤n≤100，C(n,r)有多少超过100万？,欧拉计划（Project Euler）,数据结构与算法,鱼C论坛

欧拉计划 发表于 2015-6-12 22:32:56

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

本帖最后由永恒的蓝色梦想于 2020-6-19 15:21 编辑

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 发表于 2016-9-16 11:11:51

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

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

jerryxjr1220 发表于 2016-10-12 19:57:06

直接用阶乘算，速度也还可以，1秒内出结果。
4075

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)

愤怒的大头菇 发表于 2016-11-21 19:59:05

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

芒果加黄桃 发表于 2017-1-17 12:53:22

# 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

渡风发表于 2017-6-15 10:38:58

此代码使用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 发表于 2017-9-30 12:36:02

用的matlab
结果是：
4075

时间已过 0.005218 秒。
>>

k往事如烟k 发表于 2019-4-1 10:40:04

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)

王小召 发表于 2019-6-24 17:07:07

结果是：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()))

永恒的蓝色梦想 发表于 2019-8-19 22:15:31

借用了一下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 发表于 2020-8-18 16:24:13

4075

Process returned 0 (0x0) execution time : 0.047 s
Press any key to continue.
利用同行递推式
https://wx1.sinaimg.cn/mw690/0081qlg6ly1ghv1gwbu8fj30nm00sa9u.jpg
以及组合数的对称性
https://wx3.sinaimg.cn/mw690/0081qlg6ly1ghv1izz9qrj30nm00lq2p.jpg
#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 发表于 2020-10-25 10:39:42

写的有点啰嗦……
4075
0.09194111824035645from 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 发表于 2020-10-25 10:45:44

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 发表于 2021-4-3 22:56:06

#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 发表于 2021-10-25 13:02:08

#对于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)
n += 1
if n > 100:
   break
e = time()
#'''
print(count)
print("用时%.4f秒" % (e-s))
4075
用时0.1562秒

guosl 发表于 2022-1-9 09:13:22

这题前面的几位都做得太复杂了，直接用双精度数和函数log10(x)即可。
/*
答案：4075
*/
#include <iostream>
#include <cmath>
using namespace std;

double d;

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

B1tetheDust 发表于 2022-10-25 15:27:49

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

页: [1]

鱼C论坛's Archiver

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