逆序數演算法

⑴ 求數列n（n-1）（n-2）······321的逆序數，並討論其奇偶性

n後面比n小的數有：(n-1)個

n-1後面比n-1小的數有：(n-2)個

n-2後面比n-2小的數有：(n-3)個

..................

3的後面比3小的數有：2個

2的後面比2小的數有：1個

1的後面比1小的數有：0個

因此：

(n-1)+(n-2)+(n-3)+....+3+2+1

令：

S=(n-1)+(n-2)+(n-3)+....+3+2+1

則根據等差數列可知：

S=n(n-1)/2

分析奇偶性：

i)因為n取非零自然數，n(n-1)表示連續相乘，也就是說，必定是，奇數×偶數或者偶數×奇數，不管哪種情況，n(n-1)必定是偶數，因此，n(n-1)必定能整除2

ii)根據上述分析，n(n-1)整除2後，有可能是奇數也有可能是偶數；

當n(n-1)/2是偶數時，n(n-1)中，或者是n，或者是(n-1)必定是4的倍數，因此，按照n為4的倍數的完備分類討論，取k是自然數，則：

1）

當n=4k時，n(n-1)/2=2k(4k-1)，其中4k-1是奇數，2k是偶數，因此，S是偶數；

2）

當n=4k+1時，n(n-1)/2=2k(4k+1)，其中4k+1是奇數，2k是偶數，因此，S是偶數；

3）

當n=4k+2時，n(n-1)/2=(2k+1)(4k+1)，其中2k+1是奇數，4k+1是奇數，因此，S是奇數；

4）

當n=4k+3時，n(n-1)/2=(4k+3)(2k+1)，其中2k+1是奇數，4k+3是奇數，因此，S是奇數

(1)逆序數演算法擴展閱讀：

逆序數是指一個排列中所有逆序總數，而排列，是從n個不同元素中取出m（m≤n）個元素，按照一定的順序排成一列。

145243中出現出現相同的數4， 所以145243不是排列，也就無所謂計算逆序和逆序數了。

逆序數為偶數的排列稱為偶排列；逆序數為奇數的排列稱為奇排列。[1] 如2431中，21，43，41，31是逆序，逆序數是4，為偶排列。

計算逆序數：

標准列是1 2 3 4 5 ，那麼 5 4 3 2 1 的逆序數演算法：

5之前沒有數，記為0.

看第二個，4之前有一個5，在標准列中5在4的後面，所以記1個

類似的，第三個 3 之前有 4 5 都是在標准列中3的後面，所以記2個

同樣的，2 之前有3個，1之前有4個

將這些數加起來就是逆序數=1+2+3+4=10

再舉一個 2 4 3 1 5

4 之前有0個

3 之前有1個

1 之前有3個

5 之前有0個

所以逆序數就是1+3=4

⑵ 逆序數怎麼求

解答如下：

當n=1時，排列為1 2，逆序數t=0。

當n=2時，排列為內1 3 2 4，逆序容數t=1。

當n=3時，排列為1 3 5 2 4 6，逆序數t=1+2=3。

當n=4時，排列為1 3 5 7 2 4 6 8，逆序數t=1+2+3=6。

當n=5時，排列為1 3 5 7 9 2 4 6 8 10，逆序數t=1+2+3+4=10。

相關內容解釋

在一個排列中，如果一對數的前後位置與大小順序相反，即前面的數大於後面的數，那麼它們就稱為一個逆序。一個排列中逆序的總數就稱為這個排列的逆序數。一個排列中所有逆序總數叫做這個排列的逆序數。

也就是說，對於n個不同的元素，先規定各元素之間有一個標准次序(例如n個 不同的自然數，可規定從小到大為標准次序)，於是在這n個元素的任一排列中，當某兩個元素的先後次序與標准次序不同時，就說有1個逆序。一個排列中所有逆序總數叫做這個排列的逆序數。

⑶ 怎麼算逆序數急~~~！！！

可使用直接計數法，計算一個排列的逆序數的直接方法是逐個枚舉逆序，同時統計個數。

舉個例子：

標准列是1 2 3 4 5，那麼 5 4 3 2 1 的逆序數演算法：

看第二個，4之前有一個5，在標准列中5在4的後面，所以記1個。

類似的，第三個 3 之前有 4 5 都是在標准列中3的後面，所以記2個。

同樣的，2 之前有3個，1之前有4個，將這些數加起來就是逆序數=1+2+3+4=10。

(3)逆序數演算法擴展閱讀：

其它演算法：

1、歸並排序

歸並排序是將數列a[l,h]分成兩半a[l,mid]和a[mid+1,h]分別進行歸並排序，然後再將這兩半合並起來。在合並的過程中（設l<=i<=mid，mid+1<=j<=h），當a[i]<=a[j]時，並不產生逆序數；

