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

《实验项目二：算法的基本策略.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、略求解问题；（2）熟练掌握算法基本策略的建模和编码实现。二、实验设备（环境）及要求使用C/C++语言，VisualStudio201X开发环境，Windows系列操作系统环境三、成绩评定题号题型能力分值成绩备注①设计题分析20②设计题分析30③设计题分析40④报告格式10总成绩一、实验内容与步骤1、编写程序，分别用二分法和牛顿迭代法求解方程x3–3x–1=0在x=2附近的实根，要求计算精确到小数点后7位数字为止，并将求出的近似结果与理论值2cos20°比较误差大小。设二分法的初始迭代区间为[1,3]，牛顿迭代法的起点

3、为4。2、将一张100元的钞票换成1元、2元、5元和10元的零钱，每种零钞至少一张，编写程序输出所有的换法，尽可能地提高算法效率。3、用动态规划求解设备更新问题。某人打算购买一辆新的小货车用于运货，货车的售价是22万元人民币。货车购买后，每年的各种保险费、养护费等费用如下表：如果5年内将货车售出，并再购买新车，5年内的二手车销售价如下表：设计一种购买货车的方案，使5年内用车的总费用最少。选作：将其中所有的数据，包括售价、年份、各年份的费用和各年份二手车销售价等的数据改为任意值。1.二分法：#include

4、.h>#includevoidmain(){doublex,x1=1,x2=3,f1,f2,f;f1=x1*x1*x1-3*x1-1;f2=x2*x2*x2-3*x2-1;if(f1*f2>0)printf("在此区间没有根！");else{do{x=(x1+x2)/2;f=x*x*x-3*x-1;if(f==0)break;elseif(f1*f>0){x1=x;f1=f;}else{x2=x;}}while(fabs(x1-x2)>=0.000001);printf("近似值为：%.7f",x

5、);printf("与理论值相差为：%.7f",x-1.8793852);}}牛顿迭代法：#include#includevoidmain(){doublef0,f1,x0,x1=2;do{x0=x1;f0=3*x0*x0-3;f1=x0*x0*x0-3*x0-1;x1=x0-f1/f0;}while(fabs(x1-x0)>=0.0000001);printf("近似值为：%.7f",x1);printf("与理论值相差：%.7f",x1-1.8793852);}2.#includ

6、eusingnamespacestd;intmain(){intN,i,j,k,l,n=0;cout<<"请输入一个正整数N（1≤N≤1000）"<>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<<"其中一元有："<

7、"<#includeusingnamespacestd;intpro[5]={3,5,10,16,21};//货车保护费intsale[6]={0,17,15,7,4,2};//二手车销售价格intminmoney=-65536;#defineMAX20intnum[MAX]={1,2,3,4};intn=0;vector

8、tor>ps;voidsolve(intn){vector>ps1;vector>::iteratorit;vectors;ps.push_back(s);for(inti=0;i