最大整数

Time Limit:1000MS Memory Limit:65536K
Total Submit:431 Accepted:115

Description

设有n个正整数（n≤20），将它们联接成一排，组成一个最大的多位整数。
例如：n=3时，3个整数13，312，343联接成的最大整数为：34331213
又如：n=4时，4个整数7，13，4，246联接成的最大整数为：7424613

Input

n
n个数

Output

联接成的多位数

Sample Input

3
13 312 343
4
7 13 4 246

Sample Output

34331213
7424613

把输入的n个数列成一个数组，然后按从"大"到"小"排列，最后数组顺序无空格输出
重点是比较“大”“小”,举几个例子在下面：

43 < 4 = 44 < 45 < 5

454 < 45 = 4545 < 455

有时间的代码一下

看他们楼下的

[此贴子已经被作者于2007-10-17 12:04:46编辑过]

ls没看懂题目

4个数
7 13 4 246

取它们的第一位数分别为 7 1 4 2
按从大到小排 7 4 2 1
所以答案就为 7 4 246 13

补充，如果最高位的相等就比低一位的。

用一个一维数组存储，在每组数间用一个标志分隔（flag），每次取标志后第一个数进行大小比较，如果第一个数等大，再去第二个比较，依次类推！
当比较有结果时，进行数据调整．如果一直未比较到大小则遇到标志后结束，并删去标志位．

能不能把你的思路说详细一点，我看不明白。谢谢！

感觉你的这个想法很可行，但我不会处理，你能详细说一下吗? 谢谢！

写了个程序，按照我在二楼的思路，实现了功能，效率方面没考虑过，自行优化吧。
像：最小公倍数、排序算法上改进，类接口上改进(加操作符重载、友元函数)

[CODE]#include <iostream>
using namespace std;

int sbs(int a, int b) // 最小公倍数
{
for (int i=max(a,b); ; ++i)
if (i%a==0 && i%b==0)
return i;
}

class Number
{
public:
Number(){}

void setvalue(int value)
{
for (int i=0; i<=9; ++i)
_val[i] = 0; //　先将 _val[10] 每位清0

int k = 10;
_value = value;
_n = 1;
while (value/k != 0)
{
++_n; // 求得 _value 的位数　_n
k *= 10;
}

k /= 10;
for (int i=0; i<= _n-1; ++i)
{
_val[i] = (value / k) % 10; // _value 的每位数"从左到右"存储在数组_val[10]里
k /= 10;
}
}
int getvalue()
{
return _value;
}
int getn()
{
return _n;
}
int getval(int n)
{
return _val[n]; //　得到第n位的数
}
private:
int _value;
int _n; //　_value 的位数
int _val[10]; // 各位数字存在数组里
};

bool isGreater(Number &a, Number &b)
{
for (int i=0; i<=sbs(a.getn(),b.getn())-1; ++i) // 最大比较次数为a、b位数的最小公倍数
{
if (a.getval(i%a.getn()) > b.getval(i%b.getn())) // 循环比较
return true;
else if(a.getval(i%a.getn()) < b.getval(i%b.getn()))
return false;
}
return false;
}

int main()
{
int n;
cout << "input numers: " << endl;
cin >> n;
getchar();

int a;
Number b[n];
for (int i=0; i<=n-1; ++i)
{
cin >> a;
b[i].setvalue(a);
}
cout << endl;

for (int i=n-1; i>=1; --i) // 排序
for (int j=1; j<=i; ++j)
{
if (isGreater(b[j], b[j-1]))
{
int temp = b[j].getvalue();
b[j].setvalue(b[j-1].getvalue());
b[j-1].setvalue(temp);
}
}

for (int i=0; i<=n-1; ++i)
{
cout << b[i].getvalue();
}
cout << endl;
return 0;
}
[/CODE]

[此贴子已经被作者于2007-10-13 10:55:07编辑过]