《算法设计与分析》实验报告一
学号：姓名：
日期： 2012.11.5 得分：
一、实验内容：
分别用蛮力法、分治法、减治法实现a^n。

二、实验要求：
完成试验报告、给出对此结果。

为防止大数溢出，可以用1^n来测试在n比较大是的三种算法运行情况。

四、源程序及注释：
#include <iostream>
#include <windows.h>
using namespace std;
//蛮力法求a的n次方
int Power1(int a,int n)
{ int as=1;
for(int i=0;i<n;i++)
ans*=a;
return ans;
//分治法求a的n次方
int Power2(int a,int n)
{ int ans=1;
if (n==0) ans=1;
else if(n==1) ans=a;
else
ans=Power2(a,n/2)*Power2(a,(n+1)/2);
return ans;
}
//减治法求a的n次方
int Power3(int a,int n)
{ int ans=1;
if (n==0) ans=1;
else if(n==1) ans=a;
else
{ans=Power3(a,n/2);
if(n%2==0)
ans=ans*ans;//当n为偶数
return ans;
}
int main()
{
int a=1;
int n=10000;
LARGE_INTEGER start1,end1,start2,end2,start3,end3,f;
QueryPerformanceFrequency(&f);
QueryPerformanceCounter(&start1) ;
int p1=Power1(a,n);
QueryPerformanceCounter(&end1);
QueryPerformanceCounter(&start2) ;
int p2=Power2(a,n);
QueryPerformanceCounter(&end2);
QueryPerformanceCounter(&start3) ;
int p3=Power3(a,n);
QueryPerformanceCounter(&end3);
cout<<"a="<<a<<",n="<<n<<endl;
cout<<"蛮力法求a的n次方运行时间（单位：s）及结果"<<endl<<double(end1.QuadPart-start1.QuadPart)/f.QuadPart<<" "<<p1<<endl;
cout<<"分治法求a的n次方运行时间（单位：s）及结果"<<endl<<double(end2.QuadPart-start2.QuadPart)/f.QuadPart<<" "<<p2<<endl;
cout<<"减治法求a的n次方运行时间（单位：s）及结果"<<endl<<double(end3.QuadPart-start3.QuadPart)/f.QuadPart<<" "<<p3<<endl;
return 0;}
五、运行输出结果：
六、调试和运行程序过程中产生的问题、采取的措施及获得的相关经验教训：
合适的代码是实验能够成功进行的关键，当然前提是对问题的深刻理解,从实验结果我们不难看出，应用减治法处理问题的效率还是很高的。