算法分析与设计实验报告

算法分析与设计

专业班级：姓 名：学 号：指导老师：实 验 报 告

实验一 递归算法的设计与实现 ? 计算整数的非负整数次幂

(1)设计思路

对于34按步骤可以分析： 34=32*32 32=31*31 31=31*1

对于33按步骤可以分析： 33=32*31； 32=31*31； 31=31*1；

分析可以得到：

当xn中n为奇数时，xn=x*(xn/2)2 当xn中n为偶数的，xn=（xn/2）2； 当n/2=0;return 1；

一步步进行递归返回计算，如果n位奇数，在进行一部乘以x 否则返回运算结果

(2)源程序代码

#include using namespace std;

int power(int x,int n) { int y; if(n==0) { y=1; } else { y=power(x,n/2); y=y*y; if(n%2==1) { y=y*x; }

} return y; }

void main() {

cout<<\请输入一个底数X：\ int x; cin>>x;

cout<<\请输入一个指数Y: \ int y; cin>>y; if(y<0) { cout<<\你的输入有误：请重新输入:\ cin>>y; } int c;

c=power(x,y);

cout<

(3)代码运行结果

(4)时间复杂度

令n=2k，则可以得到：f(n)=g(k)=k+1=logn+1=O(logn)

2.基于递归算法的插入排序

(1)设计思路

通过主函数传来一个数组的首地址和数组的长度，然后利用递归的原理，当n=0；程序返回，执行入栈的递归程序，依次比较2个数的大小，3个数的大小等，根据比较的结果将第n个数插入适当的位置。

(2)源程序代码

#include using namespace std;

void insert (int a[],int n) { int k; int b; n=n-1; if(n>0) { insert(a,n); b=a[n]; k=n-1; while((k>=0)&&(a[k]>b)) { a[k+1]=a[k]; k=k-1; } a[k+1]=b; } }

void main() { int a[100];