算法与程序设计实验报告

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、在一个Z定的n个元素的有序序列中查找出与给定关键字x相同的元素的具体位置。即输入一

2、个n个元素白序列<a1,a2,a3,an>,其中n个元素是按从小到大的顺序排列的，查找是否存在给定的值X。实验代码：1、n!的递归算法的编写。#include<stdio.h>intdigui(intn)if(n=1)return1;elsereturnn*digui(n-1);voidmain()intn;printf("请输入待求阶乘数(小于15的一个数)：");scanf("%d",&n);printf("结果为：%dn",digui(n);2、计算Fib(n)的递归算法#include<s

3、tdio.h>longFib(intn)if(n=111n=2)/终止递归条件return1;elsereturnFib(n-1)+Fib(n-2);voidmain()intn;printf("请输入裴波那契数列的待求项数：")；scanf("%d",&n);printf("裴波那契数列第d项值为ldn",n,Fib(n);3、二分查找法的实现。#include<stdio.h>intBinarySearch(inta,intn,intx)/*二分查找功能函数*/intl=0,r=n,i;while(l&l

4、t;=r)i=(l+r)/2;if(x=ai)returni;elseif(x<ai)r=i-1;elsel=i+1;return-1;|voidmaopao(inta口)/*冒泡排序功能函数*/inti,j;intn=10;for(i=0;i<n;i+)for(j=0;j<n-i-1;j+)if(aj>aj+1)1inttemp;temp=aj;aj=aj+1;aj+1=temp;:voidmain()inti,a10,x;intflag=-1;printf("请输入10个带查找数据(空格分隔)：")；for(i=0;i<10;i+)|sca

5、nf("%d”,&ai);maopao(a);printf("带查序列有序化后变为：");for(i=0;i<10;i+)printf("%d,",ai);printf("n");printf("请输入待查关键字：")；scanf("%d",&x);flag=BinarySearch(a,10,x);if(flag=-1)printf("未找到带查关键字！n");elseprintf("找到关键字，位于有序序列的第个位置！n"

6、;,flag+1);算法与程序设计实验报告三（4学时）实验目的：6、了解贪心算法思想7、掌握贪心法典型问题，如背包问题、作业调度问题等。实验内容：4、键盘输入一个高精度的正整数n（n<10位）去掉任意s个数字后剩下的数字按原左右次序组成一个新的正整数。编程对给定的n和s,寻找一种方案，使得剩下的数最小。5、设计实现超市收银程序，假设顾客在超市购买各种商品，来到收银台结账，收银员具有面值为100,20,10,5和1元的纸币和各种面值为5角、2角、1角的硬币。设计程序计算顾客各种所买商品的钱数，并根据顾客所付的钱数输出零钱的数目及要找的各种货币的数目。算法思想：贪心算法的基本思路1 .建立数

7、学模型来描述问题。2 .把求解的问题分成若干个子问题。3 .对每一子问题求解，得到子问题的局部最优解。4 .把子问题的解局部最优解合成原来解问题的一个解。实验代码：1 .键盘输入一个高精度的正整数n(n<10位)去掉任意s个数字后剩下的数字按原左右次序组成一个新的正整数。编程对给定的n和s,寻找一种方案，使得剩下的数最小。#include<stdio.h>#include<string.h>#defineM100main()charchM;intrM,dM,l,s,i,j,k;printf("请输入正整数：");gets(ch)；printf(

8、"请输入删除的位数：”)；scanf("%d",&s);l=0;for(i=0;chi!='0'i+)ri=i;l+;for(i=0;i<s;i+)for(j=0;j<l-i-1;j+)if(chj>chj+1)break;if(j=l-i)k=l-i-1;elsek=j;di=rk;for(j=k;j<l-i-1;j+)chj=chj+1;rj=rj+1;chj='0'printf("删除后最小的整数为:%sn",s,ch);printf("删除的数位为:")

9、;for(i=0;i<s;i+)printf("%dt",di+1);printf("n");return0;2 .设计实现超市收银程序，假设顾客在超市购买各种商品，来到收银台结账，收银员具有面值为100,20,10,5和1元的纸币和各种面值为5角、2角、1角的硬币。设计程序计算顾客各种所买商品的钱数，并根据顾客所付的钱数输出零钱的数目及要找的各种货币的数目。#include<stdio.h>#include<string.h>voidmain()doubleprice,total=0,givemoney,leamoney;

10、intn,i,k=0,m=0,x=0,y=0;printf("请输入商品的数目：")；scanf("%d",&n);printf("输入每件商品的价格：n");for(i=1;i<=n;i+)printf("第件:",i);scanf("%lf",&price);total=total+price;printf("总的价格=%5.2fn",total);printf("输入顾客所给的钱：n");scanf("%lf"

11、;,&givemoney);leamoney=givemoney-total;printf("剩余的钱为5.2fn",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

12、",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角

13、=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,输出它的绝对值。(分别用单双分支绘制)单分支结构

14、算法：(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则停

15、止输入并输出求和结果(设此题中输人的数皆为正数)。(没有指出输人数据的具体个数，且不能依据对输入数据的值来控制循环，控制循环的关键就在于对循环体中变量s的判断)7、利用贪心策略解决背包问题。现有载重为M公斤的背包和n种货物。第i种货物的重量为Wi,它的总价值为Pi,假定MWi、Pi均为整数。设计程序给出装货方法，使装入背包的货物总价值达到最大。1.输人一个数到变量 a ,输出它的绝对值。(开始)/ 输入a /实验代码:|ag*/输出咆/输而7“/赤/LJ'c结束)(结束)单分支结构算法流程图双分支结构算法流程图2.最值问题：（1）求输人的两个数中的最大值。（2）求输人的三个数中的最大值

16、。max一叫 iTmax*-xi-i+】_一f输x/（3）求输入的十个数中的最大值。3.循环求和1 .求输人20个数的和。（知道循环次数，可以采用循 环变量i来控制循环次数）计数法2 .求输入的若干个学生成绩 的和，输入-1表示结束。（不能确定次数，可以用输入的数据的值来进行控制）标志法3 .对输入的数据求和，当所求 的和超过 100则停止输入并 输出求和结果（设此题中输人 的数皆为正数）。（没有指出输人数据的具体个 数，且不能依据对输入数据的 值来控制循环，控制循环的关 键就在于对循环体中变量s的判断）C开始）2.背包问题求解#include<stdio.h>voidmain()

17、inti,j,n,s=0;floatP20,W20,value20,x20,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",&Wi);printf("请输入各种货物的价值：n&q

18、uot;);for(i=1;i<=n;i+)scanf("%f",&Pi);for(i=1;i<=n;i+)valuei=Pi/W叱计算货物的单位重量价值for(i=1;i<=n;i+)for(j=1;j<=n-i;j+)if(valuej<valuej+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;背包负重递减value