怎么算逆序數(shù)的奇偶性 求數(shù)列n（n-1）（n-2）······321的逆序數(shù)，并討論其奇偶性
跪求，計(jì)算數(shù)列的逆序數(shù)，并確定其奇偶性。 1.n(n-1)……321 2.246……（2n)135……（2n-1) 跪求詳細(xì)步驟，求排列n(n-1)....3,2,1的逆序數(shù)，并討論該排列的奇偶性 ，怎么判斷第五題逆序數(shù)的奇偶性？求數(shù)列n（n-1）（n-2）······321的逆序數(shù)，并討論其奇偶性，怎么算逆序數(shù)？急~~~！！？計(jì)算逆序數(shù)并指出奇偶性。
本文導(dǎo)航
- 跪求，計(jì)算數(shù)列的逆序數(shù)，并確定其奇偶性。 1.n(n-1)……321 2.246……（2n)135……（2n-1) 跪求詳細(xì)步驟
- 求排列n(n-1)....3,2,1的逆序數(shù)，并討論該排列的奇偶性 ？
- 怎么判斷第五題逆序數(shù)的奇偶性
- 求數(shù)列n（n-1）（n-2）······321的逆序數(shù)，并討論其奇偶性
- 怎么算逆序數(shù)？急~~~?。。?/a>
- 計(jì)算逆序數(shù)并指出奇偶性
跪求，計(jì)算數(shù)列的逆序數(shù)，并確定其奇偶性。 1.n(n-1)……321 2.246……（2n)135……（2n-1) 跪求詳細(xì)步驟
跪求，計(jì)算數(shù)列的逆序數(shù)，并確定其奇偶性。
（1#） n(n-1)……321
（2#）246……（2n)135……（2n-1) 跪求詳細(xì)步驟
解：
（1#） n(n-1)……321
{
此處內(nèi)容可以省略，為便于閱讀和理解而說明。答題時(shí)可以去掉。
按“數(shù)字 對(duì)應(yīng)的逆序的個(gè)數(shù) {由在它后面比它小的數(shù)字的集合}”列成下表：
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èi)容可省略。
奇偶性：
先設(shè)n=2k，則逆序數(shù)=k(2k-1)，其奇偶性由k決定.
即k偶則逆序數(shù)為偶,于是當(dāng)k=2t即n=4t時(shí)，逆序數(shù)為偶。
同時(shí)k奇則逆序數(shù)為奇,于是當(dāng)k=2t+1即n=4t+2時(shí)，逆序數(shù)為奇。
再設(shè)n=2k+1,則逆序數(shù)=(2k+1)*k，同樣由k決定，
k=2t即n=4t+1時(shí)，逆序數(shù)為偶。
k=2t+1即n=4t+3時(shí)，逆序數(shù)為奇。
綜上述，
}
當(dāng)n形如4t或4t+1時(shí)，逆序數(shù)為偶。其它情況則為奇。
{
我其實(shí)是這樣做的：心算n=0,1,2,3幾個(gè)特例看奇偶性，并且知道這樣的數(shù)的奇偶性是周期性的，因此直接寫出結(jié)果。
}
（2#）246……（2n)135……（2n-1)
{
此處內(nèi)容可以省略，為便于閱讀和理解而說明。答題時(shí)可以去掉。
按“數(shù)字 對(duì)應(yīng)的逆序的個(gè)數(shù) {產(chǎn)生逆序的其它數(shù)字的集合}”列成下表：
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
（由心算知）當(dāng)n形如4t,4t+3時(shí)，為偶；n形如4t+1,4t+2時(shí)，為奇。
求排列n(n-1)....3,2,1的逆序數(shù)，并討論該排列的奇偶性 ？
逆序數(shù)是n(n-1)/2。
假設(shè)n是偶數(shù)，則n＝2m，m是奇數(shù)或偶數(shù)，所以n(n-1)/2=m(2m-1)。這里的2m-1肯定是奇數(shù)，但是m可奇可偶，所以當(dāng)m是奇數(shù)2k+1（此時(shí)n＝2m=4k+2）時(shí)，n(n-1)/2是奇數(shù)。當(dāng)m是偶數(shù)2k（此時(shí)n＝2m=4k）時(shí)，n(n-1)/2是偶數(shù)。
假設(shè)n是奇數(shù)，則n＝2m+1，m是奇數(shù)或偶數(shù)，所以n(n-1)/2=m(2m+1)。同樣的討論，得到結(jié)論：當(dāng)m是奇數(shù)2k+1（此時(shí)n＝2m+1=4k+3）時(shí)，n(n-1)/2是奇數(shù)。當(dāng)m是偶數(shù)2k（此時(shí)n＝2m+1=4k+1）時(shí)，n(n-1)/2是偶數(shù)。
綜上，當(dāng)n=4k或4k+1是偶排列，當(dāng)n=4k+2或4k+3時(shí)，是奇排列。
怎么判斷第五題逆序數(shù)的奇偶性
n=1時(shí)，排列為12，逆序數(shù)為0；
n=2時(shí)，排列為1342，逆序數(shù)為1+1=2；
n=3時(shí)，排列為135642，逆序數(shù)為1+2+2+1=6；
n=4時(shí)，排列為13578642，逆序數(shù)為1+2+3+3+2+1=12；
因此，原排列逆序數(shù)為[1+2+...+(n-1)]*2=(n-1)*n
求數(shù)列n（n-1）（n-2）······321的逆序數(shù)，并討論其奇偶性
n后面比n小的數(shù)有：(n-1)個(gè)
n-1后面比n-1小的數(shù)有：(n-2)個(gè)
n-2后面比n-2小的數(shù)有：(n-3)個(gè)
..................
3的后面比3小的數(shù)有：2個(gè)
2的后面比2小的數(shù)有：1個(gè)
1的后面比1小的數(shù)有：0個(gè)
因此：
(n-1)+(n-2)+(n-3)+....+3+2+1
令：
S=(n-1)+(n-2)+(n-3)+....+3+2+1
則根據(jù)等差數(shù)列可知：
S=n(n-1)/2
分析奇偶性：
i)因?yàn)閚取非零自然數(shù)，n(n-1)表示連續(xù)相乘，也就是說，必定是，奇數(shù)×偶數(shù)或者偶數(shù)×奇數(shù)，不管哪種情況，n(n-1)必定是偶數(shù)，因此，n(n-1)必定能整除2
ii)根據(jù)上述分析，n(n-1)整除2后，有可能是奇數(shù)也有可能是偶數(shù)；
當(dāng)n(n-1)/2是偶數(shù)時(shí)，n(n-1)中，或者是n，或者是(n-1)必定是4的倍數(shù)，因此，按照n為4的倍數(shù)的完備分類討論，取k是自然數(shù)，則：
1）
當(dāng)n=4k時(shí)，n(n-1)/2=2k(4k-1)，其中4k-1是奇數(shù)，2k是偶數(shù)，因此，S是偶數(shù)；
2）
當(dāng)n=4k+1時(shí)，n(n-1)/2=2k(4k+1)，其中4k+1是奇數(shù)，2k是偶數(shù)，因此，S是偶數(shù)；
3）
當(dāng)n=4k+2時(shí)，n(n-1)/2=(2k+1)(4k+1)，其中2k+1是奇數(shù)，4k+1是奇數(shù)，因此，S是奇數(shù)；
4）
當(dāng)n=4k+3時(shí)，n(n-1)/2=(4k+3)(2k+1)，其中2k+1是奇數(shù)，4k+3是奇數(shù)，因此，S是奇數(shù)
擴(kuò)展資料：逆序數(shù)是指一個(gè)排列中所有逆序總數(shù)，而排列，是從n個(gè)不同元素中取出m（m≤n）個(gè)元素，按照一定的順序排成一列。
145243中出現(xiàn)出現(xiàn)相同的數(shù)4， 所以145243不是排列，也就無所謂計(jì)算逆序和逆序數(shù)了。
逆序數(shù)為偶數(shù)的排列稱為偶排列；逆序數(shù)為奇數(shù)的排列稱為奇排列。[1] 如2431中，21，43，41，31是逆序，逆序數(shù)是4，為偶排列。
計(jì)算逆序數(shù)：
標(biāo)準(zhǔn)列是1 2 3 4 5 ，那么 5 4 3 2 1 的逆序數(shù)算法：
5之前沒有數(shù)，記為0.
看第二個(gè)，4之前有一個(gè)5，在標(biāo)準(zhǔn)列中5在4的后面，所以記1個(gè)
類似的，第三個(gè) 3 之前有 4 5 都是在標(biāo)準(zhǔn)列中3的后面，所以記2個(gè)
同樣的，2 之前有3個(gè)，1之前有4個(gè)
將這些數(shù)加起來就是逆序數(shù)=1+2+3+4=10
再舉一個(gè) 2 4 3 1 5
4 之前有0個(gè)
3 之前有1個(gè)
1 之前有3個(gè)
5 之前有0個(gè)
所以逆序數(shù)就是1+3=4
怎么算逆序數(shù)？急~~~?。?！
可使用直接計(jì)數(shù)法，計(jì)算一個(gè)排列的逆序數(shù)的直接方法是逐個(gè)枚舉逆序，同時(shí)統(tǒng)計(jì)個(gè)數(shù)。
舉個(gè)例子：
標(biāo)準(zhǔn)列是1 2 3 4 5，那么 5 4 3 2 1 的逆序數(shù)算法：
看第二個(gè)，4之前有一個(gè)5，在標(biāo)準(zhǔn)列中5在4的后面，所以記1個(gè)。
類似的，第三個(gè) 3 之前有 4 5 都是在標(biāo)準(zhǔn)列中3的后面，所以記2個(gè)。
同樣的，2 之前有3個(gè)，1之前有4個(gè)，將這些數(shù)加起來就是逆序數(shù)=1+2+3+4=10。
擴(kuò)展資料：
其它算法：
1、歸并排序
歸并排序是將數(shù)列a[l,h]分成兩半a[l,mid]和a[mid+1,h]分別進(jìn)行歸并排序，然后再將這兩半合并起來。在合并的過程中（設(shè)l<=i<=mid，mid+1<=j<=h），當(dāng)a[i]<=a[j]時(shí)，并不產(chǎn)生逆序數(shù)；
當(dāng)a[i]>a[j]時(shí)，在前半部分中比a[i]大的數(shù)都比a[j]大，將a[j]放在a[i]前面的話，逆序數(shù)要加上mid+1-i。因此，可以在歸并排序中的合并過程中計(jì)算逆序數(shù)。
2、樹狀數(shù)組
由于樹狀數(shù)組的特性，求和是從當(dāng)前節(jié)點(diǎn)往前求，所以，這里要查詢插入當(dāng)前數(shù)值之時(shí)，要統(tǒng)計(jì)有多少個(gè)小于該數(shù)值的數(shù)還沒插入，這些沒插入的數(shù)，都會(huì)在后面插入，也就形成了逆序數(shù)。
參考資料來源：百度百科-逆序數(shù)
計(jì)算逆序數(shù)并指出奇偶性
是：n-1，n-2，……，2，1，n，是吧。如果是，那么：
n-1的逆序數(shù)=0
n-2的逆序數(shù)=1
…………
2的逆序數(shù)=n-3
1的逆序數(shù)=n-2
n的逆序數(shù)=0
t=0+1+...+(n-2)+0=(n-1)(n-2)/2
設(shè)k∈N*
n=4k-3時(shí)，t為偶數(shù)，排列為偶排列
n=4k-2時(shí)，t為偶數(shù)，排列為偶排列
n=4k-1時(shí)，t為奇數(shù)，排列為奇排列
n=4k時(shí)，t為奇數(shù)，排列為奇排列。
掃描二維碼推送至手機(jī)訪問。
版權(quán)聲明：本文由尚恩教育網(wǎng)發(fā)布，如需轉(zhuǎn)載請(qǐng)注明出處。
