实验项目二：算法的基本策略

1、算法设计与分析实验报告实验项目（二） 算法的基本策略专业、班级学号姓名实验时间实验地点指导教师教学目标使学生掌握“算法设计与分析”中的基本原理、基本技术和方法，提升计算机问题求解的水平。熟练掌握编程中常见问题的求解策略，培养学生对算法复杂性进行正确分析的能力。（1） 掌握编程求解问题的常用算法策略。（2） 熟练强化深入计算机求解问题的过程。（3） 增强理论结合实际能力，增强获得理论联系实际问题的能力。（4） 培养系统分析能力和团队协作能力。一、 实验目的及要求（1） 练习运用枚举、迭代、分治、贪心和动态规划等基本算法策略求解问题；（2） 熟练掌握算法基本策略的建模和编码实现。二、 实验设备（环

2、境）及要求使用C/C+语言，Visual Studio 201X开发环境，Windows系列操作系统环境三、 成绩评定题号题型能力分值成绩备注设计题分析20设计题分析30设计题分析40报告格式10总成绩四、 实验内容与步骤1、 编写程序，分别用二分法和牛顿迭代法求解方程x3 3x 1 = 0在x = 2附近的实根，要求计算精确到小数点后7 位数字为止，并将求出的近似结果与理论值2cos20 比较误差大小。设二分法的初始迭代区间为 1, 3，牛顿迭代法的起点为4。2、 将一张100 元的钞票换成1 元、2元、5 元和10 元的零钱，每种零钞至少一张，编写程序输出所有的换法，尽可能地提高算法效率。

3、3、 用动态规划求解设备更新问题。某人打算购买一辆新的小货车用于运货，货车的售价是22 万元人民币。货车购买后，每年的各种保险费、养护费等费用如下表：如果5年内将货车售出，并再购买新车，5 年内的二手车销售价如下表：设计一种购买货车的方案，使5 年内用车的总费用最少。选作：将其中所有的数据，包括售价、年份、各年份的费用和各年份二手车销售价等的数据改为任意值。1.二分法：#include#includevoid main() double x,x1=1,x2=3,f1,f2,f; f1=x1*x1*x1-3*x1-1; f2=x2*x2*x2-3*x2-1; if(f1*f20) printf(

4、在此区间没有根！); else do x=(x1+x2)/2; f=x*x*x-3*x-1; if(f=0) break; else if(f1*f0) x1=x; f1=f; else x2=x; while(fabs(x1-x2)=0.000001); printf(近似值为： %.7fn,x); printf(与理论值相差为： %.7f,x-1.8793852); 牛顿迭代法：#include#includevoid main()double f0,f1,x0,x1=2;do x0=x1; f0=3*x0*x0-3; f1=x0*x0*x0-3*x0-1; x1=x0-f1/f0;whi

5、le(fabs(x1-x0)=0.0000001);printf(近似值为： %.7f,x1);printf(与理论值相差： %.7f,x1-1.8793852);2.#includeusing namespace std;int main()int N,i,j,k,l,n=0;cout请输入一个正整数N（1N1000）N;for(i=1;i=N;i+)for(j=1;j=N/2;j+)for(k=1;k=N/5;k+)for(l=1;l=N/10;l+) if(i*1+j*2+k*5+l*10=N)cout其中一元有：i张 二元有：j张 五元有：k张 十元有：l张endl;n+;cout一共

6、有：n种组合方式endl;return 0;3.源代码：#include #include using namespace std;int pro5 = 3,5,10,16,21 ;/货车保护费int sale6 = 0,17,15,7,4,2 ;/二手车销售价格int minmoney = -65536;#define MAX 20int numMAX = 1,2,3,4 ;int n = 0;vectorvectorps;void solve(int n) vectorvectorps1;vectorvector:iterator it;vectors;ps.push_back(s);fo

7、r (int i = 0; i n; i+) ps1 = ps;for (it = ps1.begin(); it != ps1.end(); +it) (*it).push_back(numi);for (it = ps1.begin(); it != ps1.end(); +it) ps.push_back(*it);void show() vectorvector:iterator it;int i = 1;for (it = ps.begin(); it ps.end(); +it) int money = 0;cout 第 i 种方案: endl;i+;for (vector:ite

8、rator sit = (*it).begin(); sit != (*it).end(); +sit) if (sit = (*it).begin() money = money - pro*sit - 1 + sale*sit - 22;else money = money - pro*sit - *(sit - 1) - 1 + sale*sit - *(sit - 1) - 22;cout t在第 *sit 年卖出并购入新车 endl;if (*it).empty() money = money - pro4 + sale5 - 22;cout t在第 5 年卖出并购入新车 endl;else money =money-pro4 - *(*it).end()-1) + sale5 - *(*it).end()-1) - 22;cout t在第 5 年卖出并购入新车 endl