求逆序數演算法_怎麼算逆序數急~~~！！！

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

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

舉個例子：

標准列是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。

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

其它演算法：

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.逆序數為奇數的排列叫做奇排列，逆序數為偶數的排列叫做偶排列。

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

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

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

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

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

計算逆序數：

標准列是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

❹ 逆序數怎麼算

如4321,它的逆序數為6.
因為4的後面有3個比4小的數,3的後面有2個比3小的數,二的後面有1個比2小的數
所以3+2+1=6

❺ 請教一個線性代數問題，求逆序數的

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

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

滿意請採納^_^

❻ 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

❼ 求一個任意多位數逆序輸出的演算法，C語言實現

我的方法比較笨拙：

①先算數字有多少位；

②第二次循環中，將輸入數字除以10 的余數乘（數字位數 - 循環次數）；

intmain(void){
intnumber,m,digits,number2,i,n,temp;
printf("Enteranumber:");
scanf("%d",&number);

n=0;
temp=number;
do{
n++;
temp/=10;
}while(temp>0);
digits=0;
number2=0;
do{
digits++;
m=number%10;
number/=10;

for(i=0;i<n-digits;i++){
m*=10;
}
number2+=m;
}while(number>0);
printf("Thenumberis%d
",number2);

return0;
}
希望有更好的寫法，感謝！

❽ 逆序數怎麼算

怎樣求逆序數
這個的是0

1後面<1的數0個＋2後面<2的數0個＋3後面<3的數0個＝0

可以推廣為（a,b,c,……，z)

a後面小於a的數A個……一直加到z後面小於z的數Z個

即為它的逆序數！
排列，1，6，5，3，4，2的逆序數是多少，怎麼樣算，急
逆序數是逆序的個數，」逆序」是相對「

」順序」而言的。「順序」是指由小到大的自然數順序，如：1，2，3……所以，這道題的逆序對為6，5；6，3；6，4；6，2；5，3；5，4；5，2；3，2；4，2。所以逆序數為9。
逆序數怎麼求
我收集到的有兩種方法：歸並排序和樹狀數組。

1、歸並排序：

假設a[l...r]這個數組，先二分mid=(l+r)/2；那麼我們假設已經求出了a[l...mid],a[mid+1...r]這兩段元素的逆序數且排好序，於是可以將這兩段歸並了，歸並的同時計算逆序數，如果前段的數小於後段的數，屬於正常排序，反之，就會有逆序數產生。假設l<=i<=mid,mid+1<=j<=r,如果有a[i]>a[j]，這樣的發生說明在a的前段中i...mid的元素都比a[j]大，於是逆序數+=mid-i；如果a[i]

2、樹狀數組：

我們先假設一個1...n自然數排列，n不是很大，於是這樣就可以申請一個n個空間的a數組，首先全部置0，每次將排列中的數i取出（從左到右取出），改變a數組的元素的值為1（1），然後求出a[1...i-1],的和（1），這個和就是小於i的值的和sum，就是i這個數的逆序數。這里的（1）、（2）就會用到樹狀數組的logn時間復雜度的演算法。

但是這里說自然數的范圍很大比如（0-999，999，999）時候，而個數不多時。這樣是情況才是作者想考察我們演算法的東西，那麼這里就要說說離散化的用法了。

離散化：其實我開始理解就是想的很多大數據用數組來存儲，那麼下標就代表了數據本身了，舉個簡單的列子。

1、1000、100000、100000、999。

這樣一串數，如果用數組來存儲，只需要開辟5個int空間就夠了。這樣就把離散的大數據很輕巧的裝到小盒子裡面了。這樣說，其實你可能還在懵懂中，因為這樣的方法好像隨處可見，我開始也是這樣想的，沒什麼特別的，但是當我看到了一個別人博客里做的離散化題目後才深切的體會。那麼下面讓我們來看看在逆序數中的用法吧！

如果將逆序數的本質找到就可以很好理解了，求逆序數其實就求每個數的逆序數之和，如果要求當前逆序數，則是找當前數的後續數中比他小的數的個數，然後在抽象一下就可以知道，其實對於逆序數而言，與元素的本身沒關系，而是與元素與元素之間的大小有關系，這點理解到的很重要的。

既然是元素與元素之間大小相關的話，我們就可以這樣看的問題了，對於上面的一串數可以用另外一串具有最小數據本身的數來替代，假設用3、40、50、60、20，比較一下，可以看出他們元素與元素之間的大小關系是一樣的。於是我們就可以進一步推測能夠找到最小串的自然數來替代了，就是1、3、4、5、2。看看吧！這串數夠小了吧，而且關系和上面的大數據也相同，即是說逆序數相同。

如果找到了這樣的一串數來替代大數據的話，我們就可以開小空間數組來存儲這些數了。然後就可以用樹狀數組來求出逆序數，復雜度為nlogn。

