当前位置: 开发笔记 > 人工智能 > 正文

算法分析与设计西工大noj第二次实验

作者：文女2010_532 | 来源：互联网 | 2023-05-28 12:26

算法分析与设计西工大noj第二次实验ProblemA0-1背包问题时限：1000ms内存限制：10000K总时限：3000ms描述：需对容量为c的背包进行装载。从n个物品中选取装入

算法分析与设计西工大 noj 第二次实验

Problem A 0-1背包问题

时限：1000ms 内存限制：10000K 总时限：3000ms

描述：

需对容量为c 的背包进行装载。从n 个物品中选取装入背包的物品，每件物品i 的重量为wi ，价值为pi 。对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高。

输入：

多个测例，每个测例的输入占三行。第一行两个整数：n（n<=10）和c，第二行n个整数分别是w1到wn，第三行n个整数分别是p1到pn。

n 和 c 都等于零标志输入结束。

输出：

每个测例的输出占一行，输出一个整数，即最佳装载的总价值。

输入样例：

1 2 1 1 2 3 2 2 3 4 0 0

输出样例：

1 4

这是一道典型的01背包。由于n十分小，所以可以采用暴力搜索，也可以采用DP。

其实严格意义上我完全可以把物品的价值搞成1e9，这样就不可以使用DP了，但是数据十分水，也就过去了。

标准解法是暴力

#include #include using namespace std; #define N 20 int n, m; int w[N], v[N]; int ans = 0; inline int max(int x, int y) { return x > y ? x : y; } void dfs(int x, int sw, int sv) { if(x > n) { ans = max(ans, sw); return; } dfs(x+1, sw, sv); if(sv + v[x] <= m){ dfs(x+1, sw + w[x], sv+v[x]); } } int main() { while(scanf("%d%d", &n, &m), n||m) { ans = 0; for(int i = 1; i <= n; i++) scanf("%d", v+i); for(int i = 1; i <= n; i++) scanf("%d", w+i); dfs(1, 0, 0); printf("%d\n", ans); } return 0; }

Problem B 装载问题

时限：1000ms 内存限制：10000K 总时限：3000ms

描述：

有两艘船，载重量分别是c1、 c2，n个集装箱，重量是wi (i=1…n)，且所有集装箱的总重量不超过c1+c2。确定是否有可能将所有集装箱全部装入两艘船。

输入：

多个测例，每个测例的输入占两行。第一行一次是c1、c2和n（n<=10）；第二行n个整数表示wi (i=1…n)。n等于0标志输入结束。

输出：

对于每个测例在单独的一行内输出Yes或No。

输入样例：

7 8 2 8 7 7 9 2 8 8 0 0 0

输出样例：

Yes No

其实本质上还是一道背包问题。

把第一个小船当成背包，在不超载的前提下放置尽可能重的物品，以便于为第二艘小船留下余地。

#include #include using namespace std; #define N 20 int c1, c2, n; int w[N]; int sum; bool flag = false; void dfs(int x, int s) { if(x > n){ if(s <= c1 && (sum - s) <= c2) flag = true; return ; } dfs(x+1, s); dfs(x+1, s+w[x]); } int main() { while(scanf("%d%d%d", &c1, &c2, &n), n) { flag = false; sum = 0; for(int i = 1; i <= n; i++) scanf("%d", w+i); for(int i = 1; i <= n; i++) sum += w[i]; dfs(1, 0); if(flag) { puts("Yes"); } else { puts("No"); } } return 0; }

Problem C 堡垒问题

时限：1000ms 内存限制：10000K 总时限：3000ms

描述：

城堡是一个4×4的方格，为了保卫城堡，现需要在某些格子里修建一些堡垒。城堡中的某些格子是墙，其余格子都是空格，堡垒只能建在空格里，每个堡垒都可以向上下左右四个方向射击，如果两个堡垒在同一行或同一列，且中间没有墙相隔，则两个堡垒都会把对方打掉。问对于给定的一种状态，最多能够修建几个堡垒。

输入：

每个测例以一个整数n（1<=n<=4）开始，表示城堡的大小。接下来是n行字符每行n个，‘X’表示该位置是墙，‘.’表示该位置是空格。n等于0标志输入结束。

