109 專技高考高等考試 資訊技師 計算機數學 考古題詳解
第 一 題10 分
請用數學歸納法證明,對所有的正整數 滿足下列性質:
登入後即可作答並保存紀錄。
核心觀念
- 第一數學歸納法(First Principle of Mathematical Induction): 證明一個與正整數 相關的命題 對所有正整數皆成立,需滿足兩大要件:
- 基礎步驟(Base Step):證明當 時, 成立。
- 歸納步驟(Inductive Step):假設當 ()時命題 成立(此為歸納假設,Induction Hypothesis),推導出當 時, 亦必然成立。
- 不等式放縮與分式通分: 在歸納步驟中,透過將歸納假設的界限代入後,利用「作差法」或分式比較證明:
- 級數收斂背景(巴塞爾問題 Basel Problem 相關上界): 本題的不等式是高等微積分與演算法分析中估計調和平方和 嚴格小於 的標準經典放縮構造(其極限值實際為 )。
解題方法
題目指定必須使用「數學歸納法」證明。定義命題 為:
步驟一:基礎步驟(Base Step)
當 時:
- 左式()
- 右式()
因為 ,左式 右式成立,故 成立。
步驟二:歸納假設(Induction Hypothesis)
假設當 ( 為任意正整數,)時, 成立,即:
步驟三:歸納步驟(Inductive Step)
考慮 時的左式:
根據歸納假設,可將前 項放大替換:
我們的目標是證明該上界不大於目標右式 。將兩者作差比較:
第 二 題10 分
計算下列算式之值:
其中 為 個取 個的組合。
登入後即可作答並保存紀錄。
核心觀念
本題的核心考點為離散數學中的**二項式定理(Binomial Theorem)**及其展開式的收合應用。
二項式定理指出,對於任意實數 與非負整數 ,展開式滿足:
若固定其中一項令 ,則可簡化為單變數形式:
此外,計算時須運用負數之次方性質:當底數為 且指數為正偶數時,。
解題方法
本題若逐項展開計算 不可能在考試時間內完成,觀察其加總結構完全符合二項式展開式各項之特徵,因此應採用「二項式定理逆向收合」的方法求解。
步驟一:對照二項式定理標準式 題目所求之算式為:
將此式改寫為包含兩項基底的標準型態:
步驟二:確定各項參數並進行代數收合 對照二項式定理之展開式 :
- 項數上限:
- 第一項基數:
- 第二項基數:
因此,原加總式可完全逆向收合為:
步驟三:簡化括號內之運算並求值
由於指數 為偶數,負號相乘偶數次為正,故:
第 三 題10 分
有 個不同的盒子,分別標示號碼為 、、、、。現有 個相同的球放入此 個盒子中,若要求放入盒子中的球的個數不得少於此盒子標示的號碼,請問共有多少種不同放置球的方法?請說明答案理由。
登入後即可作答並保存紀錄。
核心觀念
本題屬於離散數學/組合數學中的經典課題:限制條件下的線性方程式整數解問題,其對應的計算核心為重複組合(Combinations with Repetition)或稱隔板法(Stars and Bars)。
- 相同物放入相異箱:將 個相同物件分入 個相異箱子,等價於求不定方程式 的整數解組數。
- 非負整數解公式:若限制各箱球數皆為非負整數(即 ),其相異解的總數為:
- 變數變換(預先分配法):若各變數有非零下限要求(),可透過平移變數令 ,將問題轉化為標準的非負整數解求解。
解題方法
1. 建立數學模型
設 5 個相異盒子依標號順序放入的球數分別為 。 根據題意,現有 100 個相同的球全部分入這 5 個盒子中,且放入各盒的球數不得少於該盒子標示的號碼,可列出數學關係式: 限制條件為整數解滿足:
2. 扣除保底數量(變數變換)
計算 5 個盒子所需之最少球數總和(等差數列求和):
因為球是相同的,我們可以「預先」將符合各盒最低限制的球數放入盒中:
- 第 1 個盒子放入 15 顆球
- 第 2 個盒子放入 17 顆球
- 第 3 個盒子放入 19 顆球
- 第 4 個盒子放入 21 顆球
- 第 5 個盒子放入 23 顆球
令各盒「額外獲得」的球數為 ,即:
第 四 題10 分
求出下列遞迴關係式的一般式:
登入後即可作答並保存紀錄。
核心觀念
本題評量離散數學中二階常係數齊次線性遞迴關係式(Second-Order Linear Homogeneous Recurrence Relation with Constant Coefficients)的求解能力。
- 標準型態: 二階常係數齊次線性遞迴關係式的標準型態為:
- 特徵方程式(Characteristic Equation): 設試驗解為 (其中 ),代入原式可得其特徵方程式:
- 通解型式(相異實根情形): 若特徵方程式有兩相異實根 (),則遞迴關係式的齊次通解為: 其中 為待定常數,由邊界條件(初始值) 聯立決定。
解題方法
步驟一:寫出標準式與特徵方程式 將原遞迴關係式移項整理為標準型態:
對應的特徵方程式為:
步驟二:求解特徵根 將特徵方程式進行因式分解: 解得兩相異實根:
步驟三:列出通解型式 因為特徵根為相異實根,故其通解為:
步驟四:利用初始條件求解待定係數 題目給定初始條件 、,代入通解:
- 當 時:
- 當 時:
第 五 題10 分
若字串為三個字母 、、 組成, 代表長度為 (),且不包含連續兩個 的字串總數,請計算 、?給出 的線性遞迴關係式(Linear Recurrence Relation)。
登入後即可作答並保存紀錄。
核心觀念
本題評量離散數學(計算機數學)中遞迴關係式的建立(Formulating Recurrence Relations)與排列組合計數原理。
- 加法原理(互斥分類):將長度為 的合法字串,依照「結尾字元」進行互斥且周延的分類。
- 條件約束與狀態轉移:
- 題目限制為「不可包含連續兩個 (即字串中不可出現子字串 )」。
- 若結尾非 (即結尾為 或 ),前綴只要是不含 的合法字串即可。
- 若結尾為 ,則其前一個字元受限制「絕不能為 」,必須為 或 ,從而回溯至長度 的合法字串。
解題方法
一、計算
長度為 的字串由字母集合 中挑選一個組成:
- 所有可能字串為:、、。
- 長度為 1 不可能出現「連續兩個 」,三者皆符合條件。
二、計算
長度為 的字串總數為 種。
- 違反應排除的字串:僅有「」一種(包含連續兩個 )。
- 合法字串數由全部扣除不合條件者(排容思考): (亦可列舉驗證:,共 8 種)
三、推導 的線性遞迴關係式
考慮長度為 ()且不含連續兩個 的字串,依其「最後一個字元」進行分類討論:
- 最後一個字元為 或 :
- 此時最後一個字元有 種選擇。
- 由於放入 或 絕不可能引發「連續兩個 」的違規,因此前 個字元只要本身是「長度為 且不含 」的合法字串即可。
- 此類字串共有:
- 最後一個字元為 :
- 為避免出現「」,其倒數第二個字元(第 個位置)絕對不能為 ,故必為 或 。
- 亦即,此類字串的結尾必為 或 ,共有 種末兩字元搭配。
第 六 題10 分
假設 代表敘述「 未通過測試」, 代表敘述「 讀了很多書」,請用邏輯敘述表示「若每個人都讀了很多書,則每人都會通過考試」。
登入後即可作答並保存紀錄。
核心觀念
本題評量一階述詞邏輯(First-Order Predicate Logic)之形式化符號表示能力,涉及以下基本定義與概念:
- 論域(Domain of Discourse, ):所有討論個體的集合,此處預設為「人」(全體人員)。
- 全稱量詞(Universal Quantifier, ):用以表示論域中「每一個」或「所有」個體皆滿足該述詞,記作 。
- 否定運算子(Negation, 或 ):將命題或述詞真值反轉。若 為「 未通過測試」,則其否定 即為「 通過測試(考試)」。
- 條件敘述(Conditional Implication, ):結構為「若 則 」(),其中 為前件(Antecedent), 為後件(Consequent)。
解題方法
本題為自然語言轉換至述詞邏輯的題型,解題切入點在於精確拆解複合金句的「前件」、「後件」及各自的「量詞作用域(Scope of Quantifiers)」。
-
確立論域 令論域 為全人類(即每一個人)。
-
前件形式化
- 語意:「每個人都讀了很多書」。
- 「每個人」對應全稱量詞 。
- 述詞 代表「 讀了很多書」。
- 前件邏輯式:。
- 後件形式化
- 語意:「每人都會通過考試」。
- 述詞 代表「 未通過測試」,因此「 通過考試」的述詞為其否定:。
- 「每人」同樣受全稱量詞修飾。
- 後件邏輯式:(亦可使用不同受詞變數寫為 ,兩者語意完全相同)。
- 複合條件連結
- 原文為「若【前件】,則【後件】」之蘊涵架構。
- 將兩者以條件運算子 連結,可得完整邏輯敘述:
第 七 題10 分
給一個無向圖(Undirected graph)。
是尤拉圖(Euler graph)的條件為何?請敘述理由。
若 為二分圖(Bipartite Graph)的條件為何?請敘述理由。
登入後即可作答並保存紀錄。
核心觀念
本題評量圖論(Graph Theory)中兩大經典圖形的結構特性與充分必要條件判定:
- 尤拉圖(Eulerian Graph):探討圖中是否存在一條走訪「每條邊恰好一次」且回到起點的閉合路徑(尤拉迴路,Eulerian Circuit)。其核心理論奠基於尤拉定理(Euler's Theorem),透過頂點的度數(Degree)奇偶性與連通性進行判定。
- 二分圖(Bipartite Graph):探討頂點集合能否被二分割為兩獨立集(Independent Sets),使得所有邊的兩端點分別屬於不同集合(等價於 2-著色問題)。其判定依據柯尼希定理(König's Theorem),核心在於圖中是否包含奇圈(Odd Cycle)。
解題方法
一、無向圖 為尤拉圖的條件與理由
1. 充分必要條件
無向圖 為尤拉圖(具有尤拉迴路)的充要條件為:
- 為連通圖(Connected Graph,若存在度數為 0 的孤立頂點則可忽略)。
- 中每一個頂點的度數皆為偶數(Even Degree),即 。
2. 理由敘述(充分性與必要性推導)
- 必要性(): 若 是尤拉圖,則存在一條尤拉迴路 。
- 連通性:迴路 遍歷所有的邊,凡是有邊相連的頂點皆被這條迴路串聯,故邊所在的子圖必然連通。
- 偶數度數:設迴路 依序走訪頂點。對於任意非起點的頂點 ,迴路每進入 一次(消耗一條關聯邊),就必須離開 一次(再消耗一條關聯邊),每次進出對 的貢獻均為 。對於起點 ,出發時消耗一條邊,最終返回時亦消耗一條邊,中途若有再次經過亦成對出現,故 亦必為偶數。由於迴路恰好用盡圖中每一條邊,故所有頂點的度數必全為偶數。
- 充分性(): 若 連通且所有頂點度數皆為偶數。
- 由於 (排除孤立點),由極長路徑法可知 中必至少包含一個簡單環路(Simple Cycle)。
- 從 中移除 的所有邊,得到剩餘子圖 。因為環路中每個頂點的度數貢獻均為 ,所以 中各頂點的度數依然保持全為偶數。
- 依此類推,利用數學歸納法,整個圖 可被完全分解為若干個邊不相交的簡單環路 (Cycle Decomposition)。
- 因原圖連通,各環路之間必有共用頂點,可藉由 Hierholzer 演算法將這些環路依交點逐步拼接整合,最終合成一條走遍所有邊的單一尤拉迴路。
二、無向圖 為二分圖的條件與理由
1. 充分必要條件
無向圖 為二分圖的充要條件為:
- 中不包含任何長度為奇數的簡單環路(No Odd Cycles)。
2. 理由敘述(充分性與必要性推導)
- 必要性(): 若 為二分圖,則頂點集可分割為互斥的兩集合 ,滿足 且 ,圖中所有的邊 均滿足一端點在 、另一端點在 。
- 考慮 中任意長度為 的環路 。
- 假設起始頂點 ,由於每走一條邊必在兩集合間切換一次:
第 八 題10 分
從 張撲克牌中,任選 張牌出來,此 張牌中至少有 張是相同花色的機率是多少?答案僅需列出最後計算公式,不需要算出最後結果。
登入後即可作答並保存紀錄。
核心觀念
- 古典機率定義: 在樣本空間 中各基本事件發生機率均等的前提下,事件 的機率為:
- 計數原理:
- 組合(Combination):從 個相異物件中不考慮順序選出 個物件的方法數為 。
- 乘法原理:完成一件事需分階段進行,各階段可能數相乘。
- 加法原理:不同互斥情況之可能數相加。
- 撲克牌結構: 一副標準撲克牌共 張牌,共有 種花色(黑桃、紅心、方塊、梅花),每種花色各有 張牌。
解題方法
本題求解從 張牌中任取 張,「至少 張相同花色」的機率。
-
求樣本空間總數 : 從 張牌中不計順序任意選出 張牌:
-
分析事件結構與分類討論: 抽出的總張數為 張,因此「至少 張相同花色」僅包含以下兩種互斥情形:
-
情況一:恰有 張同花色、第 張為其他花色
-
步驟一:從 種花色中選出 種作為擁有 張牌的花色,方法數為 。
-
步驟二:從該花色的 張牌中選取 張,方法數為 。
-
步驟三:第 張牌必須取自其他 種花色(共 張),方法數為 (亦可寫為 )。 由乘法原理,情況一的方法數為:
-
情況二: 張牌皆為相同花色
-
步驟一:從 種花色中選出 種花色,方法數為 。
-
步驟二:從該花色的 張牌中選取 張,方法數為 。 由乘法原理,情況二的方法數為:
第 九 題10 分
任給一長度為 的二位元字串 (Binary String),隨機變數 定義為 是字串 中 出現的個數加上 倍的 出現的個數之和,請計算 及 ,其中 為期望值, 為變異數。
登入後即可作答並保存紀錄。
核心觀念
本題評量離散機率與隨機變數的基本運算,主要涵蓋以下核心觀念與數學性質:
- 二位元字串之隨機模型: 在無特別聲明下,長度為 的二位元字串(Binary String)取樣為均勻分佈(Uniform Distribution),即各個位元(Bit)彼此獨立,且出現 與 的機率均等:
- 二項分佈(Binomial Distribution): 若隨機變數 代表長度為 的獨立試驗中成功(出現 )的次數,則 ,其期望值與變異數為:
- 隨機變數的線性變換性質: 若 ,且 為隨機變數,則:
解題方法
切入點:變數代換與降維(最佳解法)
令二位元字串長度 。
- 令隨機變數 表示字串 中 出現的個數。
- 令隨機變數 表示字串 中 出現的個數。
由字串總長度限制可知:
題目定義之隨機變數為 ,代入 進行化簡:
由上述式子可見, 僅由 決定,成功將原本的雙變數問題轉換為單一隨機變數之線性變換。
關鍵推導步驟
-
確立 的機率分佈: 每一位元獨立,且出現 的機率為 。總位元數 ,因此 服從參數為 的二項分佈: 計算 的期望值與變異數:
-
計算期望值 : 利用期望值的線性性質: 代入 :
第 十 題10 分
若 為一連續隨機變數定義如下:
若隨機變數
請計算 ,其中 為變異數。
登入後即可作答並保存紀錄。
核心觀念
本題評量連續隨機變數函數的期望值與變異數計算,核心觀念與必備公式如下:
- 隨機變數函數的期望值(LOTUS 法則): 若連續隨機變數 之機率密度函數(PDF)為 ,則對任一可積函數 ,其期望值定義為:
- 變異數的線性變換性質: 對任意常數 與隨機變數 ,變異數具備縮放平方與平移不變性:
- 變異數基本定義:
解題方法
本題不需透過「變數變換法(Change of Variables)」求出 的機率密度函數 ,直接利用變異數的線性變換性質將 化簡為求 ,再利用 LOTUS 定理分別積分求得 與 ,為最迅速且不易出錯的切入點。
步驟一:簡化目標式
由變異數的性質: 其中:
步驟二:計算
將 代入期望值積分式:
逐項積分:
步驟三:計算
同理,將 代入期望值積分式: