第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个回复）

61 楼

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

void deal(char* a, char* b, char* c)
{
    char *d, *e, *f;
    int length;

    f = c;

    while (*f != '\0')
    {
        *f++ = '\0';
    }
    f = c;

    while ((*a != '\0') && (*b != '\0'))
    {
        if (*a > *b)
        {
            *f++ = *b++;
        }
        else if (*b > *a)
        {
            *f++ = *a++;
        }
        else
        {
            //相等时的处理
            d = a;
            e = b;
            length = 1;

            while (1)
            {
                //记录比较的次数
                length++;

                d++;
                e++;

                if ((*d == '\0') && (*e == '\0'))
                {
                    break;
                }

                if (*d == '\0')
                {
                    d = a;
                }
                if (*e == '\0')
                {
                    e = b;
                }

                if (*d > *e)
                {
                    while ((*b != '\0') && (length > 0))
                    {
                        *f++ = *b++;
                        length--;
                    }
                    break;
                }
                else if (*e > *d)
                {
                    while ((*a != '\0') && (length > 0))
                    {
                        *f++ = *a++;
                        length--;
                    }
                    break;
                }
            }

            if ((*d == '\0') && (*e == '\0'))
            {
                //a和b如何顺序插入，大小一致
                while (*a != '\0')
                {
                    *f++ = *a++;
                }

                while (*b != '\0')
                {
                    *f++ = *b++;
                }

                //此句不可省略
                *f = '\0';
            }
        }
    }

    if ((*a == '\0') && (*b != '\0'))
    {
        strcat(c,b);
    }

    else if ((*b == '\0') && (*a != '\0'))
    {
        strcat(c, a);
    }

}

62 楼

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

保险起见，在程序头增加一步将C全部清零的程序

    f = c;

    while (*f != '\0')
    {
        *f++ = '\0';
    }
    f = c;

63 楼

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

[quote]连编译都有错[/quote]
不会吧。。。我都测试了很多组数了。。。

64 楼

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

连false都拼写错误能编译通过？？

61楼的连123 123结果都错了啊
下次请发完整的代码吧

65 楼

bai_wx [专家分：0] 发布于 2009-02-25 17:48:00

投机取巧要不得，呜呜呜

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

#define MAXLEN 10000

void deal(char* a, char* b, char* c)
{
    char *d, *e, *f;

    f = c;

    while (*f != '\0')
    {
        *f++ = '\0';
    }
    f = c;

    while ((*a != '\0') && (*b != '\0'))
    {
        if (*a > *b)
        {
            *f++ = *b++;
        }
        else if (*b > *a)
        {
            *f++ = *a++;
        }
        else
        {
            //相等时的处理
            d = a;
            e = b;

            while (1)
            {
                //记录比较的次数
                d++;
                e++;

                if ((*d == '\0') && (*e == '\0'))
                {
                    *f++ = *a++;
                    break;
                }

                if (*d == '\0')
                {
                    d = a;
                }
                if (*e == '\0')
                {
                    e = b;
                }

                if (*d > *e)
                {
                    *f++ = *b++;
                    break;
                }
                else if (*e > *d)
                {
                    *f++ = *a++;
                    break;
                }
            }

        }
    }

    if ((*a == '\0') && (*b != '\0'))
    {
        strcat(c,b);
    }

    else if ((*b == '\0') && (*a != '\0'))
    {
        strcat(c, a);
    }

}

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;
}

66 楼

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

[quote]连false都拼写错误能编译通过？？

61楼的连123 123结果都错了啊
下次请发完整的代码吧[/quote]

大姐,昨天就发现了,当时因为直接在帖子上修改的,后来回家复制编译发现了就修改了,汗...

67 楼

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

确实是,浪费燕姐时间非常抱歉了,昨天改了没改上帖子,重来过~

确信不的笔误
....

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

#define MAXLEN 100000

//todo: 在此增加你所需要的函数或者变量或者头文件
char* pos_where(char* p ,char* q,char* count);

bool pos_again(char* p,char* q,char* count);

bool check_valid(char* p);

static bool s_bIndex = false;
static char* tag = NULL;
static bool flag = false;

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

    memset(c,0,MAXLEN*2+1);

    assert(a && b && c);
    char* pos = pos_where(a,b,NULL);

    strncpy(c,a,pos-a);
    strcpy(c+(pos-a),b);
    strcpy(c+strlen(c),pos);

    memset(a,0,MAXLEN+1);
    memset(b,0,MAXLEN+1);
    s_bIndex = false;
    tag = NULL;
    flag=false;
}

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

bool check_valid(char* p)
{
    assert(p);
    while (*p != '\0')
    {
        if ( *p>'9' || *p<'0' )
        {
            return false;
        }
        p++;
    }
    return true;
}

char* pos_where(char* p ,char* q,char* count)
{
    if (*p=='\0')
    {
        if (!s_bIndex)
        {
            return p;
        }

        if (!pos_again(p,q,count))
        {
            return count;
        }
        else
        {
            return p;
        }
    }

    if (*p>*q)
    {
        if (!s_bIndex)
        {
            return p;
        }
        if (!pos_again(p,q,count))
        {
            return count;
        }
        else
        {
            return p;
        }
    }
    else if (*p<*q)
    {
        return pos_where(++p,q,count);
    }
    else if (*p==*q)
    {
        if (!s_bIndex)
        {
            count = p;
            tag = p;
            s_bIndex = true;
        }

        else if (p-tag!=1&&flag!=true)
        {
            tag = p;
            count = p;
        }
        else if (p-tag==1)
        {
            flag = true;
        }

        return pos_where(++p,q,count);
    }
    return p;
}

