算法与程序设计实验报告.docx
《算法与程序设计实验报告.docx》由会员分享，可在线阅读，更多相关《算法与程序设计实验报告.docx（16页珍藏版）》请在冰点文库上搜索。
算法与程序设计实验报告
算法与程序设计实验报告二（4学时）
实验目的：
1、掌握迭代算法的三方面工作；
2、了解递推算法，掌握递推算法的思想；
3、掌握递归算法的程序编写；。
4、了解分治算法的思想；
5、熟练使用二分查找方法实现代码的编写。
实验内容：
1、n!
的递归算法的编写
2、裴波那契（Fibonacci）数列的定义为：
它的第1项和第2项均为1，以后各项为其前两项之和。
若裴波那契数列中的第n项用Fib（n）表示，
则计算公式为：
1（n=1或2）
Fib（n）=
Fib（n-1）+Fib（n-2）（n>=2）
试编写出计算Fib（n）的递归算法
3、在一个给定的n个元素的有序序列中查找出与给定关键字x相同的元素的具体位置。
即输入一个n个元素的序列，其中n个元素是按从小到大的顺序排列的，查找是否存在给定的值x。
实验代码：
1、n!
的递归算法的编写。
#include
intdigui（intn）
{
if（n==1）
return1;
else
returnn*digui（n-1）;
}
voidmain（）
{
intn;
printf（"请输入待求阶乘数（小于15的一个数）：
"）;
scanf（"%d",&n）;
printf（"结果为：
%d\n",digui（n））;
}
2、计算Fib（n）的递归算法
#include
longFib（intn）{
if（n==1||n==2）//终止递归条件
return1;
else
returnFib（n-1）+Fib（n-2）;
}
voidmain（）
{
intn;
printf（"请输入裴波那契数列的待求项数：
"）;
scanf（"%d",&n）;
printf（"裴波那契数列第%d项值为%ld\n",n,Fib（n））;
}
3、二分查找法的实现。
#include
intBinarySearch（inta[],intn,intx）/*二分查找功能函数*/
{
intl=0,r=n,i;
while（l<=r）{
i=（l+r）/2;
if（x==a[i]）returni;
elseif（xelsel=i+1;
}
return-1;
}
voidmaopao（inta[]）/*冒泡排序功能函数*/
{
inti,j;
intn=10;
for（i=0;ifor（j=0;jif（a[j]>a[j+1]）
{
inttemp;
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
voidmain（）
{
inti,a[10],x;
intflag=-1;
printf（"请输入10个带查找数据（空格分隔）：
"）;
for（i=0;i<10;i++）
scanf（"%d",&a[i]）;
maopao（a）;
printf（"带查序列有序化后变为：
"）;
for（i=0;i<10;i++）
printf（"%d,",a[i]）;
printf（"\n"）;
printf（"请输入待查关键字:
"）;
scanf（"%d",&x）;
flag=BinarySearch（a,10,x）;
if（flag==-1）
printf（"未找到带查关键字！
\n"）;
else
printf（"找到关键字，位于有序序列的第%d个位置！
\n",flag+1）;
}
算法与程序设计实验报告三（4学时）
实验目的：
6、了解贪心算法思想
7、掌握贪心法典型问题，如背包问题、作业调度问题等。
实验内容：
4、键盘输入一个高精度的正整数n（n<10位）去掉任意s个数字后剩下的数字按原左右次序组成一个新的正整数。
编程对给定的n和s，寻找一种方案，使得剩下的数最小。
5、设计实现超市收银程序，假设顾客在超市购买各种商品，来到收银台结账，收银员具有面值为100，20，10，5和1元的纸币和各种面值为5角、2角、1角的硬币。
设计程序计算顾客各种所买商品的钱数，并根据顾客所付的钱数输出零钱的数目及要找的各种货币的数目。
算法思想：
贪心算法的基本思路
1.建立数学模型来描述问题。
2.把求解的问题分成若干个子问题。
3.对每一子问题求解，得到子问题的局部最优解。
4.把子问题的解局部最优解合成原来解问题的一个解。
实验代码：
1.键盘输入一个高精度的正整数n（n<10位）去掉任意s个数字后剩下的数字按原左右次序组成一个新的正整数。
编程对给定的n和s，寻找一种方案，使得剩下的数最小。
#include
#include
#defineM100
main（）
{charch[M];
intr[M],d[M],l,s,i,j,k;
printf（"请输入正整数：
"）;
gets（ch）;
printf（"请输入删除的位数：
"）;
scanf（"%d",&s）;
l=0;
for（i=0;ch[i]!
='\0';i++）
{
r[i]=i;
l++;
}
for（i=0;i{
for（j=0;jif（ch[j]>ch[j+1]）
break;
if（j==l-i）
k=l-i-1;
elsek=j;
d[i]=r[k];
for（j=k;j{
ch[j]=ch[j+1];
r[j]=r[j+1];
}
ch[j]='\0';
}
printf（"删除%d后最小的整数为:
%s\n",s,ch）;
printf（"删除的数位为:
"）;
for（i=0;iprintf（"%d\t",d[i]+1）;
printf（"\n"）;
return0;
}
2.设计实现超市收银程序，假设顾客在超市购买各种商品，来到收银台结账，收银员具有面值为100，20，10，5和1元的纸币和各种面值为5角、2角、1角的硬币。
设计程序计算顾客各种所买商品的钱数，并根据顾客所付的钱数输出零钱的数目及要找的各种货币的数目。
#include
#include
voidmain（）
{
doubleprice,total=0,givemoney,leamoney;
intn,i,k=0,m=0,x=0,y=0;
printf（"请输入商品的数目:
"）;
scanf（"%d",&n）;
printf（"输入每件商品的价格:
\n"）;
for（i=1;i<=n;i++）
{
printf（"第%d件:
",i）;
scanf（"%lf",&price）;
total=total+price;
}
printf（"总的价格=%5.2f\n",total）;
printf（"输入顾客所给的钱:
\n"）;
scanf（"%lf",&givemoney）;
leamoney=givemoney-total;
printf（"剩余的钱为%5.2f\n",leamoney）;
printf（"\n各种货币的数目如下:
\n"）;
while（leamoney>=100）
{
leamoney=leamoney-100;
k++;
if（leamoney<100）
printf（"100元=%d张\n",k）;
}
while（leamoney>=20）
{
leamoney=leamoney-20;
x++;
if（leamoney<20）
printf（"20元=%d张\n",x）;
}
while（leamoney>=10）
{
leamoney=leamoney-10;
printf（"10元=1张\n"）;
}
while（leamoney>=5）
{
leamoney=leamoney-5;
printf（"5元=1张\n"）;
}
while（leamoney>=1）
{
leamoney=leamoney-1;
m++;
if（leamoney<1）
printf（"1元=%d张\n",m）;
}
while（leamoney>=0.5）
{
leamoney=leamoney-0.5;
printf（"5角=1\n"）;
}
while（leamoney>=0.2）
{
leamoney=（float）（leamoney-0.2）;
y++;
if（leamoney<0.2）
printf（"2角=%d张\n",y）;
}
while（leamoney>=0.1）
{
leamoney=（float）（leamoney-0.1）;
printf（"1角=1张\n"）;
}
}
算法与程序设计实验报告四（4学时）
实验目的：
8、流程图的绘制。
9、背包问题求解。
实验内容：
6、绘制下列各题的程序流程图。
1.输人一个数到变量a，输出它的绝对值。
（分别用单双分支绘制）
单分支结构算法：
（1）输入任意数并赋值给变量a；
（2）判断a是否小于0，如果a小于0，取a的相反数；
（3）输出a。
双分支结构算法：
（1）输人任意数并赋值给变量a；
（2）判断a是否小于0，如果a小于0则输出a的相反数，否则输出a。
2.最值问题：
（1）求输人的两个数中的最大值。
（2）求输人的三个数中的最大值。
（3）求输入的十个数中的最大值。
3.循环求和（不同的控制循环方法）
（1）求输人20个数的和。
计数法
（知道循环次数，可以采用循环变量i来控制循环次数）
（2）求输入的若干个学生成绩的和，输入-1表示结束。
标志法
（不能确定次数，可以用输入的数据的值来进行控制）
（3）对输入的数据求和，当所求的和超过100则停止输入并输出求和结果（设此题中输人的数皆为正数）。
（没有指出输人数据的具体个数，且不能依据对输入数据的值来控制循环，控制循环的关键就在于对循环体中变量s的判断）
7、利用贪心策略解决背包问题。
现有载重为M公斤的背包和n种货物。
第i种货物的重量为Wi，它的总价值为Pi，假定M、Wi、Pi均为整数。
设计程序给出装货方法，使装入背包的货物总价值达到最大。
实验代码：
1.输人一个数到变量a，输出它的绝对值。
2.最值问题：
（1）求输人的两个数中的最大值。
（2）求输人的三个数中的最大值。
（3）求输入的十个数中的最大值。
3.循环求和
1.求输人20个数的和。
（知道循环次数，可以采用循环变量i来控制循环次数）
计数法
2.求输入的若干个学生成绩的和，输入-1表示结束。
（不能确定次数，可以用输入的数据的值来进行控制）
标志法
3.对输入的数据求和，当所求的和超过100则停止输入并输出求和结果（设此题中输人的数皆为正数）。
（没有指出输人数据的具体个数，且不能依据对输入数据的值来控制循环，控制循环的关键就在于对循环体中变量s的判断）
2.背包问题求解
#include
voidmain（）
{
inti,j,n,s=0;
floatP[20],W[20],value[20],x[20],values=0;
floatq=0,t=0,M=0;
printf（"请输入货物的数目n:
\n"）;
scanf（"%d",&n）;
printf（"请输入背包的负重M:
\n"）;
scanf（"%f",&M）;
printf（"请输入各种货物的重量:
\n"）;
for（i=1;i<=n;i++）
scanf（"%f",&W[i]）;
printf（"请输入各种货物的价值:
\n"）;
for（i=1;i<=n;i++）
scanf（"%f",&P[i]）;
for（i=1;i<=n;i++）
value[i]=P[i]/W[i];//计算货物的单位重量价值
for（i=1;i<=n;i++）
{
for（j=1;j<=n-i;j++）
if（value[j]{
t=value[j];value[j]=value[j+1];value[j+1]=t;//按货物的单位重量价值进行排序
q=W[j];W[j]=W[j+1];W[j+1]=q;//相应的货物重量进行排序
}
}
printf（"单位价值量（从大到小）如下:
\n"）;
for（i=1;i<=n;i++）
printf（"%5.2f",value[i]）;
printf（"\n"）;
printf（"所对应的货物重量如下:
\n"）;
for（i=1;i<=n;i++）
printf（"%5.2f",W[i]）;
printf（"\n"）;
i=1;
while（M!
=0）
{
M-=W[i];//背包负重递减
values=values+W[i]*value[i];//计算总价值
x[i]=W[i];
s=i;
s++;
if（M<=W[s]）
{
values=values+M*value[s];//如果背包的负重小于货物的重量时，则装货量等于背包的剩余载重
x[++i]=M;
M=0;
}
i++;
}
printf（"装货方式如下:
\n"）;
for（i=1;i<=n;i++）
printf（"%5.2f",x[i]）;
printf（"\n"）;
printf（"最大价值为:
values=%5.2f\n",values）;
printf（"\n"）;
}
升级会员 