计算机算法设计与分析

由天下分享时间：2024/10/11 3:18:02 加入收藏我要投稿点赞

算法设计与分析

实验报告

班级：姓名：学号：

(备注：共给出5个参考实验案例，根据学号尾数做对应的实验，即如尾号为1，则模仿案例实验123；尾号2，则模仿案例实验234；尾号3，即345；尾号4，同1.)

实验一分治与递归 ?????????????????????????????1 1、基本递归算法??????????????????????????????1 2、棋盘覆盖问题??????????????????????????????2 3、二分搜索????????????????????????????????3 4、实验小结????????????????????????????????5 实验二动态规划算法 ???? ???????????????????????5 1、最长公共子序列问题 ??????????????????????????5 2、最大子段和问题?????????????????????????????7 3、实验小结????????????????????????????????8 实验三贪心算法?? ????????????????????????????8 1、多机调度问题??????????????????????????????8 2、用贪心算法求解最小生成树????????????????????????10 3、实验小结????????????????????????????????12 实验四回溯算法和分支限界法????????????????????????12 1、符号三角形问题 ?????????????????????????????12 2、0—1背包问题??????????????????????????????14 3、实验小结 ????????????????????????????????18 实验五多种排序算法效率比较

1、算法：起泡排序、选择排序、插入排序、shell排序，归并排序、快速排序等............19 2、实验小结 ????????????????????????????????18

计算机算法设计与分析——实验报告

Part1：课程设计过程

设计选题--?题目分析---?系统设计--?系统实现--?结果分析---?撰写报告

Part2：课程设计撰写的主要规范

1. 题目分析：主要阐述学生对题目的分析结果，包括题目描述、分析得出的有关模型、相关定义及假设；

2. 总体设计：系统的基本组成部分，各部分所完成的功能及相互关系；

3. 数据结构设计：主要功能模块所需的数据结构，集中在逻辑设计上；

4. 算法设计：在数据结构基础上，完成算法设计；

5. 物理实现：主要有数据结构的物理存储，算法的物理实现，系统相关的实现。具体在重要结果的截图，测试案例的结果数据，核心算法的实现结果等；

6. 结果分析：对第五步的分析，包括定性分析和定量分析，正确性分析，功能结构分析，复杂性分析等；

7. 结论：学生需对自己的课程设计进行总结，给出评价，并写出设计体会；

8. 附录：带有注释的源代码，系统使用说明等； 9. 参考文献：列出在撰写过程中所需要用到的参考文献。

计算机算法设计与分析——实验报告

实验一分治与递归（4学时）

一：基本递归算法一、实验目的与要求

1、熟悉C/C++语言的集成开发环境；

2、通过本实验加深对递归过程的理解二、实验内容：

掌握递归算法的概念和基本思想，分析并掌握“整数划分”问题的递归算法。三、实验题

任意输入一个整数，输出结果能够用递归方法实现整数的划分。 #include using namespace std; int main() { int a,b,c; int q(int n,int m); cout<<\请输入整数及大于最大加数的数\ cin>>a>>b; c=q(a,b); cout<<\所需要的划分数为：\ return 0; }

int q(int n,int m) { if ((n<1)||(m<1)) return 0; if ((n==1)||(m==1)) return 1; if (n

实验结果：

结果分析：

实验时入得数据为：所要划分的整数是7，他的划分的最大加数的值不得大于7，根据实际其划分的情况为15种，因而可知其程序的运行结果是正确的。

二：棋盘覆盖问题 2

计算机算法设计与分析——实验报告

一、实验目的与要求

1、掌握棋盘覆盖问题的算法； 2、初步掌握分治算法二、实验题：

盘覆盖问题：在一个2k×2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。三、程序代码： #include using namespace std;

int tile=0; //全局变量，表示特殊格的号 int board[1000][1000]; int main() { int tr, tc, dr, dc, size; int tile=0; //全局变量，表示特殊格的号 void chessBoard(int tr, int tc, int dr, int dc, int size); cout<<\输入数据\ cin>>tr>>tc>>dr>>dc>>size; cout<

void chessBoard(int tr, int tc, int dr, int dc, int size)//左上角行号、列号，特殊格的行号、列号棋盘大小 {

if (size == 1) return; //???????tiao chu int t = ++tile, // L型骨牌号？？？？？？

s = size/2; // 分割棋盘 // 覆盖左上角子棋盘 if (dr < tr + s && dc < tc + s)// 特殊方格在此棋盘中 chessBoard(tr, tc, dr, dc, s); else {// 此棋盘中无特殊方格

// 用 t 号L型骨牌覆盖右下角 board[tr + s - 1][tc + s - 1] = t;