文档介绍：: .
应用数学学院信息安全专业 —班学号
姓名
实验题目递归与分治法
综合实验评分表
序号
评分项目
评分标准
满分
打分
1
完成度
按要求独立完成实验准备、程序调试、实验报告撰写。
20
2
实验内容
(1) 完成功能需求分析、存储结构设计；
(2) 程序功能完善、可正常运行；
(3) 测试数据正确，分析正确，结论正确。
30
3
实验报告
内容齐全，符合要求，文理通顺，排版美观。
40
4
总结
对实验过程遇到的问题能初步独立分析，解决后能总结问题原因及解决方法，有心得体会。
10
实验报告
、实验目的与要求
1. 掌握递归算法的设计思想
2. 掌握分治法设计算法的一般过程
3. 理解并掌握算法渐近时间复杂度的分析方法
、实验内容
1、折半查找的递归算法
(1) 源程序代码
#include <>
#include <iostream>
using namespace std;
int bin_search(int key[],int low, int high,int k)
{ .
int mid;
if(low>high)
return -1;
else(
mid = (low+high) / 2;
if(key[mid]==k)
return mid;
if(k>key[mid])
return bin_search(key,mid+ l,high,k);
else
return bin_search(key,low,mid-1 ,k);
}
}
int main()
{
int n , i, addr;
intA[10] = {2,3,5,7,8,10,12,15,19,21};
cout « ”在下面的10个整数中进行查找” « endl;
for(i=0;i<10;i++)(
cout « A[i] « "";
}
cout « endl « endl « ”请输入一个要查找的整数” « endl;
cin » n;
addr = bin_search(A,0,9,n);
if(-l != addr)
cout « endl « n « ”是上述整数中的第n « addr « ”个数” « endl;
else
cout « endl « n « ”不在上述的整数中” « endl « endl;
getchar();
return 0;
}
(2) 运行界面
①查找成功
②查找失败
2、用分治法求x的n次方，要求时间复杂度为O(lgn)
(1)源程序代码
#include <>
#include <iostream>
using namespace std;
int Pow(int x, int n)
{
if (n == 1)
return x;
else if (n > 1)
{
int s;
int m = n / 2;