主题：第42次编程比赛第二题
argentmoon [专家分：13260] 发布于 2006-09-22 12:48:00
[center]数字最少交换次数[/center]
第二题还是求最少次数，但问题描述却不一样了。
请问一个无序的数列按从小到大的序排好最少需要交换多少次数字才可以达到目的？
函数接口：
int Least(int a[], int n);
//a数组里面存有n个数，从a[0] ～ a[n – 1]，无序。
//函数返回最少交换次数
注：数据中不存在相同的数字，但数字有可能是负数。
注二：[color=FF0000]最少交换次数[/color]肯定存在，不因排序算法不同改变。
n<=10,000,000,内存限制100M.
示例
int a[] = {14, 7, 2, 0}
交换14和0, 交换7和2，数组就排好了序，所以最少交换次数是2.
回复列表 （共14个回复）
11 楼
黄金风格 [专家分：4050] 发布于 2006-09-24 19:46:00
#include<stdio.h>
#include<stdlib.h>
#define MAX_SIZE 100000
int Is_Index_Correct(int a[],int n,int index)
{
int t,m;
m=index;
for(int i=index+1;i<n;i++)
{
if(a[i]<a[m]) m=i;
}
if(m!=index)
{
t=a[index];
a[index]=a[m];
a[m]=t;
return 0;
}
return 1;
}
int Least(int a[], int n)
{
int Change_Time=0;
for(int i=0;i<n-1;i++)
{
if(Is_Index_Correct(a,n,i)==0)
Change_Time++;
}
return Change_Time;
}
int main()
{
int a[MAX_SIZE]={14, 7, 2, 0};
printf("%d\n",Least(a,4));
return 0;
}
12 楼
zww219 [专家分：0] 发布于 2006-09-24 21:32:00
内存限制是什么意思？？新手提问~~`
13 楼
xyhx [专家分：0] 发布于 2006-09-24 21:47:00
int Least(int a[], int n)
{
int i,j,k,count=0;
int key;
for(i=0;i<n-1;i++)
{
k=i;
for(j=i+1;j<n;j++)
if(a[k]>a[j])
k=j;
if(k!=i)
{
key=a[i];
a[i]=a[k];
a[k]=key;
count++;
}
}
return count;
14 楼
tiancai007 [专家分：0] 发布于 2006-09-24 23:32:00
不知道 当 n 的类型是int 的时候 n 如何= 10，000，000
总之 先交上我的程序。
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
int Least(int a[],int n)
{
int b[100000];
int c[100000];
int d[100000];
int data[100000];
int i ;
int tran;
int point = 0;
for( ;i < n; i++)
{
b[i] = i;
c[i] = i;
d[i] = i;
data[i] = a[i];
}
quicksort(a,0,n-1,b,c);
for( i = 0; i<n ;i++)
{
if( b[c[i]] == i)
{
continue;
}
else
{
tran = data[i];
data[i] = data[b[c[i]]];
data[b[c[i]]] = data[i];
b[d[i]] = b[c[i]];
d[b[c[i]]] = d[i];
point++;
}
}
return(point);
}
void quicksort(int a[], int low, int high,int b[],int c[])
{
int i,pivot,j,cp;
if( low < high )
{
pivot = a[low];
cp = c[low];
i = low; j = high;
while(i<j)
{
while(i<j&&c[j]>=pivot) j--;
if(i<j)
{
a[i] = a[j];
c[i] = c[j];
//b[c[i]] = i;
i++;
}
while(i<j&& c[i]<=pivot)i++;
if(i<j)
{
a[j] = a[i];
c[j] = c[i];
//b[c[j]] = j;
j--;
}
}
a[i] = pivot;
c[i] = cp;
//b[c[i]] = i;
quicksort(a,low,i-1,b,c);
quicksort(a,i+1,high, b,c);
}
}
我来回复
您所在位置：