演算法作業03

第1題：Insertion Sort

請依據課本推導方式，當5個數字用insertion sort排序，data movement的平均值為多少？

從

$j$開始搬運一次的平均data movement

$\frac{2}{j}+\frac{3}{j}+\frac{4}{j}+\cdots +\frac{j+1}{j}=\frac{j+3}{2}$

$X=\sum _{j=2}^n\frac{j+3}{2}=\frac{(n+8)(n-1)}{4}$

$n=5$

$X=\frac{(5+8)(5-1)}{4}=13$

$Ans:13$

請使用insertion sort排序 6,4,1,3,5。在四個回合中，每回合的data movement數量為何？總共的data movement數量為何？

第一回合

初始的序列：

a[0]	a[1]	a[2]	a[3]	a[4]
6	4	1	3	5

1. $4\mathrm{丟}\mathrm{進}\mathrm{暫}\mathrm{存}X$
2. $a_0>X，6\mathrm{往}\mathrm{後}\mathrm{移}$

現在的序列：

a[0]	a[1]	a[2]	a[3]	a[4]
6	6	1	3	5

因為

$j<0$所以跳出迴圈

3. $\mathrm{暫}\mathrm{存}X\mathrm{存}\mathrm{在}{a}_0$

現在的序列：

a[0]	a[1]	a[2]	a[3]	a[4]
4	6	1	3	5

$datamovement:3$

$sumofdatamovement:3$

第二回合

現在的序列：

a[0]	a[1]	a[2]	a[3]	a[4]
4	6	1	3	5

1. $1\mathrm{丟}\mathrm{進}\mathrm{暫}\mathrm{存}X$
2. $a_1>X，6\mathrm{往}\mathrm{後}\mathrm{移}$

現在的序列：

a[0]	a[1]	a[2]	a[3]	a[4]
4	6	6	3	5

3. $a_0>X，4\mathrm{往}\mathrm{後}\mathrm{移}$

現在的序列：

a[0]	a[1]	a[2]	a[3]	a[4]
4	4	6	3	5

因為

$j<0$所以跳出迴圈

4. $\mathrm{暫}\mathrm{存}X\mathrm{存}\mathrm{在}{a}_0$

現在的序列：

a[0]	a[1]	a[2]	a[3]	a[4]
1	4	6	3	5

$datamovement:4$

$sumofdatamovement:7$

第三回合

現在的序列：

a[0]	a[1]	a[2]	a[3]	a[4]
1	4	6	3	5

1. $3\mathrm{丟}\mathrm{進}\mathrm{暫}\mathrm{存}X$
2. $a_2>X，6\mathrm{往}\mathrm{後}\mathrm{移}$

現在的序列：

a[0]	a[1]	a[2]	a[3]	a[4]
1	4	6	6	5

3. $a_1>X，4\mathrm{往}\mathrm{後}\mathrm{移}$

現在的序列：

a[0]	a[1]	a[2]	a[3]	a[4]
1	4	4	6	5

因為

$X>a[j]$所以跳出迴圈

4. $\mathrm{暫}\mathrm{存}X\mathrm{存}\mathrm{在}{a}_1$

現在的序列：

a[0]	a[1]	a[2]	a[3]	a[4]
1	3	4	6	5

$datamovement:4$

$sumofdatamovement:11$

第四回合

現在的序列：

a[0]	a[1]	a[2]	a[3]	a[4]
1	3	4	6	5

1. $5\mathrm{丟}\mathrm{進}\mathrm{暫}\mathrm{存}X$
2. $a_3>X，6\mathrm{往}\mathrm{後}\mathrm{移}$

現在的序列：

a[0]	a[1]	a[2]	a[3]	a[4]
1	3	4	6	6

因為

$X>a[j]$所以跳出迴圈

3. $\mathrm{暫}\mathrm{存}X\mathrm{存}\mathrm{在}{a}_3$

現在的序列：

a[0]	a[1]	a[2]	a[3]	a[4]
1	3	4	5	6

$datamovement:3$

$sumofdatamovement:14$

$ans:14$

第2題：Binary Search

請參考投影片25頁與26頁，算出15個有序數列使用Binary Search，平均的比對次數為何？

樹高

