如何理解排列組合中的定序問題留空位法?

時間 2021-06-06 05:54:31

1樓:reallht

首先,你能問出這樣的問題說明你已經很善於學習了,因為你不會滿足於記住公式,而是想著深挖公式背後的原理。

其次,定序排列問題其實不算是比較難的問題,可以用正反好幾種方法來解決:空位法、倍縮法、插入法等。比如,7個人排成一隊,其中甲乙丙三個人必須按身高又高到低排列,問共有多少種排隊方法?

排列問題是分步計數方法的乙個特例,所有的原理都來自於分步計數原理:

在7個座位上先考慮另外四個人的排法: ,然後在剩餘的三個座位上再考慮甲乙丙三個人:1,所以總共有: 種方法。

有同學可能會問如果先考慮甲乙丙三個人會不一樣嗎?其實不會的:

先考慮甲乙丙的排法: 種,但是由於甲乙丙順序固定,所以需要除以 ,第二步在剩餘的四個位置上安排其餘四人: ,所以總共的方法數為: 種

上面的回答中有兩個關鍵點:

以上理解了的話,那麼

空位法:在7個座位上先考慮另外四個人的排法: ,然後在剩餘的三個座位上再考慮甲乙丙三個人:1,所以總共有: 種方法。

倍縮法:先7個人全排列,再除以甲乙丙三個人的全排列。原理是這樣的:,或者:。(如果沒看懂這兩個式子的話,說明同學你還是沒有真正懂哦)

還有一種方法

插入法:甲乙丙三人排好隊,只有1種方法;第二步考慮第四個人的選擇:在甲乙丙三個人的空隙以及兩頭共有4個空隙;第三步考慮第5個人的選擇:

有5個空隙;第四步考慮第6個人的選擇:有6個空隙;第五步考慮第7個人的選擇,有7個空隙;所以總共的方法有 種。

求助乙個排列組合的問題?

王箏 用了另外乙個演算法。首先看分母,是所有連線的方法,每一步取出兩個繩頭連起來,所以是C 2 12乘到C 2 2,但是注意到與順序無關,所以要除掉6 所以算出來是11 然後分子是6個東西連成一圈的種類數,首先全排列成6 但是起點是任意的,要除掉6,然後正反兩面是任意的,要除掉2,每個繩子有兩種方向...

如何理解C 中的「全排列問題」?

如果是求全排列,直接dfs回溯就行了。如果是std next permutation,思路就是把公升序佇列逐步轉為降序佇列。比如1234最後要轉化為4321,過程是 1234 1243 1324 1342 1423 1432 2134 2143 2314 2341 2413 2431 3124 31...

如何理解日語中 誤用的問題?

修羅 基本上就是 雨宮観鈴說的那樣,的語氣只是建議,而 的語氣其實已經比較重了。如果有人對你這樣說,其實已經是 不這樣做就要糟糕 的含義了。 有一種 你別問我,我不懂。你問田中去,他肯定懂的感覺。但對方也不是問句 可能這裡比較奇怪吧 但感覺用了也沒啥毛病,對方也懂你的意思。如果是我會加乙個 再把 變...