# Ch1. 解題指引

## 時間差計算
### 解題步驟
- ==處理輸入==：使用適當**資料型態**的變數，處理同時有數字和冒號的輸入，獲得時間一、時間二的時、分、秒。
- ==計算時間差==：使用**借位法**或**時間單位轉換**，求得時間差。
- ==處理輸出==：依序判斷時、分、秒是否小於 10 ，決定輸出時前面要不要補 0 。

### 引導問題
::: spoiler **Q. 如何處理輸入？**

C++可利用一個字元變數（`char`）讀取中間的「`:`」，例如：

int h1, m1, s1;
char colon;  // 新增字元變數
cin >> h1 >> colon >> m1 >> colon >> s1;  // 讀取第一個時間
// 下略，自行新增所需變數，讀取第二個時間

:::

:::spoiler **Q. 如何使用借位法（直覺、慢）計算時間差？**
想像我們如何處理直式減法：個位數不夠減，向十位數借 1 ，原個位數即可加 10 後再去減。當題目情境換成計算時間差，借了 1 分鐘，請問秒即可加多少再去減？

以下舉一個簡化版的例子來說明。假設題目給了兩個時間，格式為MM SS，分別代表分鐘和秒，保證第二個時間必大於第一個時間，我們嘗試以相同格式輸出時間 1 到時間 2 的時間差。
|範例輸入 1 | 範例輸出 1|
|---|---|
|`10 31`</br>`13 20`|`2分49秒`|
|範例輸入 2 | 範例輸出 2|
|`13 18`</br>`20 32`|`7分14秒`|

程式碼先找出秒的差，無論分是否經過借位處理，都可以繼續往下找出分的差。

#include <iostream>
using namespace std;
int main(){
	int m1, s1, m2, s2, m, s;
	cin >> m1 >> s1;
	cin >> m2 >> s2;

	// 判斷秒是否需要借位，找出秒的差
	if(s2 >= s1)  s = s2-s1;
	else{
		s = s2+60 - s1;
		m2 -= 1;	// 被借了1分鐘
	}
	
	// 找出分的差
	m = m2 - m1;
	
	// 輸出時間差
	cout << m << "分" << s << "秒" << endl;
	return 0;
}

都瞭解了嗎？要再多一個位數囉。

三位數相減的狀況，若十位數為 0 ，就無法借了，需要再往上向百位數借 1 。借完之後，除了原個位數加 10 後再去減，原十位數還要再加 9 。

同理，當題目情境擴充成時、分、秒，若無分可借，往上借了 1 小時，請問分鐘數要另外加上多少？
:::
::: spoiler **Q. 如何使用時間單位轉換（不直覺、快）計算時間差？**
只要把所有時間化成最小單位（秒），就沒有借位的問題了。以秒相減完，再使用取商運算子`/`和取餘數運算子`%`，即可非常快速地求出時間差為幾分幾秒。

以下舉一個簡化版的例子來說明。假設題目給了兩個時間，格式為MM SS，分別代表分鐘和秒，保證第二個時間必大於第一個時間，我們嘗試計算出兩個時間相差幾秒。
|範例輸入 1 | 範例輸出 1|
|---|---|
|`10 31`</br>`13 20`|`2分49秒`|
|範例輸入 2 | 範例輸出 2|
|`13 18`</br>`20 32`|`7分14秒`|

#include <iostream>
using namespace std;
int main(){
	int m1, s1, m2, s2;
	cin >> m1 >> s1;
	cin >> m2 >> s2;
	
	//	將兩個時間分別化為秒
	int t1 = m1*60 + s1;
	int t2 = m2*60 + s2;
	// 相減除以60再取商，即為分的差
	int m = (t2-t1)/60;	
	// 相減除以60再取餘數，即為分的差
	int s = (t2-t1)%60; 

	// 輸出時間差
	cout << m << "分" << s << "秒" << endl;
	return 0;
}

眼尖的人會發現， m 也可以寫成`((m2-m1)*60 + (s2-s1))/60`，這取決於個人的程式撰寫風格。可以選擇多令幾個變數，以簡化算式，或是少令幾個變數，直接輸出結果。
:::

:::spoiler **Q. 第二個時間小於第一個時間，如何處理？**
第二個時間小於第一個時間，表示有跨日。若要計算時間差，需要借來 24 個小時，也就是 86400 秒，再去進行運算。延續上個引導問題的範例，我們用分、秒來舉例。
我們繼續以上面簡化版的例子來說明。
若使用借位法，先算完秒的差，接著只要往上借 60 分鐘（不用還），即可求得真正的時間差。

