『嗨威说』算法设想与剖析 – 算法第二章上机实践报告(二分查找 / 改写二分搜索算法 / 两个有序序列的中位数)

『嗨威说』算法设想与剖析 – 算法第二章上机实践报告(二分查找 / 改写二分搜索算法 / 两个有序序列的中位数)

本文索引目次:

一、PTA试验报告题1 : 二分查找

  1.1  实践题目

  1.2  题目形貌

  1.3  算法形貌

  1.4  算法时刻及空间庞杂度剖析

二、PTA试验报告题2 : 改写二分搜刮算法

  2.1  实践题目

  2.2  题目形貌

  2.3  算法形貌

  2.4  算法时刻及空间庞杂度剖析

三、PTA试验报告题3 : 两个有序序列的中位数

  3.1  实践题目

  3.2  题目形貌

  3.3  算法形貌

  3.4  算法时刻及空间庞杂度剖析

四、试验心得体会(实践收成及迷惑)

 

 

一、PTA试验报告题1 : 二分查找

  1.1  实践题目:

  1.2  题目形貌:

      这道题重要论述,给你一段有序的数字序列(已排好序了),并给出须要查找的数Value,应用二分查找发法找出Value地点的下标,以及查找历程当中所比较的次数。

  1.3  算法形貌:

    二分查找的定义:

      二分查找也称折半查找(Binary Search),它是一种效力较高的查找要领。

      折半查找请求线性表必需采纳递次存储构造,而且表中元素按关键字有序分列

    二分查找的操纵:

      假如以本例的样例来讲,具体操纵流程以下:

      起首获得了一段数字序列,存入空间Temp:

 

      将这段Temp数组送入递归中,赋值摆布指针为0和3(下标)

 

 

 

 

       求得left与right的中心下标mid = ( l + r) >> 1,mid效果是向下取整的,得注重一下!

 

 

 

      获得中心下表mid以后,对mid地点的数,跟value值,举行比较,假如小了,那末就送入递归(mid +1 ,right)

      假如比value值大了,那末就送入递归(left,mid)区间。

      在此处,temp【mid】 = 2,大于题目给的value,所以,我们送入递归(0,1)中,剩下的数字就不管了。

 

      此时发明mid = (0 + 1 )/ 2 = 0, 地点的值与题干的value值 相称,今后return返回,到此统共比较2次。

      下面是代码展现:

#include<bits/stdc++.h>
using namespace std;

int temp,x,ans,cnt,mark[99999999];
int getAns(int l,int r)
{
    cnt++;
    if(l >= r) 
     return l; int mid = (l + r) / 2; if(mark[mid] == x)
     return mid; if(x<=mark[mid]) return getAns(l,mid-1); else
     return getAns(mid+1,r); } int main() { cin>>temp; for(int i = 0;i<temp;i++) cin>>mark[i]; cin>>x; ans = getAns(0,temp-1); if(mark[ans] != x) ans = -1; cout<<ans<<endl; cout<<cnt<<endl; }

  1.4  算法时刻及空间庞杂度剖析:

    团体算法上看,二分算法是不停折半查找,不停折半,所以时刻庞杂度是以2为底的系数,也就是O(log2 n)的庞杂度。

    再加上特判的一些处置惩罚,以及输出的处置惩罚,都是在O(1)的庞杂度,所以综合起来,时刻庞杂度是O(logn)。

    空间庞杂度上,运用一个与题目范围一致的Temp数组空间,而且运用了三个暂时变量,团体来讲没有拓荒新的辅佐空间。

    所以空间庞杂度是O(1)。

 

 

二、PTA试验报告题2 : 改写二分搜刮算法:

  2.1  实践题目:

  2.2  题目形貌:

    第二题是二分算法的一个小小革新,不过做了一个变化,就是不存在指定数value时,就输出小于x的最大元素位置i和大于x的最小元素位置j,假如存在这个数,就直接输出i,j,且i == j。

  2.3  算法形貌:

    起首,读题:就是不存在指定数value时,就输出小于x的最大元素位置i和大于x的最小元素位置j,实在在这里能够发明,当二分递归出来的效果l,纵然找不到,也是小于x的最大元素位置i,那末求大于x的最小元素位置j只须要加1即可,关于迥殊的点,只须要举行一些简朴的特判,就能够过了。

#include<bits/stdc++.h>
using namespace std;

