從食譜到高階程式語言 中央大學 資工系 江振瑞 教授

Presentation on theme: "從食譜到高階程式語言 中央大學 資工系 江振瑞 教授"— Presentation transcript:

1 從食譜到高階程式語言 中央大學 資工系 江振瑞 教授
認識演算法 從食譜到高階程式語言 中央大學 資工系 江振瑞 教授

2 1 演算法名稱的由來

3 阿布‧賈法‧穆罕默德‧賓‧穆薩‧阿爾-可瓦里茲米
演算法(Algorithm)一詞源自一位的阿拉伯數學家: 阿布‧賈法‧穆罕默德‧賓‧穆薩‧阿爾‧可瓦里茲米(Abu Jafar Muhammad ibn Musa al-Khwarizmi) (780 – 850 A. D.)的拉丁文譯名(al-Khwarizmi )。

4 阿爾-可瓦里茲米 (al-Khwarizmi)
阿爾–可瓦里茲米將印度所發明的十進位數字記號傳入阿拉伯地區，而阿拉伯商人在經商時則將十進位數字記號傳入歐洲成為現今我們使用的數字記號。 更重要的是，阿爾–可瓦里茲米著有一本討論有系統地解決一次方程式 (linear equation) 及一元二次方程式 (quadratic equation) 的書籍，此書被翻譯成名為”Liber algebrae et almucabala”的拉丁文書籍，啟發了代數學的萌芽，對人類的現代科技與文明發展有相當深遠的影響。代數學的英文名稱 Algebra 就是源自於此書之書名。

5 阿爾-可瓦里茲米 (續) (al-Khwarizmi)
阿爾–可瓦里茲米以一步一步(step by step)的方式，描述算術(arithmetic)運算與一元二次方程式及某些一次方程式的解答過程。稍後我們會知道，這些一步一步描述的解答過程就是我們現今所定義的演算法。這就是為什麼演算法(algorithm)的名稱是源自於阿爾–可瓦里茲米(al-Khwarizmi)的原因。 以下我們展示 一元二次方程的解法描述：

6 一元二次方程解法描述 關於解開 x 的方程: ax2 + bx + c = 0 (ax2 + bx = c) 的解法

7 2. 什麼是演算法?

8 什麼是演算法? 廣義的說，演算法是解決某一問題的一步一步程序(a step-by-step procedure for solving a problem) -- Merriam-Webster Dictionary 狹義的說，演算法是一個由一些步驟所構成的集合，依循這些步驟得以解決數學問題或完成計算機進程(a set of steps that are followed in order to solve a mathematical problem or to complete a computer process) -- Merriam-Webster Dictionary

