跪求,计算数列的逆序数,并确定其奇偶性.
(1#) n(n-1)……321
(2#)246……(2n)135……(2n-1) 跪求详细步骤
(1#) n(n-1)……321
{
此处内容可以省略,为便于阅读和理解而说明.答题时可以去掉.
按“数字 对应的逆序的个数 {由在它后面比它小的数字的集合}”列成下表:
n n-1 {n-1,n-2,...,2,1}
...
3 2 {2,1}
2 1 {1}
1 0 {空集,可省略}
}
所求=n-1+...+1+0=n(n-1)/2
{
内容可省略.
奇偶性:
先设n=2k,则逆序数=k(2k-1),其奇偶性由k决定.
即k偶则逆序数为偶,于是当k=2t即n=4t时,逆序数为偶.
同时k奇则逆序数为奇,于是当k=2t+1即n=4t+2时,逆序数为奇.
再设n=2k+1,则逆序数=(2k+1)*k,同样由k决定,
k=2t即n=4t+1时,逆序数为偶.
k=2t+1即n=4t+3时,逆序数为奇.
综上述,
}
当n形如4t或4t+1时,逆序数为偶.其它情况则为奇.
{
我其实是这样做的:心算n=0,1,2,3几个特例看奇偶性,并且知道这样的数的奇偶性是周期性的,因此直接写出结果.
}
(2#)246……(2n)135……(2n-1)
{
此处内容可以省略,为便于阅读和理解而说明.答题时可以去掉.
按“数字 对应的逆序的个数 {产生逆序的其它数字的集合}”列成下表:
2n n {1,3,...,2n-1}
2n-2 n-1 {1,3,...,2n-3}
...
2 1 {1}
1 0
2 0
...
2n-1 0
}
所求=n+n-1+...+1=n(n+1)/2
(由心算知)当n形如4t,4t+3时,为偶;n形如4t+1,4t+2时,为奇.