《算法分析与设计》
实 验 报 告
二 0 二一年三月
目 录
实验 1.3 程序执行过程分析
1. 实验目的
（1） 掌握程序执行过程的分析
2. 实验任务
（1）分析下面的算法在样例输入情况下程序的执行过程及结果
（2）上机实验，验证(1）的分析过程及结果是否正确性。
3. 实验环境
3.1 硬件环境
（1） 计算机：DESKTOP-THJBJFO
（2） CPU: AMD Ryzen 7 4800H with Radeon Graphics
2.90 GHz
（3） RAM：16GB
3.2 软件环境
（1） 操作系统：Windows10 家庭中文版
（2） 开发工具：Visual Studio 2019
4. 实验步骤及结果
4.1 实验预习
4.1.1 该问题的自然语言描述法
输入：输入整型数据 n,k 和字符型数组 chess[][]，其中#表示可以摆放
棋子的位置，.表示不能摆放。
输出：整型 ans 的值，表示可以摆放的方式的总数。
算法描述：
（1）若 k=0，则 ans 加 1 并返回。
（2）若 x 的值大于 n，则返回。
（3）其他情况下，进行双重循环，循环变量均为 0 到 n，如果 sign[j]为
0 并且 chess[i][j]的值为字符‘#’，则赋值 sign[j]为 1;再递归调用 dfs 函
数，而后再赋值 sign[j]为 0。
程序流程描述
如图 1 所示。
4.1.2 伪代码描述
输入：n,k,chess[i]
输出：ans;
算法：
if k == 0 then ans++ return;
if x>n then return;
for(i = x;i<=n;i++)do
for(j = 1;j<=n;j++)do
sign[j] = 1;
dfs(i+1,k-1);
sign[j] = 0;
图 1 程序流程图
4.1.3 程序代码
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
- 1
- 2
- 3
- 4
- 5
前往页