输出：

每个测例在单独的一行输出一个整数：最多修建堡垒的个数。

输入样例：

4 .X.. .... XX.. .... 2 XX .X 3 .X. X.X .X. 3 ... .XX .XX 4 .... .... .... .... 0

输出样例：

5 1 5 2 4

#include #include using namespace std; #define N 6 char a[N][N]; int n; int ans = 0; inline void get(int val, int &x, int &y) { x = val/n; y = val%n; } bool ck(int x, int y) { for(int i = x+1; i if(a[i][y] == 'o') return 0; else if(a[i][y] == 'X') break; } for(int i = x-1; i >= 0; i--){ if(a[i][y] == 'o') return 0; else if(a[i][y] == 'X') break; } for(int i = y+1; i if(a[x][i] == 'o') return 0; else if(a[x][i] == 'X') break; } for(int i = y-1; i >= 0; i--){ if(a[x][i] == 'o') return 0; else if(a[x][i] == 'X') break; } return true; } void dfs(int p, int s) { if(p >= n*n){ if(s > ans) ans = s; //DEBUG /* if(s == 4){ for(int i = 0; i <4; i++) { for(int j = 0; j <4; j++) { printf("%c", a[i][j]); } puts(""); } puts(""); } */ //ENDDEBUG return ; } dfs(p+1, s); int x, y; get(p, x, y); if(ck(x, y) && a[x][y] == '.') { a[x][y] = 'o'; dfs(p+1, s+1); a[x][y] = '.'; } } int main() { while(scanf("%d", &n), n){ for(int i = 0; i ans = 0; dfs(0, 0); printf("%d\n", ans); } // n = 4; // for(int i = 0; i <16; i++) // { // int x, y;; // get(i, x, y); // printf("(%d, %d) ", x, y); // } }

Problem D 8皇后问题

时限：1000ms 内存限制：10000K 总时限：3000ms

描述：

输出8皇后问题所有结果。

输入：

没有输入。

输出：

每个结果第一行是No n：的形式，n表示输出的是第几个结果；下面8行，每行8个字符，‘A’表示皇后，‘.’表示空格。不同的结果中，先输出第一个皇后位置靠前的结果；第一个皇后位置相同，先输出第二个皇后位置靠前的结果；依次类推。

输入样例：

无

输出样例：

输出的前几行： No 1: A....... ....A... .......A .....A.. ..A..... ......A. .A...... ...A.... No 2: A....... .....A.. .......A ..A..... ......A. ...A.... .A...... ....A...

这一道题目所使用的数据结构十分巧妙，由于每一行仅仅只可以有一个皇后，所以采用一维数组就可以。

注意时时刻刻想着剪枝。

判断对角线的方法是：abs(stac[i] - val) == abs(i-row)

#include #include #include using namespace std; #define N 12 int stac[N]; int cnt = 0; bool ck(int row, int val) { for(int i = 1; i <= 8; i++) { if(stac[i] == 0 || i == row) continue; if(stac[i] == val || abs(stac[i] - val) == abs(i-row)) return false; } return true; } inline void Print(int x) { for(int i = 1; i putchar('A'); for(int i = x+1; i <= 8; i++) putchar('.'); puts(""); } void dfs(int x) { if(x > 8) { printf("No %d:\n", ++cnt); for(int i = 1; i <= 8; i++) { Print(stac[i]); } return; // for(int i = 1; i <= 8; i++) printf("%d ", stac[i]); //balabala //return ; //DEBUG // exit(0); } for(int i = 1; i <= 8; i++) { if(ck(x, i)) { stac[x] = i; dfs(x+1); stac[x] = 0; } } } int main() { dfs(1); return 0; }

Problem E 素数环问题

时限：1000ms 内存限制：10000K 总时限：3000ms

描述：

把1到20这重新排列，使得排列后的序列A满足：

a. 任意相邻两个数之和是素数

b. 不存在满足条件a的序列B使得：A和B的前k（0 <= k <= 19）项相同且B的第k+1项比A的第k+1项小。(即按字典序排列的第一项)

输入：

没有输入。

