专栏首页Python小屋最快的组合数算法之Python实现

最快的组合数算法之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),作者:董付国

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python版组合数计算方法优化思路和源码

    总体说明:本文的优化思路并不局限于Python,但C、C++、C#、Java等语言无法使用内置类型直接表示大整数,需要通过数组等特定形式并自己实现大整数乘除法才...

    Python小屋屋主
  • Python花式编程案例锦集(2)

    问题描述:编写函数,计算形式如a + aa + aaa + aaaa + ... + aaa...aaa的表达式的值,其中a为小于10的自然数。 相信大多数朋友...

    Python小屋屋主
  • Python字符串处理小案例

    连续5天30个小时的Python培训圆满结束,明天早上5点半出发赶飞机回烟台,晚上收拾行李的时候突然想起来20年前做过的一个C语言题目:假设有一个字符串,里面有...

    Python小屋屋主
  • Redis底层原理--04. Redis 功能的实现

    WATCH 命令用于在事务开始之前监视任意数量的键:当调用 EXEC 命令执行事务时,如果任意一个被监视的键已经被其他客户端修改了,那么整个事务不再执行,直接返...

    付威
  • three.js 运行3D模型

    小蔚
  • (七)golang--变量之基本数据类型(看这篇就够了)

    (1)golang整数类型分为:有符号和无符号,int和uint的大小和系统有关;

    西西嘛呦
  • insert的使用

    举个例子,将DeepFakes的图片素材全部存到MySQL数据库里面。核心就是insert的使用。

    Rare0716
  • Arcgis for JS实现台风运动路径与影像范围的显示

    lzugis
  • fullcalendar日历插件的使用并实现增删改查

    我上个项目是做了一个关于教育方面的web端页面,其中的课程表就要用到fullcalendar日历插件,刚开始也是不会用,因为以前也没用过,后面也是看官方文档,问...

    故久
  • Client does not support authentication protocol requested by server

    启动命令:docker run -p 3307:3306 --name 8mysql -e MYSQL_ROOT_PASSWORD=123456 mysql:l...

    用户2146693

扫码关注云+社区

领取腾讯云代金券