演算法 日更 第四十一期 組合與排列

2022-11-24 17:31:55 字數 1506 閱讀 3642

▎排列

☞『引入』

思考一個問題:

你的眼前現在有三個人:gzr、lsh、hza,如何排列他們的位置呢?

顯然,有這樣的排法:

gzr、lsh、hza

gzr、hza、lsh

hza、lsh、gzr

hza、gzr、lsh

lsh、gzr、hza

lsh、hza、gzr

一共是六種。

☞『定義』

這不就是排個順序嗎?相信定義就不需要拿出來講了。

但是唯一要注意一點:排列是關心順序的。

☞『n中選n個求解』

那麼我們在n個人中進行排列的方案數有多少種呢?

顯然,第一個人有n種方案;

第二個人有n-1種方案;

第三個人有n-2種方案;

第n個人有1種方案;

按照乘法原理,總的方案數就是n*(n-1)*(n-2)*…*2*1。

發現了什麼?這豈不是 n! 。

☞『n中選m個求解』

依舊是上面的思路,只不過不是n!了。

現在我們來思考:n!在這種情況下,被多乘了多少次?

當然有(n-m)!次都是多乘的,所以有n!/(n-m)!個方案。

▎排列數

當n箇中取m個的時候,我們可以用

來表示。

比如說5個數排列三個位置就有

個方案。

▎組合☞

『引入』

來思考下面的問題:

有三隻小狗,分別是中華田園犬、柴犬、拉布拉多。

但是現在只有兩塊狗狗零食,那麼為了公平起見,一隻狗最多隻能吃一個,所以只能給兩隻狗狗吃,剩下的那一隻只能下次了。

所以,問題是:分配的方案數有多少種? 

這就是組合的問題。

☞『定義』

在剛才的問題中,仍然是上面的選擇方案數問題,但是卻不太一樣了。

由於狗狗吃了就是吃了,不會在意順序,而剛才的排列是在意順序的。

所以,組合和排列不同的地方就是是否關心順序是怎樣的。

☞『求解』

對比剛才的排列,如何快速求出組合的方案數呢?

不難發現同一種組合方式被當作排列一定會算

,所以就只要在排列的結果上除以

就可以了。

所以公式就是:

。▎組合數

☞『表示』

剛才的那個c的符號就是組合的符號,和排列的用法一樣。

也就是說將n中選m個的排列方案數記做

。『通項公式』

現在不思考前n-1個數是怎麼選的,只關心第n個數。

顯然,情況就兩種,要麼被選,要麼不被選。

被選上一定是從

轉移來的,不被選上一定是從

轉移來的。

所以按照加法原理,通項公式就是這樣的:

演算法 日更 第四十五期 靜態二叉排序樹(建立)

前言 小編雖然已經會了二叉排序樹,但是卻不明白靜態二叉排序樹和二叉排序樹有什麼關係。結合平衡二叉排序樹 例如 紅黑樹 食用本篇部落格,效果更佳哦 傳送門 同時也內含二叉排序樹的相關知識 靜態二叉排序樹 引入 這個東西要從線段樹說起,別問我為什麼扯這麼遠。戳這裡快速上手線段樹。不得不說,線段樹是個好東...