114 年 國立臺北大學資訊工程研究所《線性代數與離散數學》

📄 試題原卷　免費註冊後即可對照原始考卷 PDF免費註冊

第 1 題20 分

  1. (20%) True or False. In each case, answer T if the statement is always true and F otherwise. In the case of a false statement, explain why or give an example to show that the statement is not always true.

(a) If the row reduced echelon form of matrix A involves free variables, then the system Ax=bAx=b will have infinitely many solutions.
(b) det⁡(AB)=det⁡(A)det⁡(B)\det(AB) = \det(A)\det(B)
(c) A triangular matrix is nonsingular if and only if its diagonal entries are all nonzero.
(d) If x1,x2,…,xkx_1, x_2, \dots, x_k span a vector space VV, then they are linearly independent.
(e) Let {u1,u2}\{u_1, u_2\}, {v1,v2}\{v_1, v_2\}, and {w1,w2}\{w_1, w_2\} be bases for R2\mathbb{R}^2. If XX is the transition matrix corresponding to a change of basis from {u1,u2}\{u_1, u_2\} to {v1,v2}\{v_1, v_2\} and YY is the transition matrix corresponding to a change of basis from {v1,v2}\{v_1, v_2\} to {w1,w2}\{w_1, w_2\}, then Z=XYZ = XY is the transition matrix corresponding to a change of basis from {u1,u2}\{u_1, u_2\} to {w1,w2}\{w_1, w_2\}.
(f) If L:V→VL: V \to V is a linear transformation and L(v1)=L(v2)L(v_1) = L(v_2), then v1−v2∈ker⁡(L)v_1 - v_2 \in \ker(L).
(g) Any two matrices with the same trace are similar.
(h) If {u1,u2,…,uk}\{u_1, u_2, \dots, u_k\} is an orthonormal set of vectors in Rn\mathbb{R}^n and U=[u1 u2 … uk]U = [u_1 \ u_2 \ \dots \ u_k], then UUT=InU U^T = I_n (the n×nn \times n identity matrix).
(i) If AA is symmetric and det⁡(A)>0\det(A) > 0, then AA is positive definite.
(j) Let λ1,λ2,…,λn\lambda_1, \lambda_2, \dots, \lambda_n be the eigenvalues of matrix AA, then det⁡(A)=λ1+λ2+⋯+λn\det(A) = \lambda_1 + \lambda_2 + \dots + \lambda_n.

登入後即可作答並保存紀錄。

這一題的完整詳解

(a) F。有自由變數只表示齊次解有非零自由度；若 Ax=bAx=b 不相容，仍無解。例如

A=[00],b=[1],A=\begin{bmatrix}0&0\end{bmatrix},\qquad b=\begin{bmatrix}1\end{bmatrix},

方程為 0=10=1，故無解。

(b) T。對同階方陣 A,BA,B，

det⁡(AB)=det⁡(A)det⁡(B).\det(AB)=\det(A)\det(B).

(c) T。三角矩陣的行列式為對角線元素之乘積：

det⁡(A)=∏iaii.\det(A)=\prod_i a_{ii}.

因此 AA 非奇異若且唯若所有 aii≠0a_{ii}\neq 0。

(d) F。生成集合未必線性獨立。例如 {(1,0),(0,1),(1,1)}\{(1,0),(0,1),(1,1)\} 可生成 R2\mathbb R^2，但

(1,1)=(1,0)+(0,1).(1,1)=(1,0)+(0,1).

(e) F。若 XX 將 uu-座標轉為 vv-座標，YY 將 vv-座標轉為 ww-座標，則

[x]w=Y[x]v=YX[x]u.[x]_w=Y[x]_v=YX[x]_u.

故所求轉換矩陣應為 YXYX，不一定是 XYXY。

(f) T。由線性可得

L(v1−v2)=L(v1)−L(v2)=0,L(v_1-v_2)=L(v_1)-L(v_2)=0,

所以 v1−v2∈ker⁡(L)v_1-v_2\in\ker(L)。

🔒

後續完整解題步驟與【答案】

免費註冊，享三天全站完整詳解閱覽。

免費註冊

第 2 題10 分

  1. (10%) Let A=[1110]A = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}.
    Compute the singular values and singular value decomposition of A.

登入後即可作答並保存紀錄。

這一題的完整詳解

核心觀念

奇異值分解（Singular Value Decomposition, SVD）將矩陣寫成

