计算机算法分析与设计(第四版)习题算法分析部分详解(实验二).doc

计算机算法分析与设计(第四版)习题算法分析部分详解(实验二).doc实验二递归与分治策略
实验内容：算法实现问题2-1、2-5、2-7
//2-1众数问题
思路1：先排序，然后再统计，时间复杂度较高。
思路2：递归实现
-先根据某数X,将小于X的放于其左，大于X的放于其右
-统计X出现的次数T
-如果X左边数的个数〉T,向左递归
-如果X右边数的个数〉T,向右递归
#include<iostream>
#include<c stdlib>
#include< fstream>
#include<map>
using namespace std;
int key;
int maxcount=0;
void zs(int* a,int l,int r)(
int num =a [1];
int an=0;
int *b=new int[r-l+l];
int bn=0;
int *c=new int[r-l+l];
int cn=0;
for(int i=l;i<(r-l+l);i++){
if (num==a[i]) (
an++;
}else if (num<a[i]) (
b[bn]=a[i];
bn++;
}else(
c[cn]=a[i];
cn++;
)
if (an>maxcount) (
key=a[i];
maxcount二an;
}
}
if (bn>maxcount) ( 〃小于部分
zs(b,O,bn-l);
)
if (cn>maxcount) ( 〃大于部分 zs(c,O,cn-l);
)
delete b;
delete c;
) int main()
(
ifstream mputFile("",ios::in); 〃读数据文件
ofstream outputFile("",ios::out); 〃写数据文件
if(!inputFile)
{
cerr«"inputFile could not be opened. "«endl;
exit(l);
)
int number;
inputFile»number;
int l=O,r=number-l;
int * a =new int[number];
int i=0;
while(inputFile»number) ( 〃使用C++文件输入流输入数据
a[i]=number;
i++；
)
zs(a,l,r); 〃众数问题递归函数
delete a;
outputFile«key«endl«maxcount; 〃使用C++文件输出流输出结果
return 0;
)
〃、，分别存储输入数据和结果 例如：项目名sy21
)C:\Procram FilesMicrosoft Visual Studio\My^>rojects\sy21
一-
■ p w vu I g p t.:.k KLCP 1 p t ■ d dflo p c u .u 1 ! 1 ! 1 t 称ebw Ny2y2我y2y2“ f D i 。L s 8 3 s s t 名 & -"®®m.=f8 四
X
iiicros