输出：

输出A，两个数字之间用一个空格隔开，第一个数字前面和最后一个数字后面没有空格。

输入样例：

输出样例：

标准解法

如果要是要求输出所有的素数环，那么就应该采用求全排列+剪枝+判断字典序

贪心解法

但是可以使用贪心来做。从前往后先试1，然后再试2...如果找到满足条件的环，就直接输出。

打表解法

这么小的数据量，直接人脑使用贪心法进行计算，来一个puts("")

//采取贪心的思想，从小到大选择 #include #include using namespace std; #define N 25 bool v[N]; int stac[N]; bool prim[40]; void dfs(int x) { if(x > 20) { for(int i = 1; i <= 20; i++) { if(i != 20) printf("%d ", stac[i]); else printf("%d", stac[20]); } puts(""); exit(0); } for(int i = 1; i <= 20; i++) { if(!v[i] && (x == 1 || x <20 && x > 1 && (prim[stac[x-1] + i]) ||(x == 20 && (prim[stac[1] + i])))) { stac[x] = i; v[i] = 1; dfs(x+1); v[i] = 0; stac[x] = 0; } } } int main() { for(int i = 2; i <= 45; i++) { bool flag = true; for(int j = 2; j*j <= i; j++) if(i % j == 0){ flag = false; break; } if(!flag) prim[i] = 0; else prim[i] = 1; } dfs(1); // for(int i = 1; i <= 45; i++) if(prim[i]) // printf("%d ", i); return 0; }

Problem F 迷宫问题

时限：1000ms 内存限制：10000K 总时限：3000ms

描述：

给一个20×20的迷宫、起点坐标和终点坐标，问从起点是否能到达终点。

输入：

多个测例。输入的第一行是一个整数n，表示测例的个数。接下来是n个测例，每个测例占21行，第一行四个整数x1，y1，x2，y2是起止点的位置（坐标从零开始），（x1，y1）是起点，（x2，y2）是终点。下面20行每行20个字符，’.’表示空格；’X’表示墙。

输出：

每个测例的输出占一行，输出Yes或No。

输入样例：

2 0 0 19 19 .................... XXXXXXXXXXXXXXXXXXXX .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... 0 0 19 19 .................... XXXXXXXXXXXXXXXXXXX. .................... .XXXXXXXXXXXXXXXXXXX .................... XXXXXXXXXXXXXXXXXXX. .................... .XXXXXXXXXXXXXXXXXXX .................... XXXXXXXXXXXXXXXXXXX. .................... .XXXXXXXXXXXXXXXXXXX .................... XXXXXXXXXXXXXXXXXXX. XXXXXXXXXXXXXXXXXXX. XXXXXXXXXXXXXXXXXXX. XXXXXXXXXXXXXXXXXXX. .................... .XXXXXXXXXXXXXXXXXXX ....................

输出样例：

No Yes

直接进行DFS图的遍历

#include #include using namespace std; #define N 30 pair s, t; char a[N][N]; bool v[N][N]; const int n = 20; int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0}; inline bool ck(int x, int y) { if(x <0 || x >= n || y <0 || y >= n) return false; if(v[x][y]) return false; if(a[x][y] == 'X') return false; return true; } bool dfs(int nx, int ny) { if(nx == t.first && ny == t.second){ return 1; } for(int k = 0; k <4; k++) { int x = nx + dx[k]; int y = ny + dy[k]; if(ck(x, y)) { v[x][y] = 1; if(dfs(x, y)) return 1; } } return 0; } int main() { int T; cin >> T; while(T--) { for(int i = 0; i <= 20; i++) for(int j = 0; j <= 20; j++) v[i][j] = false; scanf("%d%d%d%d", &s.first, &s.second, &t.first, &t.second); for(int i = 0; i if(dfs(s.first, s.second)) { puts("Yes"); } else { puts("No"); } } return 0; }

Problem G 踩气球

时限：1000ms 内存限制：10000K 总时限：3000ms

描述：

