欢迎光临散文网 会员登陆 & 注册

《算法设计与分析》实验报告1

2022-08-04 09:49 作者:老师-忘记密码  | 我要投稿


算法设计与分析》实验报告1

 

实验名称: 统计一个排列中逆序对的个数

系    别:xxx           

    业:xxx           

    级:xxx

姓    名:xxx          

    号:xxx

实验日期:xxxxxx



1.  算法题目

统计一个排列中逆序对的个数

 

2.  设计思路与步骤

通过归并排序,在排序的过程中统计逆序的的个数。


3.  算法实现与代码

#include<stdio.h>

int num=0;

void Merge(int *A,int *B,int first,int m,int end);

void Inversion(int *A,int *B,int first,int end);

int main(){

int i,n;

int A[100];

int B[100];

printf("请输入要排序的个数;");

scanf("%d",&n);

for(i=1;i<=n;i++){

printf("请输入要排序的元素:\n");

scanf("%d",&A[i]);

}

Inversion(A,B,1,n);

for(i=1;i<=n;i++){

}

printf("逆序对个数为:%d",num);

}

void Inversion(int *A,int *B,int first,int end){

if(first<end){

int m, i;

m=(first+end)/2;

Inversion(A,B,first,m);

Inversion(A,B,m+1,end);

Merge(A,B,first,m,end);

for(i=first;i<=end;i++){

A[i]=B[i];

}

}

}

void Merge(int *A,int *B,int first,int m,int end){

int i=first;

int j=m+1;

int k=first;

while(i<=m&&j<=end){

if(A[i]<=A[j]){

B[k++]=A[i++];

}

else{

B[k++]=A[j++];

num+=m-i+1;

}

}

while(i<=m){

B[k++]=A[i++];

}

while(j<=end){

B[k++]=A[j++];

}

}

 

4.  测试用例与结果

 


5.  问题与总结:

答:xxx。


《算法设计与分析》实验报告1的评论 (共 条)

分享到微博请遵守国家法律