主题：第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个回复）
111 楼
HeroSong [专家分：940] 发布于 2009-03-01 19:02:00
#include <stdio.h>
#define MAXLEN 100000
//todo: 在此增加你所需要的函数或者变量或者头文件
#include <string.h>
void deal(char* a, char* b, char* c)
{
// todo: 在此补充你的处理代码
// 参数说明: a和b是输入的字符串，c要保存输出结果
int i,j,k,m,aLen,bLen;
char d[MAXLEN*2+1];
aLen=strlen(a);
bLen=strlen(b);
k=0;
for(i=0;i<aLen;i++)
{
//a串中的每个数字和b串的首个数字比较
if(a[i]<b[0])c[k++]=a[i];//小于则将a串的这个数字赋给结果串c的相应位置
else if(a[i]==b[0])//如果等于的话
{
//运用试探法决出最终串k=i
for(j=0;j<bLen;j++)c[i+j]=b[j];//把b串插入到这个位置
for(j=i;j<aLen;j++)c[bLen+j]=a[j];//把a串剩下的数字连接到结果串末尾
for(m=i;m<aLen;m++)//还有aLen-i个插入试探位置
{
for(j=i;j<m+1;j++)d[j-i]=a[j];//把a[i,m)放入d
for(j=0;j<bLen;j++)d[m+1-i+j]=b[j];//把b串插入到这个位置
for(j=m+1;j<aLen;j++)d[j-i+bLen]=a[j];//把a[m,aLen)放入的
for(j=i;j<aLen+bLen;j++)
{
if(d[j-i]!=c[j])
{
//如果d中有小于c中相应位置的数字，则用d替换c[i,aLen+bLen)相应位置的数字
if(d[j-i]<c[j])for(j=i;j<aLen+bLen;j++)c[j]=d[j-i];
break;//大于时则直接跳出
}
}
}
c[k=aLen+bLen]='\0';//追加字符串结束符
break;
}
else//如果大于的话
{
for(j=0;j<bLen;j++)//把b串插入到这个位置
c[k++]=b[j];
for(j=i;j<aLen;j++)//把a串剩下的数字连接到结果串末尾
c[k++]=a[j];
c[k]='\0';//追加字符串结束符
break;
}
}
if(k==aLen)//在a串中没有找到插入b串的位置
{
for(j=0;j<bLen;j++)//把b串插入到这个位置
c[k++]=b[j];
c[k]='\0';//追加字符串结束符
}
}
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;
}
112 楼
雨中飞燕 [专家分：18980] 发布于 2009-03-01 19:48:00
楼上的代码错在 122 221
113 楼
godson126 [专家分：30] 发布于 2009-03-01 21:59:00
辛苦了，谢谢。经提醒我修改了第34行，将if(*b<*(b-1))改为if(*(b+1)<*b)更正代码如下：请您提点一下。谢谢！
#include<stdio.h>
#include<string.h>
#define MAXLEN 100000
char a[MAXLEN+1];
char b[MAXLEN+1];
char c[2*MAXLEN+1];
char *B=b;
char *A=a;
void puts(char *c)
{
printf("%s",c);
*c='\0';
}
void deal(char *a,char *b,char *c)
{
if(*a=='\0'||*b=='\0'||*a>*b)
{
strncat(c,A,int(a)-int(A));
strcat(c,B);
strcat(c,a);
}
else if(*a<*b)
{
deal(a+1,b,c);
}
else if(*a==*b)
{
while(1)
{
if(*(b+1)!=*b)
break;
b++;
}
if(*(b+1)<*b)
{
strncat(c,A,int(a)-int(A));
strcat(c,B);
strcat(c,a);
}
else
{
deal(a+1,b,c);
}
}
}
int main(void)
{
while (scanf("%s%s", a, b)!=EOF)
{
deal(a, b,c);
puts(c);
}
return 0;
}
114 楼
HeroSong [专家分：940] 发布于 2009-03-01 22:36:00
#include <stdio.h>
#define MAXLEN 100000
//todo: 在此增加你所需要的函数或者变量或者头文件
#include <string.h>
void deal(char* a, char* b, char* c)
{
// todo: 在此补充你的处理代码
// 参数说明: a和b是输入的字符串，c要保存输出结果
int i,j,k,m,aLen,bLen;
char d[MAXLEN*2+1];
aLen=strlen(a);
bLen=strlen(b);
k=0;
for(i=0;i<aLen;i++)
{
//a串中的每个数字和b串的首个数字比较
if(a[i]<b[0])c[k++]=a[i];//小于则将a串的这个数字赋给结果串c的相应位置
else if(a[i]==b[0])//如果等于的话
{
//运用试探法决出最终串k=i
for(j=0;j<bLen;j++)c[i+j]=b[j];//把b串插入到这个位置
for(j=i;j<aLen;j++)c[bLen+j]=a[j];//把a串剩下的数字连接到结果串末尾
for(m=i;m<aLen;m++)//还有aLen-i个插入试探位置
{
for(j=i;j<m+1;j++)d[j-i]=a[j];//把a[i,m)放入d
for(j=0;j<bLen;j++)d[m+1-i+j]=b[j];//把b串插入到这个位置
for(j=m+1;j<aLen;j++)d[j-i+bLen]=a[j];//把a[m,aLen)放入的
for(j=i;j<aLen+bLen;j++)
{
if(d[j-i]!=c[j])
{
//如果d中有小于c中相应位置的数字，则用d替换c[i,aLen+bLen)相应位置的数字
if(d[j-i]<c[j])for(j=i;j<aLen+bLen;j++)c[j]=d[j-i];
break;//大于时则直接跳出
}
}
}
c[k=aLen+bLen]='\0';//追加字符串结束符
break;
}
else//如果大于的话
{
for(j=0;j<bLen;j++)//把b串插入到这个位置
c[k++]=b[j];
for(j=i;j<aLen;j++)//把a串剩下的数字连接到结果串末尾
c[k++]=a[j];
c[k]='\0';//追加字符串结束符
break;
}
}
if(k==aLen)//在a串中没有找到插入b串的位置
{
for(j=0;j<bLen;j++)//把b串插入到这个位置
c[k++]=b[j];
c[k]='\0';//追加字符串结束符
}
}
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;
}
115 楼
雨中飞燕 [专家分：18980] 发布于 2009-03-01 23:01:00
113楼不要自己定义puts函数，并且你的程序在多次输入下出现严重的问题，为什么你没有测试过呢
114楼的错在原来的地方
116 楼
leejqy [专家分：120] 发布于 2009-03-02 12:25:00
#include<stdio.h>
#define MAX_SIZE 10000
void deal(char*a,char* b,char* c)
{
char* pa;
char* pb,ch;
unsigned int len_a,len_b;
int res;
pa=a;
pb=b;
len_a=strlen(a);
len_b=strlen(b);
do
{
while(*pa&&*pa<*pb)
{
pa++;
}
if(!*pa||*pa>*pb)
{
ch=*pa;
*pa='\0';
strcpy(c,a);
strcat(c,b);
*pa=ch;
strcat(c,pa);
break;
}
else
{
if((pa+len_b)<(a+len_a))
{
ch=*(pa+len_b);
*(pa+len_b)='\0';
}
res=strcmp(pa,pb);
if((pa+len_b)<(a+len_a))
{
*(pa+len_b)=ch;
}
if(res>0)
{
ch=*pa;
*pa='\0';
strcpy(c,a);
strcat(c,b);
*pa=ch;
strcat(c,pa);
break;
}
else
{
if(res<0&&!((pa+len_b)<(a+len_a)))
{
int r;
char ch_temp;
ch_temp=*(pb+(a+len_a-pa));
*(pb+(a+len_a-pa))='\0';
r=strcmp(pa,pb);
*(pb+(a+len_a-pa))=ch_temp;
if(!r&&*(pb+1)<*pa)
{
ch=*pa;
*pa='\0';
strcpy(c,a);
strcat(c,b);
*pa=ch;
strcat(c,pa);
break;
}
else if(r<0&&*(pa+1)<*pa)
{
strcpy(c,a);
strcat(c,b);
break;
}
}
pa++;
}
}
}while(1);
return ;
}
int main(void)
{
char a[MAX_SIZE+1],b[MAX_SIZE+1],c[MAX_SIZE*2+1];
while(scanf("%s%s",a,b)!=EOF)
{
deal(a,b,c);
puts(c);
}
return 0;
}
117 楼
蓝桥小帽 [专家分：0] 发布于 2009-03-02 13:17:00
忘记把调试信息去掉了，这次改了再看看
#include <stdio.h>
#include <assert.h>
#include <string.h>
#define MAXLEN 100000
void deal(char* a,char* b,char* c)
{
char *ptr_a,*ptr_b,*temp;
int equal_before = 0;
int len_a,len_b,minus;
ptr_a = a;
ptr_b = b;
temp = ptr_a;
assert(a!=NULL && b!=NULL && c!=NULL);
if((*ptr_a == '\0')||(*ptr_b == '\0'))
return;
while( *temp != '\0')
{
if(*ptr_a < *ptr_b)
{
temp++;
ptr_a = temp;
ptr_b = b;
equal_before = 0;
}
else if( *ptr_a > *ptr_b)
{
if(equal_before == 1)
ptr_a = temp;
break;
}
else
{
ptr_a++;
ptr_b++;
if( (*ptr_a == '\0')||(*ptr_b == '\0'))
{
if(*ptr_b !='\0')
{
ptr_a = a;
}
else
{
temp++;
ptr_a = temp;
ptr_b = b;
equal_before = 0;
}
}
else
{
equal_before = 1;
}
}
}
/* copy*/
len_a = strlen(a);
len_b = strlen(b);
minus = ptr_a - a;
if( minus==0)/*beg*/
{
strcpy(c,b);
strcpy(c+len_b,a);
}
else if( minus== len_a)/*end*/
{
strcpy(c,a);
strcpy(c+len_a,b);
}
else if( minus >0 && minus<len_a)
{
strncpy(c,a, minus);
strcpy(c+minus,b);
strcpy(c+minus+len_b,a+minus);
}
}
char a[MAXLEN+1],b[MAXLEN+1],c[MAXLEN+1];
int main(void)
{
while(scanf("%s%s",a,b)!=EOF)
{
deal(a,b,c);
puts(c);
}
return 0;
}
118 楼
雨中飞燕 [专家分：18980] 发布于 2009-03-02 16:42:00
116和117楼的均错在122 221
119 楼
StephenWang [专家分：0] 发布于 2009-03-02 16:45:00
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
void insertandMin(const int,const int,vector<int>& vecNum);
int numLen(const int);
int minimum(const vector<int>& vecNum);
int main()
{
int a,b;
vector<int> vecNum;
cout<<"Please enter tow numbers:\n";
cin>>a>>b;
insertandMin(a,b,vecNum);
int minVal=minimum(vecNum);
cout<<"minVal="<<minVal<<endl;
return 0;
}
void insertandMin(const int a,const int b,vector<int>& vecNum)
{
int numOne=a;
int numTwo=b;
int value;
int tempValOne,tempValTwo,tempValThree;
int lenOne=numLen(numOne);
int lenTwo=numLen(numTwo);
vecNum.push_back((numTwo*pow(10,lenOne))+numOne);//access the first case of "ab"
for(int i=1;i!=(lenOne+1);i++)
{
tempValOne=numOne/(pow(10,lenOne-i));
tempValTwo=numOne%(int)(pow(10,(lenOne-i)));
tempValThree=numTwo*pow(10,lenOne-i);
value=tempValOne*pow(10,(lenOne+lenTwo-i))+tempValTwo+tempValThree;
vecNum.push_back(value);
}
}
int numLen(const int num)
{
int count=1;//define a counter.
int tempVal;//define a temporary variable.
int temp=0;
tempVal=num;
while((tempVal=tempVal/10)>0)
{
count++;
}
return count;
}
int minimum(const vector<int>& vecNum)
{
int temp=0;
vector<int> vecNumTemp(vecNum);
temp=vecNumTemp.back();
for(vector<int>::iterator it=vecNumTemp.begin();it!=vecNumTemp.end();it++)
{
if(*it<temp)
temp=*it;
}
return temp;
}
120 楼
Reversed [专家分：0] 发布于 2009-03-02 16:57:00
#include <stdio.h>
#include <string.h>
#define MAXLEN 100000
//todo: 在此增加你所需要的函数或者变量或者头文件
bool position(char* str, int& n) {
char* temp = str;
++temp;
while (*temp != '\0' && *temp == *str) {++temp; ++n;}
if (*temp == '\0' || *temp < *str)
return true;
else
return false;
}
int find_first_bigger(char* str, char c) {
if (*str == c) return 0;
char* temp = str;
int len = 0;
while (*temp <= c && *temp != '\0') {++temp; ++len;}
return len;
}
inline void move(char* a, char* b, char* c,int fLen,int aLen,int bLen) {
memmove(c, a, fLen);
memmove(c + fLen, b, bLen);
memmove(c + fLen + bLen, a + fLen, aLen - fLen + 2);
}
void deal(char* a, char* b, char* c)
{
// todo: 在此补充你的处理代码
// 参数说明: a和b是输入的字符串，c要保存输出结果
int fLen = find_first_bigger(a, *b);
int aLen = strlen(a);
int bLen = strlen(b);
if(*(a + fLen - 1) != *b) {
move(a, b, c, fLen, aLen, bLen);
}
else {
int i = 0;
bool p = position(b, i);
if (p == true)
move(a, b, c, fLen - i - 1, aLen, bLen);
else
move(a, b, c, fLen, aLen, bLen);
}
}
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;
}
我来回复
您所在位置：