算法与程序设计实验报告

1、算法与程序设计实验报告二(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相同的元素的具体位

2、置。即输入一个n个元素的序列,其中n个元素是按从小到大的顺序排 列的，查找是否存在给定的值X。实验代码：1、n!的递归算法的编写。#i ncludeint digu i(int n)if(n=1) return 1;elsereturn n *digu i(n-1);void mai n()int n; printf(请输入待求阶乘数(小于15的一个数)：);sca nf(%d,&n); printf(结果为：%dn,digui(n);2、计算Fib(n)的递归算法#in clude long Fib( int n ) if ( n=1 | n=2 )/终止递归条件return 1;elser

3、eturnFib( n-1)+Fib( n-2);void mai n()int n;printf(请输入裴波那契数列的待求项数：”)；scan f(%d,&n);printf(裴波那契数列第 %d项值为ldn,n,Fib(n);3、二分查找法的实现。#i ncludeint BinarySearch(int a,int n,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

4、)/*冒泡排序功能函数 */int i,j;int n=10;for(i=0;i n;i+)for(j=0;jaj+1)int temp;temp=ajaj=aj+1;aj+1=temp;void mai n()int i,a10,x; int flag=-1;printf(请输入10个带查找数据(空格分隔)：”)； for(i=0;i10;i+) |scan f(%d,&ai);maopao(a);printf(带查序列有序化后变为：”)； for(i=0;i10;i+)|prin tf(%d,ai);prin tf(n);printf(请输入待查关键字:);scan f(%d，& x);f

5、lag=B in arySearch(a,10,x);if(flag=-1)printf(未找到带查关键字！n ”);elseprintf(找到关键字，位于有序序列的第%d个位置！ n,flag+1);算法与程序设计实验报告三（4学时）实验目的：6、了解贪心算法思想7、掌握贪心法典型问题，如背包问题、作业调度问题等。实验内容：4、键盘输入一个高精度的正整数 n （*10位）去掉任意s个数字后剩下的数字按原左右次序组成一个新的正整数。编程对给定的n和s,寻找一种方案，使得剩下的数最小。5、设计实现超市收银程序，假设顾客在超市购买各种商品，来到收银台结账，收银员具有面值为100，20， 10， 5

6、和1元的纸币和各种面值为 5角、2角、1角的硬币。 设计程序计算顾客各种所买商品的钱数，并根据顾客所付的钱数输出零钱的数目及 要找的各种货币的数目。算法思想：贪心算法的基本思路1建立数学模型来描述问题。2. 把求解的问题分成若干个子问题。3对每一子问题求解，得到子问题的局部最优解。4. 把子问题的解局部最优解合成原来解问题的一个解。实验代码：1键盘输入一个高精度的正整数n (n10位)去掉任意s个数字后剩下的数字按原左右次序组成一个新的正整数。编程对给定的n和s,寻找一种方案，使得剩下的数最小。#in clude#in elude #defi ne M 100main () char chM;

7、int rM, dM,l, s,i,j,k;printf(”请输入正整数：”)；gets(ch);printf(请输入删除的位数：);sca nf(%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+)prin tf(%dt,di+1);pr

8、in tf(n);return 0 ;2.设计实现超市收银程序，假设顾客在超市购买各种商品，来到收银台结账，收银员具有 面值为100，20， 10， 5和1元的纸币和各种面值为5角、2角、1角的硬币。设计程序计算顾客各种所买商品的钱数，并根据顾客所付的钱数输出零钱的数目及要找的各种货币的数目。#in clude#in cludevoid mai n()double price,total=0,givem on ey,leam on ey; int n ,i,k=0,m=0,x=0,y=0;printf(”请输入商品的数目:);scan f(%d,&n);printf(输入每件商品的价格:n);

9、for(i=1;i=100)leam on ey=leam on ey-100;k+;if(leamo ney=20)leam on ey=leam on ey-20;x+;if(leamo ney=10)leam on ey=leam on ey-10; printf(10 元=1 张n);while(leam on ey=5)leam on ey=leam on ey-5;printf(5 元=1 张 n);while(leam on ey=1)leam on ey=leam on ey-1;m+;if(leam on ey=0.5)leam on ey=leam on ey-0.5;pr

10、intf(5 角=1n);while(leam on ey=0.2)leam on ey=(float)(leam on ey-0.2);y+;if(leamo ney=0.1)leam on ey=(float)(leam on ey-0.1); prin tf(1 角=1 张 n);算法与程序设计实验报告四（4学时）实验目的：8、流程图的绘制。9、背包问题求解。实验内容：6、绘制下列各题的程序流程图。1. 输人一个数到变量 a，输出它的绝对值。（分别用单双分支绘制） 单分支结构算法：（1）输入任意数并赋值给变量 a ；（2）判断a是否小于0，如果a小于0 ,取a的相反数；（3）输出a。双分

11、支结构算法：（1） 输人任意数并赋值给变量a ;（2） 判断a是否小于0 ,如果a小于0则输出a的相反数，否则输出a。2. 最值问题：（1 ）求输人的两个数中的最大值。（2 ）求输人的三个数中的最大值。（3 ）求输入的十个数中的最大值。3. 循环求和（不同的控制循环方法）（1）求输人20个数的和。 计数法（知道循环次数，可以采用循环变量i来控制循环次数）（2 ）求输入的若干个学生成绩的和，输入-1表示结束。 标志法（不能确定次数，可以用输入的数据的值来进行控制）（3）对输入的数据求和，当所求的和超过 100则停止输入并输出求和结果 （设此 题中输人的数皆为正数）。（没有指出输人数据的具体个数，

12、且不能依据对输入数据的值来控制循环，控制循 环的关键就在于对循环体中变量s的判断）7、利用贪心策略解决背包问题。现有载重为M公斤的背包和n种货物。第i种货物的重量为 Wi,它的总价值为 Pi，假定M Wi、Pi均为整数。设计程序给出装货方法， 使装入背包的货物总价值达到最大。实验代码:1. 输人一个数到变量 a，输出它的绝对值。（开始）a -2/ 输严 /（/束J单分支结构翼法流程图双分支结构算法流程圏（开始）2. 最值问题:/输人ab /输岀臼7 /输茁b1 11（结束）（1 ）求输人的两个数中的最大值。/幡人/議出电/输賂输出b / / 枪饒/C Wi ）（2 ）求输人的三个数中的最大值。

13、iImax*-xi -i+】一 i/_楡生?c /（3 ）求输入的十个数中的最大值。3.循环求和1.求输人20个数的和。（知道循环次数，可以采用循 环变量i来控制循环次数）计数法2.求输入的若干个学生成绩 的和，输入-1表示结束。（不能确定次数，可以用输入的数据的值来进行控制）标志法3.对输入的数据求和，当所求 的和超过 100则停止输入并 输出求和结果（设此题中输人 的数皆为正数）。（没有指出输人数据的具体个 数，且不能依据对输入数据的 值来控制循环，控制循环的关 键就在于对循环体中变量s的判断）2.背包问题求解#in clude void mai n ()int i,j,n ,s=0;fl

14、oat P20,W20,value20,x20,values=0;float q=0,t=0,M=0;printf(请输入货物的数目n :n);scan f(%d,&n);printf(请输入背包的负重M:n);scan f(%f,&M);printf(请输入各种货物的重量:n); for(i=1;i=n ;i+) scan f(%f,&Wi);printf(请输入各种货物的价值:n); for(i=1;i=n ;i+)scan f(%f,&Pi);for(i=1;i=n ;i+)valuei=Pi/Wi;计算货物的单位重量价值for(i=1;i=n ;i+)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+)prin tf(%5.2f”,valuei);prin tf(n);printf(所对应的货物重量如下:n);for (i=1;i=n ;i+)prin tf(%5.2f”,Wi);prin tf(n);i=1;while(M!=0)M-=Wi;背包负重递减v