线代:求解排列中的逆序数

发布时间:2020-05-10 02:27:04 作者:宅祺祺
来源:网络 阅读:1107


我们知道所谓逆序数就是求出一个数组中的每一项的之前的若干项中有多少项比它大,就叫做逆序数,把所有项的逆序数的加起来就是这个排列的逆序数。逆序数在排列中运用广泛。


举例:比如 3,5,1,4,7,2,6这个数列中

3 在首位所以逆序数是0

5 之前的3比5小,所以逆序数也是0

1 之前有3和5都比它大,所以逆序数是2

以此类推

4 的逆序数是1

7 的逆序数是0

2 的逆序数是4

6 的逆序数是1

所以这个排列的逆序数是0+0+2+1+0+4+1=8


C语言实现:

//这是实现逆序数的程序
#include<stdio.h>

int main()
{
    int i,j,a[10],ni,nisum=0;
    printf("请输入由一个十个整数元素组成排序:\n");    
    for(i=0;i<10;i++)
    {
        printf("第%d个元素:",i+1);
        scanf("%d",&a[i]);
        printf("\n");
    }
    printf("逆序数为 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语言程序的精简形式(和上面一样,只是删除了一些啰嗦的内容)

#include<stdio.h>
main()
{
    int i,j,a[10],ni,nisum=0;
    printf("请输入由一个十个整数元素组成排序:\n");    
    for(i=0;i<10;i++)
    {
        printf("第%d个元素:",i+1);
        scanf("%d",&a[i]);
        printf("\n");
    }
    printf("逆序数为 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("请输入由一个十个整数元素组成排序:\n");    
    for(i=0;i<10;i++)
    {
        printf("第%d个元素:",i+1);
        scanf("%d",&a[i]);
        printf("\n");
    }
    printf("逆序数为 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);
}

参考文献:

  1. 同济大学数学系 工程数学—线性代数 北京:高等教育出版社 2007

推荐阅读:
  1. nagios故障,求解?
  2. 枚举排列

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

c语言 程序 读者

上一篇:jQuery实现简单的手风琴效果

下一篇:Step by Step!Kubernetes持续部署指南

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》