[NOIp 1998 提高组]Probelm 2 连接多位数【2011百度实习生笔试题】

简介: /*====================================================================== [NOIp 1998 提高组]Probelm 2 连接多位数 总时间限制: 10000ms 内存限制: 65536kB 描述 设有n个正整数(n≤20),将它们联接成一排,组成一个最大的多位整数。
/*======================================================================
[NOIp 1998 提高组]Probelm 2 连接多位数
总时间限制: 10000ms 内存限制: 65536kB
描述
设有n个正整数(n≤20),将它们联接成一排,组成一个最大的多位整数。

例如:n=3时,3个整数13,312,343联接成的最大整数为:34331213

又如:n=4时,4个整数7,13,4,246联接成的最大整数为:7424613

输入
第一行:n
接下来的N行:n个数
输出
联接成的多位数
样例输入
3
13
312
343
样例输出
3433213


[问题分析]
举例说明正常的字符串比较缺陷!
如:A=’321’,B=’32’,按照标准的字符串比较规则因为A>B,
所以A+B > B+A ,而实际上’32132’< ’32321’。
所以,自定义一种字符串的比较规则:
即如果A+B>B+A,则我们认为A>B。且可以证明:如果A+B>=B+A,B+C>=C+B,则一定有:A+C>=C+A。(注意,这个地方的加号是字符串连接)
这样一来,程序就很简单了。
分3步,先把n个数字转换成字符串存储;
再按照自定义的规则把n个字符串排序;
最后按照从大到小的顺序输出这些字符串。

小结:有些问题看起来是数学问题,认真分析会发现用字符串处理很简单。
另外,一定要掌握有关字符串的各种函数,以免用到时自己编子程序。

注:这个题是2011百度实习生笔试题,上面的分析在百度文库“2011百度实习生笔试题”复制而来。
http://wenku.baidu.com/link?url=HmZNHTkL7rm2vnC4XZKs6Ero0_78Bp5hMtvHMHdkaJrRn_GcyBZLivk2sydEL2oC7msYRQ5U6ZbY4a6M3PJhJ5zCEJEXNacXziF-uexIzpq ========================================================================
*/
 1 #include<stdio.h>
 2 #include<string.h>
 3 int intToStr(int x,char a[]);//把十进制x转成字符串,存储在字符串a。返回0表示出错。返回1表示成功 
 4 int cmp(int x,int y);//把x和y当字符串,自定义一种字符串的比较规则,即如果x+y>y+x,则我们认为x>y。 
 5 int main()
 6 {
 7     int n,i,a[25],j,k,t;
 8     freopen("9.in","r",stdin);
 9     scanf("%d",&n);
10     for(i=0;i<n;i++)
11     {
12         scanf("%d",&a[i]);
13     }
14     //下面按自定义的规则对那n个数排序。从大到小排序 
15     for(i=0;i<n-1;i++)
16     {
17         k=i;
18         for(j=i+1;j<n;j++) //寻找a[i+1]~a[n-1]当中最小的元素并把它的下标记录到k里面。
19             if(cmp(a[j],a[k])>0)  //if(a[j]>a[k])
20                 k=j;
21         if(i!=k)
22         {
23             t=a[k];
24             a[k]=a[i];
25             a[i]=t;
26         }
27     }
28     //下面输出按自定义规则排序后的数字 
29     for(i=0;i<n;i++)
30     {
31         printf("%d",a[i]);
32     }
33     printf("\n");
34     return 0;
35 }
36 int cmp(int x,int y)//把x和y当字符串,自定义一种字符串的比较规则,即如果x+y>y+x,则我们认为x>y。
37 {
38     char a[30],b[30];
39     char ab[60],ba[60];
40     intToStr(x,a);
41     intToStr(y,b);
42     strcpy(ab,a);
43     strcat(ab,b);
44     strcpy(ba,b);
45     strcat(ba,a);
46     return strcmp(ab,ba);
47 }
48 int intToStr(int x,char a[])//把十进制非负整数x转成字符串,存储在字符串a。
49 {//返回0表示出错。返回1表示成功 
50     int i,len;
51     char t;
52     if(x<0)  return 0;
53     if(x==0)
54     {
55         a[0]='0';
56         a[1]='\0';
57         return 1;
58     }
59     else
60     {
61         i=0;
62         while(x>0)
63         {
64             a[i]=x%10+'0';
65             x=x/10;
66             i++;
67         }
68         a[i]='\0';
69         len=i;
70         for(i=0;i<len/2;i++)
71         {
72             t=a[i];
73             a[i]=a[len-1-i];
74             a[len-1-i]=t;
75         }
76         return 1;
77     }
78 }
//上面这个整数转字符串的函数其实函数库有相应的库函数。
/*
itoa         注意:这个不是C的标准函数,不是所有的编译器都支持的。
功 能:把一整数转换为字符串 
用 法:char *itoa(int value, char *string, int radix);
详细解释:itoa是英文integer to array(将int整型数转化为一个字符串,并将值保存在数组string中)的缩写.
参数: 
  value: 待转化的整数。 
  radix: 是基数的意思,即先将value转化为radix进制的数,范围介于2-36,比如10表示10进制,16表示16进制。 
  * string: 保存转换后得到的字符串。
返回值: 
  char * : 指向生成的字符串, 同*string。
备注:该函数的头文件是"stdlib.h"
*/

/*
C语言库函数名: atoi 
原型: int atoi(const char *nptr); 
功 能: 把字符串转换成整型数. 
名字来源:array to integer 的缩写. 
函数说明: atoi()会扫描参数nptr字符串,如果第一个字符不是数字也不是正负号返回零,
否则开始做类型转换,之后检测到非数字或结束符 \0 时停止转换,返回整型数。
*/ 

 

 

相关文章
|
1月前
|
算法 网络协议 NoSQL
百度后端笔试题知识点总结
百度后端笔试题知识点总结
38 0
|
11月前
|
小程序
百度2015年系统工程师笔试题:判断当前机器的大小端
百度2015年系统工程师笔试题:判断当前机器的大小端
48 0
|
小程序
百度2015年系统工程师笔试题
百度2015年系统工程师笔试题
|
编译器 程序员 C语言
程序的编译与链接(预处理详解)+百度面试笔试题+《高质量C/C++编程指南》笔试题
如果两者之间有任何空白存在,参数列表就会被解释为stuff的一部分。
77 0
|
存储 小程序
|
存储 小程序 编译器
一道百度经典的笔试题-大小端的判断
一道百度经典的笔试题-大小端的判断
一道百度经典的笔试题-大小端的判断
|
人工智能 算法 BI