Ch1. 解題指引

時間差計算

解題步驟

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

引導問題

Q. 如何處理輸入？

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

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

Q. 如何使用借位法（直覺、慢）計算時間差？

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

以下舉一個簡化版的例子來說明。假設題目給了兩個時間，格式為MM SS，分別代表分鐘和秒，保證第二個時間必大於第一個時間，我們嘗試以相同格式輸出時間 1 到時間 2 的時間差。

範例輸入 1	範例輸出 1
10 31 13 20	2分49秒
範例輸入 2	範例輸出 2
13 18 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 小時，請問分鐘數要另外加上多少？

Q. 如何使用時間單位轉換（不直覺、快）計算時間差？

只要把所有時間化成最小單位（秒），就沒有借位的問題了。以秒相減完，再使用取商運算子/和取餘數運算子%，即可非常快速地求出時間差為幾分幾秒。

以下舉一個簡化版的例子來說明。假設題目給了兩個時間，格式為MM SS，分別代表分鐘和秒，保證第二個時間必大於第一個時間，我們嘗試計算出兩個時間相差幾秒。

範例輸入 1	範例輸出 1
10 31 13 20	2分49秒
範例輸入 2	範例輸出 2
13 18 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，這取決於個人的程式撰寫風格。可以選擇多令幾個變數，以簡化算式，或是少令幾個變數，直接輸出結果。

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 秒。

Q. 如何適時將輸出補 0？

[法一] 時、分、秒使用獨立的 if-else 架構，例如：

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

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

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

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

成績指標

解題步驟

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

引導問題

Q. 陣列如何排序？

A. 可使用C++標準函式庫<algorithm>中的內建函式sort()。在章節2-1就有簡單的使用範例，課本p.106

Q. 假設必有及格和不及格者，如何用迴圈搜尋已排序好的陣列，搜尋的方向是？

A. 方法有兩個。

【法一】循序搜尋法 (兩種搜尋方向)

• 陣列由前往後找，找到第一個大於 60 分的分數，即為最低及格分數。
• 陣列由後往前找，找到第一個小於 60 分的分數，即為最高不及格分數。

【法二】極值變數法

• 設立極值變數，紀錄最高不及格分數，與最低及格分數，用一個方向搜尋即可。
• 只要不及格且高於目前的最高不及格分數，即為新的最高不及格分數。
• 只要及格且低於目前的最低及格分數，即為新的最低及格分數。
  使用此方法，須注意初始值設定的問題。請問：最高不及格分數、最低及格分數，一開始要設為多少，才能保證找到任何一個最高不及格分數/最低及格分數，必然可以取而代之？（提示：不存在的分數）

Q. 如何判斷全為及格、全不及格的狀況？

A. 承上一個提示，兩種方法判斷的方式不太一樣。

• 如果使用法一，因為已經排序完成，只要檢查陣列頭尾，就能夠發現了。
• 如果使用法二，只要最高不及格分數維持在你設定的初始值，就表示全部及格；反之，只要最低及格分數維持在你設定的初始值，就表示全部不及格。

雪花片片

解題步驟

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

引導問題

Q. 本題要設立哪些變數？

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

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}$來估位數，

$lo{g}_{10}{4}^{120}=120lo{g}_{10}4=240lo{g}_{10}2\approx 240\times 0.3010\approx 73$，。

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

Q. 將變數設成整數陣列的話，大小要開多大？

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

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

Q. 如何一位、一位計算 4 的次方？

請回憶國小學的直式運算。由個位數開始，一位一位地計算，且計算下一位之前，都要考慮前面是否有進位。以下示範

$4$ 到

$4^4$ 的直式運算邏輯（看起來很廢，但步驟要化成程式碼就要想一下了）：

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 ，乘完還要加總喔！雖然運算不同，同樣都要從個位數起一個一個位數運算，並將進位數字納入考量。比起觀念理解難度，更考驗的是細心程度，試試看吧！