程式撰寫流程

Program Language (程式語言) = Data Structure (資料結構) + Algorithm (演算) Program Language (程式語言)

資料結構、演算法 「資料結構」(data structure): 在電腦中有效率地存放資料，使其方便處理的學問； 「演算法」(algorithm): 探討解決問題的策略。 兩者相輔相成!

演算法初探 Horowitz, Sahni 和 Mehta ，給予演算法的明確定義： 演算法是一組可完成特定工作的指令集合，並且所有的演算法都需滿足下列條件： (1) 輸入 (input)：可以有多個其甚至是沒有輸入； (2) 輸出 (output)：至少產生一個輸出； (3) 明確(definiteness)：每個指令都清楚明確； (4) 有限(finiteness)：在任何情況下，如果逐步追蹤演算 法的每個指令，演算法會在有限的步驟內結束； (5) 有效率(effectiveness)：原則上每個指令都需 基本到人只需紙和筆即可實踐之，並且每個指令的運算不止如條件(3)般明確而已，還必須是可實行的。

程式撰寫流程 問題的需求或限制 思考與探索 資料結構與演算法設計 程式撰寫 驗証、測試與修善 數學証明 結果輸出 撰寫程式解決問題流程圖

範例 寫一程式，將輸入正整數x，輸出x是否為質數。

輸入正整數x，輸出x是否為質數 演算法 檢查質數的步驟： 1. 若 x < =1，則傳回 x 不是質數。 4. 從 i=3 到 sqrt(x) 間格 2 若 x 是 i 的倍數，則傳回 x 不是質數。 5. 傳回 x 是質數。

輸入正整數x，輸出x是否為質數 流程圖

檢查質數的C程式 #define TRUE 1 #define FALSE 0 int prime(int x) { int i; // 檢查質數的步驟： // 1. 若 x < =1，則傳回 x 不是質數。 if (x<=1) return FALSE; // 2. 若 x <= 3，則傳回 x 是質數。 if (x<=3) return TRUE; // 3. 若 x 是 偶數，則傳回 x 不是質數 。 if (x%2==0) return FALSE; // 4. 從 i=3 到 sqrt(x) 間格 2 for (i=3; i<=sqrt(x); i+=2){ // 若 x 是 i 的倍數，則傳回 x 不是質數。 if (x%i==0) return FALSE; } // 5. 傳回 x 是質數。 return TRUE; 檢查質數的C程式

測試 prime 的C程式 #include <stdio.h> #include <stdlib.h> #include <math.h> int main() { int n; // Input a positive integer printf("請輸入一正整數： "); scanf("%d", &n); // test prime number & output result if (prime(n)==TRUE) printf("\n %d 是質數！\n\n",n); else printf("\n %d 不是質數！\n\n",n); // Pause system("pause"); } 測試 prime 的C程式

檢查質數的JAVA程式 import java.io.*; import java.lang.Math; //宣告類別 public class naturenum { //成員資料 private int num; //建構子 public naturenum() { num=1; } public naturenum(int x) num=x; //類別方法 public boolean prime() { int i; // 檢查質數的步驟： // 1. 若 num < =1，則傳回 num 不是質數。 if (num<=1) return false; // 2. 若 num <= 3，則傳回 num 是質數。 if (num<=3) return true; // 3. 若 num 是 偶數，則傳回 num 不是質數 。 if (num%2==0) return false; // 4. 從 i=3 到 sqrt(x) 間格 2 for (i=3; i<=(num/2); i+=2){ // 若 num 是 i 的倍數，則傳回 num 不是質數。 if (num%i==0) return false; } // 5. 傳回 x 是質數。 return true;

檢查質數的JAVA程式 public void show() { System.out.print(num); } public void set(int x) num=x; //主程式區塊 public static void main(String args[]) { //實作物件 naturenum x = new naturenum(13); //呼叫類別方法 x.show(); if (x.prime() == true) System.out.println("是質數\n"); else System.out.println("不是質數\n"); x.set(25); }