A=UΣVT,A=U\Sigma V^{T},

其中 U、VU、V 為正交矩陣，Σ\Sigma 的對角元素為非負奇異值。

奇異值的平方等於 ATAA^{T}A 的特徵值：

ATAvi=σi2vi.A^{T}A v_i=\sigma_i^2v_i.

因此解題流程為：

  1. 計算 ATAA^{T}A。
  2. 求出 ATAA^{T}A 的特徵值與單位特徵向量。
  3. 取奇異值 σi=λi\sigma_i=\sqrt{\lambda_i}。
  4. 利用 ui=Aviσiu_i=\dfrac{Av_i}{\sigma_i} 求左奇異向量。

解題方法

題目給定

A=[1110].A= \begin{bmatrix} 1&1\\ 1&0 \end{bmatrix}.

由於 AA 為對稱矩陣，所以 AT=AA^{T}=A。先計算

ATA=A2=[1110][1110]=[2111].A^{T}A=A^2 = \begin{bmatrix} 1&1\\ 1&0 \end{bmatrix} \begin{bmatrix} 1&1\\ 1&0 \end{bmatrix} = \begin{bmatrix} 2&1\\ 1&1 \end{bmatrix}.

1. 求 ATAA^{T}A 的特徵值

特徵方程為

det⁡[2−λ111−λ]=0.\det \begin{bmatrix} 2-\lambda&1\\ 1&1-\lambda \end{bmatrix} =0.

因此

(2−λ)(1−λ)−1=0,(2-\lambda)(1-\lambda)-1=0, λ2−3λ+1=0.\lambda^2-3\lambda+1=0.

解得

λ1=3+52,λ2=3−52.\lambda_1=\frac{3+\sqrt5}{2}, \qquad \lambda_2=\frac{3-\sqrt5}{2}.

所以奇異值為

σ1=3+52,σ2=3−52.\sigma_1=\sqrt{\frac{3+\sqrt5}{2}}, \qquad \sigma_2=\sqrt{\frac{3-\sqrt5}{2}}.

令黃金比例

φ=1+52.\varphi=\frac{1+\sqrt5}{2}.

因為

φ2=3+52,1φ2=3−52,\varphi^2=\frac{3+\sqrt5}{2}, \qquad \frac{1}{\varphi^2}=\frac{3-\sqrt5}{2},

故奇異值可簡寫為

σ1=φ=1+52,σ2=1φ=5−12.\sigma_1=\varphi=\frac{1+\sqrt5}{2}, \qquad \sigma_2=\frac1\varphi=\frac{\sqrt5-1}{2}.

2. 求右奇異向量

對應於 λ1=φ2\lambda_1=\varphi^2，可取特徵向量

[φ1].\begin{bmatrix} \varphi\\ 1 \end{bmatrix}.

對應於 λ2=1φ2\lambda_2=\dfrac1{\varphi^2}，可取特徵向量

[1−φ].\begin{bmatrix} 1\\ -\varphi \end{bmatrix}.

兩者長度相同，令

N=φ2+1.N=\sqrt{\varphi^2+1}.

正規化後得到

v1=1N[φ1],v2=1N[1−φ].v_1=\frac1N \begin{bmatrix} \varphi\\ 1 \end{bmatrix}, \qquad v_2=\frac1N \begin{bmatrix} 1\\ -\varphi \end{bmatrix}.

因此

V=1N[φ11−φ].V= \frac1N \begin{bmatrix} \varphi&1\\ 1&-\varphi \end{bmatrix}.

由於 v1、v2v_1、v_2 互相正交且皆為單位向量，VV 為正交矩陣。

3. 求左奇異向量

由公式

ui=Aviσiu_i=\frac{Av_i}{\sigma_i}

求得左奇異向量。

對第一個向量：

🔒

後續完整解題步驟與【答案】

免費註冊，享三天全站完整詳解閱覽。

免費註冊

第 3 題10 分

  1. (10%) Given the following linear system Ax=bAx = b:
    x1+4x2+3x3=12x_1 + 4x_2 + 3x_3 = 12
    −x1−2x2=−12-x_1 - 2x_2 = -12
    2x1+2x2+3x3=82x_1 + 2x_2 + 3x_3 = 8

(a) Compute A−1A^{-1}.
(b) Compute the LU factorization of AA.
(c) Use the LU factorization to determine the value of det⁡(A)\det(A).
(d) Solve the linear system using x=A−1bx = A^{-1}b.
(e) Solve x1x_1 of the linear system using Cramer's Rule.

