算法与程序设计实验报告.doc

《算法与程序设计实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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个元素的有序序列中查

2、找出与给定关键字x相同的元素的具体位置。即输入一个n个元素的序列，其中n个元素是按从小到大的顺序排列的，查找是否存在给定的值x。实验代码：1、n!的递归算法的编写。#includeintdigui(intn){if(n==1)return1;elsereturnn*digui(n-1);}voidmain(){intn;printf("请输入待求阶乘数(小于15的一个数)：");scanf("%d",&n);printf("结果为：%d",digui(n));}2、计算Fib(n)的递归算

3、法..#includelongFib(intn){if(n==1

4、

5、n==2)//终止递归条件return1;elsereturnFib(n-1)+Fib(n-2);}voidmain(){intn;printf("请输入裴波那契数列的待求项数：");scanf("%d",&n);printf("裴波那契数列第%d项值为%ld",n,Fib(n));}1、二分查找法的实现。#includeintBinarySearch(inta[],intn,intx)/*二分查找功能函数*/{intl=0,r=n,

6、i;while(l<=r){i=(l+r)/2;if(x==a[i])returni;elseif(xa[j+1]){inttemp;temp=a[j];a[j]=a[j+1];a[j+1]=temp;}}voidmain(){inti,a[10],x;..intflag=-1;printf("请输

7、入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("");printf("请输入待查关键字:");scanf("%d",&x);flag=BinarySearch(a,10,x);if(flag==-1)printf("未找到带查关键字！");elseprintf("找到关键字，位于有序序列的第%d个位置！",flag+1)

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

9、：贪心算法的基本思路1.建立数学模型来描述问题。2.把求解的问题分成若干个子问题。3.对每一子问题求解，得到子问题的局部最优解。4.把子问题的解局部最优解合成原来解问题的一个解。实验代码：..1.键盘输入一个高精度的正整数n（n<10位）去掉任意s个数字后剩下的数字按原左右次序组成一个新的正整数。编程对给定的n和s，寻找一种方案，使得剩下的数最小。#include#include#defineM100main(){charch[M];intr[M],d[M],l,s,i,j,k;printf("请输入正

10、整数：");gets(ch);printf("请输入删除的位数：");scanf("%d",&s);l=0;for(i=0;ch[i]!='';i++){r[i]=i;l++