关于逆序数的程序 大神来帮小弟我改改吧 异常太多小弟我实在是改不完了
关于逆序数的程序 大神来帮我改改吧 错误太多我实在是改不完了
倒是没有语法上的错误 只是运行起来结果不对
有关于逆序数 1234的逆序数=0 1324逆序数=1 反正就是后一位的数和前面的比较
2 4 3 1 5 4之前有0个 3之前有1个 1之前有3个 5之前有0个所以逆序数就是1+3=4
然后我的程序是要输入十个数 然后输出他们各自的逆序数
下面是一直改不好的程序
------解决方案--------------------
倒是没有语法上的错误 只是运行起来结果不对
有关于逆序数 1234的逆序数=0 1324逆序数=1 反正就是后一位的数和前面的比较
2 4 3 1 5 4之前有0个 3之前有1个 1之前有3个 5之前有0个所以逆序数就是1+3=4
然后我的程序是要输入十个数 然后输出他们各自的逆序数
下面是一直改不好的程序
#include<stdio.h>
#define N 10
int main()
{
int a[N],c,*p,e,i,f,d[N][4],j,h;
c=0;f=0;
p=&a[0]; //p=a一样
printf("请定义十个数(每个数的值限制在10000以内):");
for(i=0;i<10;i++)
scanf("%d",&a[i]);
for(i=0;i<=9;i++) //整体的十个数进入总循环体
{
c=*p/10;
if(c=1)
{ j=1;
printf("\na=%d,逆序数=0",*p);}
else
{
for(j=1;c!=0;j++)
{c/=10; //确定位数
f=*p%10;
d[i][j]=f;} //第几个数的第几位是多少用二维数组储存
for(j=0;j<4;j++)
if(d[i][j]>d[i][j+1])
h=h;
else
h++;
printf("\na=%d,逆序数=%d",*p,h);
*p++;}
}
return(0);
}
------解决方案--------------------
// o(nlogn) 逆序数
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int Calc(int* a, int* b, int first, int last) {
if(first >= last) return 0; // 一个元素的情况下没有逆序数
int i,j,k=0,mid,res=0;
k=i=first;
mid=(first+last)/2;
j=mid+1;
res=Calc(a,b,i,mid)+Calc(a,b,j,last); // 递归计算两边的逆序数
// 计算两边相关联的数据的逆序数
while((i<=mid) && (j<=last)) {
if(a[i]<a[j]) b[k++]=a[i++],res+=j-mid-1;
else b[k++]=a[j++]; // 是不是没有考虑a[i]=a[j]的问题
}
while(i<=mid) b[k++]=a[i++],res+=j-mid-1;
while(j<=last) b[k++]=a[j++];