第80次编程比赛（08第二学期开学第一炮）

主题：第80次编程比赛（08第二学期开学第一炮）

雨中飞燕 [专家分：18980] 发布于 2009-02-21 18:44:00

原79次冠军因长时间不再发帖子，故本次由本人开展

[color=0000FF]题目描述：[/color]
现在，有两个正整数A和B，例如A是345，B是478，现在，需要把B插入到A里，
而A有三位，所以有四个位置选择，所得结果分别是：
478345, 347845, 344785, 345478
我们通过对比可以知道，在这当中最小的一个是344785
这两个正整数长度不超过100000位，各个位均不包含数字0
现在的目标是，要找出插入后所能得到的最小的整数，输出这个整数

[color=0000FF]样例输入：[/color]
345 478
12345 678
12 21
12 23

[color=0000FF]样例输出：[/color]
344785
12345678
1212
1223

[color=0000FF]答题要求：[/color]
请完善以下代码(C/C++均可)：
[code=c]#include <stdio.h>
#define MAXLEN 100000

//todo: 在此增加你所需要的函数或者变量或者头文件

void deal(char* a, char* b, char* c)
{
    // todo: 在此补充你的处理代码
    // 参数说明: a和b是输入的字符串，c要保存输出结果
}

char a[MAXLEN+1], b[MAXLEN+1], c[MAXLEN*2+1];
int main(void)
{
    while (scanf("%s%s", a, b)!=EOF)
    {
        deal(a, b, c);
        puts(c);
    }
    return 0;
}[/code]

其它信息：
本次比赛以公开答题代码的形式，且附以及时的测试，允许直接在本帖子讨论算法
测试内容：正确性，时间效率，空间效率，代码可读性
本次比赛结束时间3月8日 23:00

[color=FF0000]在本帖子回复广告或比赛无关内容者立即封ID及IP[/color]

最后更新于：2009-02-22 11:57:00

本帖地址： http://bbs.pfan.cn/post/294273.html

回复列表（共182个回复）

51 楼

雨中飞燕 [专家分：18980] 发布于 2009-02-24 23:40:00

50楼的最后修改于2009-2-24 23:37:00的代码
在特殊情况下会死循环

52 楼

小鹏2009 [专家分：0] 发布于 2009-02-25 00:50:00

#include <stdio.h>
#include <string>
using namespace std;
#define MAXLEN 100000
void deal(char* a, char* b, char* c)
{
    string strA(a),strB(b),minStr(a),strTemp;
    minStr.insert(0,strB);
    for(int i=1;i<strA.length()+1;i++)
    {
        strTemp=strA;
        strTemp.insert(i,strB);
        if(minStr>strTemp)
            minStr=strTemp;
    }
    c=minStr.c_str();
}
char a[MAXLEN+1], b[MAXLEN+1], c[MAXLEN*2+1];
int main(void)
{
    while (scanf("%s%s", a, b)!=EOF)
    {
        deal(a, b, c);
        puts(c);
    }
    return 0;
}

53 楼

雨中飞燕 [专家分：18980] 发布于 2009-02-25 01:22:00

52楼的代码的评价见2楼

54 楼

aizibion [专家分：4780] 发布于 2009-02-25 13:19:00

燕姐帮忙看下45楼的有问题不的.我把例子都试了下,想不出还有其他情况了

55 楼

雨中飞燕 [专家分：18980] 发布于 2009-02-25 13:45:00

连编译都有错

56 楼

251316192 [专家分：0] 发布于 2009-02-25 14:22:00

#include <iostream>
#include <string>
using namespace std;

int main(void)
{
    string a, b, c;
    void deal(string & a, string & b, string & c);
    while (cin >> a >> b) {
        deal(a, b, c);
        cout << c << endl;
    }
    return 0;
}

void deal(string & a, string & b, string & c) {
    string min = a + b;
    string temp = a;
    for(string::size_type i = 0; i < a.size(); ++i) {
        temp.insert(i,b);
        if(min > temp)
            min = temp;
        temp = a;
    }
    c = min;
}

57 楼

雨中飞燕 [专家分：18980] 发布于 2009-02-25 15:33:00

除了正确性请多考虑效率

58 楼

zhaoyg [专家分：4790] 发布于 2009-02-25 15:40:00

不算。
有一个地方写错了

59 楼

frejo [专家分：0] 发布于 2009-02-25 16:03:00

貌似数b的各位数还是原来那状态，把数b插入到数a只需要考虑数b的第一位与数a的第一位相比看哪个小，如果数a第一位小，那么就要比较数b的第一位和数a的第二位，类推过去即可。个人认为例子中的排列过于简单化了。数b的各个位数应该随着插入数a而同时发生改变。比方说748345也是一种组合哈！

60 楼

雨中飞燕 [专家分：18980] 发布于 2009-02-25 16:23:00

59楼的，你可以写个代码试试看，到时你就知道简单不简单了，记得正确性和时空效率都要考虑

我来回复

您尚未登录，请登录后再回复。点此登录或注册

主题：第80次编程比赛（08第二学期开学第一炮）

回复列表（共182个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：第80次编程比赛（08第二学期开学第一炮）

回复列表 （共182个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共182个回复）