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

《计算机算法与设计分析实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机算法与设计分析实验报告班级：姓名：学号：目录实验一分治与递归……………………………………………………………………………11、基本递归算法………………………………………………………………………………12、棋盘覆盖问题………………………………………………………………………………23、二分搜索……………………………………………………………………………………34、实验小结……………………………………………………………………………………5实验二动态规划算法………………………………………………………………………51、最长公共子序列问题……………………………………………………………………52

2、、最大子段和问题……………………………………………………………………………73、实验小结……………………………………………………………………………………8实验三贪心算法………………………………………………………………………………81、多机调度问题………………………………………………………………………………82、用贪心算法求解最小生成树………………………………………………………………103、实验小结……………………………………………………………………………………12实验四回溯算法和分支限界法………………………………………………………………121、符号三角形问题…………………………………

3、…………………………………………122、0—1背包问题………………………………………………………………………………143、实验小结……………………………………………………………………………………18实验一分治与递归（4学时）一：基本递归算法一、实验目的与要求1、熟悉C/C++语言的集成开发环境；2、通过本实验加深对递归过程的理解二、实验内容：掌握递归算法的概念和基本思想，分析并掌握“整数划分”问题的递归算法。三、实验题任意输入一个整数，输出结果能够用递归方法实现整数的划分。#includeusingnamespacestd;intmain(){inta,b,c;i

4、ntq(intn,intm);cout<<"请输入整数及大于最大加数的数"<>a>>b;c=q(a,b);cout<<"所需要的划分数为："<

5、

6、(m<1))return0;if((n==1)

7、

8、(m==1))return1;if(n

9、，因而可知其程序的运行结果是正确的。二：棋盘覆盖问题一、实验目的与要求1、掌握棋盘覆盖问题的算法；2、初步掌握分治算法二、实验题：盘覆盖问题：在一个2k×2k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。三、程序代码：#includeusingnamespacestd;inttile=0;//全局变量，表示特殊格的号intboard[1000][1000];intmain(){inttr,t

10、c,dr,dc,size;inttile=0;//全局变量，表示特殊格的号voidchessBoard(inttr,inttc,intdr,intdc,intsize);cout<<"输入数据"<>tr>>tc>>dr>>dc>>size;cout<

11、tdr,intdc,intsize)//左上角行号、列号，特殊格的行号、列号棋盘大小{if(size==1)return;//???????tiaochuintt=++tile,//L型骨牌号？？？？？？s=size/2;//分割棋盘//覆盖左上角子棋盘if(dr