主题：第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
回复列表 （共182个回复）
151 楼
Reversed [专家分：0] 发布于 2009-03-05 18:01:00
恩放弃了 算法知识积累的太少 下去继续努力
152 楼
雨中飞燕 [专家分：18980] 发布于 2009-03-05 21:50:00
149楼的错在8282828282 8282828283
153 楼
geniur [专家分：0] 发布于 2009-03-05 22:16:00
#include <stdio.h>
#include <iostream.h>
#include <stdlib.h>
#include <string.h>
#define MAXLEN 100000
//todo: 在此增加你所需要的函数或者变量或者头文件
void puts(char *c)
{
cout<<"连接后的数字是"<<c<<endl<< "**********************"<<endl;
}
void link(char * src,int pos,char* sndsrc,char *dest)
{
int srclen=strlen(src);
int sndsrclen=strlen(sndsrc);
if(pos)
{
for(int i=0;i<pos;i++)
dest[i]=src[i];
for( i=0;i<sndsrclen+1;i++)
dest[pos+i]=sndsrc[i];
for( i=pos;i<srclen+1;i++)
dest[sndsrclen+i]=src[i];
dest[srclen+sndsrclen]='\0';
}
else
{
for(int i=0;i<srclen;i++)
dest[i]=src[i];
for( i=0;i<sndsrclen+1;i++)
dest[srclen+i]=sndsrc[i];
}
}
void deal(char* a, char* b, char* c)
{
// todo: 在此补充你的处理代码
// 参数说明: a和b是输入的字符串，c要保存输出结果
if(!atoi(a)||!atoi(b))
{
cout<<"请输入两个整数"<<endl;
cin>>a>>b;
}
int alen,blen;
alen=strlen(a);
blen=strlen(b);
if(alen>10000||blen>10000)
{
cout<<"the number you enter is bigger than 10000";
return;
}
int tag=0;
if((a[0]<b[0])||(a[0]==b[0]))
{
for(int i=1;i<alen;i++)
{
if(a[i]>b[0])
{
tag = i;
break;
}
}
link(a,tag,b,c);
}
else
{
for(int i=1;i<blen;i++)
{
if(b[i]>a[0])
{
tag = i;
break;
}
}
link(b,tag,a,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;
}
154 楼
雨中飞燕 [专家分：18980] 发布于 2009-03-06 00:39:00
153楼的代码错在数据12 21上，附：这份代码十分不规范
155 楼
goal00001111 [专家分：4030] 发布于 2009-03-06 11:29:00
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#define MAXLEN 100000
//todo: 在此增加你所需要的函数或者变量或者头文件
void deal(char* a, char* b, char* c)
{
// todo: 在此补充你的处理代码
// 参数说明: a和b是输入的字符串，c要保存输出结果
int lenA = strlen(a);
int lenB = strlen(b);
int i, j, k, ti, tj;
i = j = k = 0;
while (i < lenA)
{
while (a[i] < b[0]) //先复制a的前段
c[k++] = a[i++];
if (a[i] > b[0]) //将b插入在a[i]的前面
{
j = 0;
while (j < lenB)
c[k++] = b[j++];
while (i < lenA)
c[k++] = a[i++];
c[k++] = '\0';
return;
}
else // a[i] == b[0]
{
ti = i, tj = 0;
while (ti < lenA && tj < lenB && a[ti] == b[tj])
ti++, tj++;
if (ti == lenA) //a较短
{
while (tj < lenB && b[tj] == b[tj-1])
tj++;
if (tj == lenB || b[tj] < b[tj-1]) //将b插入在a[i]的前面
{
j = 0;
while (j < lenB)
c[k++] = b[j++];
while (i < lenA)
c[k++] = a[i++];
c[k++] = '\0';
return;
}
else // c = a + b
{
while (i < lenA)
c[k++] = a[i++];
j = 0;
while (j < lenB)
c[k++] = b[j++];
c[k++] = '\0';
return;
}
}
else if (tj == lenB || a[ti] < b[tj]) //b较短，先复制a的前段
{
while (i < ti)
c[k++] = a[i++];
}
else //直接将b插入在a[i]的前面
{
j = 0;
while (j < lenB)
c[k++] = b[j++];
while (i < lenA)
c[k++] = a[i++];
c[k++] = '\0';
return;
}
}
}
}
char a[MAXLEN+1], b[MAXLEN+1], c[MAXLEN*2+1];
int main(int argc, char* argv[])
{
while (scanf("%s%s", a, b)!=EOF)
{
deal(a, b, c);
puts(c);
}
return 0;
}
156 楼
ChRise [专家分：50] 发布于 2009-03-07 14:24:00
#include <stdio.h>
#define MAXLEN 100000
//todo: 在此增加你所需要的函数或者变量或者头文件
#include <string.h>
void deal(char* a, char* b, char* c)
{
// todo: 在此补充你的处理代码
// 参数说明: a和b是输入的字符串，c要保存输出结果
memset(c,0,MAXLEN*2+1); //初始化c
char *p = a;
while ((*p <= *b)&&*p != '\0') //当p指向的值小于等于b中第一个值
{ //且不为结束符'\0'时，进入循环
p++;
}
memcpy(c,a,p-a);
memcpy(c+(p-a),b,strlen(b));
memcpy(c+strlen(c),p,strlen(p));
}
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;
}
本程序空间复杂度为0，时间复杂度最坏的情况要比较的次数为数组a长度
编译器为vc++6.0，测试结果正确！
157 楼
雨中飞燕 [专家分：18980] 发布于 2009-03-08 00:49:00
156楼的代码对于简单情况 12 21 输出结果错误
158 楼
youshaofu [专家分：20] 发布于 2009-03-08 12:39:00
#include "type.h"
#include <stdio.h>
#include <string.h>
void main()
{
//定义2个变量，存放被处理的2个不超过100000长度的数
char a[MAXLEN] = {0,};
char b[MAXLEN] = {0,};
//定义1个变量，存放结果
char result[ENMAXLLEN] = {0,};
//取得2个数
printf("Input->");
scanf("%s%s",a,b);
//在函数里处理，返回最小值
MainProcess(a,b,result);
//输出结果
printf("%s",result);
}
void MainProcess(char *a,char *b,char *result)
{
//定义1个变量，存放暂时的最小值，长度不超过200000位
char minValue[ENMAXLLEN] = {0,};
char tmp[ENMAXLLEN] = {0,};
long aLen,bLen,i,tmpLen;
memset(minValue,0xff,ENMAXLLEN);
aLen = 0;
bLen = 0;
tmpLen = 0;
aLen = strlen(a);
bLen = strlen(b);
for(i = 0 ; i < aLen ;i++)
{
myStrncpy(tmp,a,0,i);
myStrncpy(tmp,b,0,bLen);
myStrncpy(tmp,a,i,aLen-i);
if(strcmp(minValue,tmp) > 0)
{
tmpLen = strlen(tmp);
strncpy(minValue,tmp,tmpLen);
minValue[strlen(tmp)] = 0;
}
memset(tmp,0,MAXLEN);
}
strncpy(result,minValue,strlen(minValue));
result[strlen(minValue)+1] = 0;
}
void myStrncpy(char *src,char *dst,long start,long len)
{
long srcLen = strlen(src);
long dstLen = strlen(dst);
long loop = 0;
long cnt = 0;
for(cnt = 0,loop = start;cnt < len;cnt++,loop++)
{
src[srcLen+cnt] = dst[loop];
}
src[srcLen+len] = 0;
}
/////////////////type.h/////////////////
#define NULL 0
#define MAXLEN 100001 // 1个数的最大长度
#define ENMAXLLEN 200001 // 2个数组合之后的最大长度
void myStrncpy(char *src,char *dst,long start,long len);
void MainProcess(char *a,char *b,char *result);
159 楼
youshaofu [专家分：20] 发布于 2009-03-08 12:41:00
[code=c]
#include "type.h"
#include <stdio.h>
#include <string.h>
void main()
{
//定义2个变量，存放被处理的2个不超过100000长度的数
char a[MAXLEN] = {0,};
char b[MAXLEN] = {0,};
//定义1个变量，存放结果
char result[ENMAXLLEN] = {0,};
//取得2个数
printf("Input->");
scanf("%s%s",a,b);
//在函数里处理，返回最小值
MainProcess(a,b,result);
//输出结果
printf("%s",result);
}
void MainProcess(char *a,char *b,char *result)
{
//定义1个变量，存放暂时的最小值，长度不超过200000位
char minValue[ENMAXLLEN] = {0,};
char tmp[ENMAXLLEN] = {0,};
long aLen,bLen,i,tmpLen;
memset(minValue,0xff,ENMAXLLEN);
aLen = 0;
bLen = 0;
tmpLen = 0;
aLen = strlen(a);
bLen = strlen(b);
for(i = 0 ; i < aLen ;i++)
{
myStrncpy(tmp,a,0,i);
myStrncpy(tmp,b,0,bLen);
myStrncpy(tmp,a,i,aLen-i);
if(strcmp(minValue,tmp) > 0)
{
tmpLen = strlen(tmp);
strncpy(minValue,tmp,tmpLen);
minValue[strlen(tmp)] = 0;
}
memset(tmp,0,MAXLEN);
}
strncpy(result,minValue,strlen(minValue));
result[strlen(minValue)+1] = 0;
}
void myStrncpy(char *src,char *dst,long start,long len)
{
long srcLen = strlen(src);
long dstLen = strlen(dst);
long loop = 0;
long cnt = 0;
for(cnt = 0,loop = start;cnt < len;cnt++,loop++)
{
src[srcLen+cnt] = dst[loop];
}
src[srcLen+len] = 0;
}
////////type.h/////////////
#define NULL 0
#define MAXLEN 100001 // 1个数的最大长度
#define ENMAXLLEN 200001 // 2个数组合之后的最大长度
void myStrncpy(char *src,char *dst,long start,long len);
void MainProcess(char *a,char *b,char *result);
[/code]
160 楼
雨中飞燕 [专家分：18980] 发布于 2009-03-08 16:00:00
159楼的代码不符合输入输出要求
我来回复
您所在位置：