这个题目怎么做 - 编程论坛

#2

远去的列车2007-10-11 15:24

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

43 < 4 = 44 < 45 < 5

454 < 45 = 4545 < 455

有时间的代码一下

#3

忘记喧嚣2007-10-11 22:51

看他们楼下的

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

#4

aipb20072007-10-11 23:15

ls没看懂题目

#5

kisscjy2007-10-11 23:46

4个数
7 13 4 246

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

#6

zkkpkk2007-10-12 18:54

以下是引用kisscjy在2007-10-11 23:46:12的发言：
4个数
7 13 4 246

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

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

#7

风动2007-10-12 19:25

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

#8

神雕大侠2007-10-13 09:14

回复：（远去的列车）把输入的n个数列成一个数组，然后...

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

#9

神雕大侠2007-10-13 09:16

回复：（风动）用一个一维数组存储，在每组数间用一个...

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

#10

远去的列车2007-10-13 10:42

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

[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编辑过]

#11

wdtk2007-10-13 13:53

给个简单的思路:
1.把要重组的n个数字放入vector 中,最好以string 存储,
2.比较每个数的第一个"字符",
3.重组.

#12

风动2007-10-15 22:18

建议使用二维数组比较方便！行用于存一串字符，每列存一个字符．比较时用快排，或基数排，当然冒泡也行！

#13

HJin2007-10-16 01:39

don't know why my code cannot pass the online judge at the website

/*---------------------------------------------------------------------------
File name: 最大的多位整数.c
Author: HJin (email: fish_sea_bird [at] yahoo [dot] com )
Created on: 10/15/2007 09:39:25
Environment: WinXPSP2 En Pro + VS2005 v8.0.50727.762

Problem statement:
---------------------------------------------------------------------------
http://mail.bashu.cn:8080/JudgeOnline/showproblem?problem_id=1276

【1998年提高组2】最大的多位整数

Time Limit:1000MS Memory Limit:65536K
Total Submit:88 Accepted:46

Description

设有n个正整数,将他们连接成一排,组成一个最大的多位整数.
例如: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
1 2 3 4
4
7 13 4 246
3
9 98 987
3
9 8 0
2
0000000000001 002

Sample Output

34331213

Source

xinyue
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N 100000
char s[N];
char a[10000][N];

int cmp(const void* a, const void* b)
{
char *sa = (char*)a, *sb = (char*)b;
int na =strlen(sa), nb = strlen(b), i, n;

n = na<nb ? na : nb;
for(i=0; i<n; ++i)
{
if(sa[i]<sb[i])
{
return 1;
}
if(sa[i]>sb[i])
{
return -1;
}
}

return na-nb;
}

int main()
{
int n, i, j;

while(scanf("%d", &n)!=EOF)
{
getchar();

for(i=0; i<n; ++i)
{
scanf("%s", s);

j=0;
while(s[j]=='0')
++j;

strcpy(a[i], s+j);
}

qsort(a, n, N, cmp);

for(i=0; i<n; ++i)
printf("%s", a[i]);
printf("\n");
}

return 0;
}

#14

HJin2007-10-16 01:58

found the bug:

try

2
135 13

I am sure you can modify my program and remove the bug in "cmp".

#15

神雕大侠2007-10-16 12:46

回复：（远去的列车）写了个程序，按照我在二楼的思路...

我们还没有学过类，现在还不会用，你能不能不用类写一个。谢谢！

#16

远去的列车2007-10-16 13:10

回复：（HJin）found the bug:try2135 13I am sure yo...

最大比较次数n并不是最大的位数，而是两个位数的最小公倍数

13 131 n1=2,n2=3, n=6, 实际比较4次就出结果
44 444 n1=2,n2=3, n=6, 实际比较6次才出结果

#17

远去的列车2007-10-16 13:11

回复：（神雕大侠）回复：（远去的列车）写了个程序，...

那按照Hjin的程序改改就行了

#18

hhei2007-10-16 13:12

10楼这位兄弟好自信，这个程序编译都没通过。在main（）函数中，Number b[n] 这个数组声明有问题。。汗......

#19

远去的列车2007-10-16 13:26

回复：（hhei）10楼这位兄弟好自信，这个程序编译都没...

请问你用什么编译器？

#20

dart2007-10-16 13:35

应该很好做得，呵呵/////

#21

远去的列车2007-10-16 13:35

回复：（hhei）10楼这位兄弟好自信，这个程序编译都没...

我倒是发现你在论坛上写的程序
void main()
{...}
在我的编译器上通不过哦!!

#22

nuciewth2007-10-16 14:38

想到个方法,看行不行.
用字符串输入,然后直接做排序.
最后按照排序的结果最连接.
OK了.

#23

hhei2007-10-16 14:42

程序我删除了，因为我发现它有问题，
这个题目也不好做，我不会做，因为有个情况是：
一个数鼻梁外两个数大，但是他如果排在另外帘个数前面的话，数字不是最大的，比如：
746 7 48
746 比7和48 大，但连起来，746748 < 748746

[此贴子已经被作者于2007-10-16 15:27:23编辑过]

#24

nuciewth2007-10-16 14:44

#include<stdio.h>
#include<string.h>
int main()
{
char str[20][10];
int n;
while(eOf!=(scanf("%d",&n)))
{
for(int i=0;i<n;i++)
{
scanf("%s",str[i]);
}
Sort(a,n);
for(int i=0;i<n;i++)
{
printf("%s",str[i]);
}
printf("\n");
}
return 0;
}

//排序部分很容易写的.

#25

hhei2007-10-16 14:45

回复：（远去的列车）回复：（hhei）10楼这位兄弟好自...

是哪个程序啊，能不能把详细的程序贴出来，我用的是c++.net，每个程序都是我编译执行成功后才贴上来的。

#26

nuciewth2007-10-16 14:45

Sort(str,n);

#27

远去的列车2007-10-16 14:50

Enter n:
2
Enter the 2numbers of value:
13 131
At the first the line is:
13131
After that,then it is:
13113
请按任意键继续. . .

你的程序运行结果，请问 13131 < 13113 吗？
比较有问题，看懂题意再写
在2楼我就说了

#28

远去的列车2007-10-16 14:53

以下是引用hhei在2007-10-16 14:45:39的发言：
是哪个程序啊，能不能把详细的程序贴出来，我用的是c++.net，每个程序都是我编译执行成功后才贴上来的。

10楼的程序用DEV C++、MinGW Developer Studio都验证过，难道我不会试试就发上来吗？

#29

nuciewth2007-10-16 15:17

看来这个排序函数要修改一点.
短的反而要大.

#30

zkkpkk2007-10-25 11:22

以下是引用hhei在2007-10-16 14:42:41的发言：

程序我删除了，因为我发现它有问题，
这个题目也不好做，我不会做，因为有个情况是：
一个数鼻梁外两个数大，但是他如果排在另外帘个数前面的话，数字不是最大的，比如：
746 7 48
746 比7和48 大，但连起来，746748 < 748746

7 746 48，是最大的，越短的越优先考虑吧