---
title: DSAP HW1 聲明
tags: DSAP
---

> 此文件撰寫於 HackMD ，[網頁版瀏覽](https://hackmd.io/@ruby0322/SkO8o9nkq)。

# DSAP110-2 HW1

作者：資管一顧寬証，學號 B10705016。

以下所有正面表列的是有尋求、提供幫助之處，若**無特別說明則代表未尋求、提供幫助**。

> 感謝所有在網路上提供免費資訊、資源的人們，讓我在遇到問題、忘記細節時可以透過簡單搜尋就能得到良好的解。

## #B1

[PDOGS 原始題目](https://pdogs.ntu.im/my-class/4/33/challenge/368/1035)

### 解題策略

以下是我遇到題目後想出到節提策略，依照時間先後排列。

#### Solution 1

基本上就是暴力解

用 C++ vector STL 儲存所有輸入的整數

待輸入完畢

- 若 $元素個數<3$
- 輸出末位元素
- 若 $元素個數\ge3$
- 輸出第三位元素

這個方法可行，但是在大量測資下會佔用非常多的空間，所以放上 PDOGS 後只拿到 $14$ 分，其餘皆為 `MLE` 。

#### Solution 2

看到 `MLE` 後，我才馬上發現第一個解有多冗。

題目只要求在輸入筆數大於三情況下，輸出所有數字中第三大者。因此，其實持續記錄前三大的數就足夠了。

所以我宣告一個長度為三的靜態陣列，並以無限小（小於題目給定範圍）初始化所有元素。

在每一筆輸入進來後，更新陣列，並使陣列維持降冪排列，以簡化插入流程。

這樣就可以 AC 了！

## #B3

[PDOGS 原始題目](https://pdogs.ntu.im/my-class/4/33/challenge/368/1060)

### 解題策略

我在此題使用了字典結構。

### 尋求協助

看到此題結構，我認為很適合使用 **字典** 資料結構解題，可大幅降低程式碼複雜度。

雖然知道 C++ 有 map STL，但是先前只有在 Python 使用 `dict` 資料型態，未曾在 C++ 有使用 **字典** 經驗。

因此我參考了

- [C++ std::map 用法與範例](https://shengyu7697.github.io/std-map/)
- [c++ pair 用法詳解
](https://www.itread01.com/content/1548114125.html)

### 提供協助

我曾在課餘時間與 陳禹翰 分享此題的解題方法及簡短介紹 C++ map STL。

## #C1

[PDOGS 原始題目](https://pdogs.ntu.im/my-class/4/33/challenge/368/1033)

### 解題策略

因為硬體限制，電腦在儲存、計算浮點數時會有無可避免的誤差。

因此，此題的最正確的解應該是用字串儲存浮點數，並寫出浮點數字串加減法的函式，即可確保答案 100% 精確。

但我有點懶的寫這麼麻煩的東西ＸＤ

所以我就想到以前高中電腦老師說的小撇步，那就是 Epsilon 方法，但因為過於久遠，我已經忘記細節，所以這部分有上網回憶了一下。

### 尋求協助

參考了

- [Epsilon method by Trevor Hickey on StackOverflow](https://stackoverflow.com/questions/17333/what-is-the-most-effective-way-for-float-and-double-comparison)
- [C++ fabs()用法及代碼示例](https://vimsky.com/zh-tw/examples/usage/fabs-in-c.html)

解決電腦在浮點數精確度上的硬體限制

## #C2

[PDOGS 原始題目](https://pdogs.ntu.im/my-class/4/33/challenge/368/1042)

### 解題策略

沿用 #C1 判斷兩幅點數相等，這題只需要多做字串處理。

將 `$` 消除以及將 `,` 替換成 ` ` 是我的作法，因為這樣可以直接利用 C++ 標準函式庫中 `sstream` 內的 `stringstream` 簡化接收輸入的流程。

## #E1

[PDOGS 原始題目](https://pdogs.ntu.im/my-class/4/33/challenge/368/1041)

### 解題策略

寫一函式
`std::string query(const std::string& guess, const std::string& ans)`
回傳題目要求的猜測結果。
逐字檢查猜測和答案，位置及字元街正確者為 `G` ；位置不正確但字元存在答案內者為 `Y` ；以上兩者皆不滿足者為 `_` 。

可以實作一個
`bool chrInStr(char chr, const std::string& str)`
函式，回傳一布林值代表給定字元是否存在於給定字串，幫助解題。

## #E2

[PDOGS 原始題目](https://pdogs.ntu.im/my-class/4/33/challenge/368/1050)

### 解題策略

將題目提供的猜側字串及猜測結果字串原封不動儲存於兩個分別的陣列或 vector 。

後接收所有選項，逐一處理，收到後立刻決定是否要輸出該選項，無需儲存。

至於如何判斷，最簡單的做法就是沿用 #E2 的 `query` 函式，並比對此選項套用至所有猜測與猜測結果，若有任何一組猜測與猜測結果對不上則不輸出，反之亦然。

# 意見回饋

## 上課節奏

滿喜歡老師上課的節奏，注重細節、原理，但又不會過於贅述。
而且老師很幽默ＸＤ

## 回家作業

### 難易度

回家作業看似簡單，但內含許多小巧思，很多細節不能忽略，否則就無法 AC。

我很享受解題過程中的腦力激盪，我也在解題過程中注意到很多以前從未關注過的細節。

### 份量

我認為這次份量算是剛剛好，但是其實我滿希望原本的那四題可以不要砍掉。

雖然這樣講自己負擔可能會更大，但是不苦就沒辦法進步！