最快的组合数算法之Python实现

原理:以Cni(8,3)为例,按定义式将其展开为(8*7*6*5*4*3*2*1)/(3*2*1)/(5*4*3*2*1),对于8到6之间的数,分子上出现一次而分母上没出现;5到3之间的数分子、分母上各出现一次;3到1之间的数分子上出现一次而分母上出现两次。 优势:避免了求阶乘的计算,同时也避免了n太大而导致无法使用长整型变量来表示其阶乘(大多数编程语言中都存在这个问题,当然了Python不存在这个问题)。 补充:关键在于算法,可以使用任意其他语言改写程序,但当组合数结果超出了其他语言中长整型变量的表示范围时同样无法使用,使用Python不存在这个问题。 def Cni(n,i):

if not (isinstance(n,int) and isinstance(i,int) and n>=i):

print 'n and i must be integers and n must be larger than or equal to i.'

return

result = 1

Min, Max = min(i,n-i), max(i,n-i)

for i in range(n,0,-1):

if i>Max:

result *= i

elif i<=Min:

result /= i

return result

print Cni(6,2)

原文发布于微信公众号 - Python小屋(Python_xiaowu)

原文发表时间:2016-07-15

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏潇涧技术专栏

Python Algorithms - C3 Counting 101

原书主要介绍了一些基础数学,例如排列组合以及递归循环等,但是本节只重点介绍计算算法的运行时间的三种方法

9840
来自专栏ACM算法日常

海战(线段树)- HDU 4027

这一篇是典型的线段树算法,这个算法在日常工作中可能非常少见,因为可以被常规算法所取代,但是在问题达到一定数量级之后,常规算法是很难搞定类似问题的...

11620
来自专栏Small Code

【Python】统计字符串中英文、空格、数字、标点个数

题外话:今天打酱油的做了**数据挖掘工程师的在线笔试题,被打击了。 本文代码可在 这里 下载。 问题 在网上无意间看到这么一个题目:统计一个字符串中的中英文、空...

74650
来自专栏专注数据中心高性能网络技术研发

[LeetCode]Array主题系列{1,11,15,16,18,26,27,31,33,34题}

1.内容介绍 开一篇文章记录在leetcode中array主题下面的题目和自己的思考以及优化过程,具体内容层次按照{题目,分析,初解,初解结果,优化解,优化解结...

35060
来自专栏数据结构与算法

BZOJ4872: [Shoi2017]分手是祝愿

Description Zeit und Raum trennen dich und mich. 时空将你我分开。B 君在玩一个游戏,这个游戏由 n 个灯和 n...

30150
来自专栏C语言及其他语言

【每日一题】问题1075: 台球碰撞(此次问题较难)

题目描述 在平面直角坐标系下,台球桌是一个左下角在(0,0),右上角在(L,W)的矩形。有一个球心在(x,y),半径为R的圆形母球放在台球桌上(整个球都在台球...

28150
来自专栏数据结构与算法

20:反反复复

20:反反复复 总时间限制: 1000ms 内存限制: 65536kB描述 Mo和Larry发明了一种信息加密方法。他们首先决定好列数,然后将信息(只包含字...

39880
来自专栏常用编程思想与算法

常用编程思想与算法

本文是在阅读Aditya Bhargava先生算法图解一书所做的总结,文中部分代码引用了原文的代码,在此感谢Aditya Bhargava先生所作出的这么简单的...

22410
来自专栏java一日一条

我是如何击败Java自带排序算法的

Java 8 对自带的排序算法进行了很好的优化。对于整形和其他的基本类型, Arrays.sort() 综合利用了双枢轴快速排序、归并排序和启发式插入排序。这个...

13710
来自专栏谈补锅

数据结构和算法术语学习笔记

数据:是描述客观事物的符号,是计算机中可以操作的对象,是能被计算机识别,并输入给计算机处理的符号集合。数据不仅包括整型、实型等数值类型,还包括字符及声音、图像、...

12930

扫码关注云+社区

领取腾讯云代金券