【ROSALIND】【练Python，学生信】44 可变剪接数目

如果第一次阅读本系列文档请先移步阅读【ROSALIND】【练Python，学生信】00 写在前面  谢谢配合~

题目：

可变剪接的数目

Given: Positive integers n and m with 0≤m≤n≤2000.

所给：两个正整数n和m，有0≤m≤n≤2000。

Return: The sum of combinations C(n,k) for all k satisfying m≤k≤n, modulo 1,000,000.

需得：C(n,k)的所有总和，其中k满足m≤k≤n。

测试数据

6 3

测试输出

42

生物学背景

        真核生物的基因组是不连续的，只有外显子（exon）才能在最终成熟的mRNA中出现。同一个基因可以产生不同的mRNA，这是因为存在可变剪接（alternative splicing），即并非所有的外显子都会参与mRNA的形成，有些外显子可以和内含子一起被从成熟的mRNA中剔除掉。

        可变剪接在进化中十分重要，可以增加同一个基因编码蛋白的个数。

数学背景

        在可变剪接中，外显子之间的顺序不变，不涉及排列问题，因此本题的数学知识与43 计算子集数目完全一致，只是43 计算子集数目是计算所有组合的数目之和，本题只是计算给定数目的组合之和。

思路

        本题实质是在考察如何在数特别大的时候避免溢出错误，在计算组合数时，如果数值过于巨大，直接用除号/得到的浮点数无法储存，会提示错误；因此用整数除法号//来计算，得到的值是整形，程序可以正确运行。

代码

def myfactorial(n, m):
    """自己定义一个可以算阶乘的函数，计算n(n-1)(n-2)…(n-m)"""

    sum = 1
    i = n
    while i >= m:
        sum = sum * i
        i -= 1

    return sum


n = 6
m = 3
result = 0
for i in range(m,n + 1): # 利用循环计算组合总数
    tep = myfactorial(n, n-i+1)//myfactorial(i,1) # 套用组合公式，//代表整数除法
    result += tep

print(result % 1000000)