這里就要想怎樣求得這樣的串了，其實稍微一想便知道，其實這串數就是大數據的排名情況。比如1000排名第3，於是1000就是3。求排名其實就是求一個排序，排序後的數組下標就是該數據的排名。於是我們會問，你怎麼知道該數據和下標的對應關系呢？

假設我們為每個大數據建立起1對1的關系的話就好說了。

struct Ln

{

int a;表示大數據

int b;表示下標ln[i],這里的i==b

}

Ln ln[N];

建立好對應關系後，對ln排序，排好序後每個小標都有排名了，即是大數據的排名，然後將他放入a數組中，建立......
行列式逆序數怎麼算
按第一列展開,D11=1,D12=3,D13=2,正負號就看他們的下標和是負數還是正數,如：D11的下標和是2,D13的下標和是4,所以是正的
行列式的逆序數怎麼算
只計算行逆序數（列號升序的情況下）或者列逆序數（行號已經按升序排列的情況下）
求3756412的逆序數？
在3後面比它小的有2個，逆序數為2

在7後面比它小的有5個，逆序數為5

在5後面比它小的有3個，逆序數為3

在6後面比它小的有3個，逆序數為3

在4後面比它小的有2個，逆序數為2

在1後面比它小的有0個，逆序數為0

所以序列的逆序數有2+5+3+3+2=15
逆序數的逆序數的計算
計算一個排列的逆序數的直接方法是逐個枚舉逆序，同時統計個數。例如在序列 { 2, 4, 3, 1 } 中，逆序依次為 (2,1), (4,3), (4,1), (3,1)，因此該序列的逆序數為 4。下面這個 Visual Basic 6.0 編寫的示例使用的就是直接計數的方法，函數 NiXushu 返回一個字元串的逆序數。Private Function NiXuShu(ByVal l As String) As Long '逆序數計算Dim i As Integer, j As Integer, c As LongDim n() As IntegerReDim n(Len(l))For i = 1 To Len(l)n(i) = Val(Mid(l, i, 1))For j = 1 To i - 1If n(i) < n(j) Thenc = c + 1End IfNext jNext iNiXuShu = cEnd Function 直接計數法雖然簡單直觀，但是其時間復雜度是 O(n^2)。一個更快（但稍復雜）的計算方法是在歸並排序的同時計算逆序數。下面這個 C++ 編寫的例子演示了計算方法。函數 mergeSort() 返回序列的逆序數。int is1[n],is2[n]; is1為原數組，is2為臨時數組，n為個人定義的長度long mergeSort(int a,int b) 下標，例如數組int is[5]，全部排序的調用為mergeSort(0,4){if(a

❾ 逆序數怎麼算

計算一個排列的逆序數的直接方法是逐個枚舉逆序，同時統計個數。例如在序列 {2,4，3,1}中，逆序依次為(2,1),(4,3),(4,1),(3,1)，因此該序列的逆序數為4。

下面這個VisualBasic6.0編寫的示例使用的就是直接計數的方法，函數NiXushu返回一個字元串的逆序數。

PrivateFunctionNiXuShu(ByVallAsString)AsLong'逆序數計算

DimiAsInteger,jAsInteger,cAsLong

Dimn()AsInteger

ReDimn(Len(l))

Fori=1ToLen(l)

n(i) =Val(Mid(l,i,1))

For j=1Toi-1

If n(i)<n(j)Then

c=c+1

EndIf

Nextj

Nexti

NiXuShu=c

EndFunction

逆序數歸並排序

直接計數法雖然簡單直觀，但是其時間復雜度是O（n²）。一個更快（但稍復雜）的計算方法是在歸並排序的同時計算逆序數。下面這個C++編寫的例子演示了計算方法。函數 mergeSort() 返回序列的逆序數。

int is1[n],is2[n];// is1為原數組，is²為臨時數組，n為個人定義的長度

long merge(int low,int mid,int high)

int i=low,j=mid+1,k=low;

long count=0;

while(i<=mid&&j<=high)

if(is1[i]<=is1[j])// 此處為穩定排序的關鍵，不能用小於

is2[k++]=is1[i++];

else

is2[k++]=is1[j++];

count+=j-k;// 每當後段的數組元素提前時，記錄提前的距離

while(i<=mid)

is2[k++]=is1[i++];

while(j<=high)

is2[k++]=is1[j++];

for(i=low;i<=high;i++)// 寫回原數組

is1[i]=is2[i];

return count;

long mergeSort(int a,int b)// 下標，例如數組int is[5]，全部排序的調用為mergeSort(0,4)if（a＜b）

int mid=(a+b)/2;

long count=0;

count+=mergeSort(a,mid);

count+=mergeSort(mid+1,b);

count+=merge(a,mid,b);

return count;

return 0

❿ 求數列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是奇數

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