int temp,x,ans,cnt,mark[99999999];
int getAns(int l,int r)
{
    cnt++;
    if(l >= r) 
    return l; int mid = (l + r) / 2; if(mark[mid] == x)
    return mid; if(x<=mark[mid])
   return getAns(l,mid-1); else
return getAns(mid+1,r); } int main() { cin>>temp>>x; for(int i = 0;i<temp;i++) cin>>mark[i]; ans = getAns(0,temp-1); if(mark[ans] != x) { if(ans == 0) cout<<"-1 0"; else cout<<ans<<" "<<ans+1; return 0; } cout<<ans<<" "<<ans<<endl; return 0; }

  2.4  算法时刻及空间庞杂度剖析:

    算法庞杂度照旧和第一题一样,实质都是二分搜刮,时刻庞杂度为O(log n)

    空间庞杂度上,照旧用了四个暂时变量并运用一个与题目范围同大的Temp数组,团体来讲没用运用分外的辅佐空间,空间庞杂度为O(1)。

 

 

三、PTA试验报告题3 : 两个有序序列的中位数:

  3.1  实践题目:

  3.2  题目形貌:

    该题目为:题干给你两段有序的数字序列,想方法运用logn的算法完成找出两段兼并后的序列内的中位数。

  3.3  算法形貌:

    这道题我一上来的主意思绪就是用排序然后取值,然则如许的时刻庞杂度就会到O(nlogn),超出了题目所限定的时刻庞杂度,因而我们须要别的思索一个新的方法,那就是运用二分搜刮,对差别的两段数学离别求解中位数:

    ①假如两段序列的中位数,都是相称的话,那末中位数即为该数。

    ②假如当第一段的中位数大于第二段的时刻,那末两头合中位数一定在第一段中位数前或第二段中位数后,这时候只取这两部分,再继续举行二分比较

    ③假如当第一段的中位数小于第二段的时刻,那末两头合中位数一定在第一段中位数背面或第二段中位数前面,这时候只取这两部分,再继续举行二分比较

    这里我须要用一下我火伴做的一张图,我以为做的还不错,专程分享一下:

     AC代码:

#include<iostream>
using namespace std;
int n,a[100000],b[100000];
int getAns(int a[],int b[],int n) {
    int l1 = 0, l2 = 0, r1 = n - 1, r2 = n - 1;
    while(l1 < r1 && l2 < r2) {
        int mid1 = (l1 + r1) / 2;
        int mid2 = (l2 + r2) / 2;
        if (a[mid1] == b[mid2])
            return a[mid1];
        if (a[mid1] < b[mid2]) {
            if ((l1 + r1) % 2 == 0) {
                l1 = mid1;
                r2 = mid2;
            }
            else {
                l1 = mid1 + 1;
                r2 = mid2 ;
            }
        }
        else {
            if ((l1 + r1) % 2 == 0) {
                r1 = mid1;
                l2 = mid2;
            }
            else {
                r1 = mid1;
                l2 = mid2 +1;
            }
        }
    };
    if (a[l1] < b[l2])
        cout << a[l1] << endl;
    else
        cout << b[l2] << endl;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];
    getAns(a, b, n);
    return 0;
}

  3.4  算法时刻及空间庞杂度剖析:

    由于采纳二分查找算法来寻觅中位数而不是排序,所以时刻庞杂度为O(logn)。

    照旧用了四个暂时变量并运用两个与题目范围同大的数组,没用运用其他的辅佐空间,所以空间庞杂度为O(1)。

 

 

四、试验心得体会(实践收成及迷惑):

    二分搜刮看起来思绪挺简朴的,然则在实行历程当中,总会有一些细节上的小毛病,在这次的试验历程种也感觉到了:

    ① 边界点的等号是不是取到,中心点的位置是不是可取

    ② 二分的对象该怎样稳健处置惩罚

    等等的细节题目,在我一样平常ACM打题时也有碰到像double浮点数,处置惩罚上可能会更贫苦一点点,除此之外,二分还只是最基本的算法,更多的另有三分,尺取法等。最中心的头脑也就是,分而治之

    也在一些书本找到一些关于分治算法的诠释:

    分治算法是递归的处理题目的平常步骤为:

      (1)找出基线前提,这类前提必需尽量简朴

      (2)不停将题目剖析(或者说减少范围),直到相符基线前提。

      (3)按原题目的请求,推断子题目的解是不是就是原题目的解,或是须要将子题目的解逐层兼并组成原题目的解。

    分治法的设想头脑是,将一个难以直接处理的大题目,分割成一些范围较小的雷同题目,以便各个击破,分而治之。

 

 

若有毛病不当之处,烦请斧正。

Up Next:

同步FIFO design and IP level verification

同步FIFO design and IP level verification