暂时只想到"全排列"的方法,列出所有的排列,计算其距离平方和,找到最大值.
会出现很多的重复值,效率不高.
测试结果:
请输入总数量n: 4
请输入4个数字:1 3 7 10
1 3 7 10 (第1项)sum=110
1 3 10 7 (第2项)sum=98
1 7 3 10 (第3项)sum=182
1 7 10 3 (第4项)sum=98
......
最大值是 182
序列是: 1 7 3 10
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 100
int g_data[MAX_N];
int g_maxArray[MAX_N];
int g_N;
int g_max;
int g_count;
int cmp(const void *c,const void *d)
{
return *(int*)c-*(int*)d;
}
//顺序互换
void Reverse(int m,int n)
{
int temp;
while (m<n)
{
temp=g_data[m];
g_data[m]=g_data[n];
g_data[n]=temp;
m++;
n--;
}
}
//求N的阶乘，即全排列的个数
int fact()
{
int count=1,i=2;
while (i<=g_N)
{
count*=i;
i++;
}
return count;
}
//输出数列
void Output()
{
int i;
int diff;
int sum=0;
for (i=0;i<g_N;i++)
{
printf("%4d",g_data[i]);
diff=g_data[(i+1) % g_N]-g_data[i % g_N];
sum=sum+diff*diff;
}
g_count++;
printf(" (第%d项)sum=%d\n",g_count,sum);
if(sum>g_max)
{
g_max=sum;
for (i=0;i<g_N;i++)
{
g_maxArray[i]=g_data[i];
}
}
}
//全排列
void Fun()
{
int index1,index2;
int i,k,min,n,temp;
g_max=-1;
g_count=0;
Output();
n=fact();//n等于g_N的阶乘
//n次循环
for (k=1;k<n;k++)
{
//求index1下标
for (index1=g_N-2;index1>=0;index1--)
{
if (g_data[index1]<g_data[index1+1])
{
break;
}
}
min=32767; //暂定最小值
//求index2
for (i=index1+1 ; i<g_N ; i++)
{
if (g_data[i]>g_data[index1])
{
if (g_data[i]<min)
{
min=g_data[i];
index2=i;
}
}
}
//交换g_data[index1],g_data[index2]
temp=g_data[index1];
g_data[index1]=g_data[index2];
g_data[index2]=temp;
//逆置g_data[index1]到g_data[g_N-1]的数
Reverse(index1+1,g_N-1);
//输出
Output();
}
}
int main()
{
int i;
printf("请输入总数量n: ");
scanf("%d",&g_N);
printf("请输入%d个数字: ",g_N);
for (i=0;i<g_N;i++)
{
scanf("%d",&g_data[i]);
}
//先将g_N个数排序
qsort(g_data,g_N,sizeof(g_data[0]),cmp);
Fun();
printf("最大值是 %d\n",g_max);
printf("序列是: ");
for (i=0;i<g_N;i++)
{
printf("%d ",g_maxArray[i]);
}
printf("\n");
return 0;
}