大师作文网请教一个线性代数问题,求逆序数的
来源：学生作业帮 编辑：大师作文网作业帮 分类：数学作业 时间：2024/11/17 01:17:53
请教一个线性代数问题,求逆序数的
求(2k)1(2k-1)2(2k-2)3(2k-3)……(k+1)k 的逆序数?为什么答案是0+1+1+2+2+……+(k-1)+k
求(2k)1(2k-1)2(2k-2)3(2k-3)……(k+1)k 的逆序数?为什么答案是0+1+1+2+2+……+(k-1)+k
根据你的结果,其逆序数是这样计算的:
对每个数,看其左边有几个比它大的数
比如:
0 2k 左边没有比它大的数
1 1左边有1个比1大的数
1 2k-1 左边有1个比2k-1大的数
.
PS.还有一种算法:对每个数,看其右边有几个比它小的数
最后结果是一样的.
再问： 我知道计算方法，就是不明白具体怎么数出来的，比如上面那串数我没看出它有何规律，还有k有没有范围限制呢
再答： k 一般默认是正整数 你分两部分考虑 1 左边有1个大于它 2 左边有2个大于它 ... k 左边有k个大于它 这部分有逆序 1+2+3+...+k 个 (2k) 左边有0个大于它 (2k-1) 左边有1个大于它 (2k-2) 左边有2个大于它 (2k-3) 左边有3个大于它 .... (k+1) 左边有k-1个大于它 这部分有逆序 0+1+2+3+...+(k-1) 个 找它的规律好了
对每个数,看其左边有几个比它大的数
比如:
0 2k 左边没有比它大的数
1 1左边有1个比1大的数
1 2k-1 左边有1个比2k-1大的数
.
PS.还有一种算法:对每个数,看其右边有几个比它小的数
最后结果是一样的.
再问： 我知道计算方法，就是不明白具体怎么数出来的，比如上面那串数我没看出它有何规律，还有k有没有范围限制呢
再答： k 一般默认是正整数 你分两部分考虑 1 左边有1个大于它 2 左边有2个大于它 ... k 左边有k个大于它 这部分有逆序 1+2+3+...+k 个 (2k) 左边有0个大于它 (2k-1) 左边有1个大于它 (2k-2) 左边有2个大于它 (2k-3) 左边有3个大于它 .... (k+1) 左边有k-1个大于它 这部分有逆序 0+1+2+3+...+(k-1) 个 找它的规律好了