算法与程序设计实验一

《算法与程序设计实验一》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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;i

5、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