bool pos_again(char* p,char* q,char* count)
{
    assert(count!=NULL);
    strncpy(c,count,p-count);
    strcat(c,q);
    char* temp = c;
    while (1)
    {
        if (*count=='\0')
        {
            break;
        }

        if (*c=='\0')
        {
            memset(c,0,MAXLEN*2+1);
            return true;
        }

        if (*q=='\0')
        {
            if (*(temp)>*(count))
            {
                memset(c,0,MAXLEN*2+1);
                return false;
            }
            else if(*(temp++)<*(count++))
            {
                memset(c,0,MAXLEN*2+1);
                return true;
            }

            continue;
        }

        if (*(temp)>*(q))
        {
            memset(c,0,MAXLEN*2+1);
            return false;
        }
        else if (*(temp++)<*(q++))
        {
            memset(c,0,MAXLEN*2+1);
            return true;
        }
    }

    memset(c,0,MAXLEN*2+1);
    return false;
}

68 楼

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

987987 987986这个错了

65楼的代码是没改过的吗？

69 楼

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

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

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

string deal(string  a, string  b, string  c) {
    int i = 0;
    int sentry = 1;
    while(i != a.size()) {
        if(b[0] < a[i]) {
            sentry = -1;
            break;
        }
        else if(b[0] == a[i]) {
            sentry = 0;
            break;
        }
        ++i;
    }
    if(sentry == -1)
        c = string(a).insert(i,b);
    if(sentry == +0) {
        if(a.size() == 1) {
            string tp1(a), tp2;
            tp1 += b;
            tp2 = b + a;
            c = tp1 > tp2? tp2 : tp1;
        }
        else {
            string tp1(a), tp2;
            tp1.insert(i,b);
            if(i == a.size() - 1)
                tp2 += b;
            else {
                tp2 = a[0] + deal(a.substr(1), b, c);
            }
            c = tp1 > tp2? tp2 : tp1;
        }
    }
    if(sentry == +1)
        c = a + b;
    return c;
}

70 楼

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

我一定要用这个算法把这道题解了,再接再励

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

#define MAXLEN 100000

//todo: 在此增加你所需要的函数或者变量或者头文件
char* pos_where(char* p ,char* q,char* count);

bool pos_again(char* p,char* q,char* count);

bool check_valid(char* p);

static bool s_bIndex = false;
static char* tag = NULL;
static bool flag = false;

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

    memset(c,0,MAXLEN*2+1);

    assert(a && b && c);
    char* pos = pos_where(a,b,NULL);

    strncpy(c,a,pos-a);
    strcpy(c+(pos-a),b);
    strcpy(c+strlen(c),pos);

    memset(a,0,MAXLEN+1);
    memset(b,0,MAXLEN+1);
    s_bIndex = false;
    tag = NULL;
    flag=false;
}

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

bool check_valid(char* p)
{
    assert(p);
    while (*p != '\0')
    {
        if ( *p>'9' || *p<'0' )
        {
            return false;
        }
        p++;
    }
    return true;
}

char* pos_where(char* p ,char* q,char* count)
{
    if (*p=='\0')
    {
        if (!s_bIndex)
        {
            return p;
        }

        if (!pos_again(p,q,count))
        {
            return count;
        }
        else
        {
            return p;
        }
    }

    if (*p>*q)
    {
        if (!s_bIndex)
        {
            return p;
        }
        if (!pos_again(p,q,count))
        {
            return count;
        }
        else
        {
            return p;
        }
    }
    else if (*p<*q)
    {
        return pos_where(++p,q,count);
    }
    else if (*p==*q)
    {
        if (!s_bIndex)
        {
            count = p;
            tag = p;
            s_bIndex = true;
        }

        else if (p-tag!=1&&flag!=true&&*p == *(p+1))
        {
            tag = p;
            count = p;
        }
        else if (p-tag==1)
        {
            flag = true;
        }

        return pos_where(++p,q,count);
    }
    return p;
}

bool pos_again(char* p,char* q,char* count)
{
    assert(count!=NULL);
    strncpy(c,count,p-count);
    strcat(c,q);
    char* temp = c;
    while (1)
    {
        if (*count=='\0')
        {
            break;
        }

        if (*c=='\0')
        {
            memset(c,0,MAXLEN*2+1);
            return true;
        }

        if (*q=='\0')
        {
            if (*(temp)>*(count))
            {
                memset(c,0,MAXLEN*2+1);
                return false;
            }
            else if(*(temp++)<*(count++))
            {
                memset(c,0,MAXLEN*2+1);
                return true;
            }

            continue;
        }

        if (*(temp)>*(q))
        {
            memset(c,0,MAXLEN*2+1);
            return false;
        }
        else if (*(temp++)<*(q++))
        {
            memset(c,0,MAXLEN*2+1);
            return true;
        }
    }

    memset(c,0,MAXLEN*2+1);
    return false;
}

我来回复

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

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

回复列表（共182个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

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

回复列表 （共182个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共182个回复）