# 演算法作業08
## 第1題: Voronoi Diagram
### 請畫出下圖兩個VD合併結果，畫出新建立的線段(註明為哪兩點的中垂線)，並說明簡述流程。
:::info
藍色代表目前線段結果
綠色代表新增的部分
橘色代表刪除的部分
紅色是兩點的連線
:::
:::success
#### 第一回合
選出最高的點($P_1$&$P_5$)
$\overline{P_1P_5}$
($Z$在圖外面所以看不到)
$Z$在$\overline{P_4P_5}$的中垂線上，所以下一個是用$P_4$取代$P_5$
也就是$\overline{P_1P_4}$
:::
:::success
#### 第二回合
從第一回合獲得的$\overline{P_1P_4}$
$Z$在$\overline{P_1P_3}$的中垂線上，所以下一個是用$P_3$取代$P_1$
也就是$\overline{P_3P_4}$
:::
:::success
#### 第三回合
從第二回合獲得的$\overline{P_3P_4}$
$Z$在$\overline{P_4P_6}$的中垂線上，所以下一個是用$P_6$取代$P_4$
也就是$\overline{P_3P_6}$
:::
:::success
#### 第四回合
從第三回合獲得的$\overline{P_3P_6}$
$Z$在$\overline{P_2P_3}$的中垂線上，所以下一個是用$P_2$取代$P_3$
也就是$\overline{P_2P_6}$
:::
:::success
#### 第五回合
從第四回合獲得的$\overline{P_2P_6}$
$P_2$跟$P_6$已經是最低的兩個點了
所以結束了
:::
:::success
#### 最終結果
:::
## 第2題: Voronoi Diagram的應用
### 請說明The Euclidean all nearest neighbor problem為何，以及如何應用VD來解此問題？
:::success
Euclidean是指歐基里德距離
指的是平面上$n$個點找出所有的點裡的距離最近的鄰居
:::
:::success
因為最近距離的那個點一定會共用VD的邊，
所以把VD圖上的每個邊檢查一次，把兩個邊的資訊更新到點上，
如果是最小值的話，那邊的兩邊各是對方的最近鄰居。
:::
## 第3題: FFT
### 當輸入為：{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}，請說明如何應用FFT得到結果(只須說明計算過程，不用算出結果)？
把16個用奇數項和偶數項分開
`1,3,5,7,9,11,13,15` & `2,4,6,8,10,12,14,16`
把8個8個再切成奇數項和偶數項分開
`1,5,9,13` & `3,7,11,15` & `2,6,10,14` & `4,8,12,16`
再切
`1,9` & `5,13` & `3,11` & `7,15` & `2,10` & `6,14` & `4,12` & `8,16`
切成一個一個後
進行下圖的方法
因為已經分成奇偶項了，所以可以拿前面的結果節省時間
$c$指的是奇數項的那條做過FFT的結果
$d$指的是偶數項的那條做過FFT的結果
EX:
`1,5,9,13`切成`1,9` & `5,13`
`1,9`$\to$`10,-8`
`5,13`$\to$`18,-8`
$c=$`10,-8`
$d=$`18,-8`
再推到
$b_j=c_j+\omega^{-j}d_j$
$b_{j+\frac{n}{2}}=c_j-\omega^{-j}d_j$
$n=4,\omega=\sqrt{-1}=i,\frac{n}{2}=2$
$\omega^{0}=1$、$\omega^{-1}=-i$、$\omega^{-2}=-1$、$\omega^{-3}=i$、$\omega^{-4}=1$
$j=0:$
$b_0=10+\omega^{0}18=10+18=28$
$b_2=10-\omega^{0}18=10-18=-8$
$j=1:$
$b_1=-8+(\omega^{1}\times-8)=-8+8i$
$b_3=-8-(\omega^{1}\times-8)=-8-8i$
$[b0,b1,b2,b3]=[28,-8,-8+8i,-8-8i]$
以此類推，可以算出每段的FFT
最終就能算出整體的FFT
## 第4題: 由Preorder與Inorder建構二元樹
### 解題思路
preorder:中左右
inorder:左中右
把它切成節點跟左右子樹就可以了
我很常寫這個，所以很直覺的寫完了
### 程式碼
```cpp=
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if(preorder.size()==0)
{
return NULL;
}
TreeNode* res = new TreeNode(preorder[0]);
if(preorder.size()==1)
{
return res;
}
int i;
for(i=0;i<inorder.size();i++)
{
if(inorder[i]==preorder[0])
{
break;
}
}
vector<int> lp(preorder.begin()+1,preorder.begin()+i+1);
vector<int> li(inorder.begin(),inorder.begin()+i);
vector<int> rp(preorder.begin()+i+1,preorder.end());
vector<int> ri(inorder.begin()+i+1,inorder.end());
res->left=buildTree(lp,li);
res->right=buildTree(rp,ri);
return res;
}
};
```
### 測試輸出輸入的畫面截圖
### 花費時間
14分鐘
### 完成程度
完全自己解出
## 第5題: 由Postorder與Inorder建構二元樹
### 解題思路
inorder:左中右
postorder:左右中
我拿了上一題的程式修改一下就過ㄌ
### 程式碼
```cpp=
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if(postorder.size()==0)
{
return NULL;
}
TreeNode* res = new TreeNode(postorder[postorder.size()-1]);
if(postorder.size()==1)
{
return res;
}
int i;
for(i=0;i<inorder.size();i++)
{
if(inorder[i]==postorder[postorder.size()-1])
{
break;
}
}
vector<int> lp(postorder.begin(),postorder.begin()+i);
vector<int> li(inorder.begin(),inorder.begin()+i);
vector<int> rp(postorder.begin()+i,postorder.begin()+postorder.size()-1);
vector<int> ri(inorder.begin()+i+1,inorder.end());
res->left=buildTree(li,lp);
res->right=buildTree(ri,rp);
return res;
}
};
```
### 測試輸出輸入的畫面截圖
### 花費時間
4分鐘
### 完成程度
完全自己解出
## 第6題：由Pretorder與Postorder建構二元樹
### 解題思路
一樣拿前面的做修改，不過這題我有想怎麼分左右子樹
首先preorder的第一個是root，再去切左右子樹，
`preorder[1]`會是preorder的左子樹的root，
而且會同時在postorder的左子樹的最右邊，所以只要找到一個$i$符合
`preorder[1] == postorder[i]` 那個$i$就會是左子樹的節點數量
就可以照這個做左右子樹的切分ㄌ
### 程式碼
```cpp=
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
if(postorder.size()==0)
{
return NULL;
}
TreeNode* res = new TreeNode(postorder[postorder.size()-1]);
if(postorder.size()==1)
{
return res;
}
int i;
for(i=0;i<postorder.size();i++)
{
if(preorder[1]==postorder[i])
{
break;
}
}
vector<int> lpr(preorder.begin()+1,preorder.begin()+i+2);
vector<int> lpo(postorder.begin(),postorder.begin()+i+1);
vector<int> rpr(preorder.begin()+i+2,preorder.end());
vector<int> rpo(postorder.begin()+i+1,postorder.begin()+postorder.size()-1);
res->left=constructFromPrePost(lpr,lpo);
res->right=constructFromPrePost(rpr,rpo);
return res;
}
};
```
### 測試輸出輸入的畫面截圖
### 花費時間
12分鐘
### 完成程度
完全自己解出
## 心得
Sign in with Wallet
Connect another wallet