题目描述:
设有n个正整数,将它们联接成一排,组成一个最小的多位整数。
例如:
n=2时,2个整数32,321连接成的最小整数为:32132,
n=4时,4个整数55,31,312, 33 联接成的最小整数为:312313355
分析:
其实这题就是将这些整数以字符串方式排序,整数的第一位越小,其越靠前;若第一位相同则同理比较第二位。依次类推,直至能确定其顺序。当其中一个数是另一个数的部分时,如32(记为A)和321(记为B),则比较B(321)与B的剩余位(1)与A的连接(即132)的大小。
代码如下:
#include<iostream> using namespace std; struct Node { char str[11]; Node* next; }; int Compare(const char* str1,const char* str2) { char c1=str1[0],c2=str2[0]; int i=1; while(c1==c2) { c1=str1[i]; c2=str2[i]; if(c1=='\0') { if(c2=='\0') return 0; char temp[10]; strcpy(temp,str2+i); strcat(temp,str1); return Compare(str2,temp); } if(c2=='\0') { char temp[10]; strcpy(temp,str1+i); strcat(temp,str2); return Compare(temp,str1); } i++; } return c1-c2; } void main() { int n,arr[100],i; cout<<"请输入要输整数的个数:"; cin>>n; for(i=0;i<n;i++) { cout<<"请输入第 "<<(i+1)<<" 个整数:"; cin>>arr[i]; } //排序 Node *head=new Node; Node *p=new Node; head->next=p; p->next=NULL; itoa(arr[0],p->str,10); Node *newNode; bool isEnd; for(i=1;i<n;i++) { //生成新节点 newNode=new Node; itoa(arr[i],newNode->str,10); newNode->next=NULL; //插入节点 p=head; isEnd=false; while(Compare(newNode->str,p->next->str)>=0) { if(p->next->next==NULL) { isEnd=true; break; } p=p->next; } if(isEnd) p->next->next=newNode; else { newNode->next=p->next; p->next=newNode; } } cout<<"有上述整数连接成的最小整数是:"; p=head->next; while(p!=NULL) { cout<<p->str<<" "; p=p->next; } cout<<endl; }