[刷题]算法竞赛入门经典 3-7/UVa1368 3-8/UVa202 3-9/UVa10340

书上具体所有题目：http://pan.baidu.com/s/1hssH0KO

都是《算法竞赛入门经典（第二版）》的题目，标题上没写（第二版）

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

代码：

//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

代码：

//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

代码：

//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是不是有点违和。。）