六一儿童节，小朋友们做踩气球游戏，气球的编号是1～100，两位小朋友各踩了一些气球，要求他们报出自己所踩气球的编号的乘积。现在需要你编一个程序来判断他们的胜负，判断的规则是这样的：如果两人都说了真话，数字大的人赢；如果两人都说了假话，数字大的人赢；如果报小数字的人说的是真话而报大数字的人说谎，则报小数字的人赢（注意：只要所报的小数字是有可能的，即认为此人说了真话）。

输入：

输入为两个数字，0 0表示结束；

输出：

输出为获胜的数字。

输入样例：

36 62 49 343 0 0

输出样例：

62 49

这一道题目使我畏惧，真的是太太太离谱了！

暴力搜索法：

虽然看起来有很多情况，但是由于int范围内的相乘大于int的数字其实并没有多少，所以也还可以

#include #include #include using namespace std; int small, big;//大的数字以及小的数字 int mul1, mul2;//已经当前已经踩过的气球的乘积 bool f1, f2;//记录说的是不是真话 void dfs(int k) { if(k <= 1){ if(mul1 == small && mul2 == big) { f1 = 1, f2 = 1; } else if( (!f1 || !f2) && mul1 == small ){ f1 = 1, f2 = 0; } else if(!f1&&!f2&&mul2 == big){ f1 = 0, f2 = 1; } return ; } if(mul1*k <= small && small % k == 0){ mul1 *= k; dfs(k-1); mul2 /= k; } if(mul2 * k <= big && big % k == 0){ mul2 *= k; dfs(k-1); mul2 /= k; } dfs(k-1); } int main() { while(scanf("%d%d", &big, &small), big || small){ if(small > big) swap(small, big); mul1 = 1, mul2 = 1; f1 = 0, f2 = 0; dfs(100); if(f1 && f2 || !f1 && !f2){ printf("%d\n", big); } else{ if(f1) printf("%d\n", small); else printf("%d\n", big); } } //cout < return 0; }

Problem H 字母转换

时限：1000ms 内存限制：10000K 总时限：3000ms

描述：

通过栈交换字母顺序。给定两个字符串，要求所有的进栈和出栈序列（i表示进栈，o表示出栈），使得字符串2在求得的进出栈序列的操作下，变成字符串1。输出结果需满足字典序。例如TROT 到 TORT:

[

i i i i o o o o

i o i i o o i o

]

输入：

给定两个字符串，第一个字符串是源字符串，第二个字符是目标目标字符串。

输出：

所有的进栈和出栈序列,输出结果需满足字典序

输入样例：

madam adamm bahama bahama long short eric rice

输出样例：

[ i i i i o o o i o o i i i i o o o o i o i i o i o i o i o o i i o i o i o o i o ] [ i o i i i o o i i o o o i o i i i o o o i o i o i o i o i o i i i o o o i o i o i o i o i o i o ] [ ] [ i i o i o i o o ]

#include #include #include #include #include using namespace std; #define N 100005 char a[N], b[N]; stack st; vector op; int p = 1; int q = 1; int len = 0; void dfs(int n) { if(n > 2 * len) { for(int i = 0; i { if(i != op.size() - 1) printf("%c ", op[i]); else printf("%c", op[i]); } puts(""); return; } if(p <= len) { op.push_back('i'); st.push(a[p]); p++; dfs(n+1); op.pop_back(); st.pop(); p--; } if(st.size() && st.top() == b[q]) { op.push_back('o'); char tmp = st.top(); st.pop(); q++; dfs(n+1); q--; st.push(tmp); op.pop_back(); } } int main() { //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); while(scanf("%s%s", a+1, b+1) != EOF) { int len1 = strlen(a+1); int len2 = strlen(b+1); if(len1 != len2){ printf("[\n]\n"); continue; } len = len1; printf("[\n"); dfs(1); printf("]\n"); } return 0; }

Problem I 农场灌溉问题

时限：1000ms 内存限制：10000K 总时限：3000ms

描述：

一农场由图所示的十一种小方块组成，蓝色线条为灌溉渠。若相邻两块的灌溉渠相连则只需一口水井灌溉。

输入：

给出若干由字母表示的最大不超过50×50具体由(m，n)表示，的农场图

输出：

编程求出最小需要打的井数。每个测例的输出占一行。当M=N=-1时结束程序。