// ...前略
// 找出分的差
// 借60分鐘（不用還）	
if(m2 < m1)	m2 += 60;	
m = m2 - m1;
// 後略...

而若使用時間單位轉換，直接借 3600 秒，也就是一小時，即可一勞永逸：

// ...前略
// 借3600秒（不用還）
if(t2 < t1)	t2 += 3600;
// 相減除以60再取商，即為分的差
int m = (t2-t1)/60;	
// 相減除以60再取餘數，即為分的差
int s = (t2-t1)%60;
// 後略...

另外還有一種省略判斷式的寫法，運用取餘數運算子，來因應兩種不同情況：

// ...前略
int m = (t2+3600 - t1) % 3600 / 60;
int s = (t2+3600 - t1) % 3600 % 60;
// 後略...

同理，當題目情境擴充成時、分、秒，若第二個時間比較小，需要往上借 1 天，也就是 24 小時或 86400 秒。
:::

::: spoiler **Q. 如何適時將輸出補 0？**
[法一] 時、分、秒使用獨立的 if-else 架構，例如：

// 如果小於 10，前面就多輸出一個字元 0
if(h < 10)  cout << "0";
cout << h << ":";
// 後面請自己寫寫看

[法二] 內建函式：
利用`<iomanip>`中的`setw()`，調整輸出欄位寬度和`setfill()`填補文字，例如：

// 保證冒號之前的數字為兩位數，未滿兩位數補0
cout << setw(2) << setfill('0') << h << ":";
// 後面請自己寫寫看

