一 問題描述
設有n個正整數(n<=20)，將它們聯成一排，組成一個最大的多位數。程序輸入：n,程序輸出：n個數連接成的多位數。二 問題分析
可以將問題這樣變化一下：
比如我輸入的是 １２３ ２ ３3 １００6 １２這樣幾個數字
我先找出最大的數字的位數為四位，再將所有的數字變成四位數：
１２３０ ２０００ ３3００ １００6 １２００
然後進行排序
３3００ ２０００ １２３０ １２００ １００6
這樣將後面加上的０去掉的序列不就是最大數字嗎？
於是最大數字就是
３3２１２３１２１００6
因為以下程序用的INT的類型所以只在-32728~32727間有效，假如想要更大范圍須改成long類型
三 C程序
#define MAXSIZE 100
#include<stdio.h>
int max(int a[],int i) /*判定出最大數字的位數*/
{int m;
int size();
m=a[i];
for(;i>=0;i--)
if(a[i]>m)
m=a[i];
return(size(m));
}
int size(int interger) /*判定出這個要組合數字的位數*/
{
if(interger>10000)
return 5;
else if(interger>1000)
return 4;
else if(interger>100)
return 3;
else if(interger>10)
return 2;
else
return 1;
}
int change(int i ,int maxsize) /*將本數字變成和最大數相同位數的數字*/
{
int size();
switch(maxsize-size(i))
{case 0:break;
case 1:i=i*10;break;
case 2:i=i*100;break;
case 3:i=i*1000;break;
case 4:i=i*10000;break;
default:printf("error
");
}
return i;
}
main()
{
int a[MAXSIZE],b[MAXSIZE],i,j,count,temp,s;
printf("Please input some intergers and input -1 to finish
");
for(i=0;i<MAXSIZE;i++)
{
scanf("%d",&a[i]);
if(a[i]<0)
break;
}
count=i-1;
s=max(a,count);
for(i=count;i>=0;i--)
b[i]=change(a[i],s);
for(j=0;j<=count-1;j++) /*用冒泡法對變化數排序，其實本質是在對原組合數字進行排序*/
for(i=0;i<=count-1;i++)
{
if(b[i]<b[i+1])
{
temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;
temp=b[i];
b[i]=b[i+1];
b[i+1]=temp;
}
}
printf("max interger =");
for(i=0;i<=count;i++)
printf("%d",a[i]);
}
四 實驗結果
輸入:56 2 1 輸出:5621
輸入:21 35 2 輸出:35221
