求逆序数算法_怎么算逆序数急~~~！！！

❶ 怎么算逆序数急~~~！！！

可使用直接计数法，计算一个排列的逆序数的直接方法是逐个枚举逆序，同时统计个数。

举个例子：

标准列是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)求逆序数算法扩展阅读：