# 演算法 HW8
## :book: 觀念題
### 第一題 Voronoi Diagram
請畫出下圖兩個VD合併結果，畫出新建立的線段(註明為哪兩點的中垂線)，並說明簡述流程。
* ans
畫出鄰近的點和點之間的中垂線(perpendicular bisector)，形成 Voronoi Diagram。
==所有的VD都是中垂線，但並非所有的中垂線都是VD。==
* 先找出合併左右兩個convex Hull的結果
* 會新增L~15~、L~26~
* 由上往下，找中垂線
* 找P~1~，P~5~的中垂線(b~15~)。
* 找P~1~，P~4~的中垂線(b~14~)，並將b~15~和b~14~連接起來。
* 找P~4~，P~3~的中垂線(b~34~)，並將b~14~和b~34~連接起來。
* 找P~3~，P~6~的中垂線(b~36~)，並將b~34~和b~36~連接起來。
* 找P~2~，P~6~的中垂線(b~26~)，並將b~36~和b~26~連接起來。
* 結果
### 第二題 Voronoi Diagram的應用
請說明The Euclidean all nearest neighbor problem為何，以及如何應用VD來解此問題？
* ans
1. 平面上有n個點，要找出所有點的nearest neighbor。
2. VD性質 : ==我最近的鄰居一定會跟我共用VD邊。==
* 檢查所有的邊，提供兩點距離。
* 每個點依據所提供的兩點距離，找出最近的鄰居。
* 如果P~j~是P~i~的closest neighbor，則Pi和Pj共用同一個VD edge。
如果P~j~是closest neighbor但沒有共用同一個VD edge，一定有別的更近的鄰居。
$P_{i}N<P_{i}M\ and\ P_{i}L<P_{i}N$
$means\ that\ P_{i}P_{k}=2P_{i}L<2P_{i}N<2P_{i}M=P_{i}P_{j}$
### 第三題 FFT(快速傅立葉轉換)
當輸入為：{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}，請說明如何應用FFT得到結果(只須說明計算過程，不用算出結果)？
* ans
* 將其不斷分成兩堆(奇數項一堆，偶數項一堆)
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,15}
-> {1,3,5,7,9,11,13,15},{2,4,6,8,10,12,14,16}
-> {{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}}}}
* 並會發現，每兩兩一組會有一特別關係，將其合併。
$$
b=\displaystyle\sum_{k=0}^{n-1}a_ke^{i2𝞹jk/n}=\displaystyle\sum_{k=0}^{n-1}a_kw^{kj}\\
n=16,w=e^{i2𝞹}/16,{w_8}^4=-1,{w_8}^{16}=1
$$
## :desktop_computer: 程式題 Divide and Conquer (使用語言 : C++)
### 第四題 由Preorder與Inorder建構二元樹
* leetcode 105
* 時間:3小時
* 自己完成的程度 : 參考之前寫過的題目
* 思路 :
:::success
前序是中左右，中序是左中右
藉由前序的"中"(由左到右)，可得到左右子樹節點個數，同時也找到中序的"中"(前序[i]==中序[j])
將"中"依序放入linked list的左邊及右邊。(要先做左邊在做右邊)
找到"中"後，就可以將前序跟中序分成左右兩邊，重複同樣動作，直到NULL。
:::
* 程式碼 :
```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) {
int preI=0;
return tree(preorder,inorder,preI,0,inorder.size()-1);
}
TreeNode *tree(vector<int> &pre,vector<int>&in,int &preI,int inL,int inH)
{
if(inL>inH)
return NULL;
int x=pre[preI];
TreeNode *temp=new TreeNode(x);
preI++;
if(inL==inH)
return temp;
else
{
int i;
for(i=inL;i<=inH;i++)
{
if(in[i]==x)
break;
}
temp->left=tree(pre,in,preI,inL,i-1);
temp->right=tree(pre,in,preI,i+1,inH);
return temp;
}
}
};
```
> 要注意，preI要使用傳址的方式。
* 通過截圖
### 第五題 將排序好的數列轉為二元搜尋樹
* leetcode 106
* 時間:0.5小時
* 自己完成的程度：靠自己
* 思路 :
:::success
類似leetcode 105，但因為後序:左右中，所以
順序要改為後序由右到左找"中"
一樣分兩堆後，先做右邊再做左邊。
:::
* 程式碼:
```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) {
int postI=postorder.size()-1;
return tree(postorder,inorder,postI,0,inorder.size()-1);
}
TreeNode *tree(vector<int> &post,vector<int>&in,int &postI,int inL,int inH)
{
if(inL>inH)
return NULL;
int x=post[postI];
TreeNode *temp=new TreeNode(x);
postI--;
if(inL==inH)
return temp;
else
{
int i;
for(i=inL;i<=inH;i++)
{
if(in[i]==x)
{
temp->right=tree(post,in,postI,i+1,inH);
temp->left=tree(post,in,postI,inL,i-1);
return temp;
break;
}
}
return temp;
}
}
};
```
* 通過截圖
## :pushpin:心得
### 第六題 本週心得
* 觀念題其實原本不太懂FFT的公式到底怎麼來的，推不太出來，問了同學才大概理解一點。
* 程式題之前有寫過類似的題目，但因為上次沒有用到linked list，而這次使用了，耗了挺久的時間才完成，甚至寫到有點自信心崩掉(原本以為之前寫過，這次很快就可以寫完了，結果花了好久)，還好後面心態有調整好，並自己寫出來了。
###### tags: `演算法`
Sign in with Wallet
Connect another wallet