资源描述:
《算法与程序设计实验一》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、实验一递归与分治一.实验目的理解递归算法的思想和递归程序的执行过程,并能熟练编写递归程序。掌握分治算法的思想,对给定的问题能设计出分治算法予以解决。二.实验基本步骤1.选定实验题冃,仔细阅读实验要求,设计好输入输岀,按照分治法的思想构思算法,选取合适的存储结构实现应用的操作。2.设计的结果应在VisualC++实验环境下实现并进行调试。(也可使用JAVA编程)3.实验要有详细的测试记录,包括各种可能的测试数据。三.实验内容1.人整数乘法编程实现采用分治算法实现两个n位二进制(或者十进制)大整数的乘法,算法参考教
2、材18-19页。实验代码:#include#include#includeusingnamespacestd;charc1[100];charc2[100];intnum1[200];intnum2[100];intresult[205];int11,12;intchange(intI,intnum[],charc[]){intk,i,j,r;r=l%4;k=0;for(i=l-1;i>=r;i-=4){for(j=i;j>i-4;j--){intd=c[j]
3、-,O,;num[k]+=pow(10,(i-j))*d;}k++;}if(r!=O)for(i=r-1;i>=O;i-)num[k]+=pow(10,(r-1-i))*(c[i]-'O*);k++;returnk;}voidprint(in11){intk=O5i;intflag=O;for(i=200-1;i>=0;i-){if(result[i]!=O&&!flag){cout«result[i];flag=1;}else{if(flag){if(result[i]/1000!=0)cout«result
4、[i];elseif(result[i]/100!=0)cout«"0"«result[i];elseif(result[i]/10)cout«"00M«result[i];elseif(result[i]!=O)cout«"000"«result[i];elsecout«"0000";}}}}voidfun(){inti,j,c;c=0;for(i=0;i5、OO;result[j+i]%=1OOOO;print(H);}intmain(){cout«"请输入两个人幣数:”vvendl;cin>>c1»c2;memset(nurrd,0,sizeof(num1));memset(num2,0,sizeof(num2));memset(result,0,sizeof(result));I1=strlen(c1);I2=strlen(c2);I1=change(l1,num1,c1);I2=change(l2,num2,c2);cout«"结果是:”vvendl;fun
6、();cout«endl;return0;实验结杲:in
7、xll邮箱显Pressanykeytocontinuebd更务1.Fibonacci数列无穷数列1,1,2,3,5,8,13,21,34,55,……,称为Fibonacci数列。它可以递归地定义为:1〃=0F(ri)=<1n=lF(n-T)+F(n-2)n>l第n个Fibonacci数可递归地计算如下:intfibonacci(intn){if(n<=1)return1;returnfibonacci(1)+fibonacci(n-2);}1)编写完整的
8、主函数,分别记录利用上述递归函数求第45,46,47,48个Fibonacci数所花费的时间。2)将递归函数改为尾递归,或者是递推函数,求第45,46,47,48个Fibonacci数所花费的时间,观察效率是否得到提高。实验代码:#include#defineCOL6longscan(){intn;printf(MInputtheN=");scanf(”%d”,&n);returnn;}longfibonacci(intn){if(0==nlll==n){return1;}else{retur
9、nfibonacci(n・l)+fibonacci(n・2);}}intmain(void){inti,n;n=scan();printf("Fibonacci数列的前%d项u,n);for(i=0;i