最大組合數Python

❶ 關於楊輝三角python代碼的問題

楊輝三角，是二項式系數在三角形中的一種幾何排列。
前提：每行端點與結尾的數為1.
每個數等於它上方兩數之和。
每行數字左右對稱，由1開始逐漸變大。
第n行的數字有n項。
第n行數字和為2n-1。
第n行的m個數可表示為 C(n-1，m-1)，即為從n-1個不同元素中取m-1個元素的組合數。
第n行的第m個數和第n-m+1個數相等 ，為組合數性質之一。
每個數字等於上一行的左右兩個數字之和。可用此性質寫出整個楊輝三角。即第n+1行的第i個數等於第n行的第i-1個數和第i個數之和，這也是組合數的性質之一。即 C(n+1,i)=C(n,i)+C(n,i-1)。
(a+b)n的展開式中的各項系數依次對應楊輝三角的第(n+1)行中的每一項。
將第2n+1行第1個數，跟第2n+2行第3個數、第2n+3行第5個數……連成一線，這些數的和是第4n+1個斐波那契數；將第2n行第2個數(n>1)，跟第2n-1行第4個數、第2n-2行第6個數……這些數之和是第4n-2個斐波那契數。
將各行數字相排列，可得11的n-1（n為行數）次方：1=11^0; 11=11^1; 121=11^2……當n>5時會不符合這一條性質，此時應把第n行的最右面的數字」1」放在個位，然後把左面的一個數字的個位對齊到十位… …，以此類推，把空位用「0」補齊，然後把所有的數加起來，得到的數正好是11的n-1次方。以n=11為例，第十一行的數為：1,10,45,120,210,252,210,120,45,10,1，結果為 25937424601=1110。
完整代碼：
#!/usr/bin/python
#coding=utf-8
# __author__ = 'cy'
#輸出楊輝三角數值表
def triangle(num):
#初始表值為[1]
triangle=[[1]]
#添加i個值([1])至triangle表,eg:[1]*3,triangle=[[1], [1], [1]]
for i in range(2, num+1):
triangle.append([1]*i)
#改變triangle表的值,eg:
#當num=5時，i取5，j取3
#triangle[4][1] = triangle[3][1]+triangle[3][0]
#triangle[4][2] = triangle[3][2]+triangle[3][1]
#triangle[4][3] = triangle[3][3]+triangle[3][2]
#相當於triangle表的第4位的值(這里的值為一個表)的第1,2,3位值等於第3位的值(這里的值也是一個表)的第1,2,3位值和0,1,2的值分別相加(即錯位相加)。
for j in range(1, i-1):
triangle[i-1][j] = triangle[i-2][j]+triangle[i-2][j-1]
return triangle
#格式化輸出(輸出的是一個表)
def printtriangle(triangle, width):
#列寬
column = len(triangle[-1])*width
for sublist in triangle:
result = []
for contents in sublist:
#控制間距
result.append('{0:^{1}}'.format(str(contents), width))
#控制縮進，{0:^{1}}：空格在兩邊補齊空位『^』居中對齊，『:』號後面帶填充的字元
print('{0:^{1}}'.format(''.join(result), column))
#啟動函數
if __name__ == '__main__':
#輸入整數
num = int(input('How many rows do you want:'))
#列印信息
print "The triangle rows as follows:"
triangle = triangle(num)
#列寬
width = len(str(triangle[-1][len(triangle[-1])//2]))+3
printtriangle(triangle, width)

❷ python第六講：組合數類型

定義：集合是多個元素的無序組合

特點：集合類型與數學中的集合概念一致，幾何元素之間無序、每個元素唯一、不存在相同元素，幾何元素不可更待、不能存在可變數據類型。

非可變數據類型：整數、浮點數、復數、字元串類型、元組類型等

表示：{},元素間用，分隔

建立：{} 或者set{}，建立空集合必須使用set{}

舉例：

基本操作符：

增強操作符：

實例：

A-B
{123}

B-A
{'3','1','2'}

A&B

{'p','y'}

A|B

{'1','p','2','y','3',123}

A^B

{'2',123,'3','1'}

p123y

A

set()

1.包含關系比較：

True

False

2.數據去重

{'p','y',123}

['p','y',123]

定義：序列是具有先後關系的一組元素

特點：序列是一維元素向量，元素類型可以不同，元素可以相同：類似數學元素序列：元素間有序列引導，通過下標訪問序列的特定元素

序列是一個基類類型，衍生為：字元串類型、元組類型、列表類型

序號的定義：正向遞增序號、反向遞減序號，與字元串中相似。

['.io',123,'python']

'oi.321nohtyp'

序列類型的通用函數和方法：

3

'y'

定義：元組類型是序列類型的一種擴展，一旦創建就不能修改

形式：元組使用（）或者tuple（）創建，元素之間用逗號分隔：小括弧使不使用都可以。

舉例：

('cat','dog','tiger','human')

(4352,'bule',('cat','dog','tiger','human'))

元組類型繼承序列類型全部通用操作：操作符、處理函數、處理方法

元組類型創建後不能修改，因此沒有特殊操作

('human','tiger',dog','cat')

'tiger'

定義：列表是序列類型的一種擴展，創建後其中的元素可以被隨意修改

使用：[]或者list()創建，元素間可以用逗號隔開，列表中各元素類型可不同，無長度限制

['cat','dog','tiger',1024]

['cat','dog','tiger',1024]

列表類型操作函數及其方法：

['cat',1,2,3,4,'tiger',1024]

修改列表：

練習：

序列：元組和列表兩種重要類型

應用場景：元組用於元素不改變的場景，更多用於固定搭配場景：列表更加靈活，它是最常用的序列類型

作用：表達一組有序數據並且處理問題；數據保護

元素遍歷：

元組類型：

數據保護：不希望數據被程序所改變，轉換成元組類型

('cat',1,2,3,4,'tiger',1024)

基本統計值需求：給出一組數並且理解

定義：總個數、求和、平均值、方差、中位數...

總個數：len()

求和：for...in

平均值：求和/總個數

方差：各數據與平均數差的平方的和的平均數

中位數：排序，然後... 奇數找中間一個，偶數中間兩個的平均

映射：是一種索引和數據的對應關系，也是鍵和值的對應關系。

映射類型：由用戶數據為定義索引

字典類型：數據的組織與表達的一種新的形態，是映射的體現。

鍵值對：鍵是數據索引的擴展，字典是鍵值對的集合，鍵值對間無序。

生成：{}和dict()創建，鍵值對之間用冒號：表示

舉例：{<鍵1>:<值1>,<鍵2>:<值2>,...,<鍵n>:<值n>}

在字典變數中，通過鍵獲得值：

<字典變數>={<鍵1>:<值1>,...,<鍵n>:<值n>}

<值>=<字典變數>[<鍵>]

<字典變數>[<鍵>]=<值>

用[]來向字典中增加或者索引鍵值對

舉例：

'北京'

生成空字典：

de={};type(de)

<class 'dict'>

type(x) 返回變數x的類型

舉例：

True

dict_keys(['中國','美國','法國])

dict_values(['北京','華盛頓','巴黎'])

實例：

'北京'

'伊斯蘭堡'

('中國','北京')
練習：

1.映射的表達：映射無處不在，鍵值對也無處不在，統計數據出現的次數，數據是鍵，次數是值。

字典的主要作用：表達鍵值對的數據進而操作他們

2.元素遍歷：

for k in d:

​ <語句塊>

定義：jieba庫是優秀的第三方中文分詞庫，需要額外安裝

安裝方法：（cmd命令下）pip install jieba

作用：利用中文詞庫確定漢字間的關聯概率，字間概率大的組成片語，形成分詞效果，用戶還可以向其中自定義的添加片語。

分類：精確模式、全模式、搜索引擎模式

精確模式：將片語精確的分開，不存在冗餘單詞

全模式：將所有可能的片語都掃描出來，有冗餘

搜索引擎模式：在精確模式的基礎上，將長詞再次切分

舉例：

['中國','是','一個','偉大','的','國家']

['中國','國是','一個','偉大','的','國家']

['中華','華人','人民','共和','共和國','中華人民共和國','是','偉大','的']

需求：一篇文章中出現的詞的頻率統計

分類：英文文本，中文文本

舉例：

英文：哈姆雷特（hamlet）

中文：三國演義（threekingdoms）

❸ 一個組合數之和17,最大值組合是

最大值組合是9和8
8和9兩個數都是合數，而且符合合數之和是17。

❹ Python之動態規劃演算法

動態規劃演算法中是將復雜問題遞歸分解為子問題，通過解決這些子問題來解決復雜問題。與遞歸演算法相比，動態編程減少了堆棧的使用，避免了重復的計算，效率得到顯著提升。

先來看一個簡單的例子，斐波那契數列.

斐波那契數列的定義如下。

斐波那契數列可以很容易地用遞歸演算法實現：

上述代碼，隨著n的增加，計算量呈指數級增長，演算法的時間復雜度是 。

採用動態規劃演算法，通過自下而上的計算數列的值，可以使演算法復雜度減小到 ，代碼如下。

下面我們再看一個復雜一些的例子。

這是小學奧數常見的硬幣問題： 已知有1分，2分，5分三種硬幣數量不限，用這些硬幣湊成為n分錢，那麼一共有多少種組合方法。

我們將硬幣的種類用列表 coins 定義；
將問題定義為一個二維數組 dp，dp[amt][j] 是使用 coins 中前 j+1 種硬幣( coins[0:j+1] )湊成總價amt的組合數。

例如： coins = [1,2,5]

dp[5][1] 就是使用前兩種硬幣 [1,2] 湊成總和為5的組合數。

對於所有的 dp[0][j] 來說，湊成總價為0的情況只有一種，就是所有的硬幣數量都為0。所以對於在有效范圍內任意的j，都有 dp[0][j] 為1。

對於 dp[amt][j] 的計算，也就是使用 coins[0:j+1] 硬幣總價amt的組合數，包含兩種情況計算：

1.當使用第j個硬幣時，有 dp[amt-coins[j]][j] 種情況，即amt減去第j個硬幣幣值，使用前j+1種硬幣的組合數；

2.當不使用第j個硬幣時，有 dp[amt][j-1] 種情況，即使用前j種硬幣湊成amt的組合數；

所以： dp[amt][j] = dp[amt - coins[j]][j]+dp[amt][j-1]

我們最終得到的結果是：dp[amount][-1]

上述分析省略了一些邊界情況。

有了上述的分析，代碼實現就比較簡單了。

動態規劃演算法代碼簡潔，執行效率高。但是與遞歸演算法相比，需要仔細考慮如何分解問題，動態規劃代碼與遞歸調用相比，較難理解。

我把遞歸演算法實現的代碼也附在下面。有興趣的朋友可以比較一下兩種演算法的時間復雜度有多大差別。

上述代碼在Python 3.7運行通過。

❺ 怎樣求大組合數（取模）（ACM演算法）

這種題目然做過的，
意思比較簡單，就由 m 個共 0 和 n 個 1 組成一個串，但從左到右要1出現的次數不少於0出現的次數。
由大牛的演算法： 結果就是 C(m+n, n) - C(m+n, m-1) 再取模，我們可以對式子化簡一下就是：
(n+m)！*
(n-m+1) / ((m)！* (n+1)！)
再取模，但由於組合數很大，直接用大數乘除就會超時了，看了別人的報告才知道原來可以用素數化簡快速求模的， n! = 2^p[i] *
3^p[i] * 5^p[i]*...... 再求模就可以很快了~(^ = ^)~。。。

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
#define M 2000005
#define mm 20100501
bool sig[M];
int prime[150000], p[150000], len; // prime 記錄素數， p 記錄素數的冪 len 記錄長度
void getprime() // 篩法找素數
{
int i,j,k=0;
prime[k++] = 2;
for(i=3; i<=M; i+=2)
{
if( !sig[i] )
{
prime[k++] = i;
for(j=i; j<=M; j+=i)
sig[j] = 1;
}
}
}
void get(int k, int s) // K! 的素數分解, S為指數的加減(分母，分子)
{
int i, mid;
for(i=0; prime[i]<=k && prime[i]; i++)
{
mid = k;
while(mid)
{
if(s)
p[i] += mid/prime[i];
else
p[i] -= mid/prime[i];
mid /= prime[i];
}
}
if(len < i)
len = i;
}
__int64 cal() // 計算結果 (prime[i...]^p[i...]) % mm
{
__int64 i,ans = 1;
for(i=0; i<=len; i++)
{
if( p[i] )
{
__int64 t = prime[i], b = p[i], ret = 1;
while(b) //計算 (t^b) % mm
{
if(b%2) ret *= t %mm;
t = t*t%mm;
b /= 2;
}
ans = ( ans*ret ) % mm;
}
}
return ans;
}
int main()
{
int t,m,n,i,mid;
__int64 ans;
getprime();
cin>>t;
while(t--)
{
cin>>n>>m;
len = 0;
memset(p, 0, sizeof(p));
mid = n-m+1; //先前要把 n-m+1 的因子加進 P 中去才能使 (m+n)! / ((m)!*(n+1)!) 整除
for(i=0; mid>1; i++)
{
if( mid%prime[i] == 0)
{
while(mid%prime[i]==0)
{
p[i] += 1;
mid /= prime[i];
}
}
}
get(m+n, 1);
get(m, 0);
get(n+1, 0);
ans = cal();
printf("%I64d\n", ans);
}
return 0;
}

可以用素數分解法，
先求出上面和下面的素數表示，然後約分後，再用求冪公式

❻ 如何使用Python的遞歸方法來實現組合數

defC(n,m):
ifm>n:
return0
elifm==1:
returnn
elifn==1:
return1
else:
returnC(n-1,m-1)+C(n-1,m)


print(C(5,1))#5
print(C(5,2))#10
print(C(5,3))#10
print(C(5,4))#5
print(C(5,5))#1

❼ 給定兩個常數n和k，其中n>0，k>=0，定義一個函數求組合數的值，n、k作為該函數的參數。 python

❽ Python實現,輸入一個正整數數組,把數組里所有數字拼接起來排成一個數,列印能拼接

你的例子第一列全是 3，我給個例子吧：[321, 32, 3, 4]，輸出該是 321,32,3,4。

第一個數越大，則應該排在後面，畢竟 4XXX 是比 3XXX 大的。

setp1:[0][1][2]
321
32
3
4
排序第0列，越大的排越後。
ret=[?,?,?,4]

setp2:[0][1][2]
321
32
3<3><-補位3，因為3是同3組第一個元素。
排序第1列，越大的排越後。
ret=[?,?,3,4]

setp3:[0][1][2]
321
32<3><-補位3，因為3是同3組第一個元素。
排序第2列，越大的排越後。323比321大，所以……
ret=[?,32,3,4]

只剩一個，那個排第一：
ret=[321,32,3,4]

以上就是基本思路了。綜上可得：

1. 先按 [0] 列分組：

2. 組中每個數都補位到同樣長度，然後再排序。

完整代碼：

defjoinmin(ls):
groups={}
foriteminls:
prefix=item
n=0
whileprefix>10:
prefix//=10
n+=1
groups.setdefault(prefix,[]).append([item,n])
sorted_keys=list(sorted(groups))
ret=0
forprefixinsorted_keys:
items=groups[prefix]
max_n=max([t[1]fortinitems])
presort_items=[]
foritem,item_ninitems:
padding=item
n=item_n
whilemax_n>n:
padding*=10
padding+=prefix
n+=1
presort_items.append((padding,item,item_n))
for_,item,ninsorted(presort_items):
whilen>-1:
ret*=10
n-=1
ret+=item
returnret

不是看在你的分上答的，不過這種小題目蠻有趣的。

❾ 如何用python計算根據N組3個數字組成的排列計算出下一組排列的概率

PERMUT 函數返回從給定數目的對象集合中選取的若干對象的排列數。
COMBIN 函數返回從給定數目的對象集合中提取若干對象的組合數。

❿ 7個數字1,0,0,3,5,6,9最大組合數是多少

7個數字1，0，03，5，6，9最大組合數是：9653100。