输入样例：

2 2 DK HF 3 3 ADC FJK IHE -1 -1

输出样例：

2 3

简直是带模拟

需要注意判断可达性的时候，不仅仅与当前的格子有关系，并且与其他的格子有关系。

#include #include using namespace std; bool th[128][5]; int n,m; char a[100][100]; bool v[100][100]; void init(); void dfs(int x, int y) { v[x][y] = 1; int r, c; //0 r = x, c = y-1; if(r >= 1 && r <= n && c >= 1 && c <= m && !v[r][c]){ if(th[a[x][y]][0] && th[a[r][c]][2]){ dfs(r, c); } } //1 r = x-1, c = y; if(r >= 1 && r <= n && c >= 1 && c <= m && !v[r][c]){ if(th[a[x][y]][1] && th[a[r][c]][3]){ dfs(r, c); } } //2 r = x, c = y+1; if(r >= 1 && r <= n && c >= 1 && c <= m && !v[r][c]){ if(th[a[x][y]][2] && th[a[r][c]][0]){ dfs(r, c); } } //3 r = x+1, c = y; if(r >= 1 && r <= n && c >= 1 && c <= m && !v[r][c]){ if(th[a[x][y]][3] && th[a[r][c]][1]){ dfs(r, c); } } } int main() { init(); while(scanf("%d%d", &n, &m), n!=-1 || m!=-1) { for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) v[i][j] = 0; for(int i = 1; i <= n; i++) scanf("%s", a[i] + 1); int ans = 0; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) { if(!v[i][j]) { dfs(i, j); ans ++; } } printf("%d\n", ans); // for(int i = 1; i <= n; i++) // { // for(int j = 1; j <= m; j++) // cout < // puts(""); // } } return 0; } void init() { th['A'][0] = 1; th['A'][1] = 1; th['B'][1] = 1; th['B'][2] = 1; th['C'][0] = 1; th['C'][3] = 1; th['D'][2] = 1; th['D'][3] = 1; th['E'][1] = 1; th['E'][3] = 1; th['F'][0] = 1; th['F'][2] = 1; th['G'][0] = 1; th['G'][1] = 1; th['G'][2] = 1; th['H'][0] = 1; th['H'][1] = 1; th['H'][3] = 1; th['I'][0] = 1; th['I'][2] = 1; th['I'][3] = 1; th['J'][1] = 1; th['J'][2] = 1; th['J'][3] = 1; th['K'][0] = 1; th['K'][1] = 1; th['K'][2] = 1; th['K'][3] = 1; }

Problem J 求图像的周长

时限：1000ms 内存限制：10000K 总时限：3000ms

描述：

给一个用 . 和X表示的图形，图形在上、下、左、右、左上、左下、右上、右下8个方向都被看作是连通的，并且图像中间不会出现空洞，求这个图形的边长。

输入：

首先给出m、n、x、y四个正整数，下面给出m×n的图形，x、y表示点击的位置，全0表示结束。

输出：

点击的图形的周长。

输入样例：

2 2 2 2 XX XX 6 4 2 3 .XXX .XXX .XXX ...X ..X. X... 0 0 0 0

输出样例：

8 18

#include #include using namespace std; #define N 10005 int n, m, sx, sy; char a[N][N]; bool v[N][N]; int ans = 0; int dx[8] = {-1, -1, -1 ,0, 0, 1, 1, 1}; int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1}; int lenth(int nx, int ny) { int all = 4; static const int qx[4] = {-1, 0, 0, 1}; static const int qy[4] = {0, -1, 1, 0}; for(int k = 0; k <4; k++) { int x = nx + qx[k]; int y = ny + qy[k]; if(x <1 || x > n || y <0 || y > m) continue; if(a[x][y] == 'X')all --; } return all; } void dfs(int nx, int ny) { v[nx][ny] = 1; ans += lenth(nx, ny); for(int k = 0; k <8; k++) { int x = dx[k] + nx; int y = dy[k] + ny; if(v[x][y]) continue; if(a[x][y] != 'X') continue; dfs(x, y); } } int main() { while(scanf("%d%d%d%d", &n, &m, &sx, &sy), n || m || sx || sy) { for(int i = 1; i <= n; i++) scanf("%s", a[i]+1); for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) v[i][j] = 0; ans = 0; dfs(sx, sy); printf("%d\n", ans); } return 0; }

