---
disqus: chiaoshin369
---
# 資料結構 W1 線上教學
**Data Structures**
>**講師/教授**[name=黃國璽][color=#ed794b]
:::spoiler **文章大綱**
[TOC]
:::

## 課前 學校資訊 (行事曆與宣傳事項)
>老師預先在9/11錄影，以**非同步教學**

講解一些注意事項，教材一律放在**高科教學平台**
並且注意**學校行事曆**預先規劃的日期

==校安中心電話== `0800-550-995` 分機 2 (楠梓校區)
若有人受傷先連絡119，再聯絡110做相關筆錄

輔導室在行政大樓6樓、健康中心在行政大樓後方操場附近

## 上課注意事項 (課程大綱)
### 什麼是教學大綱?
>用來理解 課堂 **上課內容** 與 **所需資料**

### 校務系統
注意帳密資安
帳號guest密碼123，可以利用 **訪客登入** 查詢 ==課程大綱==
可以藉由 **教師課表** 找尋 **授課大綱**

若要找教授，請在該教授課堂時間點另行預約
==[office hour](https://webap.nkust.edu.tw/nkust/f_index.html)== **詢問老師相關問題**
資料結構上完三節，下一節 統一詢問 ==(16:30~17:20)==

==2403電腦教室(二)==，==週一及週五==

==系辦==，==週三(5、6節)==

### 授課大綱
#### What about 資料結構?
>用來**處理資料的方法**，如何有效的運用資料，提升程式執行效率。

:::success
**情境題**
兩個人比賽寫程式，看誰的資料最快出來，第一個查資料花了5秒，第二個花了3秒，
請問他們兩個的程式，2秒差距在哪?
<br>:+1: **差別在於資料處理的結構**
:::

:::success
**情境題2**
假設你是老闆，兩個員工工作，第一個查資料花了3分鐘，第二個花了5天，
請問你會怎麼選擇?
<br>:+1: **選擇效率最高的員工** ~~(就能壓榨他了)~~ :satisfied:
:::

>[高頻交易](https://zh.wikipedia.org/wiki/%E9%AB%98%E9%A0%BB%E4%BA%A4%E6%98%93)
>利用資訊不對等去換取相對的報酬。

:::danger
:warning: 若對資料結構有興趣，可以再修 **演算法**
(技能樹=> 管數/java排序➜資料結構➜演算法)
:::

>**化理論為實作**
>用程式設計競賽問題，[onlinejudge線上解題系統](https://zh.wikipedia.org/wiki/%E5%9C%A8%E7%BA%BF%E8%AF%84%E6%B5%8B%E7%B3%BB%E7%BB%9F)，去強化程式能力。

>額外延伸想法 SITCON2021
>[建置自己的 online Judge 系統](https://blog.techbridge.cc/2020/03/20/build-your-own-online-judge/)[name=薰Shin][color=#EA0]

>**學東西什麼都可以學，最好什麼都會一些，再找自己有興趣的，再專研再深入。**[name=黃國璽][color=#EA0000]
>技能樹先點深，再點廣。(參考[工程師技能樹](https://hackmd.io/@chiaoshin369/LearnOnActivity/https%3A%2F%2Fhackmd.io%2F%40chiaoshin369%2FnkustLearn1)活動所學)

#### 教科書
投影片主要以 [**Fundamental Data Structures Using C++ 2/e**](https://www.tenlong.com.tw/products/9780929306377) 為主

Horowitz、Sahni 資訊界做演算法，厲害的前輩

[中文翻譯: **基礎資料結構 ─ 使用 C++ 第二版**](https://www.tenlong.com.tw/products/9789868359703)

戴顯權老師 成大電機系或資工系

>相關PPT老師有提供，已經放在[教學平台](https://elearning.nkust.edu.tw/mooc/index.php)上，請自行下載。

#### 成績評分方式
平時成績(實作作業、小考、出席) 40%
期中考 30%、期末考 30%

**期中期末** 為 ==筆試==

## 教學資源與作業
>前往[教學平台](https://elearning.nkust.edu.tw/mooc/index.php)獲取資料

提供**兩種格式**的檔案做列印
1. A4大小印四個畫面排版
2. 一般PPT

### 解壓縮軟體
大部分都使用 [WinRAR](https://zh.wikipedia.org/wiki/WinRAR)

可以使用 [Bandizip](https://tw.bandisoft.com/bandizip/) 去解壓縮
[Bandizip - 維基百科，自由的百科全書](https://zh.wikipedia.org/wiki/Bandizip)

老師推另一款 [7-Zip](https://www.developershome.com/7-zip/)
[7-Zip - 維基百科，自由的百科全書](https://zh.wikipedia.org/wiki/7-Zip)
開放原始碼的解壓縮軟體

### 課堂每週作業
>可以看到 [CPE列表](https://drive.google.com/file/d/1-Y-rSkw969LHqa3eFPRglMrDowiYP7Dp/view?usp=sharing)
>此為CPE[一顆星程式選集](https://cpe.cse.nsysu.edu.tw/environment.php#starList)的作業
>總共寫16個禮拜(到學期末結束)

>==每週做三題==[color=#EA0000]
>多一些實作，少一些理論

#### What about CPE ?
>[CPE](https://cpe.cse.nsysu.edu.tw/) 是 大學程式能力檢定 (大專免費證照考試)

#### What about [一顆星程式選集](https://cpe.cse.nsysu.edu.tw/environment.php#starList) ?
>為最簡單的程式題目 練習題

老師有將難易度調整，結果為 [**CPE列表**](https://drive.google.com/file/d/1-Y-rSkw969LHqa3eFPRglMrDowiYP7Dp/view?usp=sharing)
49題就沒有放進來，主要就是簡單的排序跟輸出相關。

##### onlinejudge解題系統
>用程式設計競賽問題，[onlinejudge線上解題系統](https://zh.wikipedia.org/wiki/%E5%9C%A8%E7%BA%BF%E8%AF%84%E6%B5%8B%E7%B3%BB%E7%BB%9F)，去強化程式能力。

按照老師作法，點擊 **選集** 中的==第24題==
會連到UVA的 [onlinejudge](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1012)

如圖
>如果畫面看不到，對圖片 **按右鍵**，點 **在新分頁開啟圖片**

此系統蒐集了全世界從以前到現在的程式設計競賽題目
大部分都是英文版本的國際賽

>第一題(CPE選集中第24題)

{%pdf https://onlinejudge.org/external/100/p10071.pdf %}

畫面上分別有
1. 題目主要說明
2. Input 輸入資料說明
3. Output 輸出資料說明
4. Sample Input 範例輸入資料
5. Sample Output 範例輸出 結果資料

:::success
:paperclip: **題解**

**粒子具有初始速度和加速度。
如果它在一定時間後的速度是 v 那麼它在兩倍的時間內的位移是多少？**
<br>==對於輸入的每一行，在一行中打印一個整數，表示該時間的兩倍的位移。==
<br>第一個值為速度v
第二個值為時間t
<br>:+1: 兩倍時間*v
<br>
1. (0*2)*0=0
2. (5*2)*12=120

:::

>第十七題(CPE選集中第1題)

{%pdf https://onlinejudge.org/external/100/p10041.pdf %}

:::success
:paperclip: **題解**

**舉世聞名的黑幫大佬維托·戴斯通 (Vito Deadstone) 即將搬到紐約。
他在那裡有一個很大的家庭，他們都住在拉馬菲亞大街。**

**由於他會經常拜訪他的所有親戚，因此他試圖在他們附近找到一所房子。
Vito 想要最小化與所有這些人的總距離，並勒索您編寫一個程序來解決他的問題。**
<br>==對於每個測試用例，您的程序必須編寫與最佳 Vito 房屋的最小距離總和給他的每一位親戚。==

==兩個街道號碼 si 和 sj 之間的距離是 dij = |si − sj |。==
<br>有兩組資料
分別為 2 2 4、3 2 4 6
第一組資料，有兩個親戚，分別住在2跟4
第二組資料，有三個親戚，分別住在2跟4跟6
<br>:+1: 兩數的最小距離
<br>
1.
2.
<br>:exclamation:用到陣列跟排序
:::

>**註冊 UVA onlinejudge**[color=#EA0000]

先到 https://onlinejudge.org/ 去申請帳號
<br>到 **註冊的信箱** 點擊 ==認證信==

>**課堂額外延伸思考**
>[什麼是LeetCode？ LeetCode是一個收集軟體工程師面試考古題的線上練功網站。 | by 吳致賢（Jhih-Sian Wu） | 一個人的文藝復興 | Medium](https://medium.com/%E4%B8%80%E5%80%8B%E4%BA%BA%E7%9A%84%E6%96%87%E8%97%9D%E5%BE%A9%E8%88%88/%E4%BB%80%E9%BA%BC%E6%98%AFleetcode-66b043e95cb8)[name=薰Shin][color=#EA0]

### 第一週作業
>至 [教學平台](https://elearning.nkust.edu.tw/mooc/index.php)

作業要求：
1. 請至 UVa Online Judge 網站申請帳號，
https://uva.onlinejudge.org/

2. 申請完畢後請至以下Google表單回報您的 UVa Username 與 UVa Online Judge ID。
https://goo.gl/forms/DLJGKZXeITlSH9l32

3. 於上述Google表單回報完成後，點選此作業之「開始作答」->「確定繳交」，完成本作業繳交程序。

>**步驟一** 到My Account


>**步驟二** 填google表單回報
https://goo.gl/forms/DLJGKZXeITlSH9l32

>**步驟三** 到教學平台 按「開始作答」->「確定繳交」


#### 透過uHunt查找是否解題
[uHunt | UVa Hunting](https://uhunt.onlinejudge.org/)
>可以知道什麼時間點，解題時間是如何等
>所以千萬別心存僥倖，乖乖練功強化技能

### 第二週 作業開始
9/28前交3題，每週不斷累積題目。

pdf檔案不大於1MB。

>10071

{%pdf https://onlinejudge.org/external/100/10071.pdf %}

public class Main
{
    public static void main(String args[])
    {
        //
    }
}

>10055

{%pdf https://onlinejudge.org/external/100/10055.pdf %}

public class Main
{
    public static void main(String args[])
    {
        //
    }
}

[Java 變數型態與宣告](http://www.tsnien.idv.tw/Java1_WebBook/chap2/2-3%20%E8%AE%8A%E6%95%B8%E5%9E%8B%E6%85%8B%E8%88%87%E5%AE%A3%E5%91%8A.html)

>10738

{%pdf https://onlinejudge.org/external/107/10783.pdf %}

public class Main
{
    public static void main(String args[])
    {
        //
    }
}

#### ==英翻中==工具
[Lucky貓的 UVA（ACM）園地](http://web.kshs.kh.edu.tw/academy/luckycat/)

#### 讓程式碼==有顏色易辨識==
影片56:40開始、64:45設定
(老師利用notepad++改變顏色)

>可以利用 **vs code** 寫 java，去**改變程式碼顏色**
>(已用信件詢問老師)[name=薰Shin][color=#EA0]


1. 下載vs code
2. 套件安裝(共4~5個)
3. 拉 存程式的資料夾 到 VS Code，直接複製貼上到word即可

:warning: <font color=#EA0000>**編輯器背景主題記得一律==預設==!!!**</font>

若用到暗黑模式或其他主題，貼到word中則會呈現底色問題。

:warning: <font color=#EA0000>**若中文部分產生亂碼，將==ANSI== 變成 ==UTF-8==!!!**</font>

>因為vscode無法讀取ANSI的編碼，所以改回big8他就會正常讀取了。
>
>**參考文章 :**
>>[VSCODE运行java代码，中文乱码解决方法_jfztaq的博客-CSDN博客](https://blog.csdn.net/jfztaq/article/details/102648273)

<a class="btn btn-primary" href="https://hackmd.io/@chiaoshin369/vscode_java" role="button"> 簡化補充部分 **>**</a>

#### word 格式編輯
>按照老師影片跟範本格式修正

>有個地方，可以把**程式碼縮小**。
>>回去聽第三部67:00min後的部分

>**操作示範**[color=#EA0000]


#### ==延伸了解== online judge
[Online Judge 概要 - HackMD](https://hackmd.io/@ETC/rkvDzrKHr/https%3A%2F%2Fhackmd.io%2F%40wiwiho%2FCPN-online-judge)

#### 如何用 online judge ==開始解題==
>==線上解題系統==都有一個**範本**去**讀取資料**[color=#EA0000]
[參考 JMJudge](http://jmj.cmgsh.tp.edu.tw/UserGuide.jsp)

這堂課程需要用到JAVA的範本格式

public class JAVA 
{
	public static void main(String[] args)
       {
		Scanner keyboard=new Scanner(System.in);
		String s;
		while (keyboard.hasNext()) 
               {
			s=keyboard.nextLine();
			System.out.println("hello, " + s);
		}
	}
}

>需要用到 `keyboard.hasNext()` 才能讓他**不斷執行**系統給的**資料庫資料**。[color=#EA0000]

[java.util.Scanner.hasNext()方法實例 - Java.util包](http://tw.gitbook.net/java/util/scanner_hasnext.html)

##### 如果不會用，UVA的online judge
>可以嘗試用 [**高中生程式解題系統**](https://zerojudge.tw/)

裡面全程中文，也能方便debug後，並送出驗證程式碼錯誤。
同時也有==CPE一顆星選集==的題目可以練習。
[CPE一顆星選集](https://zerojudge.tw/Problems?tabid=UVA#tab03)
[c022. 10783 - Odd Sum - 高中生程式解題系統](https://zerojudge.tw/ShowProblem?problemid=c022)

>可以利用 **題庫編號** 如:10783 ，查到**需要解題的題庫**。

:::spoiler 最後更新日期
>==第一版==[time=2021 9 12 , 4:31 AM]

>第二版[time=2021 9 17 , 10:53 PM]

>第三版[time=2021 9 22 , 8:16 PM]

>**最後版[time=2021 9 29 , ]**[color=#786ff7]
:::

###### tags: `資料結構` `高科大` `複習用`