線代：求解排列中的逆序數(shù)

• 這一系列的工程數(shù)學(xué)教程面向的是已經(jīng)掌握C語言編程基礎(chǔ)讀者

我們知道所謂逆序數(shù)就是求出一個(gè)數(shù)組中的每一項(xiàng)的之前的若干項(xiàng)中有多少項(xiàng)比它大，就叫做逆序數(shù)，把所有項(xiàng)的逆序數(shù)的加起來就是這個(gè)排列的逆序數(shù)。逆序數(shù)在排列中運(yùn)用廣泛。

舉例：比如 3,5,1,4,7,2,6這個(gè)數(shù)列中

3 在首位所以逆序數(shù)是0

5 之前的3比5小，所以逆序數(shù)也是0

1 之前有3和5都比它大，所以逆序數(shù)是2

以此類推

4 的逆序數(shù)是1

7 的逆序數(shù)是0

2 的逆序數(shù)是4

6 的逆序數(shù)是1

所以這個(gè)排列的逆序數(shù)是0+0+2+1+0+4+1=8

C語言實(shí)現(xiàn)：

//這是實(shí)現(xiàn)逆序數(shù)的程序
#include<stdio.h>

int main()
{
    int i,j,a[10],ni,nisum=0;
    printf("請(qǐng)輸入由一個(gè)十個(gè)整數(shù)元素組成排序:\n");    
    for(i=0;i<10;i++)
    {
        printf("第%d個(gè)元素:",i+1);
        scanf("%d",&a[i]);
        printf("\n");
    }
    printf("逆序數(shù)為 0");
    for(i=1;i<10;i++)
    {
        ni=0;
        for(j=0;j<i;j++)
        {
            if(a[i]<a[j])
            {
                ni++;
            }
        }
        printf("+%d",ni);
        nisum=nisum+ni;
    }
    printf("=%d\n",nisum);
    return 0;
}

C語言程序的精簡形式(和上面一樣，只是刪除了一些啰嗦的內(nèi)容)

#include<stdio.h>
main()
{
    int i,j,a[10],ni,nisum=0;
    printf("請(qǐng)輸入由一個(gè)十個(gè)整數(shù)元素組成排序:\n");    
    for(i=0;i<10;i++)
    {
        printf("第%d個(gè)元素:",i+1);
        scanf("%d",&a[i]);
        printf("\n");
    }
    printf("逆序數(shù)為 0");
    for(i=1;i<10;i++)
    {
        ni=0;
        for(j=0;j<i;j++)
            if(a[i]<a[j])
                ni++;
        printf("+%d",ni);
        nisum+=ni;
    }
    printf("=%d\n",nisum);
}

更精簡但是不推薦的形式：

#include<stdio.h>
main()
{
    int i,j,a[10],ni,nisum=0;
    printf("請(qǐng)輸入由一個(gè)十個(gè)整數(shù)元素組成排序:\n");    
    for(i=0;i<10;i++)
    {
        printf("第%d個(gè)元素:",i+1);
        scanf("%d",&a[i]);
        printf("\n");
    }
    printf("逆序數(shù)為 0");
    for(i=1;i<10;i++)
    {
        ni=0;
        for(j=0;j<i;a[i]<a[j]?ni++:0,j++);
        printf("+%d",ni);
        nisum+=ni;
    }
    printf("=%d\n",nisum);
}

參考文獻(xiàn):

1. 同濟(jì)大學(xué)數(shù)學(xué)系 工程數(shù)學(xué)—線性代數(shù) 北京:高等教育出版社 2007