逆序数算法

⑴ 求数列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