程序设计综合实践课程报告
搜索 1 实验
学生姓名 刘芳秀
学院名称 智算
专 业 大类
学 号 3021244240
1. 正方形
1.1 题目分析
先求边长，如果不能整除或者边数小于 4 都直接输出 no，其他情况使用 dfs 深
度优先搜索，当所有的边都被遍历过而且每条边都被使用时输出 yes，所以这个
就可以作为 dfs 的结束条件。在 dfs 内部，先设定一个数组，记录这条边是否被
选择过。用 t 记录边长，当遍历到一条边时，先用 t 减去这条边的边长，如果 t
小于 0，就代表不合适，返回上一个递归，如果等于零，就代表正好，可以直接
进行下一次的递归，而当 t 还大于零的时候，就需要继续减去下一个边长，以此
类推，直到搜索结束。
1.2 题目代码（带注释）
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int m, T, bc;
int a[20];
int dfs(int now, int cnt)
{
if (now == m || cnt == m) {//如果已经把所有的边都遍历或者每条边都被使
用
if (now == m && cnt == m)//如果两个都符合
return 1;//返回 1
return 0;//否则返回 0
}
int vis[20];
memset(vis, 0, sizeof(vis));
int t = bc;
for (int i = now + 1; i <= m; i++) {
if (vis[i] == 0) {//如果这条边没被用过，就用这条边
vis[i] = 1;//代表这条边已经被使用
t -= a[i];//现在的 t 代表还需要的长度
if (t == 0) {//如果还需要的长度等于 0，代表已经构成了一条边
cnt++;//构成的边数加 1
return dfs(i, cnt);//递归
}
else if (t < 0) {//如果这条边的长度大于边长
vis[i] = 0;//代表这条边重新恢复没被使用的状态
return dfs(i - 1, cnt);//递归 i-1 条边
}
}
}
return 1;
}
int main()
{
cin >> T;
for(int k=0;k<T;k++)
{
cin >> m;
int sum = 0;
for (int i = 1; i <= m; i++) {
cin >> a[i];//输入每条边的长度
sum += a[i];//sum 是所有边长度的和
}
if (m < 4) {//如果边数小于 4，不能形成正方形
cout << "no" << endl;//输出 no
break;
}
if (sum % 4 != 0) {//如果 sum 不是 4 的倍数，不能形成正方形
cout << "no" << endl;//输出 no
continue;
}
bc = sum / 4;
sort(a + 1, a + m + 1);//把所有的边按从小到大的顺序排序
if (dfs(0, 0))//从 a[0]，使用的边数是零开始递归，如果返回值是 1
cout << "yes" << endl;
else
cout << "no" << endl;
}
return 0;
}
2. prime circle
2.1 题目分析
本题需要建立一个判断素数的函数，之后使用 dfs，遍历 2 及以后的元素，如果
遍历的位置小于等于 n，就代表可以继续进行，从 1 到 n 找元素（for 循环内），
如果是素数就让 a[i]等于现在的 i，往后遍历，如果已经到 n，就计算 a[n]+a[1]
是不是素数，是就输出。不是的话继续遍历，但是先把 pick[i]赋值为零，代表
没遍历过这个位置。
2.2 题目代码（带注释）
#include <bits/stdc++.h>
using namespace std;
int a[20], vis[20], n;
int isPrime(int k) {
for (int j = 2; j < k; j++ ) {
if(k % j == 0)
return 0;
}
return 1;
}
void dfs(int p) {
if (p > n) {//如果当前元素的序号大于 n
if(isPrime(a[n] + a[1])) {//如果最后一个元素加第一个元素是素数
for (int i = 1; i < n; i++)
cout << a[i] << " ";//输出所有的元素
cout << a[n] << endl;
}
}
else
for (int i = 1; i <= n; i++) {//当前元素的序号小于等于 n
if (isPrime(i + a[p - 1]) && vis[i] == 0) {//如果 i 没遍历过且
i+a[p-1]是素数
a[p] = i;//a[p]等于 i（这样可以保证加起来都是素数）
vis[i] = 1;//记录已经遍历过这个位置的元素
dfs(p + 1);//递归下一个位置的元素
vis[i] = 0;//如果 p+1 大于 n 之后就会执行这条语句，从而可以输出所
有的情况
}
}
}
int main()
{
int b = 1;
while (cin >> n) {
a[1] = 1;//第一个数是 1
vis[1] = 1;//第一个元素已经遍历过
cout << "Case " << b << ":" << endl;
dfs(2);//直接遍历第二个元素
cout << endl;
b++;
}
return 0;
}
评论0