這兩個函式的使用規則是什麼呢？請參考一個常見英文教學網站：[GeeksforGeeks](https://www.geeksforgeeks.org/stdsetbase-stdsetw-stdsetfill-in-cpp/)的說明，如果單用`setw(數字)`函式，程式會讓「空格+待輸出字元」的總字元數，等於括弧內`數字`個。而若在`setw(數字)`前面再補上`setfill(字元)`，該`字元`會取代預設的空格，根據指定的總字元數，填補在待輸出字元的前面。兩個函式之間、前面、後面，都要記得加上`<<` 喔！
:::

## 成績指標

### 解題步驟
- ==處理輸入==：輸入學生人數、各學生分數。
- ==使用函式==：使用內建或自訂函式，排序陣列並輸出。
- ==尋找目標==：使用迴圈尋找，確認最低分及格者、最高分不及格者。
- ==處理輸出==：根據是否全為及格、全不及格，輸出相應結果。

### 引導問題
::: spoiler Q. **陣列如何排序？**
A. 可使用C++標準函式庫`<algorithm>`中的內建函式`sort()`。在章節`2-1`就有簡單的使用範例，課本`p.106`
:::
::: spoiler Q. **假設必有及格和不及格者，如何用迴圈搜尋已排序好的陣列，搜尋的方向是？**

A. 方法有兩個。

【法一】循序搜尋法 (兩種搜尋方向)
- 陣列由前往後找，找到第一個大於 60 分的分數，即為最低及格分數。
- 陣列由後往前找，找到第一個小於 60 分的分數，即為最高不及格分數。

【法二】極值變數法
- 設立**極值變數**，紀錄最高不及格分數，與最低及格分數，用一個方向搜尋即可。
- 只要==不及格==且==高於目前的最高不及格分數==，即為新的最高不及格分數。
- 只要==及格==且==低於目前的最低及格分數==，即為新的最低及格分數。
使用此方法，須注意==初始值設定==的問題。請問：最高不及格分數、最低及格分數，一開始要設為多少，才能保證找到任何一個最高不及格分數/最低及格分數，必然可以取而代之？（提示：==不存在的分數==）
:::
::: spoiler Q. **如何判斷全為及格、全不及格的狀況？**
A. 承上一個提示，兩種方法判斷的方式不太一樣。
- 如果使用法一，因為已經排序完成，只要檢查陣列頭尾，就能夠發現了。
- 如果使用法二，只要最高不及格分數維持在你設定的初始值，就表示全部及格；反之，只要最低及格分數維持在你設定的初始值，就表示全部不及格。
:::

## 雪花片片
### 解題步驟
- ==處理輸入==：就一個 N 值，最大只到 120 ，但是...
- ==尋找規律==：課本的題目敘述有較完整的提示。找出每個 N 值對應的邊數，再從這個邊數推敲出每個 N 值多了幾個、總共有幾個三角形。找到各項之間的規律，就可以找出等比級數的規律。
- ==決定變數資料型態==：根據題目給定的 $N$ 值，判斷本題需要使用的資料型態。（破梗：總和會大到需要使用**整數陣列**或**字串**來存放！為什麼？）
- ==建立演算法==：思考如何使用雙層迴圈，內層迴圈計算 $4^i$，亦即單項的等邊三角總數量，外層迴圈累加 $1 + 2 + ... + 4^{(N-1)}$ ，也就是每一項的等邊三角形總數量。
- ==大數加法/乘法==：思考如何以整數陣列或字串，設立暫存變數與總和變數，累加等邊三角形總數量。
- ==處理輸出==：如果整數陣列是從個位數開始存，記得反過來輸出。

### 引導問題
::: spoiler **Q. 本題要設立哪些變數？**
A. 除了數字 N ，還要有暫存變數和總和變數，代表每一個 N 值的等邊三角形數（等比數列中每一項），以及每一項等邊三角形數加總（等比級數）。
本題每次重算 4 的次方會很崩潰（後述），而暫存變數的好處是，每次多乘以一個 4 ，就可以再累加到總和變數。
:::

::: spoiler **Q. 觀察題目輸入數字範圍，為什麼不能使用`int`, `long long`或`unsigned long long`？**
A. 首先大家可以翻開以前的參考書，回憶這些資料型態可以存放整數範圍。已知 $2^{10} \approx 10^3$ 只看正整數的話，`unsigned long long`能存放的範圍是：$2^{64} – 1$，大約接近20位數。
然而，題目告訴我們，N 值可能為 1 到 120 的正整數，也就是說最大為 120，於是我們可以使用等比數列、等比級數公式得知：
- $a_{120} = 4^{119}$
- $S_{120} = \frac{4^{120}-1}{4-1}$

我們直接取$4^{120}$來估位數，$log_{10}{4^{120}} = 120log_{10}{4} = 240log_{10}{2} \approx 240 \times 0.3010 \approx 73$，。

顯然，這是`unsigned long long`也無法hold住的數字範圍。
那麼要使用字串，還是使用整數陣列呢？
前者會需要提取出每個字元，在ASCII code和`int`之間進行轉換，直觀、容易估算範圍，但位數判斷需要非常精確。而後者不用進行型別轉換，相較方便，以下將以後者進行說明。
:::

::: spoiler **Q. 將變數設成整數陣列的話，大小要開多大？**
A. 建議大家不要使用VLA，根據最大位數開一個已知大小的整數陣列。可以奢侈一點，把暫存（第幾項的）變數、總和變數，都開成大小為 100 的整數陣列。
:::

::: spoiler **Q. 如何使用整數陣列紀錄一個很大的整數？**
A. 例如 1024 有 4 個位數，那麼可以用一個大小為 4 的整數陣列，索引值為多少，就代表第幾位數字：
|數字| 4| 2| 0| 1|
|---|---|---|---|---|
|索引值| 0| 1| 2| 3|

為什麼建議從個位數開始存呢？雖然閱讀比較不方便，但等等在使用`for`迴圈進行大數運算時，才能像直式運算一樣，統一由索引值最小的個位數開始計算。

// ... 前略
int temp[4] = {4, 2, 0, 1}  // 整數陣列
for(int i = 3; i >= 0; i--) // 輸出各位數字
	cout << temp[i];
// 輸出結果為1024

:::

::: spoiler **Q. 如何一位、一位計算 4 的次方？**
請回憶國小學的直式運算。由個位數開始，一位一位地計算，且計算下一位之前，都要考慮前面是否有==進位==。以下示範 $4$ 到 $4^4$ 的直式運算邏輯（看起來很廢，但步驟要化成程式碼就要想一下了）：


:::

::: spoiler **Q. 如何使用整數陣列，將一個數字乘以4？**
以 $64 \times 4$ 為例：

int a[10] = {4, 6};
int carry = 0, digit = 2;
// 從最小位數開始，紀錄乘以4的結果
for(int i = 0; i < digit; i++){
    a[i] = carry + a[i] * 4; // 乘以4並加上一回合進位
    carry = a[i]/10;  // 紀錄進位，例如16取十位數1
    a[i] = a[i]%10;  // 保留未進位的數字，例如16取個位數6
}
// 處理最高位數
a[digit] = carry;  // 最後一位為進位
if(carry > 0)  digit++;  // 如果有進位，把digit加上1
// 輸出乘積
for(int i = digit-1; i >= 0; i--)
    cout << a[i];

如果陣列開得夠大，確定可以用`for`迴圈跑完每一位的計算並存放於整數陣列，那麼`digit`變數就非必要了，最後從索引值較高者檢查，從第一個非 0 整數開始輸出每一位數即可。
本題除了乘以 4 ，乘完還要加總喔！雖然運算不同，同樣都要從個位數起一個一個位數運算，並將進位數字納入考量。比起觀念理解難度，更考驗的是細心程度，試試看吧！

:::