登入後即可作答並保存紀錄。

這一題的完整詳解

核心觀念

本題綜合考查矩陣反矩陣、LU 分解、行列式與克拉瑪法則：

  • 若 AA 可逆，則
    A−1A=AA−1=IA^{-1}A=AA^{-1}=I
  • LU 分解將矩陣寫成
    A=LUA=LU
    其中 LL 為下三角矩陣、UU 為上三角矩陣。
  • 三角矩陣的行列式等於對角線元素乘積，因此
    det⁡(A)=det⁡(L)det⁡(U)\det(A)=\det(L)\det(U)
  • 克拉瑪法則中，若以 bb 取代 AA 的第 jj 欄形成 AjA_j，則
    xj=det⁡(Aj)det⁡(A)x_j=\frac{\det(A_j)}{\det(A)}

由題目可得

A=[143−1−20223],b=[12−128].A= \begin{bmatrix} 1&4&3\\ -1&-2&0\\ 2&2&3 \end{bmatrix}, \qquad b= \begin{bmatrix} 12\\ -12\\ 8 \end{bmatrix}.

(a) 計算 A−1A^{-1}

先計算 det⁡(A)\det(A)：

det⁡(A)=1∣−2023∣−4∣−1023∣+3∣−1−222∣=1(−6)−4(−3)+3(2)=12.\begin{aligned} \det(A) &=1 \begin{vmatrix} -2&0\\ 2&3 \end{vmatrix} -4 \begin{vmatrix} -1&0\\ 2&3 \end{vmatrix} +3 \begin{vmatrix} -1&-2\\ 2&2 \end{vmatrix}\\ &=1(-6)-4(-3)+3(2)\\ &=12. \end{aligned}

因為 det⁡(A)=12≠0\det(A)=12\neq 0，所以 AA 可逆。

各代數餘子式為

C=[−632−6−366−32].C= \begin{bmatrix} -6&3&2\\ -6&-3&6\\ 6&-3&2 \end{bmatrix}.

因此伴隨矩陣為

adj⁡(A)=CT=[−6−663−3−3262].\operatorname{adj}(A)=C^T = \begin{bmatrix} -6&-6&6\\ 3&-3&-3\\ 2&6&2 \end{bmatrix}.

由公式

A−1=1det⁡(A)adj⁡(A),A^{-1}=\frac{1}{\det(A)}\operatorname{adj}(A),

得到

A−1=112[−6−663−3−3262]\boxed{ A^{-1} = \frac{1}{12} \begin{bmatrix} -6&-6&6\\ 3&-3&-3\\ 2&6&2 \end{bmatrix} }

亦可寫成

A−1=[−12−121214−14−14161216].\boxed{ A^{-1} = \begin{bmatrix} -\frac12&-\frac12&\frac12\\ \frac14&-\frac14&-\frac14\\ \frac16&\frac12&\frac16 \end{bmatrix} }.

(b) 計算 AA 的 LU 分解

採用不選主元的高斯消去法。

原矩陣為

[143−1−20223].\begin{bmatrix} 1&4&3\\ -1&-2&0\\ 2&2&3 \end{bmatrix}.

第一欄消去所使用的乘數為

ℓ21=−11=−1,ℓ31=21=2.\ell_{21}=\frac{-1}{1}=-1, \qquad \ell_{31}=\frac{2}{1}=2.

進行列運算：

R2←R2−(−1)R1=R2+R1,R_2\leftarrow R_2-(-1)R_1=R_2+R_1, R3←R3−2R1.R_3\leftarrow R_3-2R_1.

得到

[1430230−6−3].\begin{bmatrix} 1&4&3\\ 0&2&3\\ 0&-6&-3 \end{bmatrix}.

第二欄消去的乘數為

ℓ32=−62=−3.\ell_{32}=\frac{-6}{2}=-3.

因此

R3←R3−(−3)R2=R3+3R2,R_3\leftarrow R_3-(-3)R_2=R_3+3R_2,

得到上三角矩陣

U=[143023006].U= \begin{bmatrix} 1&4&3\\ 0&2&3\\ 0&0&6 \end{bmatrix}.

將消去乘數放入下三角矩陣，得到

L=[100−1102−31].L= \begin{bmatrix} 1&0&0\\ -1&1&0\\ 2&-3&1 \end{bmatrix}.

故

