# 演算法作業03
## 第1題：Insertion Sort
### 請依據課本推導方式，當5個數字用insertion sort排序，data movement的平均值為多少？
:::info
從$j$開始搬運一次的平均data movement
$\frac{2}{j}+\frac{3}{j}+\frac{4}{j}+ \cdots+\frac{j+1}{j}=\frac{j+3}{2}$
:::
:::info
$X=\sum\limits_{j=2}^{n}\frac{j+3}{2}=\frac{(n+8)(n-1)}{4}$
:::
:::success
$n=5$
$X=\frac{(5+8)(5-1)}{4}=13$
$Ans:13$
:::
### 請使用insertion sort排序 6,4,1,3,5。在四個回合中，每回合的data movement數量為何？總共的data movement數量為何？
#### 第一回合
:::info
初始的序列：
| a[0] | a[1] | a[2] | a[3] | a[4] |
|:----:|:----:|:----:|:----:|:----:|
| 6 | <font color="#f00">4</font> | 1 | 3 | 5 |
1. $4丟進暫存X$
2. $a_0>X，6往後移$
現在的序列：
| a[0] | a[1] | a[2] | a[3] | a[4] |
|:----:|:----:|:----:|:----:|:----:|
| <font color="#f00">6</font> | <font color="#f00">6</font> | 1 | 3 | 5 |
因為$j<0$所以跳出迴圈
3. $暫存X存在a_0$
現在的序列：
| a[0] | a[1] | a[2] | a[3] | a[4] |
|:----:|:----:|:----:|:----:|:----:|
| <font color="#f00">4</font> | 6 | 1 | 3 | 5 |
$data\ movement:3$
$sum\ of\ data\ movement:3$
:::
#### 第二回合
:::info
現在的序列：
| a[0] | a[1] | a[2] | a[3] | a[4] |
|:----:|:----:|:----:|:----:|:----:|
| 4 | 6 | <font color="#f00">1</font> | 3 | 5 |
1. $1丟進暫存X$
2. $a_1>X，6往後移$
現在的序列：
| a[0] | a[1] | a[2] | a[3] | a[4] |
|:----:|:----:|:----:|:----:|:----:|
| 4 | <font color="#f00">6</font> | <font color="#f00">6</font> | 3 | 5 |
3. $a_0>X，4往後移$
現在的序列：
| a[0] | a[1] | a[2] | a[3] | a[4] |
|:----:|:----:|:----:|:----:|:----:|
| <font color="#f00">4</font> | <font color="#f00">4</font> | 6 | 3 | 5 |
因為$j<0$所以跳出迴圈
4. $暫存X存在a_0$
現在的序列：
| a[0] | a[1] | a[2] | a[3] | a[4] |
|:----:|:----:|:----:|:----:|:----:|
| <font color="#f00">1</font> | 4 | 6 | 3 | 5 |
<font color="#900">
$data\ movement:4$
$sum\ of\ data\ movement:7$
</font>
:::
#### 第三回合
:::info
現在的序列：
| a[0] | a[1] | a[2] | a[3] | a[4] |
|:----:|:----:|:----:|:----:|:----:|
| 1 | 4 | 6 | <font color="#f00">3</font> | 5 |
1. $3丟進暫存X$
2. $a_2>X，6往後移$
現在的序列：
| a[0] | a[1] | a[2] | a[3] | a[4] |
|:----:|:----:|:----:|:----:|:----:|
| 1 | 4 | <font color="#f00">6</font> | <font color="#f00">6</font> | 5 |
3. $a_1>X，4往後移$
現在的序列：
| a[0] | a[1] | a[2] | a[3] | a[4] |
|:----:|:----:|:----:|:----:|:----:|
| 1 | <font color="#f00">4</font> | <font color="#f00">4</font> | 6 | 5 |
因為$X>a[j]$所以跳出迴圈
4. $暫存X存在a_1$
現在的序列：
| a[0] | a[1] | a[2] | a[3] | a[4] |
|:----:|:----:|:----:|:----:|:----:|
| 1 | <font color="#f00">3</font> | 4 | 6 | 5 |
<font color="#900">
$data\ movement:4$
$sum\ of\ data\ movement:11$
</font>
:::
#### 第四回合
:::info
現在的序列：
| a[0] | a[1] | a[2] | a[3] | a[4] |
|:----:|:----:|:----:|:----:|:----:|
| 1 | 3 | 4 | 6 | <font color="#f00">5</font> |
1. $5丟進暫存X$
2. $a_3>X，6往後移$
現在的序列：
| a[0] | a[1] | a[2] | a[3] | a[4] |
|:----:|:----:|:----:|:----:|:----:|
| 1 | 3 | 4 | <font color="#f00">6</font> | <font color="#f00">6</font> |
因為$X>a[j]$所以跳出迴圈
3. $暫存X存在a_3$
現在的序列：
| a[0] | a[1] | a[2] | a[3] | a[4] |
|:----:|:----:|:----:|:---------------------------:|:----:|
| 1 | 3 | 4 | <font color="#f00">5</font> | 6 |
<font color="#900">
$data\ movement:3$
$sum\ of\ data\ movement:14$
</font>
:::
:::success
$ans:14$
:::
## 第2題：Binary Search
### 請參考投影片25頁與26頁，算出15個有序數列使用Binary Search，平均的比對次數為何？
:::info
樹高
$\lfloor{log_{2}n}\rfloor+1$
:::
:::info
$A(N)= \frac{1}{2n+1} ($<font color="#090">$\sum\limits_{i=1}^{k}i2^{i-1}$</font>+<font color="#f00">$k(n+1)$</font>$),where\ k=\lfloor{log_{2}n}\rfloor+1$
$\sum\limits_{i=1}^{k}i2^{i-1} = 2^{k}(k-1)+1$
$A(N)= \frac{1}{2n+1}($<font color="#f00">$2^{k}(k-1)+1$</font>$+k(n+1)),where\ k=\lfloor{log_{2}n}\rfloor+1$
:::
:::success
$k_{n=15}=\lfloor{log_{2}15}\rfloor+1=4$
$A(15)= \frac{1}{2\times15+1}(2^{4}(4-1)+1+4(15+1))$
$A(15)=\frac{1}{31}\times(16\times3+1+4\times16)$
$A(15)=\frac{1}{31}\times(48+1+64)$
$A(15)=\frac{1}{31}\times(113)$
$A(15)=\frac{113}{31}\simeq3.645$
$Ans:\frac{113}{31}\simeq3.645$
:::
## 第3題：完全平方數
### 解題思路
第一個小於2147483647的完全平方數是$46340\times 46340$
先判斷是不是在範圍內
找到第一個大於等於$\sqrt[2]{num}$的$l$
然後判斷$l \times l$是否等於$num$
### 程式碼
```cpp=
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題
### 解題思路
二分搜找第一個大於他的值
然後再判斷是不是超出去了
### 程式碼
```cpp=
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
```cpp=
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$
如果數量不到三個就一個一個看
### 程式碼
```cpp=
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題
### 解題思路
跟上次作業求最大值的二分搜概念一樣
把如果是前半段比較大的就把左界拉過去
而右界基本上就是一直縮
加上判斷是不是最尾端再輸出就好
### 程式碼
```cpp=
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題
已填
Sign in with Wallet
Connect another wallet