9 食譜 (recipe) 是演算法 出處:嘉義市政府衛生局網頁
(

10 流程圖 (flowchart) 是演算法

11 其他廣義演算法的例子 企業組織的標準作業程序(Standard Operating Procedure, SOP) 也是演算法
工作人員面對特定問題時，只要按照步驟指示一步一步進行就能解決問題 設備的使用手冊(manual)或故障排除手冊也包含許多演算法 因為它包含許多可以用於解決某一問題(例如，如何安裝新設備及解決印表機的卡紙問題等) 的一步一步程序。

12 演算法計算角度的嚴謹定義 演算法(algorithm)：
由有限(finite)步驟(step)所構成的集合，依照給定輸入(input)依序執行每個明確(definite)且有效(effective) 的步驟，以便能夠解決特定的問題；而步驟的執行必定會終止(terminate)，並產生輸出(output) 。

13 演算法的特性 根據演算法計算角度的嚴謹定義，演算法是由解決某一特定問題的步驟所組成，具有以下特性:
指定輸入(input)：演算法必須指定輸入，可以由外界輸入0 個、1 個或多個資料。 具有輸出(output)：演算法必定有至少1 個以上的輸出。 有限性(finiteness)：演算法步驟的個數必須是有限的，而且步驟的執行最後會終止(terminate)。 明確性(definiteness)：演算法的每個步驟都必須是明確(definite) 而不含糊的(unambiguous)。 有效性(effectiveness)：演算法的每個步驟必須是有效的(effective) 或說是可行的(feasible)。 Definiteness: each instruction is clear and unambiguous. To compute “add 6 or 7 to x” is not definite. Finiteness: (the number of steps should be finite and the execution of the steps should terminate) if we trace out the instructions of an algorithm, then for all cases, the algorithm terminates after a finite number of steps. Finiteness implies termination (OS is thus not an algorithm) Effectiveness: All operations should be feasible. Each step must be such that it can, at least in principle, be done by a person using pencil and paper in a finite amount of time.

14 演算法的特性(續) 演算法必須指定輸入 演算法必須要有一個以上的輸出 演算法必須滿足有限性(finiteness)
我們有時會透過介面(例如鍵盤) 由外界獲得問題輸入，有時也會將輸入直接寫在演算法中。 因此演算法可以由外界輸入0 個、1 個或多個資料。 演算法必須要有一個以上的輸出 如此演算法才能為人們所用。 演算法必須滿足有限性(finiteness) 它的步驟個數必須是有限的，而且步驟的執行最後會終止(terminate)； 如此，演算法才有可能在執行有限步驟之後終止並產生輸出為人們所用。 Definiteness: each instruction is clear and unambiguous. To compute “add 6 or 7 to x” is not definite. Finiteness: (the number of steps should be finite and the execution of the steps should terminate) if we trace out the instructions of an algorithm, then for all cases, the algorithm terminates after a finite number of steps. Finiteness implies termination (OS is thus not an algorithm) Effectiveness: All operations should be feasible. Each step must be such that it can, at least in principle, be done by a person using pencil and paper in a finite amount of time.

15 演算法的特性(續) 演算法必須滿足明確性(definiteness)，也就是說它的每一個步驟必須是明確(definite) 而不含糊的(unambiguous)。 例如，若有一個步驟是「加6 或7 到變數x」，則這個步驟是不明確的，因為我們可能加6 也可能加7 到變數x 中 但是，「加亂數生成器(random number generator) 函數的值到變數x」則是明確的步驟，因為我們可以很明確地將亂數產生器函數的值加到變數x 又例如，「計算5/0」是不明確的，因為分母(除數) 為0 是沒有明確定義的計算。 Definiteness: each instruction is clear and unambiguous. To compute “add 6 or 7 to x” is not definite. Finiteness: (the number of steps should be finite and the execution of the steps should terminate) if we trace out the instructions of an algorithm, then for all cases, the algorithm terminates after a finite number of steps. Finiteness implies termination (OS is thus not an algorithm) Effectiveness: All operations should be feasible. Each step must be such that it can, at least in principle, be done by a person using pencil and paper in a finite amount of time.

16 演算法的特性(續) 演算法必須滿足有效性(effectiveness)，也就是說演算法的每個步驟必須是有效的(effective)或說是可行的(feasible) 每個步驟即使由人們拿著紙筆，都可以在有限時間內計算出結果。 例如，步驟「計算出√2 完全無誤差的值」不滿足有效性，因為它是不可行的，我們需要進行無窮位數的計算才可以得到√ 2 完全無誤差的值。 相反的，「計算√2 到小數點以下10 位，並捨棄其後位數」則滿足有效性，因為它是可行的，人們即使只是藉由紙筆，都可以計算出√2 = 的結果。 Definiteness: each instruction is clear and unambiguous. To compute “add 6 or 7 to x” is not definite. Finiteness: (the number of steps should be finite and the execution of the steps should terminate) if we trace out the instructions of an algorithm, then for all cases, the algorithm terminates after a finite number of steps. Finiteness implies termination (OS is thus not an algorithm) Effectiveness: All operations should be feasible. Each step must be such that it can, at least in principle, be done by a person using pencil and paper in a finite amount of time.

17 3. 演算法的例子

18 解決正整數m是不是正整數n的倍數問題的流程圖

19 解決正整數m是不是正整數n的倍數問題的C++程式

20 一個既不會終止，也不產生輸出的C程式 – 不是演算法

21 4. 如何表示演算法?

22 演算法的表示 一般我們使用以下方式來表示演算法: 自然語言(中文或英文等語言) 流程圖(flow chart)
虛擬碼(pseudo code) 以下我們舉一個古老的演算法  歐幾里德演算法(Euclid Algorithm)為例子，說明如何以上列三種方式表示演算法。

23 歐幾里德(輾轉相除)演算法 歐幾里德演算法(Euclid, Euclid’s or Euclidean algorithm) 大約在西元前300年由希臘數學家歐幾里德提出，可用於求出二個整數的最大公因數(gcd, greatest common divisor)，又稱為輾轉相除演算法(division algorithm) 。 「歐幾里得算法是所有算法的鼻祖，因為它是現存最古老的非凡算法。」 ——高德納，《電腦程式設計藝術，第二卷：半數值算法》，第二版 (1981), p. 318. "[The Euclidean algorithm] is the granddaddy of all algorithms, because it is the oldest nontrivial algorithm that has survived to the present day." Donald Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 2nd edition (1981), p. 318.

24 歐幾里德演算法 (Euclid Algorithm) 以自然語言表示
歐幾里德演算法: 問題：給定二個正整數m及n，找出此二數的最大公因數GCD(也就是能同時整除m及n的最大正整數) 解法： 步驟1.[找出餘數] 求出m除以n的餘數，並記錄於r。 步驟2.[餘數為0嗎?] 如果r=0則停止，輸出n為GCD。 步驟3.[換被除數與除數] 設定m=n,n=r，並跳至步驟1。

25 歐幾里德演算法 (Euclid Algorithm) 以流程圖表示

26 ANSI流程圖符號

27 ANSI流程圖符號(續)

28 歐幾里德演算法 (Euclid Algorithm) 以虛擬碼表示

29 虛擬碼 (Pseudo Code) 虛擬碼以一種混雜著自然語言與高階程式語言結構的方式來描述演算法。
可以達到簡潔易讀、容易分析，而且也容易轉換為高階程式語言的目的。 以下我們介紹本課程所採用的虛擬碼撰寫規則，因為虛擬碼仍然具有自然語言性質，因此這些撰寫規則有時可以稍稍調整，以方便閱讀者理解為原則。

30 虛擬碼 (Pseudo Code)(續) 虛擬碼撰寫規則如下:
演算法名稱及參數：以 Algorithm 演算法名稱 (參數 1, 參數 2,…) 來列出演算法名稱並指明其輸入參數。 輸入：以 Input 輸入描述 來進行輸入說明 輸出：以 Output 輸出描述 來進行輸出說明

31 虛擬碼 (Pseudo Code)(續) 設定：以 ← 表示，可以將一個算式 (expression) 的值指定給某一個變數 (置入某變數中) 算術運算：以 + − ∗ / % 表示加、減、乘、除、模 (除法求餘數)運算

32 虛擬碼 (Pseudo Code)(續) 比較與邏輯運算：以 = > <    表示等於、大於、小於、大於等於、小於等於及不等於的運算，並使用   ~ 表示邏輯的且、或與反向的運算。 決策結構：以 if 條件 then 條件為真的動作 else 條件為偽的動作 end if 來表示。當條件成立時，演算法執行所有包含在「條件為真的動作」的所有指令 (步驟)；反之則執行所有包含在「條件為偽的動作」的所有指令。

33 虛擬碼 (Pseudo Code)(續) while 迴圈：以 while 條件 do 迴圈動作 end while 來表示。當條件成立時，演算法會重複執行所有包含在「迴圈動作」的所有指令；反之則離開迴圈，進入下一個指令。 for 迴圈：以 for 迴圈變數變動之範圍及其變動方式do 迴圈動作 end for 來表示。當「迴圈變數」的值在指定的範圍中時，演算法會重複執行所有包含在「迴圈動作」的所有指令；反之則離開迴圈，進入下一個指令。

34 虛擬碼 (Pseudo Code)(續) 陣列元素索引：以 陣列名稱 [i] 代表命名為陣列名稱的陣列索引 (index) 為 i 的元素，一個有 n 個元素的陣列，其元素索引值為 0,1,…,n-1 演算法呼叫：以 演算法名稱 (參數…) 來表示演算法的呼叫 演算法返回: 以 return 返回值 來代表演算法結束執行並輸出返回值。

35 5. 如何實作演算法?

36 演算法的實作(implementation)
除了以自然語言、流程圖、虛擬碼表示演算法之外，我們也可以使用高階程式語言(high level programming language)來表示演算法。 當我們以高階程式語言表示演算法時，我們可以在電腦上直接執行以高階程式語言編寫而成的程式，並藉此得到執行結果。我們特別將之稱為「以高階程式語言實作(implement)演算法」，或是稱為「以高階程式語言進行演算法的實作(implementation)」。

37 演算法的實作(implementation)(續)
以下我們將舉例說明使用C、C++、Java 與Python 語言實作歐幾里德演算法，或稱為歐幾里德GCD(Euclid GCD)演算法。 建議使用Jeep5軟體進行C、C++、Java 與Python 語言的編輯、編譯與執行。Jeep5 為Java Editor for Chinese Programmer v5.0 的簡稱，是由江振瑞教授使用Java 語言所編寫的整合開發環境(Integrated Development Environment, IDE)軟體，支援C、C++、Java 與Python 四種語言，並透過簡潔的中文介面，讓使用者輕易完成四種不同語言程式的編輯、編譯與執行等工作。請參考本單元後的Jeep5補充資料以獲得Jeep5詳細的資訊 。

38 演算法的實作(implementation)(續)
因為演算法有指定輸入的特性，因此演算法僅處理特定的輸入。例如，剛剛提過的歐幾里德演算法指定輸入二個正整數m及n。當然，當我們以高階程式語言實作演算法，讓使用者特過輸入介面由外界傳入演算法輸入時，可能會輸入錯誤的資料(例如輸入負數)。本課程聚焦於演算法解決問題的核心概念，因而假設所有的輸入都符合演算法的指定，所以在實作演算法時不處理使用者輸入錯誤資料的狀況。

39 演算法的實作(implementation)(續)
在實務上，若我們將符合演算法指定的輸入資料以文字檔案形式儲存，並以作業系統之輸入轉向(redirect)方式將文字檔案資料直接輸入高階程式語言程式中，則所有的輸入都會符合演算法的指定。基本上，著名的計算機協會國際大學生程式設計競賽(Association of Computing Machinery International Collegiate Programming Contest，簡稱 ACM ICPC）就是採取上述的方法作為高階語言程式的輸入方式以進行比賽。 ACM ICPC是一個試煉各種演算法實作的好場合，國際間也有許多團體提供相關的ICPC訓練教學網站(例如，UVa Online Judge)與ICPC賽事裁判系統(例如，PC2(Programming Contest Control)系統)。請參考本單元後的補充資料以獲得ACM ICPC詳細的資訊 。

40 以C程式語言實作 歐幾里德GCD演算法 下列的C語言程式EuclidGCD.c以int EuclidGCD(int m, int n)函式或函數(function)實作歐幾里德演算法。並在主要函式main()中加入標準輸入(printf(...))與標準輸出(scanf(...))敘述，並呼叫EuclidGCD方法，讓演算法可以由外部輸入訊息，並輸出計算結果。

41 以C程式語言實作 歐幾里德GCD演算法–執行結果
實作展示: 以Jeep5編輯、編譯及執行 執行結果:

42 以C++程式語言實作 歐幾里德GCD演算法
下列的C++語言程式EuclidGCD.cpp以int EuclidGCD(int m, int n)函式實作歐幾里德演算法。並在主要函式int main()中加入標準輸入(cin>>...)與標準輸出(cout<<...)敘述，並呼叫EuclidGCD方法，讓演算法可以由外部輸入訊息，並輸出計算結果。

43 以C++程式語言實作 歐幾里德GCD演算法–執行結果
實作展示: 以Jeep5編輯、編譯及執行 執行結果:

44 以Java程式語言實作 歐幾里德GCD演算法
下列的Java語言程式EuclidGCDClass1.java以方法(method)static int EuclidGCD(int m, int n)實作了歐幾里德演算法。並在主類別EuclidGCDClass1中的主要方法public static void main(…)中加入標準輸入(Scanner Cin=new Scanner(System.in);...Cin.nextInt())與標準輸出(System.out.print(...))敘述，並呼叫EuclidGCD方法，讓演算法可以由外部輸入訊息，並輸出計算結果。

45 以Java程式語言實作 歐幾里德GCD演算法–執行結果
實作展示: 以Jeep5編輯、編譯及執行 執行結果:

46 以Java程式語言實作 歐幾里德GCD演算法(續)
下列的Java語言程式EuclidGCDClass2.java與EuclidGCDClass1.java類似，但是採用視窗輸入(JOptionPane.showInputDialog(...))與視窗輸出(JOptionPane.showMessageDialog(...))敘述，讓演算法可以由外部輸入訊息，並輸出計算結果。 另外，程式EuclidGCDClass2.java也善用Java語言支援UTF-8字元編碼的國際化特性，使用中文來替變數命名。這樣做有一個好處，當讀者看到程式中出現中文的變數名稱時，就可以知道這是由使用者自行命名的，而英文的部份則很清楚的是語言的關鍵字或是語言系統中內建的類別。

47 以Java程式語言實作 歐幾里德GCD演算法–執行結果(續)
實作展示: 以Jeep5編輯、編譯及執行 執行結果:

48 以Python程式語言實作 歐幾里德GCD演算法
下列的Python語言程式EuclidGCD.py以EuclidGCD(m, n)方法實作歐幾里德演算法。並以標準輸入(raw_input(...))與標準輸出(print(...))敘述由外部輸入訊息及輸出計算結果。

49 以Python程式語言實作 歐幾里德GCD演算法–執行結果
實作展示: 以Jeep5編輯及執行 執行結果:

50 6. 演算法的正確性

51 演算法的正確性 (1) 一個演算法一定要能夠產生正確的結果，也就是滿足正確性(correctness)，如此演算法才能夠為人們所用。
我們可以透過以下的證明，來證明演算法的正確性: 演繹法(deduction)(也就是直接證明(direct proof)) 歸納法(induction) 矛盾法(contradiction)(也就是反證法) 演算法的正確性無疑的是演算法最重要的特性，然而因為課程時間有限，我們有時不會特別說明演算法的正確性證明。請大家自行參考文獻資料以獲得演算法的正確性證明。 提出演繹法的是法國人笛卡兒，提出歸納法的是英國人培根。 記憶法：演一隻豬腳、跪那條培根 A theorem is a statement in mathematics or logic that can be proved to be true by reasoning. (Collins Dictionaries)

52 演算法的正確性 (2) 我們利用以下以三個命題(proposition)或定理(theorem)為例，解釋上述三種證明法:
歐幾里德輾轉相除最大公因數演算法正確性定理 因數(divisor or factor)相關定理 質數(prime or prime number)與合數(composite number)相關定理 我們先介紹以下一些定義: 若m和n為不全為零的整數，則m和n的最大公因數(greatest common divisor)，標示為gcd(m,n)，是同時整除它們的最大整數。若gcd(m,n)=1，則我們說m和n互質或互素(relatively prime, mutually prime, co-prime or coprime)。 質數(prime or prime number)，又稱素數，指的是除了1和該數本身之外，無法被其他正整數整除的大於1的整數。根據定義，1不是質數，而2是最小的質數。 合數(composite number): 大於1的整數若不是質數，則稱為合數。例如，除了2以外，所有的偶數都是合數；而0與1既不是質數也不是合數。 提出演繹法的是法國人笛卡兒，提出歸納法的是英國人培根。 記憶法：演一隻豬腳、跪那條培根 A theorem is a statement in mathematics or logic that can be proved to be true by reasoning. (Collins Dictionaries)

53 演繹法 或 演繹推論 或 直接證明 演繹法(deduction)或演繹推理(deductive reasoning)或直接證明(direct proof) 證明思維: 利用邏輯推理，由已知的命題推導出下一個命題，如此一一推導出欲證明的命題為真。 我們在以下列出常見的演繹推理形式。 (取材自維基百科: 演繹推理, 演繹推理（英語：Deductive Reasoning）在傳統的亞里士多德邏輯中是「結論，可從叫做『前提』的已知事實，『必然地』得出的推理」。如果前提為真，則結論必然為真。

54 常見演繹推理 名字 相繼式 描述 肯定前件 論式 (p → q) ; p ├ q 若 p 則 q; p ,所以 q 德·摩根定律(1)
肯定前件 論式 (p → q) ; p ├ q 若 p 則 q; p ,所以 q 德·摩根定律(1) ¬(p ∧ q) ├ (¬p ∨ ¬ q) (p 與 q)的否定等 價於(非 p 或非 q) 否定後件 論式 (p → q) ; ¬q ├ ¬p 若 p 則 q; 非 q; 所以，非 p 德·摩根定律(2) ¬(p ∨ q) ├ (¬p ∧ ¬ q) (p 或 q)的否定等 價於(非 p 與非 q) 假言三段 論式 (p → q) ; (q → r) ├ (p → r) 若 p 則 q; 若 q 則 r; 所以，若 p 則 r 交換律(1) (p ∨ q) ├ (q ∨ p) (p 或 q)等價於(q 或 p) 選言三段 論式 (p ∨ q) ; ¬p ├ q 要麼 p 要麼 q; 非 p; 所以, q 交換律(2) (p ∧ q) ├ (q ∧ p) (p 與 q)等價於(q 與 p) 創造性二 難論式 (p → q)∧(r → s) ; (p ∨ r) ├ (q ∨ s) 若 p 則 q; 並且若 r 則 s; 但是要麼 p 要麼 r; 所以，要 麼 q 要麼 s 結合律(1) p ∨ (q ∨ r) ├ (p ∨ q) ∨ r p 或(q 或 r)等價 於(p 或 q)或 r

55 常見演繹推理 名字 相繼式 描述 破壞性二 難論式 (p → q)∧(r → s) ; (¬q ∨ ¬s) ├ (¬p ∨ ¬r)
破壞性二 難論式 (p → q)∧(r → s) ; (¬q ∨ ¬s) ├ (¬p ∨ ¬r) 若 p 則 q; 並且若 r 則 s; 但是要麼非 q 要麼非 s; 所以， 要麼非 p 要麼非 r 結合律(2) p ∧ (q ∧ r) ├ (p ∧ q) ∧ r p 與(q 與 r)等價 於(p 與 q)與 r 簡化論式 (p ∧ q) ├ p p 與 q 為真; 所以， p 為真 分配律(1) p ∧ (q ∨ r) ├ (p ∧ q) ∨ (p ∧ r) p 與(q 或 r)等價 於(p 與 q)或(p 與 r) 合取式 p, q ├ (p ∧ q) p 與 q 分別為真; 所以，它們結合起 來是真 分配律(2) p ∨ (q ∧ r) ├ (p ∨ q) ∧ (p ∨ r) p 或(q 與 r)等價 於(p 或 q)與(p 或 r) 增加論式 p ├ (p ∨ q) p 是真; 所以析取 式(p 或 q)為真 雙重否定律 p ├ ¬¬p p 等價於非 p 的 否定 合成論式 (p → q) ∧ (p → r) ├ p → (q ∧ r) 若 p 則 q; 並且若 p 則 r; 所以，若 p 是真則 q 與 r 為真 換位律 (p → q) ├ (¬q → ¬p) 若 p 則 q 等價於 如果非 q 則非 p

56 演繹法範例 定理: 歐幾里德演算法是正確的。
證明: 只要證明gcd(m,n)=gcd(n,r)就可得證，其中r=m%n。 令gcd(m,n)=g，則我們可得m=ig, n=jg。r=m-kn=ig-jkg = (i-jk)g，這表示g也是r的因數。設j與i-jk的最大公因數為d，則可設j=xd, i-jk=yd。我們可得i=jk-yd=xdk-yd=(xk-y)d。因而推得m=(xk-y)dg, n=xdg，並可推得gcd(m,n)=dg。因為gcd(m,n)=g，我們可推得d=1(也就是i-jk與j互質)。所以gcd(n,r)=gcd(jg, i-jkg)=g，故得證。 □ 歐幾里德使用反證法證明「有無限多個質數」。 QED又寫作Q.E.D.。這是拉丁片語「quod erat demonstrandum」（這就是所要證明的）的縮寫。 現在的證明完畢符號，通常是■（實心黑色正方形），稱之為「墓碑」或「哈爾莫斯（Halmos symbol）」（因保羅·哈爾莫斯最先採用此做法）。墓碑有時是空心的□。

57 歸納法 歸納法(induction)通常用於證明命題針對大於某個基礎值的自然數n均成立。 證明思維:
歸納基底(induction base):先證明當n等於基礎值n0時命題成立。 歸納假設(induction hypothesis): 假設當n=kn0時命題成立。 歸納步驟(induction step): 基於歸納假設推導(deduce)n=K+1時命題也成立。 最後根據歸納原則(induction principle)即可證明當n大於或等於基礎值n0時命題都成立。 備註: 有許多學者將歸納假設與歸納步驟合為一步。

58 歸納法證明範例 唯一分解定理(unique factorization theorem): 大於1的整數n必可分解為唯一的一組質數乘積的表示式，亦即 𝑛= 𝑝 1 𝑘 1 𝑝 2 𝑘 2 ⋯ 𝑝 𝑗 𝑘 𝑗 其中 𝑝 1 < 𝑝 2 <⋯< 𝑝 𝑗 皆為質數，且這個表示式是唯一的。

59 歸納假設：假定所有符合2≤𝑚<𝑛的整數m可表示成一組質數乘積
證明：我們利用歸納法證明上述表示式存在 歸納基底： 2= 2 1 歸納假設：假定所有符合2≤𝑚<𝑛的整數m可表示成一組質數乘積 歸納步驟：如果n是質數，則𝑛= 𝑛 1 為我們的表示式。否則，n為合成數，代表存在整數𝑚,ℎ>1使得𝑛=𝑚ℎ。很清楚地，𝑚,ℎ<𝑛。因此，藉由歸納假設，m與h可表示為質數乘積。亦即 𝑚= 𝑝 1 𝑘 1 𝑝 2 𝑘 2 ⋯ 𝑝 𝑗 𝑘 𝑗 ℎ= 𝑞 1 𝑙 1 𝑞 2 𝑙 2 ⋯ 𝑞 𝑖 𝑙 𝑖 由於𝑛=𝑚ℎ ， 𝑛= 𝑝 1 𝑘 1 𝑝 2 𝑘 2 ⋯ 𝑝 𝑗 𝑘 𝑗 𝑞 1 𝑙 1 𝑞 2 𝑙 2 ⋯ 𝑞 𝑖 𝑙 𝑖 聚集相等的質數並根據質數值遞增排列，即可得到需要的表示式。 根據歸納原則故定理得證。 QED QED又寫作Q.E.D.。這是拉丁片語「quod erat demonstrandum」（這就是所要證明的）的縮寫。 現在的證明完畢符號，通常是■（實心黑色正方形），稱之為「墓碑」或「哈爾莫斯（Halmos symbol）」（因保羅·哈爾莫斯最先採用此做法）。墓碑有時是空心的□。

60 矛盾法(反證法) 矛盾法(contradiction)也稱反證法
證明思維:欲證明某命題為真，則先假設該命題為假，若能由假設推理導致邏輯上的矛盾，則能夠 證明最初的假設錯誤，也就是證明原命題為真。

61 矛盾法(反證法)範例 定理: 質數有無限多個。
證明: 假設只有有限的n(n>0)個質數，令其由小而大為 p1 , p2, ..., pn。考慮整數p＝(p1 × p2 ×...× pn)+1，根據假設p必定為質數，因為p比所有質數p1 , p2, ..., pn都大。我們可得以下兩個情況: (情況1) p 可被小於p的質數p1 , p2, ...或pn整除。但是這情況不成立，因為p1 , p2, ..., pn除p都餘1(p＝(p1 × p2 ×...× pn)+1 ) 。 (情況2) p可被小於p的合數q整除。但這也不成立，因為連續因數分解q可得q為質數乘積q1× q2 ×...× qm，其中q1, q2, ..., qm < q < p。因為p可被q整除，所以p也可被質數q1, q2, ..., qm整除，但是p1 , p2, ..., pn除p都餘1，所以這情況也不成立。 因為矛盾產生，所以假設是錯誤的，因此得證質數有無限多個。 ■ 歐幾里德使用反證法證明「有無限多個質數」。 QED又寫作Q.E.D.。這是拉丁片語「quod erat demonstrandum」（這就是所要證明的）的縮寫。 現在的證明完畢符號，通常是■（實心黑色正方形），稱之為「墓碑」或「哈爾莫斯（Halmos symbol）」（因保羅·哈爾莫斯最先採用此做法）。墓碑有時是空心的□。

62 The End