A=[100−1102−31][143023006]\boxed{ A= \begin{bmatrix} 1&0&0\\ -1&1&0\\ 2&-3&1 \end{bmatrix} \begin{bmatrix} 1&4&3\\ 0&2&3\\ 0&0&6 \end{bmatrix} }

即

🔒

後續完整解題步驟與【答案】

免費註冊，享三天全站完整詳解閱覽。

免費註冊

第 4 題10 分

  1. (10%) Let LL be a linear operator on R2\mathbb{R}^2, and let v1=[1−3]v_1 = \begin{bmatrix} 1 \\ -3 \end{bmatrix}, v2=[−35]v_2 = \begin{bmatrix} -3 \\ 5 \end{bmatrix}, v3=[1−9]v_3 = \begin{bmatrix} 1 \\ -9 \end{bmatrix}.

(a) Are v1,v2,v3v_1, v_2, v_3 linearly independent?
(b) If L(v1)=[24]L(v_1) = \begin{bmatrix} 2 \\ 4 \end{bmatrix} and L(v2)=[35]L(v_2) = \begin{bmatrix} 3 \\ 5 \end{bmatrix}, find the value of L(v3)L(v_3).

登入後即可作答並保存紀錄。

這一題的完整詳解

核心觀念

本題旨在考驗向量空間中的線性獨立（Linearly Independent）與線性運算子（Linear Operator）的線性性質（Linearity Property）。

  1. 維度與線性獨立性定理：在 nn 維向量空間 VV 中，任意包含超過 nn 個向量的集合必然為線性相依（Linearly Dependent）。特別地，在維度為 2 的向量空間 R2\mathbb{R}^2 中，任意 3 個向量皆線性相依。
  2. 線性轉換的保線性：若 L:V→WL: V \to W 為線性轉換（或線性運算子），則對於任意向量 u,v∈Vu, v \in V 及純量 c1,c2∈Rc_1, c_2 \in \mathbb{R}，滿足：
    L(c1u+c2v)=c1L(u)+c2L(v)L(c_1 u + c_2 v) = c_1 L(u) + c_2 L(v)
  3. 基底與線性組合：若 {v1,v2}\{v_1, v_2\} 為 R2\mathbb{R}^2 的一組基底，則空間中任意向量 v3v_3 皆可唯一表示為 v1v_1 與 v2v_2 的線性組合，即存在唯一純量對 (c1,c2)(c_1, c_2) 使得 v3=c1v1+c2v2v_3 = c_1 v_1 + c_2 v_2。

解題方法

  • (a) 小題：
    直接運用維度定理進行判定。因為向量 v1,v2,v3∈R2v_1, v_2, v_3 \in \mathbb{R}^2，集合大小為 3，大於空間維度 dim⁡(R2)=2\dim(\mathbb{R}^2) = 2，故此三向量必定線性相依（即不滿足線性獨立）。亦可透過矩陣列運算求秩（Rank）來給出嚴謹推導。

  • (b) 小題：

    1. 先確認 {v1,v2}\{v_1, v_2\} 是否線性獨立（行列式非零），確定其可構成 R2\mathbb{R}^2 的一組基底。
    2. 將 v3v_3 表示為 v1v_1 與 v2v_2 的線性組合：v3=c1v1+c2v2v_3 = c_1 v_1 + c_2 v_2。
    3. 解二元一次聯立方程組求得純量 c1,c2c_1, c_2。
    4. 利用線性運算子 LL 的加法與純量乘法可拆解性，求出 L(v3)=c1L(v1)+c2L(v2)L(v_3) = c_1 L(v_1) + c_2 L(v_2) 的值。

子題詳細推導

(a) 判斷 v1,v2,v3v_1, v_2, v_3 是否線性獨立

方法一：維度定理判斷
向量空間 R2\mathbb{R}^2 的維度 dim⁡(R2)=2\dim(\mathbb{R}^2) = 2。根據有限維向量空間性質，任意含有大於維度個數之向量集合必為線性相依。集合 {v1,v2,v3}\{v_1, v_2, v_3\} 包含 3 個向量，因為 3>23 > 2，故 v1,v2,v3v_1, v_2, v_3 必為線性相依，非線性獨立。

