posts - 18,  comments - 104,  trackbacks - 0

题目描述:设有n个正整数,将它们联接成一排,组成一个最小的多位整数。
程序输入:n个数程序输出:联接成的多位数
例如:n=2时,2个整数32,321连接成的最小整数为:32132,n=4时,4个整数55,31,312, 33 联接成的最小整数为:312313355
[题目要求]1. 给出伪代码即可,请给出对应的文字说明,并使用上面给出的例子试验你的算法。2. 给出算法的时间空间复杂度。3. 证明你的算法。(非常重要)


#include 
<vector>
#include 
<algorithm>
#include 
<cmath>
#include 
<string>
#include 
<iostream>
#include 
<iterator>
#include 
<sstream>
using namespace std;

struct Less
{
    
bool operator()(long i, long j)
    
{
        
static stringstream ss;
        ss.clear();
        ss
<<i<<" "<<j;
        
string stri,strj;
        ss
>>stri>>strj;
        
return (i*powl(10,strj.length())+j) < (j*powl(10,stri.length()) +i);
    }

}
;

int main()
{
    
long x[] = {565565655};
    sort(x, x
+3, Less());
    copy(x, x
+3, ostream_iterator<long>(cout));
}

证明:

假设: 排序后的 a0a1...an不是最小的,那么存在a0a1...ajai....an<a0a1...an,且ajai > aiaj.
那么交换ajai会使可以使a0a1...an更小,与假设a0a1...ajai....an<a0a1...an矛盾。

证明完毕。
posted on 2009-06-04 23:49 尹东斐 阅读(668) 评论(2)  编辑 收藏 引用

FeedBack:
# re: 连接数字
2009-10-15 00:21 | wulin
善始者实繁,克终者盖寡。 博主好久没写博客了啊。  回复  更多评论
  
# re: 连接数字
2009-10-15 10:51 | yindf
@wulin

哎~~最近比较忙呀,没空研究技术啦 。  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2009年6月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

常用链接

留言簿(4)

随笔档案

文章分类

文章档案

相册

好友博客

搜索

  •  

最新评论

阅读排行榜

评论排行榜