範例：挑選排序法 (Selection sort) 思考與探索： 欲將整數由小至大排序，可把數字小者放在左邊，數字大者放在右邊，… 挑出所有資料中最小者，做為左邊第一個資料，接著再挑出剩下資料中最小者，放在左邊做為第二個資料，依此類推，直至全部資料都排列完成。 若所有資料共計 n 個，則會執行n次挑出最小的運算，其第 i 次的運算，即為挑出未排序資料中最小者，其結果做為第 i 個資料。

挑選排序法 (Selection sort) 11, 7, 14, 1, 5, 9, 10 1, 7, 14, 11, 5, 9, 10 1, 5, 14, 11, 7, 9, 10 1, 5, 7, 11, 14, 9, 10 1, 5, 7, 9, 14, 11, 10 1, 5, 7, 9, 10, 11, 14 Input Output

範例：挑選排序法 (Selection sort)演算法 輸入：data[0], data[1], data[2], …, data[n-1]，共 n 筆整數資料 輸出：data[0], data[1],…, data[n-1]；其中 若i<j，則data[i]data[j]，0i<jn 方法： (用虛擬碼Pseudo code表示) for (i=0; i<n; i++) { 挑出data[i]至data[n-1]中最小者：data[min] 將data[i] 和 data[min] 對調 }

範例：挑選排序法 (Selection sort)程式C void SelectionSort(int data[], int n) { int i, j; int min, temp; for (i=0; i<n; i++) { // 挑出data[i]至data[n-1]中最小者：data[min] min = i; for (j=i+1; j<n; j++) if (data[j]<data[min]) min = j; // 將data[i] 和 data[min] 對調 temp = data[i]; data[i] = data[min]; data[min] = temp; }

程式的驗証、測試與修繕 數學証明―最佳的驗証；比較困難。 測試―輸入大量各式資料測試之。 若此為提供他人的程式，還應考慮輸入正確性(input validation)；若資料量非常大，則資料儲存用的陣列，宜用動態配置的技巧宣告使用

測試 selectionsort 的程式 int main() { int i, n=10, c[50]; // Input data for (i=0; i<n; i++) scanf("%d ", &c[i]); // sort SelectionSort(c, n); // Output Result printf("%d %d \n", i, c[i]); system("pause"); return 0; }

練 習 若資料是逐漸新增的方式加入資料，請寫一程式，當資料輸入後，立即就將資料依由小至大排好順序。

插入排序法 (Insertion sort) 11, 7, 14, 1, 5, 9, 10 11 7, 11 7, 11, 14 1, 7, 11, 14 1, 5, 7, 11, 14 1, 5, 7, 9, 11, 14 1, 5, 7, 9, 10, 11, 14

插入排序法 (Insertion sort)演算法 輸入：data[0], data[1], data[2], …, data[n-1]，共 n 筆整數資料 輸出：data[0], data[1],…, data[n-1]；其中 若i<j，則data[i]data[j]，1i,jn 方法： (用虛擬碼Pseudo code表示) while (有資料) { 將data[i]插入data[0]至data[i]中之適當位置 (data[i]從後往前，與前一個比，若data[i]較小則再往前，否則，即為data[i]的位置。) }

插入排序法 (Insertion sort)程式 void insertionSort(int data[], int n) { int i=0, j; int temp; while (data[i]>0){ // 有資料 // 將data[i]插入data[0]至data[i]中之適當位置 // (data[i]從後往前，與前一個比，若data[i]較小則再往前，否則，即為data[i]的位置。) j=i-1; temp=data[i]; while( j>=0 && temp<data[j]){ data[j+1]=data[j]; //向後移一位 j=j-1; } data[j+1]=temp; i=i+1;

#include <cstdlib> #include <iostream> using namespace std; void insertionSort(int data[], int n); int main(int argc, char *argv[]) { // 排序資料 int y[20] = {10,7,8,9,4, 2, 3, 6, 5,1, -1}; // 排序 insertionSort(y, 10); // 輸出排序結果 for (int i=0; i< 10; i++) cout << y[i] << ' '; cout<<endl; system("PAUSE"); return EXIT_SUCCESS; }

End