$\lfloor lo{g}_{2}n\rfloor +1$

$A(N)=\frac{1}{2n+1}($

$\sum _{i=1}^{k}i{2}^{i-1}$+

$k(n+1)$

$),wherek=\lfloor lo{g}_{2}n\rfloor +1$

$\sum _{i=1}^{k}i{2}^{i-1}=2^k(k-1)+1$

$A(N)=\frac{1}{2n+1}($

$2^k(k-1)+1$

$+k(n+1)),wherek=\lfloor lo{g}_{2}n\rfloor +1$

$k_{n=15}=\lfloor lo{g}_{2}15\rfloor +1=4$

$A(15)=\frac{1}{2\times 15+1}(2^4(4-1)+1+4(15+1))$

$A(15)=\frac{1}{31}\times (16\times 3+1+4\times 16)$

$A(15)=\frac{1}{31}\times (48+1+64)$

$A(15)=\frac{1}{31}\times (113)$

$A(15)=\frac{113}{31}\simeq 3.645$

$Ans:\frac{113}{31}\simeq 3.645$

第3題：完全平方數

解題思路

第一個小於2147483647的完全平方數是

$46340\times 46340$
先判斷是不是在範圍內
找到第一個大於等於

$\sqrt[2]{num}$的

$l$
然後判斷

$l\times l$是否等於

$num$

程式碼

class Solution {
public:
    bool isPerfectSquare(int num) {
        if(num>46340*46340)
        {
            return 0;
        }
        int l=1,r=46340,mid;
        while(l<=r)
        {
            mid=(l+r)/2;
            if(mid*mid>=num)
            {
                r=mid-1;
            }
            else
            {
                l=mid+1;
            }
        }
        return l*l==num;
    }
};

測試輸出輸入的畫面截圖

花費時間

7分鐘

完成程度

完全自己解出

第4題

解題思路

二分搜找第一個大於他的值
然後再判斷是不是超出去了

程式碼

class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        int l=0,r=letters.size()-1,mid;
        while(l<=r)
        {
            mid=(l+r)>>1;
            if(letters[mid]>target)
            {
                r=mid-1;
            }
            else
            {
                l=mid+1;
            }
        }
        return l>=letters.size()?letters[0]:letters[l];
    }
};

如果用STL可以秒解:D

class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        int l = upper_bound(letters.begin(),letters.end(),target) - letters.begin();
        return l>=letters.size()?letters[0]:letters[l];
    }
};

測試輸出輸入的畫面截圖

花費時間

4分鐘

完成程度

完全自己解出

第5題

解題思路

二分搜去找mid那點的斜率
分成三個可能

1. /
   $l<=mid<=r$
2. \
   $l>=mid>=r$
3. ^
   $l<=mid>=r$

如果數量不到三個就一個一個看

程式碼

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int l=0,r=arr.size()-1,mid;
        while(r-l>=3)
        {
            mid=(l+r)>>1;
            if(arr[mid+1]>arr[mid]&&arr[mid]>arr[mid-1])
            {
                l=mid+1;
            }
            else if(arr[mid-1]>arr[mid]&&arr[mid]>arr[mid+1])
            {
                r=mid-1;
            }
            else
            {
                return mid;
            }
        }
        int ma=arr[l],in=l;
        for(int i=l+1;i<=r;i++)
        {
            if(arr[i]>ma)
            {
                ma=arr[i];
                in=i;
            }
        }
        return in;
    }
};

測試輸出輸入的畫面截圖

花費時間

14分鐘

完成程度

完全自己解出

第6題

解題思路

跟上次作業求最大值的二分搜概念一樣
把如果是前半段比較大的就把左界拉過去
而右界基本上就是一直縮
加上判斷是不是最尾端再輸出就好

程式碼

class Solution {
public:
    int findMin(vector<int>& nums) {
        int l=0,r=nums.size()-1,mid;
        while(l<=r)
        {
            mid=(l+r)>>1;
            if(nums[mid]>=nums[0])
            {
                l=mid+1;
            }
            else
            {
                r=mid-1;
            }
        }
        return l>=nums.size()?nums[0]:nums[l];
    }
};

測試輸出輸入的畫面截圖

花費時間

8分鐘

完成程度

完全自己解出

第7題

已填