怎么用C语言实现:设有n个正整数,将它们连接成一排,组成一个最大的多位整数。 例如:n=3时,3个整数13,312,343,连成的最大整数为34331213。 又如:n=4时,4个整数7,13,4,246,连成的最大整数为7424613。
时间: 2024-05-03 21:20:39 浏览: 16
这道问题可以考虑使用字符串的排序来实现。将输入的n个正整数全部转换成字符串,然后将这些字符串按照字典序进行排序,最后将排序后的字符串进行拼接即可得到组成的最大整数。
C语言的代码实现如下:
```c
#include <stdio.h>
#include <string.h>
#define MAXN 100
char num[MAXN][MAXN]; // 存储输入的数
int cmp(char* a, char* b) {
char tmp1[MAXN * 2], tmp2[MAXN * 2];
strcpy(tmp1, a);
strcat(tmp1, b);
strcpy(tmp2, b);
strcat(tmp2, a);
return strcmp(tmp2, tmp1);
}
int main() {
int n, i, j;
printf("请输入n的值:");
scanf("%d", &n);
printf("请输入%d个正整数:\n", n);
for (i = 0; i < n; i++) {
scanf("%s", num[i]);
}
// 用冒泡排序按照 cmp 规则排序
for (i = 0; i < n - 1; i++) {
for (j = i + 1; j < n; j++) {
if (cmp(num[i], num[j]) < 0) {
char tmp[MAXN];
strcpy(tmp, num[i]);
strcpy(num[i], num[j]);
strcpy(num[j], tmp);
}
}
}
printf("组成的最大整数为:\n");
for (i = 0; i < n; i++) {
printf("%s", num[i]);
}
return 0;
}
```
注意:这个算法的时间复杂度为O(n^2),如果n很大,可能会超时。实际上,这个问题还有更好的时间复杂度为O(nlogn)的实现方法,即使用快排或归并排序,具体实现可以自行探究。