第二届“顶嵌杯”全国嵌入式系统C语言编程大赛初赛试题分析及题解

四道题目都挺简单的，但是中间断断续续的因为睡觉、吃饭、体能测试、剪头发耽误了不少时间，基本不涉及什么算法，主要是字符串处理，大整数相加等，测试数据要考虑周全，先将题目辑录下来，27日比赛结束后再贴AC代码。

27日已经更新AC代码。

Problem A: 分数加减法

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 1552		Accepted: 500

Description

编写一个C程序，实现两个分数的加减法

Input

输入包含多行数据
每行数据是一个字符串，格式是"a/boc/d"。

其中a, b, c, d是一个0-9的整数。o是运算符"+"或者"-"。

数据以EOF结束
输入数据保证合法

Output

对于输入数据的每一行输出两个分数的运算结果。
注意结果应符合书写习惯，没有多余的符号、分子、分母，并且化简至最简分数

Sample Input

1/8+3/8
1/4-1/2
1/3-1/3

Sample Output

1/2
-1/4
0

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

int gbs(int m,int n){//返回m和n的最小公倍数
	int i;
	for(i=m<n?m:n;m%i||n%i;i--);
    return m*n/i;
}

int gys(int x, int y){//返回m和n的最大公约数
	int t;
	if (!x || !y) return x > y ? x : y;
	for (; t = x % y; x = y, y = t);
	return y;
}

void main(){
	char string[10];
	int	 temp,a,b,c,d,beishu,yueshu;
	int m,n;//保存结果的分子和分母
	while(scanf("%s",string) != EOF){
		//首先通分
		a = string[0] - '0';
		b = string[2] - '0';
		c = string[4] - '0';
		d = string[6] - '0';
		if (b != d)
		{
			temp = gbs(b,d);
			m = temp;
			beishu = temp / b;
			a *= beishu;
			b *= beishu;

			beishu = temp / d;
			c *= beishu;
			d *= beishu;
		}
		else m = b;
		switch(string[3]){
		case '+': n = a + c;
				  break;
		case '-': n = a - c;
				  break;
		}

		if (n == 0)
		{
			printf("0/n");
			continue;
		}

		if (n < 0)
		{
			printf("-");
			n = -n;
		}

		if (gbs(m,n) != m * n)//若m与n不互质，则需约分
		{
			yueshu = gys(m,n);
			m = m / yueshu;
			n = n / yueshu;
		}
		if (m == 1)
		{
			printf("%d/n",n);
			continue;
		}
		printf("%d/%d/n",n,m);
	}	
}

Problem B: 取模运算





Time Limit: 1000MS


Memory Limit: 65536K



Total
 Submissions: 806


Accepted: 566



Description
编写一个C函数mod(int n, int m),实现取模运算%
Input
输入包含多行数据 

每行数据是两个整数a, b (1 <= a, b <= 
32767) 
数据以EOF结束
Output
于输入的每一行输出a%b
Sample Input
5 3
100 2
Sample Output
2
0
#include <stdio.h>
void main(){
	int m,n,re;
	while (scanf("%d%d",&m,&n)!=EOF)
	{
		re = m%n;
		printf("%d/n",re);
	}
}
Problem C: 字符串替换





Time
 Limit: 1000MS


Memory Limit: 65536K



Total Submissions: 897


Accepted: 468



Description
编写一个C程序实现将字符串中的所有"you"替换成"we"
Input
输入包含多行数据 

每行数据是一个字符串，长度不超过1000 

数据以EOF结束
Output
对于输入的每一行，输出替换后的字符串
Sample Input
you are what you do
Sample Output
we are what we do
#include <stdio.h>
#include <string.h>
void main(){
	char s[1001];
	while(gets(s)){
		int i;
		char *start = NULL;
		while (1)
		{
			start = strstr(s,"you");
			if (start == NULL)
				break;
			strncpy(start,"we",2);
			for (i=0;*(start+2+i) != '/0';i++)
			{	
				*(start+2+i) = *(start+3+i);
			}	
		}
		printf("%s/n",s);
	}
}
Problem D: 序列





Time
 Limit: 1000MS


Memory Limit: 65536K



Total Submissions: 881


Accepted: 403



Description
数列A满足An = An-1 + An-2 + An-3, n >= 3 


编写程序，给定A0, A1 和 A2, 计算A99
Input
输入包含多行数据 

每行数据包含3个整数A0, A1, A2 (0 <= A0, A1, 
A2 <= 32767) 
数据以EOF结束
Output
对于输入的每一行输出A99的值
Sample Input
1 1 1
Sample Output
69087442470169316923566147
#include <stdio.h>
#include <string.h>
#define MAXHANG 110
#define MAXLIE 100
//大数加法处理,循环计算，动态规划思想
void main(){
	int fibo[MAXHANG][MAXLIE] = {0};//每行存一个大整数
	char a[3][10]={0};
	int i,j,nLen,k,flag = 0;
	while (scanf("%s",a[0]) != EOF)
	{
		scanf("%s%s",a[1],a[2]);
		for(k=0;k<3;k++){
			nLen = strlen(a[k]);
			j = 0;
			for(i = nLen -1;i >= 0;i--)
				fibo[k][j++] = a[k][i] - '0';
		}
		//下面循环做大整数加法，逐步推出a99
		for (j = 0; j< MAXHANG-3;j++)
		{
			for (i = 0;i < MAXLIE-1; i ++)
			{
				fibo[3+j][i] += fibo[0+j][i] + fibo[1+j][i] + fibo[2+j][i];
				if(fibo[3+j][i] >= 20){
					fibo[3+j][i] -= 20;
					fibo[3+j][i+1]++;
					fibo[3+j][i+1]++;
				}
				else if (fibo[3+j][i] >= 10)
				{
					fibo[3+j][i] -= 10;
					fibo[3+j][i+1]++;
				}
			}
		}
		for (j = MAXLIE - 1;j >= 0;j-- )
			{
				if (flag)
				{
					printf("%d",fibo[99][j]);//flag用于跳过多余的0
				}
				
				else if(fibo[99][j]) {
					printf("%d",fibo[99][j]);
					flag = 1;
				}
			}
			printf("/n");
			for (i = 0; i< MAXHANG; i++)
				for (j = 0;j < MAXLIE; j++)
						fibo[i][j] = 0;	
		    for (i = 0; i< 3;i++)
				for (j = 0;j < 10; j++)
						a[i][j]=0;
			flag = 0;
	}
}