11月7号晚上18:30，西工大算法实验期末考试开始，那天是立冬，天气有了些凉意。五天已过，虽然成绩尚未公布，结果却已是心知肚明，0.5学分虽然非常微小，但算法实验的意义却远比这一点学分重要得多。
下面，对这次算法实验考试题目进行回顾。
总计六道题，共4小时。
一，二分查找
此题为简单的二分查找问题，为六题中最简单一题，只需设置low，mid，high变量循环查找即可，不作赘述，代码如下：
#include <stdio.h>
#include <stdlib.h>
int n;//数字数量
int m;//要查找的数字数量
int data[10000];
void input();
int search();
int main()
{
int i;
input();
for (i = 0; i < m; i++)
{
search();
}
}
void input()
{
int i;
scanf("%d", &n);
for (i = 0; i < n; i++)
{
scanf("%d", &data[i]);
}
scanf("%d", &m);
}
int search()
{
int low, high, mid, k;
scanf("%d", &k);
low = 0;
high = n - 1;
mid = low + (high - low) / 2;
while (low <= high)
{
if (data[mid] == k)
{
printf("Yes\n");
return 1;
}
else if (data[mid] > k)
{
high = mid - 1;
}
else
{
low = mid + 1;
}
mid = low + (high - low) / 2;
}
printf("No\n");
return 0;
}
二，0-1背包问题
这一题是动态规划的经典0-1背包问题了，但是此题实际上是0-1背包的弱化版，因为题目限定n<=10，最多状态数为2^10=1024种。这个数字不大，故无论采用回溯、分支限界还是动态规划都可以通过，考试时我选择的是动态规划+滚动数组。值得一题的是，对于循环输入，while判断条件应当是n和c只要有一个不为0即进入循环，在这里我一开始条件判断错误，耽误了一些时间。
动态规划+滚动数组代码如下：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define max(a, b) a > b ? a : b
int C;//背包容量
int N;//物品个数
int weight[11];//每件物品的重量
int value[11];//每件物品的价值
int f[10000];//前i件物品，剩余j重量的最大价值
void dp();
int main()
{
int i;
scanf("%d%d", &N, &C);
while (N != 0 || C != 0)
{
memset(f, 0, sizeof(f));
memset(weight, 0, sizeof(weight));
memset(value, 0, sizeof(value));
for (i = 1; i <= N; i++)
{
scanf("%d", &weight[i]);
}
for (i = 1; i <= N; i++)
{
scanf("%d", &value[i]);
}
dp();
scanf("%d%d", &N, &C);
}
return 0;
}
void dp()
{
//f[i][j]=max(f[i-1][j],f[i-1][j-weight[i]]+value[i])
//f[0][j]=0
//f[1][j]=value[1] if(j>=weight[1])
//f[1][j]=0 if(j<weight[1])
//初始化f[1][j]，要求f[n][j]，则需要迭代n-1次
int i, j;
for (j = 0; j <= C && j < weight[1]; j++)
{
f[j] = 0;
}
for (; j <= C; j++)
{
f[j] = value[1];
}
for (i = 2; i <= N; i++)//迭代N-1次
{
for (j = C; j >= 0; j--)
{
if (j - weight[i] >= 0)
{
f[j] = max(f[j], f[j - weight[i]] + value[i]);
}
}
}
printf("%d\n", f[C]);
}
三，电子老鼠闯迷宫
经典迷宫问题，这一题应使用分支限界法，亦即广度优先搜索，状态参数为所在行与列。此题只需简单搜索即可，较同为广搜的独轮车简单了一些，那题还需要考虑颜色、方向等状态参量，代码如下：
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100000
typedef struct
{
int x;
int y;
} Position;
typedef struct
{
Position elem[MAXSIZE];
int front;
int rear;
} Sequeue;
Sequeue q;
int sx, sy, tx, ty;
char maze[13][14];
int step[13][13];
int vis[13][13];
int dx[4] = { 1, 0, 0, -1 };
int dy[4] = { 0, 1, -1, 0 };
void input();
void bfs();
void enterqueue(int x, int y);
void deletequeue(int* x, int* y);
int isempty();
int main()
{
input();
bfs();
printf("%d\n", step[tx][ty]);
return 0;
}
void input()
{
int i;
scanf("%d%d%d%d", &sx, &sy, &tx, &ty);
sy--;
ty--;
for (i = 1; i <= 12; i++)
{
scanf("%s", maze[i]);
}
}
void bfs()
{
if (sx == tx && sy == ty)
{
return;
}
int x, y, nx, ny, i;
vis[sx][sy] = 1;
enterqueue(sx, sy);
while (!isempty())
{
deletequeue(&x, &y);
for (i = 0; i < 4; i++)
{
nx = x + dx[i];
ny = y + dy[i];
if (nx >= 1 && nx <= 12 && ny >= 0 && ny < 12 && maze[nx][ny] == '.' && !vis[nx][ny])
{
vis[nx][ny] = 1;
step[nx][ny] = step[x][y] + 1;
if (nx == tx && ny == ty)
{
return;
}
enterqueue(nx, ny);
}
}
}
}
void enterqueue(int x, int y)
{
q.elem[q.rear].x = x;
q.elem[q.rear].y = y;
q.rear = (q.rear + 1) % MAXSIZE;
}
void deletequeue(int* x, int* y)
{
*x = q.elem[q.front].x;
*y = q.elem[q.front].y;
q.front = (q.front + 1) % MAXSIZE;
}
int isempty()
{
return q.front == q.rear;
}
以上代码是自己实现queue，也可用c++自带的queue，如此，则代码如下：
#include <iostream>
#include <queue>
using namespace std;
typedef struct
{
int x;
int y;
} Position;
queue <Position> q;
int sx, sy, tx, ty;
char maze[13][14];
int step[13][13];
int vis[13][13];
int dx[4] = { 1, 0, 0, -1 };
int dy[4] = { 0, 1, -1, 0 };
void input();
void bfs();
int main()
{
input();
bfs();
cout << step[tx][ty] << endl;
return 0;
}
void input()
{
int i;
cin >> sx >> sy >> tx >> ty;
sy--;
ty--;
for (i = 1; i <= 12; i++)
{
cin >> maze[i];
}
}
void bfs()
{
if (sx == tx && sy == ty)
{
return;
}
Position start, now, next;
int i;
start.x = sx;
start.y = sy;
vis[sx][sy] = 1;
q.push(start);
while (!q.empty())
{
now = q.front();
q.pop();
for (i = 0; i < 4; i++)
{
next.x = now.x + dx[i];
next.y = now.y + dy[i];
if (next.x >= 1 && next.x <= 12 && next.y >= 0 && next.y < 12 && maze[next.x][next.y] == '.' && !vis[next.x][next.y])
{
vis[next.x][next.y] = 1;
step[next.x][next.y] = step[now.x][now.y] + 1;
if (next.x == tx && next.y == ty)
{
return;
}
q.push(next);
}
}
}
}
四，最长公共子序列
这一题必须使用动态规划或者备忘录方法了，因为长度有200个字符，其他方法会超时。
设maxlen(i,j)表示a前i个字符和b前j个字符的最长公共子序列，则题目要求maxlen(strlen(a),strlen(b))，状态转移方程为：
if(a[i-1]==b[j-1])
maxlen(i,j)=maxlen(i-1,j-1)+1
else
maxlen(i,j)=max{maxlen(i-1,j),maxlen(i,j-1)}
依据状态转移方程，可得代码如下：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define max(a, b) a > b ? a : b
char a[1001];
char b[1001];
int MAXLEN[1001][1001];
int main()
{
int len1, len2;
scanf("%s%s", a, b);
len1 = strlen(a);
len2 = strlen(b);
for (int i = 1; i <= len1; i++)
{
for (int j = 1; j <= len2; j++)
{
if (a[i - 1] == b[j - 1])
{
MAXLEN[i][j] = MAXLEN[i - 1][j - 1] + 1;
}
else
{
MAXLEN[i][j] = max(MAXLEN[i - 1][j], MAXLEN[i][j - 1]);
}
}
}
printf("%d\n", MAXLEN[len1][len2]);
return 0;
}
五，素数环问题
此题为回溯问题，从第一个位置开始，逐个试探1-20每个值，并进行判断，若符合题目条件则继续搜索下一个位置，直到搜索到第一个可行解，输出即可。
（注：理论上，此题效率最高的方法是手动进行这个过程，从第一位开始试，直到得出结果，效率其实不低，因为得出的第一个结果就是答案，然后直接printf输出结果???）
代码如下：
#include <stdio.h>
int data[20];
int visited[21];
int flag;
void dfs(int k);
int issu(int k);
int main()
{
dfs(0);
return 0;
}
void dfs(int k)
{
int i;
if (flag)
{
return;
}
if (k == 20)
{
if (issu(data[0] + data[19]))
{
flag = 1;
for (i = 0; i < 20; i++)
{
printf(" %d" + !i, data[i]);//这里的作用是使得空格只出现在数字中间
}
printf("\n");
}
return;
}
for (i = 1; i <= 20; i++)
{
if (!visited[i])
{
data[k] = i;
if (k == 0 || issu(data[k] + data[k - 1]))
{
visited[i] = 1;
dfs(k + 1);
visited[i] = 0;
}
}
}
}
int issu(int k)
{
int i;
for (i = 2; i * i <= k; i++)
{
if (k % i == 0)
{
return 0;
}
}
return 1;
}
六，求图像的周长
这题应当是六题中相对有一点挑战的题目，一个简明的思路是将问题分成两部分：第一部分是确定图像，第二部分是求已确定的图像的周长。
第一部分使用深度优先搜索即可，第二部分则从左上角遍历到右下角，对于每个是图像的点，判断其上下左右是否为该图像的边界，若是，则周长增加。
如此，经过把问题拆解，可以写出代码如下：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char graph[102][102];
int m, n, x, y;//图形大小m*n，点击(x,y)
int object[102][102];//所求图形
int perimeter;//周长
int dx[8] = { 1, 0, -1, 0, 1, -1, -1, 1 };
int dy[8] = { 0, 1, 0, -1, 1, -1, 1, -1 };//前四个是上下左右，后四个为对角
void dfs(int row, int col);
void getper();
int main()
{
int i;
scanf("%d%d%d%d", &m, &n, &x, &y);
while (m != 0 || n != 0 || x != 0 || y != 0)
{
for (i = 1; i <= m; i++)
{
scanf("%s", graph[i] + 1);
}
//operate
dfs(x, y);
getper();
memset(graph, 0, sizeof(graph));
memset(object, 0, sizeof(object));
perimeter = 0;
scanf("%d%d%d%d", &m, &n, &x, &y);
}
}
void dfs(int row, int col)
{
object[row][col] = 1;
int i, nx, ny;
for (i = 0; i < 8; i++)
{
nx = row + dx[i];
ny = col + dy[i];
if (nx >= 1 && nx <= m && ny >= 1 && ny <= n && !object[nx][ny] && graph[nx][ny] == graph[row][col])
{
dfs(nx, ny);
}
}
}
void getper()
{
int i, j, k, nx, ny;
for (i = 1; i <= m; i++)
{
for (j = 1; j <= n; j++)
{
if (object[i][j])
{
for (k = 0; k < 4; k++)
{
nx = i + dx[k];
ny = j + dy[k];
if (!(nx >= 1 && nx <= m && ny >= 1 && ny <= n && object[nx][ny]))
{
perimeter++;
}
}
}
}
}
printf("%d\n", perimeter);
}
以上就是全部的六道题及相应代码了，总体而言，此次算法考试不算特别难，题目均为noj实验原题，且未出现诸如八数码、木乃伊迷宫、僵尸双来了等较为复杂的问题。根据noj排名来看，有108人满分。不过，对于算法实验来说，考试并不是目的，能够熟练掌握各种基础算法解题，并领会到其思想内涵，也许才是学习这门课的最大意义吧。很遗憾，在这方面我还有待努力。期待未来会更好。