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

计算机算法与设计分析

实 验 报 告

班级： 姓名： 学号：

目录

实验一 分治与递归 ?????????????????????????????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

计算机组织与体系结构——实验报告

实验一 分治与递归（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

if (n==m) return q(n,m-1)+1; return q(n,m-1)+q(n-m,m);

实验结果：

结果分析：

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

1

计算机组织与体系结构——实验报告

二：棋盘覆盖问题 一、实验目的与要求

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<

chessBoard(tr, tc, dr, dc, size); for(int i=1;i<=size;i++) { }

for(int j=1;j<=size;j++) cout<

return 0;

}

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 {// 此棋盘中无特殊方格

2