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

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<stdio.h>#include<math.h>void main() double x,x1=1,x2=3,f1,f2,f; f1=x1*x1*x1-3*x1-1; f2=

4、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; else if(f1*f>0) x1=x; f1=f; else x2=x; while(fabs(x1-x2)>=0.000001); printf("近似值为： %.7fn",x); printf("与理论值相差为： %.7f",x-1.8793852); 牛顿迭代法：#include<stdio.h>#

5、include<math.h>void 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;while(fabs(x1-x0)>=0.0000001);printf("近似值为： %.7f",x1);printf("与理论值相差： %.7f",x1-1.8793852);2.#include<iostream>using namespace std;int main()int N,i,j,k,l,n=0;cout

6、<<"请输入一个正整数N（1N1000）"<<endl;cin>>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<<"张"<<" 五

7、元有："<<k<<"张"<<" 十元有："<<l<<"张"<<endl;n+;cout<<"一共有："<<n<<"种组合方式"<<endl;return 0;3.源代码：#include <iostream>#include <vector>using namespace std;int pro5 = 3,5,10,16,21 ;/货车保护费i

8、nt sale6 = 0,17,15,7,4,2 ;/二手车销售价格int minmoney = -65536;#define MAX 20int numMAX = 1,2,3,4 ;int n = 0;vector<vector<int>>ps;void solve(int n) vector<vector<int>>ps1;vector<vector<int>>:iterator it;vector<int>s;ps.push_back(s);for (int i = 0; i < n; i+) ps

9、1 = 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() vector<vector<int>>:iterator it;int i = 1;for (it = ps.begin(); it < ps.end(); +it) int money = 0;cout << "第 " <<

10、i << " 种方案:" << endl;i+;for (vector<int>:iterator 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在第 " &

11、lt;< *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;cout <<"t共花费"<<-