---
# System prepended metadata

title: 演算法 HW6
tags: [演算法]

---

# 演算法 HW6

## :book: 觀念題 

### 第一題 Minimum Spanning Tree
![](https://i.imgur.com/HAAxbxZ.png)
1. 請以Kruskal方法，找出下圖的最小生成樹。請依序列出所選擇加入的邊。
    * 將邊由小到大排序。
    * 由小到大將邊加入forest(不能形成迴圈)，直到找到n-1個邊。
        ![](https://i.imgur.com/j4nYcod.png)
2. 同上題，請改為使用Prim(從a開始)方法。
    * 會有兩個集合 : A(被選入的點集合)、B(未被選入的點集合)，且會有一個初始選入的點。
    * 並從A裡面的點的相鄰點中找到最小權重的邊所連到的節點，將其節點加入A。
    * 直到所有點都被巡過了。
        ![](https://i.imgur.com/A4QkPo4.png)

### 第二題 Single Source Shortest Path
* 請用Dijkstra演算法找出下圖的由A出發的shortest path tree，並完成右表(共五回合)。
![](https://i.imgur.com/lXZT2gT.png)


| 回合 | 已選取點    | 選取點 |  (B)   | \(C\)  |  (D)   |  (E)   |  (F)   |
|:----:| ----------- |:------:|:------:|:------:|:------:|:------:|:------:|
|  1   | A           |   A    | ==10== |   15   |   +∞   |   +∞   |   +∞   |
|  2   | A,B         |   B    |   -    | ==15== |   22   |   +∞   |   25   |
|  3   | A,B,C       |   C    |   -    |   -    | ==22== |   25   |   25   |
|  4   | A,B,C,D     |   D    |   -    |   -    |   -    |   24   | ==23== |
|  5   | A,B,C,D,F   |   F    |   -    |   -    |   -    | ==24== |   -    |
|  6   | A,B,C,D,F,E |   E    |   -    |   -    |   -    |   -    |   -    |

### 第三題 Huffman Code
* 已知一份文件內7個符號出現的頻率為：A:2, B:8, C:3, D:4, E:6, F:10, G:7。
* 請找出此7個符號的Huffman code。
* ![](https://i.imgur.com/WDTosnI.png)


|  A   | B   | C    | D   | E   | F   | G   |
|:----:| --- | ---- | --- | --- | --- | --- |
| 0110 | 00  | 0111 | 010 | 110 | 10  | 111 |
* 若有一組編碼為1100110111，求解碼後的符號。
    110 0110 111 -> E A G

##  :desktop_computer: 程式題 Greedy類型 (使用語言 : C++)

### 第四題 隔出最多的水

* leetcode 11
* 時間:20分鐘
* 自己完成的程度 : 完全靠自己
* 思路 : 
:::success
因為這個題目不需要考慮中間隔板高度，僅需要考慮最旁邊的高度及兩者間的距離，因此
直接計算最大容量 -> ==min(左邊高度，右邊高度) * 兩者距離==;
偌大於原本所記錄的最大容量，則更新最大容量。
且
因為左右兩邊高度會影響最大容量，因此將==較短隔板那邊的index向內縮==，尋找是否更高的隔板可使容量增加。
:::
* 程式碼 :
```cpp==
class Solution {
public:
    int maxArea(vector<int>& height) {
        int left=0;
        int right=height.size()-1;
        int max=0;
        while(left<right)
        {
            int vol=0;
            vol=min(height[left],height[right])*(right-left);
            if(vol>max)
                max=vol;
            if(height[right]>height[left])
                left++;
            else if(height[right]==height[left])
            {
                left++;
                right--;
            }
            else
                right--;
        }
        return max;
    }
};
```
* 通過截圖
    ![](https://i.imgur.com/Y8CXcbb.png)

### 第五題 跳到最後-V2

* leetcode 45
* 時間:40分鐘
* 自己完成的程度：參考網路
* 思路 : 
:::success
先判斷目前可到達的最遠位置，並記錄上一次到達之最遠距離。
若現在index為上一次可達最遠之位置 -> 需要再跳一次 -> 次數+1。
並將本次最遠位置設為目前最後一次可達最遠位置。
:::
* 程式碼:

```cpp==
class Solution {
public:
    int jump(vector<int>& nums) {
        int times=0;
        int far=0;
        int end=0;
        
        for(int i=0;i<nums.size()-1;i++)
        {
            far=max(far,nums[i]+i);
            if(i==end)
            {
                times++;
                end=far;
            }
        }
        return times;
    }
};
```
* 通過截圖
    ![](https://i.imgur.com/kmSPm9c.png)

## :pushpin:心得

### 第六題 本週心得
本次觀念題的部分，幾乎離散都有教過，都還有些印象，所以在看影片和寫觀念題的時候，比較輕鬆。
而程式題的部分，不曉得為甚麼，還是有些障礙，看來需要多練練了。

###### tags: `演算法`