Problem K 图的m着色问题

时限：1000ms 内存限制：10000K 总时限：3000ms

描述：

给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。如果有一种着色法使G中每条边的2个顶点着不同颜色，则称这个图是m可着色的。图的m着色问题是对于给定图G和m种颜色，找出所有不同的着色法。

输入：

第1行有3个正整数n，r 和m（n <20,r <200,m <10），表示给定的图G有n个顶点和r条边，m种颜色。顶点编号为0，1，2，…，n-1。接下来的r行中，每行有2个正整数u,v，表示图G 的一条边(u,v)。

输出：

输出不同的着色方案的总数。

输入样例：

3 2 2 0 1 1 2

输出样例：

2

#include #include using namespace std; #define N 25 int a[N][N]; int c[N]; int n, r, m; int ans = 0; inline bool ck(int x, int val) { for(int y = 1; y { if(!a[x][y]) continue; if(val == c[y]) return 0; } return true; } void dfs(int x) { if(x > n){ ans ++; // for(int i = 1; i <= n; i++) printf("%d ", c[i]); // puts(""); return; } for(int i = 1; i <= m; i++) { if(ck(x, i)) { c[x] = i; dfs(x+1); c[x] = 0;//浅浅回复一下 } } } int main() { scanf("%d%d%d", &n, &r, &m); for(int i = 1; i <= r; i++) { int u, v; scanf("%d%d", &u, &v); u++, v++; a[u][v] = 1; a[v][u] = 1; } dfs(1); printf("%d\n", ans); return 0; }

Problem L 三阶幻方

时限：1000ms 内存限制：10000K 总时限：3000ms

描述：

三阶幻方是最简单的幻方，又叫九宫格，是由1,2,3,4,5,6,7,8,9九个数字组成的一个三行三列的矩阵，其对角线、横行、纵向的的和都为15。

输入：

无

输出：

按字典序输出所有的满足条件的幻方矩阵，每两个数字之间带一个空格，行尾无空格，每个幻方后带一个空行。

无输入以及输出样例

//幻方！都可以幻方！！！！ #include #include #include using namespace std; bool v[12]; int a[4][4]; inline bool judge(int x, int y, int val) { //DEBUG //return true; int sum = 0; if(x == 0 && y == 2){ for(int i = 0; i <3; i++) sum += a[0][i]; if(sum == 15) return true; else return false; } if(x == 1 && y == 2){ for(int i = 0; i <3; i++) sum += a[1][i]; if(sum == 15) return true; else return false; } if(x == 2 && y == 0) { int s1 = 0, s2 = 0;; for(int i = 0; i <3; i++) s1 += a[i][0]; s2 += a[0][2] + a[1][1] + a[2][0];; if(s2 == 15 && s1 == 15) return true; else return false; } if(x == 2 && y == 1){ for(int i = 0; i <3; i++) sum += a[i][1]; if(sum == 15) return true; else return false; } if(x == 2 && y == 2){ int s1 = 0, s2 = 0, s3 = 0; for(int i = 0; i <3; i ++) s1 += a[i][2]; for(int i = 0; i <3; i ++) s2 += a[i][i]; for(int i = 0; i <3; i ++) s3 += a[2][i]; if(s1 == 15 && s2 == 15 && s3 == 15) return true; else return false; } return true; } //int dede = 0; void dfs(int p) { if(p >= 3*3) { for(int i = 0; i <3; i++) { for(int j = 0; j <3; j++) { if(j <2) printf("%d ", a[i][j]); else printf("%d", a[i][j]); } puts(""); } puts(""); //if(++dede >= 5) exit(0); } int nx = p/3; int ny = p%3; for(int i = 1; i <= 9; i++) { a[nx][ny] = i; if(judge(nx, ny, i) && !v[i]){ v[i] = 1; dfs(p+1); v[i] = 0; } a[nx][ny] = 0; } } int main() { dfs(0); return 0; }