程序基本算法习题解析 设有n个正整数，将它们连成一排，组成一个最大的多位整数。要求输入n个正整数后，输出连成的最大整数。

整数，将它们连成一排，组成一个最大的多位整数。要求输入n个正整数后，输出连成的最大整数。"/>

程序基本算法习题解析 设有n个正整数，将它们连成一排，组成一个最大的多位整数。要求输入n个正整数后，输出连成的最大整数。

例如n=3时，3个整数13,312,343连成的最大整数为34331213；又如n=4时，4个整数7,13,4,246连成的最大整数为7424613.

思路：

采用贪心策略，先把整数转换为字符串，然后再比较a+b和b+a。如果a+b>b+a，就把a排在b前面，反之把a排在b后面。

程序如下：

// Chapter9_2.cpp : Defines the entry point for the application.
// 设有n个正整数，将它们连成一排，组成一个最大的多位整数。
// 例如n=3时，3个整数13,312,343连成的最大整数为34331213；
// 又如n=4时，4个整数7,13,4,246连成的最大整数为7424613.
// 要求输入n个正整数后，输出连成的最大整数。#include "stdafx.h"
#include<iostream>
#include<string>
#include<sstream>
using namespace std;int main()
{int N,i,j;//输入整数个数和其值cout << "input N: ";cin >> N;int *num = new int[N]; //int类型数组string *strNum = new string[N]; //char类型数组cout << "input the numbers: ";for(i=0;i<N;i++)cin >> num[i];//将输入的int型数据转换为字符串for(i=0;i<N;i++){stringstream ss; //用于将int类型转换为string类型ss << num[i];ss >> strNum[i];}//组合（将组合起来较大的数调到前面去）for(i=0;i<N-1;i++)for(j=i+1;j<N;j++){//如果组合起来较大的数在后面，则交换两数的位置if(strNum[i]+strNum[j] < strNum[j]+strNum[i]){string temp;temp = strNum[j];strNum[j] = strNum[i];strNum[i] = temp;}}cout << "最大整数为：" << endl;for(i=0;i<N;i++)cout << strNum[i];cout << endl;delete []num;delete []strNum;system("pause");return 0;
}

运行结果如下：