刘汝佳《算法竞赛入门经典（第二版）》第三章习题（二）
习题3-5 谜题（ACM/ICPC World Finals 1993，UVa227）
有一个5*5的网格，其中恰好有一个格子是空的，其他格子各有一个字母。一共有4种指令：A，B，L，R，分别表示把空格上、下、左、右的相邻字母移到空格中。输入初始网格和指令（以数字0结束），输出指令执行完毕后的网格。如果有非法指令，应输出“This puzzle has no final configuration.”。（附图参见刘汝佳《算法竞赛入门经典（第二版）》P57-58）
解析
用两个常量数组分别存储指令和指令对应的坐标变化，根据命令移动空格位置（比如执行A命令，将空格和空格上方的字符对调）即可。
#include <cstdio>
#include <cstdlib>
#include <memory>
#include <string>
#include <iostream>
using namespace std;
int main (void)
{
const char order[5] = "ABLR";//指令数组
const int move[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};//存储对应指令的坐标变化
char net[5][6];
memset(net, '\0', sizeof(net));
string s;
int line = 0;
int x = 0, y = 0;
for (int i = 0; i < 5; i++)//初始化网格
{
getline (cin,s);
for (int j = 0; j < 5; j++)
net[line][j] = s[j];
line++;
}
for (int i = 0; i < 5; i++)//找出空格所在位置
for (int j = 0; j < 5; j++)
if (net[i][j] == ' ')
{
x = i;
y = j;
}
char ch;
while ((ch = getchar()) != '0')
{
int kase = 0;
for (int j = 0; j < 5; j++)//找到对应指令所在位置，根据指令执行对应操作
if (ch == order[j])
{
swap(net[x][y], net[x+move[j][0]][y+move[j][1]]);
//交换之后要更新空格的坐标值
x += move[j][0];
y += move[j][1];
kase = 1;
}
if (!kase)//如果有非法指令则输出提示
printf ("This puzzle has no final configuration.\n");
}
//打印最终网格（不能有多余空格）
for (int i = 0; i < 5; i++)
{
for (int j = 0; j < 5; j++)
{
if(j)
printf (" %c",net[i][j]);
else
printf ("%c",net[i][j]);
}
printf ("\n");
}
return 0;
}
习题3-6 纵横字谜的答案（ACM/ICPC World Finals 1994，UVa232）
输入一个r行c列（1≤r，c≤10）的网格，黑格用“*”表示，每个白格都填有一个字母。如果一个白格的左边相邻位置或者上边相邻位置没有白格（可能是黑格，也可能出了网格边界），则称这个白格是一个起始格。
2 2
AT
*O
6 7
AIM*DEN
*ME*ONE
UPON*TO
SO*ERIN
*SA*OR*
IES*DEA
0
puzzle #1:
Across
1.AT
3.O
Down
1.A
2.TO
puzzle #2:
Across
1.AIM
4.DEN
7.ME
8.ONE
9.UPON
11.TO
12.SO
13.ERIN
15.SA
17.OR
18.IES
19.DEA
Down
1.A
2.IMPOSE
3.MEO
4.DO
5.ENTIRE
6.NEON
9.US
10.NE
14.ROD
16.AS
18.I
20.A
解析
开两个数组，一个用来存输入数据，一个标记起始格位置并编号。题目思路看似简单但坑不少，输入输出格式都有很多要求。比如每组输出之间的空行，输出单词之前的序号为右对齐等等。稍不注意这道题就没法AC了。
#include <iostream>
#include <memory>
#include <iomanip>
using namespace std;
int main(void)
{
int r,gap = 0;
while (cin >> r && r)
{
int i,j,c;
cin >> c;
char data[10][11];
int mark[10][10];
int kase = 0;
memset(mark, 0, sizeof(mark));
for (i = 0; i < r; i++)//边输入边判断是否为起始格
for (j = 0; j < c; j++)
{
cin >> data[i][j];
if (data[i][j] != '*' && (i == 0 || j == 0 || data[i-1][j] == '*' || data[i][j-1] == '*'))//标记起始格位置
mark[i][j] = ++kase;
}
if (gap)//判断是否为第一组输出
cout << endl;
cout<<"puzzle #"<<++gap<<":"<<endl;
cout<<"Across"<<endl;
for (i = 0; i < r; i++)//输出横向单词
{
j = 0;
while (j < c)
{
if (data[i][j] == '*')
{
j++;
continue;
}
if (j < c)
cout << setw(3) << mark[i][j] << ".";
while (j < c && data[i][j] != '*')
{
cout << data[i][j];
j++;
}
cout << endl;
}
}
cout << "Down" << endl;
for (i = 0; i < r; i++)//输出竖向单词
for (j = 0; j < c; j++)
{
if(data[i][j] == '*' || mark[i][j] == 0)
continue;
cout << setw(3) << mark[i][j] << ".";
int k = i;
while(k<r && data[k][j] != '*')
{
cout << data[k][j];
mark[k][j] = 0;//为避免输出单词子集需要将输出过的单词位置置0
k++;
}
cout << endl;
}
}
return 0;
}
习题3-7 DNA序列（ACM/ICPC Seoul 2006，UVa1368）
输入m个长度均为n的DNA序列，求一个DNA序列，到所有序列的总Hamming距离尽量小，两个等长字符串的Hamming距离等于字符不同的位置个数，例如，ACGT和GCGA的Hamming距离为2（左数第1,4个字符不同）。
输入整数m和n（4≤m≤50，4≤n≤1000），以及m个长度为n的DNA序列（只包含字母A，C，G，T），输出到m个序列的Hamming距离和最小的DNA序列和对应的距离。如有多解，要求为字典序最小的解。例如，对于下面5个DNA序列，最优解为TAAGATAC。
TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT
解析
所谓字典序，就是字符串在字典中的顺序。一般地，对于两个字符串，从第一个字符开始比较，当某一个位置的字符不同时，该位置字符较小的串，字典序较小（例如，abc比bcd小）；如果其中一个字符串已经没有更多字符，但另一个字符串还没结束，则较短的字符串的字典序较小（例如，hi比history小）。
统计每一个DNA序列中各字母出现的次数，再按列比较，输出每一列出现次数最多的字母，若有相同次数则选择字典序较小的输出（出现次数最多的字母的Hamming距离和必定最小），然后再把选出的字母对应的次数以外的次数全部相加即可得到Hamming距离和。文字如果不好理解请看下面图解（以书中给的输入为例）。
图解
#include <iostream>
#include <memory>
#include <iomanip>
#include <string>
using namespace std;
int main (void)
{
int m,n,t,i,j,k;
string s[50];
const char DNA[5] = "ACGT";
int cnt[1000][4];
int cnt2[1000];
cin >> t;
while (t--)
{
memset(cnt, 0, sizeof(cnt));
cin >> m >> n;
//存储DNA序列
for (i = 0; i < m; i++)
cin >> setw(n) >> s[i];//用setw设置字段长度，防止误输，本题中可有可无
//统计DNA序列中各字母出现次数
for (i = 0; i < m; i++)
for (j = 0; j < n; j++)
for (k = 0; k < 4; k++)
if (s[i][j] == DNA[k])
cnt[j][k]++;
memset(cnt2, 0, sizeof(cnt2));
int sum = 0;
for (j = 0; j < n; j++)
{
//找出每列出现次数最多的字母
for (k = 0; k < 4; k++)
if (cnt[j][k] > cnt[j][cnt2[j]])
cnt2[j] = k;
//计算该字母的Hamming距离和
for (k = 0; k < 4; k++)
if (k != cnt2[j])
sum += cnt[j][k];
}
for (i = 0; i < n; i++)
cout << DNA[cnt2[i]];
cout << endl << sum;
}
return 0;
}
习题3-8 循环小数（ACM/ICPC World Finals 1990，Uva202）
输入整数a和b（0≤a≤3000，1≤b≤3000），输出a/b的循环小数表示以及循环节长度。例如a=5，b=43，小数表示为0.(116279069767441860465)，循环节长度为21。
Each line of the input file consists of an integer numerator, which is nonnegative, followed by an integer denominator, which is positive. None of the input integers exceeds 3000. End-of-file indicates the end of input.
For each line of input, print the fraction, its decimal expansion through the first occurrence of the cycle to the right of the decimal or 50 decimal places (whichever comes first), and the length of the entire repeating cycle.
In writing the decimal expansion, enclose the repeating cycle in parentheses when possible. If the entire repeating cycle does not occur within the first 50 places, place a left parenthesis where the cycle begins - it will begin within the first 50 places - and place ``...)" after the 50th digit.
Print a blank line after every test case.
76 25
5 43
1 397
76/25 = 3.04(0)
1 = number of digits in repeating cycle
5/43 = 0.(116279069767441860465)
21 = number of digits in repeating cycle
1/397 = 0.(00251889168765743073047858942065491183879093198992...)
99 = number of digits in repeating cycle
解析
本来想用sprintf把商转化为字符串形式然后再找循环节，然而……
由上面结果可以看到，由于浮点数运算的精度限制，较多的位数已经不能精确表示。
硬来不行就只能用程序模拟除法的计算过程了（小学就学过的）。列出除法式，观察可发现，在除的过程中，除数b的值始终不变，变的是被除数a，将用过的被除数记录下来，一旦出现重复即可找出循环节。特别需要注意的是，用于存放数据的数组元素个数不能少于a和b的数据上限3000，因为在除的过程中被除数a有可能会上到3000（手动计算1/2999就明白了）。
#include <iostream>
using namespace std;
const int N = 3000;
int main (void)
{
int a,b;
while (cin >> a >> b)
{
cout << a << "/" << b << " = " << a/b << ".";//输出整数部分和小数点
a %= b;
bool used[N+1] = {0};
int quo[N+1] = {0}, div[N+1] = {0};
int n = 0;
//执行除法，知道被除数出现重复为止
while (!used[a])
{
div[n] = a;//记录被除数的值
used[a] = true;//记录被除数是否出现
a *= 10;
quo[n] = a/b;//记录每一次循环得出的商（即小数）
n++;
a %= b;
}
//计算循环节前的小数位数
int m = 0;
for (m = 0; m < n; m++)
if (div[m] == a)
break;
//输出循环节前的小数
for (int i = 0; i < m; i++)
cout << quo[i];
//输出循环节
cout << "(";
for (int i = m; i < n && i < m+50; i++)
cout << quo[i];
//当“循环节”（可能是无限不循环）位数已超过50位时在“循环节”末尾加入“...”
if (n-m > 50)
cout << "...";
cout << ")" << endl;
cout << n << " = " << "number of digits in repeating cycle" << endl;
}
return 0;
}