如果第一次閱讀本系列文檔請(qǐng)先移步閱讀【ROSALIND】【練Python，學(xué)生信】00 寫(xiě)在前面 ?謝謝配合~

題目：

計(jì)算子集數(shù)目（Counting Subsets）

Given: A positive integer n (n≤1000).

所給：一個(gè)正整數(shù)n（n不大于1000）。

Return: The total number of subsets of {1,2,…,n} modulo 1,000,000.

需得：集合{1,2,…,n}的所有子集數(shù)目，結(jié)果取模。

?

測(cè)試數(shù)據(jù)

3

測(cè)試輸出

8

?

生物學(xué)背景

? ? ? ? 特征（character）是生物基因或表型上的特性，可以依據(jù)一個(gè)特征把一群同類(lèi)生物劃分為兩個(gè)亞群。單核苷酸多態(tài)性（SNP）是一種常用的基因特征，主要是指在基因組水平上由單個(gè)核苷酸的變異所引起的DNA序列多態(tài)性。利用人類(lèi)SNP可以研究基因組的遷徙、融合及進(jìn)化現(xiàn)象。

? ? ? ??我們可以把一組特征想象為一個(gè)集合，可以用某個(gè)特征是否存在來(lái)描述生物體。這樣一個(gè)生物體具有的特征就是這個(gè)集合的一個(gè)子集。

?

數(shù)學(xué)背景

? ? ? ??集合是數(shù)學(xué)中的基本概念。集合包含的每個(gè)對(duì)象稱(chēng)為集合的元素。舉例來(lái)說(shuō)，{the moon, the sun, Wilford Brimley}是一個(gè)集合，the moon是集合的一個(gè)元素。集合元素不分順序，只要元素相等就是同一個(gè)集合，即{the moon, the sun, Wilford Brimley}等價(jià)于{Wilford Brimley, the moon, the sun}。集合中元素不可重復(fù)。

? ? ? ??如果集合A是集合B的子集（A?B），則集合A中的每一個(gè)元素都是B的元素。例如{the sun, the moon}?{the sun, the moon, Wilford Brimley}。需要注意的是，空集?是任何集合的子集。

? ? ? ??組合是指從n個(gè)不同元素中取出m個(gè)不同元素（0≤m≤n），不管其順序合成一組，稱(chēng)為從n個(gè)元素中不重復(fù)地選取m個(gè)元素的一個(gè)組合。

?

思路

? ? ? ??本題較簡(jiǎn)單，實(shí)質(zhì)是計(jì)算組合總數(shù)。直接套用組合的公式，算組合數(shù)即可?？梢灾苯佑肞ython定義好的階乘函數(shù)，自己寫(xiě)的話(huà)也很簡(jiǎn)單。不要忘了空集也是子集。

?

代碼

def myfactorial(n, m):
??? """自己定義一個(gè)可以算階乘的函數(shù)，計(jì)算n(n-1)(n-2)…(n-m)"""

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

??? return sum


n = 3
result = 1 # 將空集先加入結(jié)果
for i in range(1,n + 1): # 利用循環(huán)結(jié)算組合總數(shù)
??? tep = myfactorial(n, n-i+1)/myfactorial(i,1) # 套用組合公式
??? result += tep

print(int(result % 1000000))