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

《算法设计与分析》实验报告
实验项目（二）算法的基本策略
专业、班级学号姓名实验时间实验地点指导教师教学目标
使学生掌握“算法设计与分析”中的基本原理、基本技术和方法，提升计算机问题求解的水平。熟练掌握编程中常见问题的求解策略，培养学生对算法复杂性进行正确分析的能力。
掌握编程求解问题的常用算法策略。
熟练强化深入计算机求解问题的过程。
增强理论结合实际能力，增强获得理论联系实际问题的能力。
培养系统分析能力和团队协作能力。
实验目的及要求
练习运用枚举、迭代、分治、贪心和动态规划等基本算法策略求解问题；
熟练掌握算法基本策略的建模和编码实现。
实验设备（环境）及要求
使用C/C++语言，VisualStudio201X开发环境，Windows系列操作系统环境
成绩评定题号题型能力分值成绩备注设计题分析20设计题分析30设计题分析40报告格式10总成绩实验内容与步骤
编写程序，分别用二分法和牛顿迭代法求解方程x3–3x–1=0在x=2附近的实根，要求计算精确到小数点后7位数字为止，并将求出的近似结果与理论值2cos20比较误差大小。设二分法的初始迭代区间为[1,3]，牛顿迭代法的起点为4。
将一张100元的钞票换成1元、2元、5元和10元的零钱，每种零钞至少一张，编写程序输出所有的换法，尽可能地提高算法效率。
用动态规划求解设备更新问题。
某人打算购买一辆新的小货车用于运货，货车的售价是22万元人民币。货车购买后，每年的各种保险费、养护费等费用如下表：

如果5年内将货车售出，并再购买新车，5年内的二手车销售价如下表：

设计一种购买货车的方案，使5年内用车的总费用最少。
选作：将其中所有的数据，包括售价、年份、各年份的费用和各年份二手车销售价等的数据改为任意值。
1.二分法：
#include<stdio.h>
#include<math.h>
voidmain()
{
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\n",x);
printf("与理论值相差为：%.7f",x-1.8793852);
}
}

牛顿迭代法：
#include<stdio.h>
#include<math.h>
voidmain()
{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.#include<iostream>
usingnamespacestd;
intmain()
{
intN,i,j,k,l,n=0;
cout<<"请输入一个正整数N（1≤N≤1000）"<<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<<"张"<<"五元有："<<k<<"张"<<"十元有："<<l<<"张"<<endl;
n++;
}
}
}
}
}
cout<<"一共有："<<n<<"种组合方式"<<endl;
return0;
}

3.源代码：
#include<iostream>
#include<vector>
usingnamespacestd;
intpro[5]={3,5,10,16,21};//货车保护费
intsale[6]={0,17,15,7,4,2};//二手车销售价格
intminmoney=-65536;
#defineMAX20
intnum[MAX]={1,2,3,4};
intn=0;
vector<vector<int>>ps;
voidsolve(intn){
vector<vector<int>>ps1;