方法二：矩陣秩（Rank）證明
將 v1,v2,v3v_1, v_2, v_3 做為行向量構造矩陣 AA 並進行高斯消去法列運算：
A=[v1v2v3]=[1−31−35−9]A = \begin{bmatrix} v_1 & v_2 & v_3 \end{bmatrix} = \begin{bmatrix} 1 & -3 & 1 \\ -3 & 5 & -9 \end{bmatrix}
進行列運算 R2←R2+3R1R_2 \leftarrow R_2 + 3 R_1：
[1−310−4−6]\begin{bmatrix} 1 & -3 & 1 \\ 0 & -4 & -6 \end{bmatrix}
矩陣 AA 的樞紐位置（Pivot position）數量為 2，即 rank(A)=2<3\text{rank}(A) = 2 < 3。由於矩陣的秩小於向量個數，齊次方程組 Ax=0A \mathbf{x} = \mathbf{0} 必存在無窮多非零解，故 v1,v2,v3v_1, v_2, v_3 為線性相依。

(b) 計算 L(v3)L(v_3) 的值

  1. 確認 {v1,v2}\{v_1, v_2\} 為 R2\mathbb{R}^2 的一組基底：
    構建矩陣 [v1v2]\begin{bmatrix} v_1 & v_2 \end{bmatrix} 並計算其行列式：
    det⁡[1−3−35]=(1)(5)−(−3)(−3)=5−9=−4≠0\det \begin{bmatrix} 1 & -3 \\ -3 & 5 \end{bmatrix} = (1)(5) - (-3)(-3) = 5 - 9 = -4 \neq 0
    行列式不等於 0，代表 {v1,v2}\{v_1, v_2\} 線性獨立，故可作為 R2\mathbb{R}^2 的一組基底。

  2. 求解線性組合係數 c1,c2c_1, c_2：
    設 v3=c1v1+c2v2v_3 = c_1 v_1 + c_2 v_2，帶入數值：
    [1−9]=c1[1−3]+c2[−35]\begin{bmatrix} 1 \\ -9 \end{bmatrix} = c_1 \begin{bmatrix} 1 \\ -3 \end{bmatrix} + c_2 \begin{bmatrix} -3 \\ 5 \end{bmatrix}
    展開得到二元一次聯立方程式：
    {c1−3c2=1— (1)−3c1+5c2=−9— (2)\begin{cases} c_1 - 3c_2 = 1 \quad &\text{--- (1)} \\ -3c_1 + 5c_2 = -9 \quad &\text{--- (2)} \end{cases}

🔒

後續完整解題步驟與【答案】

免費註冊，享三天全站完整詳解閱覽。

免費註冊

第 5 題10 分

  1. (10%) Solve the recurrence relation an=an−1+2n+3a_n = a_{n-1} + 2n + 3 where a0=5a_0 = 5.

登入後即可作答並保存紀錄。

這一題的完整詳解

核心觀念

本題考查**一階非齊次線性遞迴關係式（First-order Non-homogeneous Linear Recurrence Relation）**的求解。

主要運用的觀念與公式包括：

  1. 累加法（Telescoping Sum / Iterative Substitution）：當遞迴式呈現 an−an−1=f(n)a_n - a_{n-1} = f(n) 形式時，可透過對消累加求得一般項。
  2. 等差級數求和公式：
    ∑k=1nk=n(n+1)2\sum_{k=1}^n k = \frac{n(n+1)}{2}
    ∑k=1nc=c⋅n(c 為常數)\sum_{k=1}^n c = c \cdot n \quad (c \text{ 為常數})
  3. 待定係數法（Method of Undetermined Coefficients）（可作為另解 verification）：將一般解拆解為齊次解（Homogeneous Solution）與特解（Particular Solution）之和 an=an(h)+an(p)a_n = a_n^{(h)} + a_n^{(p)}。

解題方法

方法一：累加法（推薦主解法）

步驟 1：遞迴式整理
將遞迴關係式 an=an−1+2n+3a_n = a_{n-1} + 2n + 3 移項，使非齊次項獨立於右式：
an−an−1=2n+3a_n - a_{n-1} = 2n + 3

步驟 2：列出各項並對消累加
將 nn 分別以 1,2,3,…,n1, 2, 3, \dots, n 代入上式：

a1−a0=2(1)+3a2−a1=2(2)+3a3−a2=2(3)+3    ⋮an−an−1=2(n)+3\begin{aligned} a_1 - a_0 &= 2(1) + 3 \\ a_2 - a_1 &= 2(2) + 3 \\ a_3 - a_2 &= 2(3) + 3 \\ &\;\;\vdots \\ a_n - a_{n-1} &= 2(n) + 3 \end{aligned}

將上述 nn 個等式左右兩邊分別相加：
∑k=1n(ak−ak−1)=∑k=1n(2k+3)\sum_{k=1}^n (a_k - a_{k-1}) = \sum_{k=1}^n (2k + 3)

步驟 3：化簡求和式
左式對消後僅剩兩頭項：
∑k=1n(ak−ak−1)=an−a0\sum_{k=1}^n (a_k - a_{k-1}) = a_n - a_0

右式運用求和公式展開：

∑k=1n(2k+3)=2∑k=1nk+∑k=1n3=2⋅n(n+1)2+3n=n(n+1)+3n=n2+n+3n=n2+4n\begin{aligned} \sum_{k=1}^n (2k + 3) &= 2 \sum_{k=1}^n k + \sum_{k=1}^n 3 \\ &= 2 \cdot \frac{n(n+1)}{2} + 3n \\ &= n(n+1) + 3n \\ &= n^2 + n + 3n \\ &= n^2 + 4n \end{aligned}

步驟 4：代入初始條件
結合左右式可得：
an−a0=n2+4na_n - a_0 = n^2 + 4n

代入初值 a0=5a_0 = 5：
an−5=n2+4n  ⟹  an=n2+4n+5a_n - 5 = n^2 + 4n \implies a_n = n^2 + 4n + 5

方法二：特解與齊次解法（另解）

  1. 齊次解 an(h)a_n^{(h)}：
    對應齊次式 an−an−1=0a_n - a_{n-1} = 0，特徵方程式為 r−1=0  ⟹  r=1r - 1 = 0 \implies r = 1。
🔒

後續完整解題步驟與【答案】

免費註冊，享三天全站完整詳解閱覽。

免費註冊

第 6 題10 分

  1. (10%) Simplify the following compound proposition to minimize the number of "and", "or", and "not" operations.
    (p∧q∧r)∨(¬p∧¬q∧¬r)∨(¬p∧q∧r)∨(p∧¬q∧r)∨(p∧q∧¬r)(p \land q \land r) \lor (\neg p \land \neg q \land \neg r) \lor (\neg p \land q \land r) \lor (p \land \neg q \land r) \lor (p \land q \land \neg r)

登入後即可作答並保存紀錄。

這一題的完整詳解

令 s=p∨qs=p\lor q。原命題在「至少兩個命題為真」或「三者皆假」時為真，因此

🔒

後續完整解題步驟與【答案】

免費註冊，享三天全站完整詳解閱覽。

免費註冊

第 7 題10 分

  1. (10%) Consider the following program segment. Let nn be a positive integer. Find the final values of aa and bb as functions of nn.
a ← 1
b ← 2
while (b ≤ n) do
{
  a ← a + 3
  b ← b * b
}

登入後即可作答並保存紀錄。

這一題的完整詳解

核心觀念

本題旨在考驗程式迴圈的迭代分析（Loop Iteration Analysis）、**遞迴關係式（Recurrence Relation）以及雙重對數（Iterated Logarithm）與高斯符號（Floor Function）**的精確應用。

  1. 算術數列與變數更新：變數 aa 在每次迭代中進行加法更新 a←a+3a \leftarrow a + 3，呈現等差數列成長。
  2. 連續平方與雙重指數成長：變數 bb 在每次迭代中進行平方更新 b←b×bb \leftarrow b \times b，呈現雙重指數（Double Exponential）成長。
  3. 迴圈終止條件與高斯符號：迴圈終止於 b>nb > n。由於迴圈執行次數必為非負整數，需利用高斯符號 ⌊⋅⌋\lfloor \cdot \rfloor 精確表達迴圈執行的總次數 kk。

解題方法

1. 追蹤變數隨迭代次數 kk 的數學關係式

設 kk 為迴圈執行的總次數（即迴圈體被執行的代數， k≥0k \ge 0）。

  • 初始狀態（k=0k = 0）：
    a0=1a_0 = 1
    b0=2=220b_0 = 2 = 2^{2^0}

  • 第 1 次迭代後（k=1k = 1）：
    a1=a0+3=1+3(1)=4a_1 = a_0 + 3 = 1 + 3(1) = 4
    b1=b02=22=4=221b_1 = b_0^2 = 2^2 = 4 = 2^{2^1}

  • 第 2 次迭代後（k=2k = 2）：
    a2=a1+3=1+3(2)=7a_2 = a_1 + 3 = 1 + 3(2) = 7
    b2=b12=(22)2=24=16=222b_2 = b_1^2 = (2^2)^2 = 2^4 = 16 = 2^{2^2}

  • 推廣至第 kk 次迭代後：
    ak=1+3ka_k = 1 + 3k
    bk=22kb_k = 2^{2^k}

2. 求出迴圈執行次數 kk

迴圈繼續執行的條件為 b≤nb \le n。當迴圈執行 kk 次結束時，代表第 k−1k-1 次時條件仍成立，但第 kk 次時條件不成立：

  1. 當 n=1n = 1 時：
    初始狀態 b0=2>1b_0 = 2 > 1，迴圈條件 b ≤ n 成立否？否。
    因此迴圈執行 00 次（k=0k = 0）。
    最終值為 a=1a = 1，b=2b = 2。

  2. 當 n≥2n \ge 2 時：
    迴圈執行 k≥1k \ge 1 次結束，滿足以下不等式：
    bk−1≤n<bkb_{k-1} \le n < b_k
    將 bk=22kb_k = 2^{2^k} 代入：
    22k−1≤n<22k2^{2^{k-1}} \le n < 2^{2^k}

    兩邊同取以 2 為底的對數 log⁡2\log_2：
    2k−1≤log⁡2n<2k2^{k-1} \le \log_2 n < 2^k

    因 n≥2  ⟹  log⁡2n≥1n \ge 2 \implies \log_2 n \ge 1，可再次同取以 2 為底的對數 log⁡2\log_2：
    k−1≤log⁡2(log⁡2n)<kk - 1 \le \log_2(\log_2 n) < k

    根據高斯符號的定義，整數 k−1k - 1 即為 log⁡2(log⁡2n)\log_2(\log_2 n) 的向下取整值：
    k−1=⌊log⁡2(log⁡2n)⌋  ⟹  k=⌊log⁡2(log⁡2n)⌋+1k - 1 = \lfloor \log_2(\log_2 n) \rfloor \implies k = \lfloor \log_2(\log_2 n) \rfloor + 1

3. 求出 aa 與 bb 的最終值

將 kk 代入變數 aka_k 與 bkb_k 的通用表達式：

  • 變數 aa 的最終值：
    a=1+3k=1+3(⌊log⁡2(log⁡2n)⌋+1)=3⌊log⁡2(log⁡2n)⌋+4a = 1 + 3k = 1 + 3\left( \lfloor \log_2(\log_2 n) \rfloor + 1 \right) = 3 \lfloor \log_2(\log_2 n) \rfloor + 4

  • 變數 bb 的最終值：
    b=22k=22⌊log⁡2(log⁡2n)⌋+1b = 2^{2^k} = 2^{2^{\lfloor \log_2(\log_2 n) \rfloor + 1}}

🔒

後續完整解題步驟與【答案】

免費註冊，享三天全站完整詳解閱覽。

免費註冊

第 8 題20 分

  1. (20%) Find all integer solutions for xx and yy such that x≡2(mod3)x \equiv 2 \pmod{3}, x≡4(mod5)x \equiv 4 \pmod{5}, x≡6(mod7)x \equiv 6 \pmod{7} and y≡4(mod15)y \equiv 4 \pmod{15}, y≡7(mod21)y \equiv 7 \pmod{21}, y≡14(mod35)y \equiv 14 \pmod{35}.

登入後即可作答並保存紀錄。

這一題的完整詳解

核心觀念

  1. 中國剩餘定理 (Chinese Remainder Theorem, CRT)：
    若 m1,m2,…,mkm_1, m_2, \dots, m_k 為兩兩互質 (Pairwise Coprime) 的正整數，且 M=m1m2…mkM = m_1 m_2 \dots m_k，則線性同餘方程組：

    {x≡a1(modm1)x≡a2(modm2)⋮x≡ak(modmk)\begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \vdots \\ x \equiv a_k \pmod{m_k} \end{cases}

    在模 MM 下存在唯一特解 x0≡∑i=1kaiMiyi(modM)x_0 \equiv \sum_{i=1}^k a_i M_i y_i \pmod M，其中 Mi=MmiM_i = \frac{M}{m_i}，而 yiy_i 為 MiM_i 模 mim_i 的乘法反元素（即 Miyi≡1(modmi)M_i y_i \equiv 1 \pmod{m_i}）。通解為 x=x0+kM,k∈Zx = x_0 + kM, k \in \mathbb{Z}。

  2. 非兩兩互質模數同餘方程組之化簡：
    當模數不滿足兩兩互質條件時，不能直接套用 CRT。必須將各同餘式依模數的質因數分解拆解為質數冪次 (Prime Power) 的同餘式：

    • 檢驗相同質數模數下的同餘條件是否相容；若發生矛盾則方程組無解。
    • 若相容，則簡化合併為一組模數兩兩互質的同餘方程組後再進行求解。

  3. 同餘補數觀察法：
    若同餘式中 ai≡−c(modmi)a_i \equiv -c \pmod{m_i}（即餘數與模數差值恆定為 cc），則 x+cx + c 為所有模數的公倍數。

解題方法

第一部分：求解整數 xx

已知同餘方程組：

{x≡2(mod3)x≡4(mod5)x≡6(mod7)\begin{cases} x \equiv 2 \pmod{3} \\ x \equiv 4 \pmod{5} \\ x \equiv 6 \pmod{7} \end{cases}

求解推導（中國剩餘定理標準步驟）：

  1. 確認模數兩兩互質並計算總模數 MM：
    因 gcd⁡(3,5)=gcd⁡(5,7)=gcd⁡(3,7)=1\gcd(3,5) = \gcd(5,7) = \gcd(3,7) = 1，故模數兩兩互質。
    M=3×5×7=105M = 3 \times 5 \times 7 = 105

  2. 計算各分項模數 MiM_i 及其模反元素 yiy_i：

    • 對於 m1=3m_1 = 3：M1=1053=35M_1 = \frac{105}{3} = 35。
      求 35y1≡1(mod3)  ⟹  2y1≡1(mod3)  ⟹  y1≡2(mod3)35 y_1 \equiv 1 \pmod{3} \implies 2 y_1 \equiv 1 \pmod{3} \implies y_1 \equiv 2 \pmod{3}。
    • 對於 m2=5m_2 = 5：M2=1055=21M_2 = \frac{105}{5} = 21。
      求 21y2≡1(mod5)  ⟹  1y2≡1(mod5)  ⟹  y2≡1(mod5)21 y_2 \equiv 1 \pmod{5} \implies 1 y_2 \equiv 1 \pmod{5} \implies y_2 \equiv 1 \pmod{5}。
    • 對於 m3=7m_3 = 7：M3=1057=15M_3 = \frac{105}{7} = 15。
      求 15y3≡1(mod7)  ⟹  1y3≡1(mod7)  ⟹  y3≡1(mod7)15 y_3 \equiv 1 \pmod{7} \implies 1 y_3 \equiv 1 \pmod{7} \implies y_3 \equiv 1 \pmod{7}。

  3. 計算特解與通解：
    x0=(2×35×2)+(4×21×1)+(6×15×1)=140+84+90=314x_0 = (2 \times 35 \times 2) + (4 \times 21 \times 1) + (6 \times 15 \times 1) = 140 + 84 + 90 = 314
    將特解對總模數 105105 取餘數：
    314≡104(mod105)314 \equiv 104 \pmod{105}
    因此，整數 xx 的通解為：
    x=104+105k,k∈Zx = 104 + 105k, \quad k \in \mathbb{Z}

第二部分：求解整數 yy

已知同餘方程組：

{y≡4(mod15)y≡7(mod21)y≡14(mod35)\begin{cases} y \equiv 4 \pmod{15} \\ y \equiv 7 \pmod{21} \\ y \equiv 14 \pmod{35} \end{cases}

求解推導：

  1. 將非兩兩互質模數拆解為質數模數同餘式：
    • 由 y≡4(mod15)y \equiv 4 \pmod{15}（因 15=3×515 = 3 \times 5）： {y≡4≡1(mod3)y≡4(mod5)\begin{cases} y \equiv 4 \equiv 1 \pmod{3} \\ y \equiv 4 \pmod{5} \end{cases}
🔒

後續完整解題步驟與【答案】

免費註冊，享三天全站完整詳解閱覽。

免費註冊

其他考古題

114 年臺北大學的其他科目

資料結構與演算法

臺北大學《線性代數與離散數學》其他年度

115 年112 年111 年109 年108 年

其他學校的資工系考古題

臺灣大學36清華大學3陽明交通大學24成功大學24中央大學51中正大學34中山大學50高雄大學7暨南國際大學6嘉義大學4臺南大學2