/*
题目描述:
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
分治算法求一个数组中的最大元素。
*/
/*
思路:要用分治法来解决数组中的最大了元素,我们可以采用递归的思想,两两比较用小标的变化来标志出存储最大的元素。
*/
/*
算法:
1.首先输入数组的个数
2.用rand()随机产生数组
3.调用递归函数
3.1 递归函数找到最大元素的下标
4.输出最大元素
*/
#include
using namespace std;
int Max(int a[], int low, int high);
int main()
{
int a[1000], m,n;
cout<<"请输入数组的个数:";
cin>>n;
for(int i = 0;i < n;i++)
a[i] = rand() %100;
for(int j = 0;j < n;j++)
cout<a[max2]?max1: max2;
return max;
}
}
/*
题目描述:设计分治算法,实现将数组A[n]中所有的元素循环左移k个位置,要求时间复杂度为,空间复杂度为,例如,对abcdefgh循环左移3位得到defghabc.
*/
/*
思路:将数组元素左移n块,则将数组分成几块,然后将每一块进行编号,
然后进行移动,序号相同的,前一段序号的那个数移到后一段序号的那个数即可。
*/
/*
算法:
1.实现相邻两端相同编号的数进行移动
2.k个函数调用实现每个序号的
书
关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf
都进行移动
3.输出数组
*/
#include
using namespace std;
void Converse(char *A,int n,int k) ;
void Reverse(char *A, int from, int to);
int main()
{
char A[100];
int k;
cout<<"请输入数组:"<>A;
cout<<"请输入左移的位数k:"<>k;
Converse(A,strlen(A),k);
return 0;
}
void Reverse(char *A, int from, int to)
{
for(int i=0;i<(to-from+1)/2;i++)
{
char temp=A[from+i];
A[from+i]=A[to-i];
A[to-i]=temp;
}
}
void Converse(char *A,int n,int k)
{
Reverse(A, 0, k-1);
Reverse(A, k, n-1);
Reverse(A, 0, n-1);
cout<<"移动后的数组为:"< i则我们就直接在数组的左边找;否则就在右边找。
2.3.找到目标输出;
*/
#include
using namespace std;
void f(int a[],int n);
int main ()
{
int a[1001];
int i,n;
cout<<"请输入有序数组的个数:";
cin>>n;
for(i = 0;i < n;i++)
{
cin>>a[i];
}
f(a,n);
return 0;
}
void f(int a[],int n)
{
int left = 0,right = n - 1,mid;
while(left < right)
{
mid = (left + right) / 2;
if(a[mid] = mid)
{
cout<<"这个元素是:"< mid)
right = mid;
else
left = mid;
}
}
/*
题目描述:在一个序列中出现次数最多的元素称为众数,
请设计算法寻找众数并分析算法的时间复杂性;
*/
/*
思路:题目要求是要用分治法,那我们就只有在排序上用分治法,将数组用快速排序,之后再遍历一次数组我们就可以找到众数。此时算法的时间复杂性为nlog(n);
*/
/*
算法:
1.输入数组;
2.对数组进行快速排序
3.for循环遍历数组,用if判断找出众数
4.输出众数。
*/
#include
using namespace std;
int Partition(int r[ ], int first, int end);
void QuickSort(int r[ ], int first, int end);
int main()
{
int r[10001];
int n,cont = 0,max = 0,temp;
cout<<"请输入数组的个数:";
cin>>n;
cout<<"请输入数组的元素:";
for(int j = 0;j < n;j++)
cin>>r[j];
QuickSort(r,0,n-1);
for(int i = 0;i < n;i++)
{
int k = i + 1;
while(r[i] == r[k] && i < n)
{
cont++;
i++;
}
if(cont > max)
{
temp = i - 1;
max = cont;
cont = 0;
i = i - 1;
}
}
cout<<"众数是:"<
记录
混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载
交换到前面
i++;
}
while (i < j && r[i] <= r[j]) i++; //左侧扫描
if (i < j) {
int temp = r[i]; r[i] = r[j]; r[j] = temp; //将较大记录交换到后面
j--;
}
}
return i; // 返回轴值记录的位置
}
void QuickSort(int r[ ], int first, int end) //快速排序
{
int pivot;
if (first < end) {
pivot = Partition(r, first, end); //划分,pivot是轴值在序列中的位置
QuickSort(r, first, pivot-1); //求解子问题1,对左侧子序列进行快速排序
QuickSort(r, pivot+1, end); //求解子问题2,对右侧子序列进行快速排序
}
}
/*
题目描述:设M 是一个n×n 的矩阵,其中每行的元素从左到右单增有序,
每列的元素从上到下单增有序。给出一个分治算法计算出给定元素x
在M 中的位置或者表明x 不在M 中。分析算法的时间复杂性。
*/
/*
思路:在n×n 的矩阵中其中每行的元素从左到右单增有序,每列的元素从上到下单增有序。那么我们就可以找到矩阵的中心元素对其进行比较,比较后要找的元素可能有两块区域,再对这两块区域再进行递归调用就可以找到我们想要的元素。
*/
/*
算法:输出元素是否存在及其位置。
1,调用MatrixBinary函数
2.1 每次都找到中心元素
2.2用要查找的元素与之进行比较
2.3如果比中心元素大就在其右侧或左下角反之在其左侧或者右上角
2.4继续递归调用MatrixBinary
2.5找到了返回1,否则返回0;
3.输出。
*/
#include
using namespace std;
int M[5][5]=
{
{ 1, 2, 3, 4, 5},
{ 6, 7, 8, 9,10},
{11,12,13,14,15},
{16,17,18,19,20},
{21,22,23,24,25}
};
int x = 19;
int MatrixBinary(int M[5][5],int rb,int re,int cb,int ce)
{
int rm = (rb+re) / 2;
int cm = (cb+ce) / 2;
if (rb > re || cb > ce)
{
return 0;
}
if(x == M[rm][cm])
{
cout< M[rm][cm])
{
return MatrixBinary(M,rb,re,cm+1,ce)||MatrixBinary(M,rm+1,re,cb,cm);
}
else
{
return MatrixBinary(M,rb,rm-1,cb,ce)||MatrixBinary(M,rm,re,cb,cm-1);
}
}
int main()
{
int a = MatrixBinary(M,0,4,0,4);
if(a == 1)
{
cout<<"要查找的"<
using namespace std;
int Partition(int r[ ], int first, int end);
void QuickSort(int r[ ], int first, int end);
int main()
{
int r[10001];
int n,s1 = 0,s2 = 0,c;
cout<<"请输入数组的个数:";
cin>>n;
cout<<"请输入数组的元素:";
for(int j = 0;j < n;j++)
cin>>r[j];
QuickSort(r,0,n-1);
int k = n / 2;
for(int i = 0;i < k;i++)
{
s1 = s1 + r[i];
}
for(int q = k;q < n;q++)
{
s2 = s2 + r[q];
}
c = s2 - s1;
cout<<"两个子集元素之和的最大差是:"<
using namespace std;
void Table(int k,int **a);
int main ()
{
int k;
cin>>k;
int n = 1;
for(int j = 1;j <= k;j++) // 参加比赛选手的人数
n = n * 2;
int **a = new int *[n+1]; //根据n动态分配二维数组a for(int i = 0;i <= n;i++)
{
a[i] = new int[n+1];
}
Table(k,a); //分配日程函数
for(int q=1; q<=n; q++)
{
for(int l=1; l<=n; l++)
{
cout<
本文档为【算法设计 第4章 分治法】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483