基本解題技巧

# 基本解題技巧 * [C++講義-1](https://hackmd.io/___nSr0LQLmhZKLNoWgsOg)(變數,輸入輸出,字元處理,判斷,迴圈) * [C++講義-2](https://hackmd.io/PbClBLHOROiMKHCZLhsyvg)(陣列,函式) ## 輸入 * **搭配 while** 例如: | 輸入說明| | -------- | | 輸入為一個整數 n，其中 n 不大於 10000。若 n = 0 表示資料結束。 | ```c++= //EXAMPLE int n; while(cin>>n&&n!=0){ do... } ``` 同理可知: 如果是.... | 輸入說明| | -------- | | 輸入為一個字串 Str，其中 Str...。若 Str = "GuoBao" 表示資料結束。 | ```c++= //只需要改成... string Str; while(cin>>Str&&Str!="GuoBao"){ do... } ``` 但是會有這種**奇怪的**輸入說明 ? | 輸入說明| | -------- | | 輸入以 EOF 結束。每一筆測試資料有一個數字 n，其中 n > 0。 | 那什麼是**EOF**...? **EOF** : 其實就是指"End Of File",也是一個**特殊名稱**,不能當變數名稱而當遇到EOF時,其實會回傳`false` ```c++= //所以...只要改成while(cin>>n)就可以了 int n; while(cin>>n){ do... } ``` **while**的其他用法 | 輸入說明| | -------- | | 輸入第一行為一個數字 n，接著有 n 個正整數。 | ```c++= int n,num; cin>>n; while(n--){ cin>>num; } //可以代替for loop幫你做單純要幾次的事 ``` ## 簡易Debug ==*Developers use dark IDE themes because bugs are attracted to the light*== * **語法錯誤** 當你build完你的程式,發現跳出一堆紅字在terminal... **學會看錯誤訊息**: 不要因為跳出看不太懂的英文放棄閱讀!嘗試找出裡面的**關鍵字**或嘗試推論 (除非你是用vscode 或 repl 之類的IDE....) 例如: ![](https://i.imgur.com/SwBUflr.png) 很明顯可以看到在第七行少了一個";" 又或是: ![](https://i.imgur.com/AIQDLqW.png) 有出現**declare**又有**變數C** ,大概就可以推斷出**c**還沒宣告 * **邏輯錯誤** 程式碼沒有跑出理想的結果... 但是又寫了好幾十行,也找不出什麼端倪... **改善方法** 在**寫好一小部分**時,就先輸出看看有沒有錯誤! 例如: | 題目說明 | | -------- | | 輸入兩個數字構成的字串,並輸出他們相加的結果 | 而你想到的方法是: 輸入後先換成數字,再相加 **可以拆成:** 1.字串轉數字 2.相加所以可以在轉成數字後,先輸出來看一下 **if(** 有錯 **)** Debug(找邏輯錯誤或調整想法) **else** 把2.寫完 ## 時間複雜度寫出一個解決問題的程式可能不困難不過程式要在 **時間最短(最有效率)** 的情況下++達成同樣目的++就有難度了例如: 你要尋找一個陣列中的某個元素的位置後並紀錄它是第幾個元素 **陣列:**`list={10,20,30,40,50}` **元素:**`num=30` 而你打算用一個for迴圈跑過: ```c++= int address;//存放位置的變數 int list={10,20,30,40,50},listsize=5;//陣列 int num=30;//要找的某元素 for(int i=0;i<llistsize;i++){ if(list[i]==num){ address=i+1; } } ``` 但是你會發現:當我找到`num`後,for迴圈會跑到**list的最後一個元素**才停止明顯浪費**找到`num`後到迴圈跑完的時間** **但陣列元素只有5個,沒什麼差吧?** 當今天**陣列元素是100000個**,並且你要找的元素就在**第一個**... 就可以感受到明顯差異! **改善方法:** 可以加上`break`:一找到`num`就停止,就可以省下許多時間 ```c++= int address;//存放位置的變數 int list={10,20,30,40,50},listsize=5;//陣列 int num=30;//要找的某元素 for(int i=0;i<llistsize;i++){ if(list[i]==num){ address=i+1; break;//一找到,就跳出迴圈! } } ``` 然而,面對**已經排列好**的陣列 **線性搜索**(向上面一樣:就直直的由前往後找)當然就不會是有效率的方法 **二分搜**: 將一個陣列不停**切半**，直到遇到某資料為止一個陣列`list={1,2,3,5,7,10,14,19,21}` 9筆資料，要找5 **r**:右端 **l**:左端 | 0| 1| 2| 3| 4| 5| 6| 7| 8| |-|-|-|-|-|-|-|-|-| |1|2|3|5|7|10|14|19|21| mid=(r+l)/2=4 (取list[4]) 得到**7** 但7>5所以要繼續往**左端**找 (**l=mid=4**) | 0| 1| 2| 3| 4| |-|-|-|-|-|-| |1|2|3|5|7| mid=(r+l)/2=2 (取list[2]) 得到**3** 但3<5所以要往**右端**找 (**r=mid=2**) | 2| 3| 4| |-|-|-| |3|5|7| mid=(r+l)/2=3 (取list[3]) 得到**5** 完成搜尋! 整體看起來會像: | 0| 1| 2| 3| 4| 5| 6| 7| 8| |-|-|-|-|-|-|-|-|-| |1|2|3|5|7|10|14|19|21| | 0| 1| 2| 3| 4| |-|-|-|-|-|-| |1|2|3|5|7| | 2| 3| 4| |-|-|-| |3|5|7| | 3| |-| |5| 假設陣列長度為n 如果與剛剛的線性搜索比 **二分搜**最多需要**Log~2~n次**就可以而**線性搜索**至多需要**n次**才能達成而我們會將評估效率的方式叫做「**時間複雜度**」(Big O Notation) 而這些都屬於「**演算法**」的範疇所以利用適當的判斷條件可以大大降低**時間複雜度**

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.