當a[i]>a[j]時，在前半部分中比a[i]大的數都比a[j]大，將a[j]放在a[i]前面的話，逆序數要加上mid+1-i。因此，可以在歸並排序中的合並過程中計算逆序數。

2、樹狀數組

由於樹狀數組的特性，求和是從當前節點往前求，所以，這里要查詢插入當前數值之時，要統計有多少個小於該數值的數還沒插入，這些沒插入的數，都會在後面插入，也就形成了逆序數。

⑷ n階行列式逆序數怎麼算，有沒有具體公式一步將逆序數

沒有具體公式，演算法如下：

在行列式：

顯然，1,2,...,n也是一個n級排列，這個排列具有自然順序，就是按遞增的順序排起來的；其它的排列都或多或少地破壞自然順序。

逆序

定義2 在一個排列中，如果一對數的前後位置與大小順序相反，即前面的數大於後面的數，那麼它們就稱為一個逆序。

註：

1.對於n個不同的元素，先規定個元素之間有一個「標准次序」（例如n個不同的自然數，可規定由小到大為標准次序），於是在這n個元素的任一排列中，當某兩個元素的先後次序與標准次序不同時，就有1個「逆序」。

2.一個排列中所有逆序的總數叫做這個排列的逆序數。

3.逆序數為奇數的排列叫做奇排列，逆序數為偶數的排列叫做偶排列。

⑸ 什麼叫逆序

跟標准列相反序數的總和
比如說
標准列是1 2 3 4 5
那麼 5 4 3 2 1 的逆序數演算法：
看第二個，4之前有一個5，在標准列中5在4的後面，所以記1個
類似的，第三個 3 之前有 4 5 都是在標准列中3的後面，所以記2個
同樣的，2 之前有3個，1之前有4個
將這些數加起來就是逆序數=1+2+3+4=10

再舉一個 2 4 3 1 5
4 之前有0個
3 之前有1個
1 之前有3個
5 之前有0個
所以逆序數就是1+3=4

這樣能明白嗎

⑹ 計算行列式D={0100；0020；0003 4000『}是多少怎麼做請詳細解答謝謝

可以用定義直接得
行列式 = （-1）^t(2341) *1*2*3*4= - 24 .

此類題關鍵是求逆序數 t(2341) = 1+1+1 = 3

逆序數的演算法是: 看每個數的右邊比它小的數的個數, 加起來就是逆序數.

滿意請採納^_^

⑺ 1326逆序數是

逆序數是這樣計算的:
對每個數,看其左邊有幾個比它大的數
比如:
0 2k 左邊沒有比它大的數
1 1左邊有1個比1大的數
1 2k-1 左邊有1個比2k-1大的數
.
PS.還有一種演算法:對每個數,看其右邊有幾個比它小的數
最後結果是一樣的.

⑻ 求逆序數是看比 這個數小還是比這個數大

逆序數是這樣計算的:
對每個數, 看其左邊有幾個比它大的數
比如:
0 2k 左邊沒有比它大的數
1 1左邊有1個比1大的數
1 2k-1 左邊有1個比2k-1大的數
.........

PS.還有一種演算法: 對每個數, 看其右邊有幾個比它小的數
最後結果是一樣的.

⑼ 當排列數中出現相同的數時，逆序數怎麼計算，比如145243

逆序數是指一個排列中所有逆序總數，而排列，是從n個不同元素中取出m（m≤n）個元素，按照一定的順序排成一列。

145243中出現出現相同的數4， 所以145243不是排列，也就無所謂計算逆序和逆序數了。

逆序數為偶數的排列稱為偶排列；逆序數為奇數的排列稱為奇排列。[1]如2431中，21，43，41，31是逆序，逆序數是4，為偶排列。

(9)逆序數演算法擴展閱讀

計算逆序數：

標准列是1 2 3 4 5 ，那麼 5 4 3 2 1 的逆序數演算法：

5之前沒有數，記為0.

看第二個，4之前有一個5，在標准列中5在4的後面，所以記1個

類似的，第三個 3 之前有 4 5 都是在標准列中3的後面，所以記2個

同樣的，2 之前有3個，1之前有4個

將這些數加起來就是逆序數=1+2+3+4=10

再舉一個 2 4 3 1 5

4 之前有0個

3 之前有1個

1 之前有3個

5 之前有0個

所以逆序數就是1+3=4

⑽ 654123逆序數

逆序數15。
5之前有1個，4之前有2個，1之前有5個，2之前有4個，3之前有3個，所以1+2+5+4+3=15.
跟標准列相反序數的總和
比如說
標准列是12345
那麼54321的逆序數演算法：
看第二個，4之前有一個5，在標准列中5在4的後面，所以記1個
類似的，第三個3之前有45都是在標准列中3的後面，所以記2個
同樣的，2之前有3個，1之前有4個
將這些數加起來就是逆序數=1+2+3+4=10
再舉一個24315
4之前有0個
3之前有1個
1之前有3個
5之前有0個
所以逆序數就是1+3=4