XieNaoban's Blog
0%

算法竞赛入门经典 3-7UVa1368 3-8UVa202 3-9UVa10340

发表于 更新于 分类于 ， 阅读次数： 评论次数：
本文字数： 3.2k 阅读时长 ≈ 3 分钟

书上具体所有题目：http://pan.baidu.com/s/1hssH0KO 都是《算法竞赛入门经典（第二版）》的题目，标题上没写（第二版）

题目：算法竞赛入门经典 3-7/UVa1368：DNA Consensus String 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//UVa1368 - DNA Consensus String
#include<iostream>
using namespace std;

#define MAX_M 52
#define MAX_N 1005
char DNA[MAX_M][MAX_N];

int main()
{
	int T, m, n, err, num[4];//num用于存放ACGT个数
	const int &mm = m, &nn = n;//防止自己代码书写错误
	char consensus[MAX_N], ACGT[] = "ACGT";//consensus为计算结果
	cin >> T;
	while (T--) {
		err = 0;
		cin >> m >> n;
		cin.getline(DNA[51], 3);//吸收'\n'
		for (int i = 0;i < mm;++i)
			cin.getline(DNA[i], MAX_N);
		for (int i = 0;i < nn;++i) {
			num[0] = num[1] = num[2] = num[3] = 0;//初始化或重置num
			for (int j = 0;j < mm;++j)
				switch (DNA[j][i]) {
				case 'A': ++num[0];break;
				case 'C': ++num[1];break;
				case 'G': ++num[2];break;
				case 'T': ++num[3];break;
				default:cerr << "Error:1\n";exit(0);
				}
			int max = 0;
			for (int j = 1;j < 4;++j)
				if (num[j]>num[max])max = j;
			consensus[i] = ACGT[max];
			err += mm - num[max];
		}
		consensus[nn] = '\0';
		cout << consensus << '\n' << err << '\n';
	}
	return 0;
}

分析：找出每个DNA序列的第i个的碱基，找到出现最多的项，即为Consensus String的第i个碱基 在算法竞赛入门经典里看到使用常量数组的方法，可以有效减少switch与if的使用，感觉很好用（虽然记得学校教材上也讲到过，但是当时没那么印象深刻）。于是这次在ACGT[]="ACGT"这里用到了，真心好用呀。

题目：算法竞赛入门经典 3-8/UVa202：Repeating Decimals 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
//UVa202 - Repeating Decimals
#include<iostream>
using namespace std;

#define MAX 502
unsigned Decimal[MAX];//存放各个小数
unsigned Remainder[MAX];//存放各位小数对应的余数

int main()
{
	unsigned numerator, denominator;//分子、分母
	const unsigned &de = denominator;
	int temp, digit;//由于分母可以正可以负,先输入temp至int再转为unsigned,digit记录位数(或者说是位数-1)
	while (cin >> numerator) {
		cin >> temp;
		digit = 0;
		cout << numerator << '/' << temp << " = ";
		if (temp < 0)temp = -temp, cout << '-';
		denominator = (unsigned)temp;
		cout << numerator / de << '.';
		Decimal[0] = (numerator % de * 10) / de;
		Remainder[0] = (numerator % de * 10) % de;
		while (digit < MAX) {
			unsigned di, t = Remainder[digit++] * 10;
			Decimal[digit] = t / de;
			Remainder[digit] = t % de;
			for (di = 0;di < digit;++di)
				if (Decimal[di] == Decimal[digit] && Remainder[di] == Remainder[digit])
					break;
			if (di < digit) {
				for (int i = 0;i < di;++i)
					cout << Decimal[i];
				cout << '(';
				if (digit - di <= 50)
					for (int i = di;i < digit;++i)
						cout << Decimal[i];
				else {
					for (int i = 0;i < 50;++i)
						cout << Decimal[di+i];
					cout << "...";
				}
				cout << ")\n\t" << digit - di << " = number of digits in repeating cycle\n\n";
				break;
			}
		}
		if (digit == MAX) { cerr << "Error:1\n";exit(0); }
	}
	return 0;
}

分析：算出下一位小数b并与之前每一位小数比较，如果找到一位小数a，a的小数值与对应的余数均与b的小数与余数相等，则这两个数a----b之间的就是循环部分。想不出好办法，不是所有小数都是像1/3一样从第一位开始洗脑循环。

题目：算法竞赛入门经典 3-9/UVa10340：All in All 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//UVa10340 - All in All
#include<iostream>
#define M 101000
char s[M], t[M], *ps, *pt;//s短t长
int main()
{
	while (std::cin>>s>>t) {
//为什么scanf按了crtl^z还是不停止，还得再按一下回车才能结束程序。。。
//于是使用scanf导致提交总是超时，因为程序还在等着输入
//而cin只要按一下crtl^z再回车，马上就结束了。不懂。。
//好吧，于是虽然试图尽量少用cin cout，但是c的东西还是不大会用，不熟练
		ps = s, pt = t;
		while (*ps != '\0') {
			while (*pt != *ps&&*pt != '\0')++pt;
			if (*pt == '\0') break;
			++ps,++pt;
		}
		printf(*ps == '\0' ? "Yes\n" : "No\n");
	}
	return 0;
}

分析：不难（上面用cin下面用printf是不是有点违和。。）