沈阳谷歌网站建设,搬家公司怎么做网站,dedecms 建两个网站的问题,安徽省交通运输厅门户网站41题 41题解答#xff1a;
#xff08;1#xff09;图 G 的邻接矩阵 A 如下所示#xff1a;
由题意得#xff0c;A为上三角矩阵#xff0c;在上三角矩阵A[6][6]中#xff0c;第1行至第5行主对角线上方的元素个数分别为5, 4, 3, 2, 1
用 “ 平移” 的思想#xff0c;…41题 41题解答
1图 G 的邻接矩阵 A 如下所示
由题意得A为上三角矩阵在上三角矩阵A[6][6]中第1行至第5行主对角线上方的元素个数分别为5, 4, 3, 2, 1
用 “ 平移” 的思想将题目中前5个、后4个、后3个、后2个、后1个元素分别移动到矩阵对角线 (“O”) 右边的行上,可得下图 2根据上面的邻接矩阵画出有向带权图G 3按照算法先计算各个事件的最早发生时间计算过程如下 关键路径为 0-1-2-3-5如下图所示粗线表示长度为 454316。 42题 暴力解1将两个数组合并成一个然后找中位数即可
int merge(Sqlist A,Sqlist B) {int i0,j0,count0;while(1){if(A.data[i]B.data[i]){if(count(A.lengthB.length)/2){return A.data[i];}i;}else{if(count(A.lengthB.length)/2){return B.data[i];}j;}}
}暴力解2
新建一个数组C合并到数组C排序 要求找到两个等长有序序列合并后的中位数暴力解就直接合并但你会发现并不需要合并全部我们只需要中间位置的一个值即可所以 mid 就是 len-1我们按照常规合并有序序列的方法只移动指针即可
int serach_mid(int A[], int B[], int len) {int i 0, j 0;while (i j len - 1) {if (A[i] B[j]) {i;} else {j;}return A[i] B[j] ? A[i] : B[j];}
}最优解
思路:
1求两个序列A和B的中位数最简单的办法就是将两个升序序列进行归并排序然后求其中位数。这种解法虽可求解但在时间和空间两方面都不大符合高效的要求但也能获得部分分值。
根据题目分析分别求两个升序序列A和B的中位数设为a和b。
① 若ab则a或b即为所求的中位数。
原因容易验证如果将两个序列归并排序则最终序列中排在子序列ab前边的元素为先前两个序列中排在a和b前边的元素排在子序列ab后边的元素为先前两个序列中排在a和b后边的元素。所以子序列ab一定位于最终序列的中间又因为ab显然a就是中位数。
② 否则假设ab中位数只能出现ab范围内。
原因同样可以用归并排序后的序列来验证归并排序后必然有形如…a…b…的序列出现中位数必出现在ab之间。因此可以做如下处理舍弃a所在序列A的较小一半同时舍弃b所在序列B的较大一半。在保留两个升序序列中求出新的中位数a和b重复上述过程直到两个序列中只含一个元素时为止则较小者即为所求的中位数。每次总的元素个数变为原来的一半。
算法的基本设计思想如下。
分别求出序列A和B的中位数设为a和b求序列A和B的中位数过程如下
① 若ab则a或b即为所求中位数算法结束。
② 若ab则舍弃序列A中较小的一半同时舍弃序列B中较大的一半要求舍弃的长度相等。
③ 若ab则舍弃序列A中较大的一半同时舍弃序列B中较小的一半要求舍弃的长度相等。
在保留的两个升序序列中重复过程①、②、③直到两个序列中只含一个元素时为止较小者即为所求的中位数。
int M_Search(int A[], int B[], int n) {int s1 0, d1 n - 1, m1, s2 1, d2 n - 1, m2;//分别表示序列A和B的首位数、末位数和中位数while (s1 ! d1 || s2 ! d2) {m1 (s1 d1) / 2;m2 (s2 d2) / 2;if (A[m1] B[m2])return A[m1]; //满足条件1if (A[m1] B[m2]) { //满足条件2if ((s1 d1) % 2 0) { //若元素个数为奇数s1 m1; //舍弃A中间点以前的部分且保留中间点d2 m2; //舍弃B中间点以后的部分且保留中间点} else { //元素个数为偶数s1 m1 1; //舍弃A中间点及中间点以前部分d2 m2; //舍弃B中间点以后部分且保留中间点}} else { //满足条件3if ((s1 d1) % 2 0) { //若元素个数为奇数d1 m1; //舍弃A中间点以后的部分且保留中间点s2 m2; //舍弃B中间点以前的部分且保留中间点}else { //元素个数为偶数d1 m1 1; //舍弃A中间点以后部分且保留中间点s2 m2; //舍弃B中间点及中间点以前部分}}}return A[s1] B[s2] ? A[s1] : B[s2];
}
