2022年算法与程序设计实验报告 .pdf

算法与程序设计实验报告二（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(int n)if(n=1)return 1;else return n*digui(n-1);void main()int n;printf(请输入待求阶乘数(小于 15 的一个数)：);scanf(%d,&n);printf(结果为：%dn,digui(n);2、计算 Fib(n)的递归算法名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 11 页 -#include long Fib(int n)if(n=1|n=2)/终止递归条件return 1;else return Fib(n-1)+Fib(n-2);void main()int n;printf(请输入裴波那契数列的待求项数：);scanf(%d,&n);printf(裴波那契数列第%d项值为%ldn,n,Fib(n);3、二分查找法的实现。#include intBinarySearch(int a,intn,int x)/*二分查找功能函数*/int l=0,r=n,i;while(l=r)i=(l+r)/2;if(x=ai)return i;else if(xai)r=i-1;else l=i+1;return-1;void maopao(int a)/*冒泡排序功能函数*/inti,j;int n=10;for(i=0;in;i+)for(j=0;jaj+1)int temp;temp=aj;aj=aj+1;aj+1=temp;void main()inti,a10,x;名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 11 页 -int flag=-1;printf(请输入 10 个带查找数据（空格分隔）：);for(i=0;i10;i+)scanf(%d,&ai);maopao(a);printf(带查序列有序化后变为：);for(i=0;i10;i+)printf(%d,ai);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（n10 位）去掉任意s 个数字后剩下的数字按原左右次序组成一个新的正整数。编程对给定的n 和 s，寻找一种方案，使得剩下的数最小。5、设计实现超市收银程序，假设顾客在超市购买各种商品，来到收银台结账，收银员具有面值为100，20，10，5 和 1 元的纸币和各种面值为5 角、2 角、1 角的硬币。设计程序计算顾客各种所买商品的钱数，并根据顾客所付的钱数输出零钱的数目及要找的各种货币的数目。算法思想：贪心算法的基本思路1.建立数学模型来描述问题。2.把求解的问题分成若干个子问题。3.对每一子问题求解，得到子问题的局部最优解。4.把子问题的解局部最优解合成原来解问题的一个解。实验代码：名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 11 页 -1.键盘输入一个高精度的正整数n（n10 位）去掉任意s个数字后剩下的数字按原左右次序组成一个新的正整数。编程对给定的n 和 s，寻找一种方案，使得剩下的数最小。#include#include#define M 100 main()charchM;int rM,dM,l,s,i,j,k;printf(请输入正整数：);gets(ch);printf(请输入删除的位数：);scanf(%d,&s);l=0;for(i=0;chi!=0;i+)ri=i;l+;for(i=0;is;i+)for(j=0;jchj+1)break;if(j=l-i)k=l-i-1;else k=j;di=rk;for(j=k;jl-i-1;j+)chj=chj+1;rj=rj+1;chj=0;printf(删除%d 后最小的整数为:%sn,s,ch);printf(删除的数位为:);for(i=0;is;i+)printf(%dt,di+1);printf(n);return 0;2.设计实现超市收银程序，假设顾客在超市购买各种商品，来到收银台结账，收银员具有面值为 100，20，10，5 和 1 元的纸币和各种面值为5 角、2 角、1 角的硬币。设计程序计算顾客各种所买商品的钱数，并根据顾客所付的钱数输出零钱的数目及要找的各种货币的数目。名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 11 页 -#include#include void main()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=100)leamoney=leamoney-100;k+;if(leamoney=20)leamoney=leamoney-20;x+;if(leamoney=10)leamoney=leamoney-10;printf(10 元=1 张n);while(leamoney=5)leamoney=leamoney-5;printf(5 元=1张 n);名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 11 页 -while(leamoney=1)leamoney=leamoney-1;m+;if(leamoney=0.5)leamoney=leamoney-0.5;printf(5 角=1n);while(leamoney=0.2)leamoney=(float)(leamoney-0.2);y+;if(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；名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 11 页 -（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.最值问题：名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 11 页 -（1）求输人的两个数中的最大值。（2）求输人的三个数中的最大值。（3）求输入的十个数中的最大值。3.循环求和1.求输人20 个数的和。(知道循环次数，可以采用循环变量i 来控制循环次数)计数法2.求输入的若干个学生成绩的和，输入-1 表示结束。（不能确定次数，可以用输入的数据的值来进行控制）标志法3.对输入的数据求和，当所求的和超过100 则停止输入并输出求和结果（设此题中输人的数皆为正数）。（没有指出输人数据的具体个数，且不能依据对输入数据的值来控制循环，控制循环的关键就在于对循环体中变量s 的判断）名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 11 页 -2.背包问题求解#include void main()inti,j,n,s=0;float P20,W20,value20,x20,values=0;float q=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,&Wi);printf(请输入各种货物的价值:n);for(i=1;i=n;i+)scanf(%f,&Pi);for(i=1;i=n;i+)valuei=Pi/Wi;/计算货物的单位重量价值for(i=1;i=n;i+)名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 11 页 -for(j=1;j=n-i;j+)if(valuejvaluej+1)t=valuej;valuej=valuej+1;valuej+1=t;/按货物的单位重量价值进行排序q=Wj;Wj=Wj+1;Wj+1=q;/相应的货物重量进行排序 printf(单位价值量(从大到小)如下:n);for(i=1;i=n;i+)printf(%5.2f,valuei);printf(n);printf(所对应的货物重量如下:n);for(i=1;i=n;i+)printf(%5.2f,Wi);printf(n);i=1;while(M!=0)M-=Wi;/背包负重递减values=values+Wi*valuei;/计算总价值xi=Wi;s=i;s+;if(M=Ws)values=values+M*values;/如果背包的负重小于货物的重量时，则装货量等于背包的剩余载重x+i=M;M=0;i+;printf(装货方式如下:n);名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 11 页 -for(i=1;i=n;i+)printf(%5.2f,xi);printf(n);printf(最大价值为:values=%5.2f n,values);printf(n);名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 11 页 -