A-level 計算機/WJEC (Eduqas)/元件 1/演算法和程式

演算法

演算法是解決特定問題的有限指令集。它可以使用虛擬碼、流程圖或結構化英語來表示。

表示

虛擬碼

虛擬碼是用“通用”語言編寫的演算法。它們是在沒有考慮任何特定程式語言的情況下編寫的，而是旨在更接近於純英語。這使程式設計師能夠理解解決方案的邏輯和演算法方面，而無需擔心編碼語言的細微差別。提供虛擬碼是明確的，並且遵循任何程式語言的基本規則（例如變數宣告）。在考試中，你會遇到這種虛擬碼

標準	表示
變數宣告	Num 是整數
變數初始化	設定 Num = 0
使用者輸入	輸入 Num
輸出訊息	輸出“輸入下一個數字。”
註釋/標註	{新增增值稅後的價格}
連線	輸出“最高分數”, 總計
選擇（IF）	如果平均值 > 75 則 輸出“需要進一步治療。” 否則 輸出“不需要進一步治療。” 結束 IF
While 迴圈	當 Num < 0 時 輸入 Num 結束 While
For 迴圈	對於 Count = 1 到 20 如果 Value > Max 則 Max = Value 結束 For
While 迴圈	重複 如果 Number MOD Divisor = 0 則 Prime = FALSE 結束 IF 設定 Divisor = Divisor +1 直到 (Prime = FALSE) 或 (Divisor = Number)

流程圖

在流程圖中顯示決策。這些形狀的組合構成了決策流程圖。

流程圖是視覺化表示演算法的一種方法（有關形狀，請參見規範中的附錄 D）。這是透過使用圖表來完成的，從開始標籤開始，並遵循各種語句和問題之間的線條，這些語句和問題被執行和遵守，直到到達終點。

每個不同的指令型別都用不同的形狀表示：開始和結束點通常用橢圓形或圓角矩形表示，過程（例如計算）發生在矩形內，輸入由梯形接收，平行四邊形表示輸出，菱形（菱形）用於表示決策。決策菱形是流程圖路徑分叉的地方，從它出來有兩條線，通常標記為“是”或“否”。在遵循流程圖時，根據決策菱形本身寫出的問題的答案選擇正確的線。

正如你可能已經知道的那樣，對於較大的程式，流程圖很快就會變得複雜，建立足夠複雜的流程圖可能需要一段時間，並且通常難以遵循。因此，流程圖通常只用於較小的、不太複雜的程式。

目錄

變數和常量

常量

Algorithm CalculateVAT

RateVAT = 0.2   {this is a constant to store the VAT rate}

這些在程式中儲存固定值，與變數不同，變數可以隨時更改。相反，常量在程式頂部定義，並在整個程式中儲存相同的值，如果程式的任何部分嘗試更改它，則會丟擲錯誤。這可以防止意外更改常量。常量不會經常改變，但如果改變，在程式頂部更改它們比在程式主體中出現的地方更容易（例如，在程式中變數的多個例項）。

識別符號

自文件識別符號

不可避免地，其他人會閱讀你的程式碼，獨自工作的情況很少見。變數應該以一種你可以理解其內容將包含什麼的方式命名，例如，MemberID 將包含成員的 ID。它是自文件的，你不需要閱讀任何額外的內容或查閱解釋以理解它將包含什麼內容。一個非自文件變數的例子是“value”或“x”，因為含義非常不清楚。

註釋

{comments help other programmers to understand code}

註釋是插入到程式碼中的英文片段。它們幫助其他程式設計師理解程式碼，但對於程式執行來說是完全不需要的。註釋用於透過不同的程式設計師或同一程式設計師在以後的時間（例如，在提高效率時）使程式更易於閱讀。當程式被編譯時，註釋會被丟棄。

程式佈局

有些語言明確要求您以特定方式佈局程式碼，以便程式碼能夠正常執行。然而，其他語言在方法上則比較寬鬆。良好的程式佈局要求您縮排程式碼並符合某些標準，例如在運算子之間新增空格。有些公司更喜歡用 駝峰式命名法 編寫程式碼，而其他公司更喜歡用 蛇形命名法，但無論您使用哪種方法，都應該在整個編碼專案中保持一致。請檢視以下示例，瞭解程式佈局的含義。

If CodeLayoutCheckPassed = 1 Then
       codeIndented = 1
       selfDocumentingIdentifiersUtilised = 1
Else
       codeIndented = 0
       selfDocumentingIdentifiersUtilised = 0
End If

這種方式不太好，因為您無法清楚地看到程式可能採用的不同路徑。

If CodeLayoutCheckPassed=1 Then
code_Indented=1
self_Documenting_IdentifiersUtilised=1
Else
code_Indented=0
self_DocumentingIdentifiersUtilised=0
End If

變數的作用域

變數具有作用域。作用域是指變數在程式中可以使用的地方。區域性變數只能在定義它們的子程式中使用，而全域性變數可以在整個程式中使用。全域性變數僅在程式執行期間存在，並且可以在任何時候訪問。區域性變數僅在程式處於宣告它們的範圍時存在，例如在 For 迴圈中，當迴圈結束時，"Item" 變數會遞增 1。

子程式

大型程式也可以被分解成執行特定任務的命名程式碼塊。這些就是子程式，它們很重要，因為一旦定義，子程式可以在程式中的任何位置被呼叫以執行其任務。這使得它們成為解決需要在整個程式中重複相同指令序列的問題的理想選擇。大多數語言使用兩種型別的子程式——函式和過程。兩者在功能上非常相似，除了一個重要的區別：函式 **必須** 將單個值返回到程式的主體，而過程則不會。這種區別通常在函式和過程的定義方式中明確表示。

引數

兩種型別的子程式都依賴於引數來傳遞要利用的值。傳遞引數有兩種方式：按值傳遞或按引用傳遞。按值傳遞是指建立一個區域性 **副本** ，並在過程執行後將其丟棄。按引用傳遞是指傳遞 **地址** 而不是實際資料。按值傳遞的優點是它避免了意外的副作用，在這些副作用中，引數的值在主程式中發生變化，並且該過程也發生了變化。按引用傳遞的優點是它避免了與建立資料副本相關的大量處理和儲存，並允許將所需的更改傳遞迴主程式。

遞迴

Function Fvalue (Num: Integer) : Integer
If Num = 1 Then
    Set Fvalue = 0
Else
    If Num = 2 Then
        Set Fvalue = 1
    Else
        Set Fvalue = Fvalue(Num-2) + Fvalue
    End If
End If
End Function

遞迴演算法是指 **演算法在自身中呼叫自身**，直到滿足終止的 **基本情況**。程式會開啟多個“副本”，直到這些副本終止（結束）。一個常見的例子是階乘，它是小於或等於該值的全部正整數的乘積。例如，$5!=5\times 4\times 3\times 2\times 1=120.$

數學運算

運算子	符號	描述	示例
加法	+	這些值的總和。	$1+1=2$
減法	-	從另一個值中減去一個值。	$2-1=1$
乘法	*	兩個數字的重複加法。	$2\times 3=6$
除法	/	計算一個數字包含在另一個數字中的次數。	$20/4=5$
整數除法	DIV	返回一個數字包含在另一個數字中的次數。	$10DIV3=3$
取模	MOD	返回計算一個數字包含在另一個數字中的次數後的餘數。	$10MOD3=1$
取反	-	翻轉數字的符號。	$-(3)=-3$
指數	^	將第一個數字提升到第二個數字的冪。	$7^{2}=49$

第二種是選擇。這些語句根據給定的輸入和程式設計師設定的邏輯規則，決定輸出（或要執行的程式碼）。這是基本的 IF 語句——如果這是真的，那麼執行此操作，否則執行另一個操作。演算法的最後部分是迭代——其中程式碼旨在多次執行，直到滿足終止條件。例如，FOR 迴圈將重複一定次數，而 WHILE 迴圈將在某個條件為真時重複。

任何演算法的每個部分都依賴於變數來儲存資料。變數是計算機記憶體中一個命名的位置，它可以在程式執行時用於儲存資料，然後可以在以後被呼叫。這儲存在計算機的 RAM 中，並從 0 開始用記憶體地址進行標記。變數通常在程式中分配名稱，而儲存位置的具體細節留給翻譯器處理。除了它儲存的資訊之外，變數還有兩個主要屬性——作用域和生命週期。簡單來說，變數的作用域是指它在程式中可以訪問的地方，而變數的生命週期是指變數可以訪問的時間長度。區域性變數的作用域很小，生命週期有限，因為它只能在定義它的子程式中訪問，而全域性變數存在於程式的整個生命週期中，將具有較大的作用域和較長的生命週期。

驗證與確認

型別和示例

合適的檢查	無效資料的示例
存在性檢查	框中沒有內容
格式檢查，以確保資料項與先前確定的模式匹配，例如只接受 7 位數字。	12345X
長度檢查用於確保輸入資料的長度合理，例如在 8 到 13 之間。	12345678901234567890
型別檢查用於確保資料項屬於特定型別，例如所有條目必須為數字。	Micheal

驗證

驗證發生在**資料輸入時**。驗證檢查的目的是檢測錯誤並確保資料合理。一些常見的例子包括：存在檢查，其中輸入不能為 NULL（空），長度檢查以確保輸入滿足字元限制/要求（對密碼欄位強制執行），格式檢查以確保資料以特定方式輸入（電子郵件必須包含 @ 符號），或者字元檢查以檢查僅輸入接受的字元（不想在信用卡號中輸入文字）。

驗證

驗證發生在**資料輸入時**或當資料從一個地方傳輸到另一個地方時。驗證的目的是確保資料一致性（誤輸入）並確保資料沒有被破壞。有兩個常見的驗證方式：雙重輸入（通常用於密碼）和校對，例如，在訂購披薩之前呈現一個帶有總結的頁面。雙重輸入是指輸入兩個值並**比較**它們。如果它們匹配，則沒有輸入錯誤；如果它們不匹配，則存在輸入錯誤。

搜尋

搜尋演算法允許定位特定資料，例如特定使用者或其組許可權。

線性搜尋

從陣列的開頭開始，將 SearchValue 與陣列中的**每個連續項**進行比較。此過程一直持續到找到匹配項（找到 SearchValue）或到達陣列的**末尾**（SearchValue 不存在於陣列中）。

myArray(6) Is Integer
SearchValue Is Integer
Found Is Boolean
Set Found = False
    
Input SearchValue
    
For i = 0 to 6
    If SearchValue = myArray(i)then
        Set Found = True
        Output "SearchValue found at position ", i
    End If
End For

If Found = False
    Output "SearchValue not found."
End if

二分搜尋

首先，二分搜尋要求所有元素按升序排序。這種搜尋比線性搜尋好得多，因為如果發現大於 SearchValue 的元素，則可以終止搜尋，因為所有其他項都將大於 SearchValue。其工作原理如下：

1. 計算一箇中點，並將 SearchValue 與中間元素進行比較。
2. 如果這不是 SearchValue，則搜尋下半部分或上半部分，直到找到 SearchValue 或中間元素大於 SearchValue。

myArray(6) Is Integer
Start Is Integer
End Is Integer
Found Is Integer
Mid Is Integer

Set Start = 0
Set End = 6
Set Found = False

Input SearchValue

    Repeat
        Set Mid = (Start + End) DIV 2

        If SearchValue = myArray(Mid) Then
            Set Found = True
            Output "SearchValue found at position ", Mid
        End If

        If SearchValue > myArray(Mid) Then
            Set Start = Mid + 1
        End If

        If SearchValue < myArray(Mid) Then
            Set End = Mid – 1
        End If

    Until (Found = True) OR (End < Start)

If Found = False
    Output "SearchValue not found."
endif

排序

排序演算法允許將一組無序的資料元素進行組織，例如按升序/降序或按字母順序。

氣泡排序

在氣泡排序中，專案根據它們是否高於或低於列表中的下一項進行移動。這導致最大的項重複地“冒泡”到列表的頂部，這就是該演算法名稱的來源。

1. 對資料進行一次遍歷，將每個值與其後續值進行比較，並在必要時交換它們。
2. 重複此過程，直到資料按順序排列，並且不再進行交換。

Start Procedure SortMyArray
    n Is Integer
    temp Is Integer
    swapped Is Boolean

    set n = length(myArray) {returns the length of myArray}
    repeat
        set swapped = FALSE
            for i = 0 to (n – 1)
                if myArray(i) < myArray(i + 1) then
                temp = myArray(i + 1)
                myArray(i + 1) = myArray(i)
                myArray(i) = temp
                swapped = TRUE
                end if
            end for
   until (swapped = FALSE)

End Procedure

插入排序

1. 專案逐個複製到一個新的排序陣列中。
2. 每個新專案都插入到正確的位置。
3. 新陣列中的所有專案都向上移動一個位置。

快速排序

1. 選擇一個專案/樞紐（哪個專案並不重要）
2. 生成兩個新列表，分別包含較小的數字和較大的數字
3. 對新子列表重複以上步驟（遞迴地），直到排序完成

Declare subprocedure QuickSort (myArray is string, indexLow is integer, indexHi is integer)

Pivot is string
tmpSwap is string
tmpLow is integer
tmpHi is integer
tmpLow = indexLow
tmpHi =indexHi
pivot = myArray (int(indexLow + indexHi)/2))

while (tmpLow <= tmpHi)
    while (myArray(tmpLow) < pivot and tmpLow < indexHi)
        tmpLow = tmpLow + 1
    wend

    while (myArray(tmpHi) > pivot and tmpHi > indexLow)
        tmpHi = tmpHi – 1
    wend

    if (tmpLow <= tmpHi) then
        tmpSwap = myArray(tmpLow)
        myArray(tmpLow) = myArray(tmpHi)
        myArray(tmpHi) = tmpSwap
        tmpLow = tmpLow + 1
        tmpHi = tmpHi -1
    end if
wend

if (indexLow < tmpHi) then
    QuickSort (myArray , indexLow, tmpHi)
Elseif (indexHi > tmpLow) then
    QuickSort (my Array, tmpLow, indexHi)
end if

end sub

程式設計結構

順序

順序表示逐行執行指令，一次執行一條。下面是使用匯編語言編寫的程式碼片段，每行程式碼將依次執行以執行該程式碼片段。

LOAD 1,d1
LOAD 2,d2
XORR 1,2
STOR 1,d3
XORR 1,2

選擇和重複

選擇的目的是在滿足特定條件時執行程式碼，在本例中，如果 Num2> Biggest 為 True，則執行 Biggest = Num2。

重複（也稱為迴圈）的目的是重複執行程式碼，直到滿足某個條件，在本例中，直到 Num1 為整數為止。

Biggest Is Integer
Num1 Is Integer
Num2 Is Integer

Repeat
    Input Num1
Until (Num1 is an Integer)

Repeat
    Input Num2
Until (Num1 is an Integer)

Set Biggest = Num1

If Num2 > Biggest Then Biggest = Num2

Output Biggest

計數

使用一個**變數**（整數）來計算滿足某個條件的值。

請記住，計數總是從 0 開始，因此必須將變數的值**初始化**為 0。

異常值

異常值被查詢表視為終止訊號。

模組化程式設計

標準函式

標準函式是指由直譯器或編譯器提供的某些常用函式，例如平方根、隨機數生成器和在 Visual Basic 中看到的輸出訊息框等。包含這些標準函式的語言比沒有這些函式的語言要好得多，因為它們可以節省程式設計師的時間，因為他們不需要編寫那麼多程式碼。該函式在之前已經過測試，不太可能包含錯誤，並且它是由該領域的專家編寫的，因此將簡潔高效。

使用者定義子程式

與一個大型程式相比，使用者定義的子程式（如模組和函式）更容易編寫，使程式更易讀，易於單獨測試，並且可以由個人編寫並實施在大型程式中。它們也可能是以前編寫的，可以從另一個程式中複製，或者可能已經存在於特定問題中。

壓縮

壓縮檔案時，會使檔案變小（可能透過減少資料量）。壓縮檔案可以節省儲存空間，並在透過網路傳送檔案時加快傳輸速度。壓縮主要有兩種型別：有失真壓縮和無失真壓縮。

有失真壓縮和無失真壓縮

有失真壓縮（正如您可能從名稱中猜到的那樣）是指使檔案變小，但在過程中會丟失一些資訊。無失真壓縮是指使檔案變小，但不會丟失任何資訊。大多數情況下，無失真壓縮更可取，但有失真壓縮用於網站上的影像，尤其是當它們很小的時候，因為少量丟失的資訊（質量）不會有太大影響，但會加快頁面載入速度。

無失真壓縮的示例

當一個字元被重複多次時，會使用行程長度編碼，它可以在重複特定畫素顏色的影像中使用。它使用一個標誌字元來表示開始 ($)、重複的字母以及它重複的次數，因此 AAAAAAAAA 會變成 $A9。你明白了吧。

霍夫曼編碼是字典編碼的一個例子（一個包含常用字元的字典，每個字元都有自己的引用）。在英語中，一些字母的使用頻率遠高於其他字母，例如“A”比“Z”更常見。霍夫曼編碼透過為出現頻率更高的字母賦予更短的程式碼，為出現頻率更低的字母賦予更長的程式碼來工作，從而產生一個更小的壓縮檔案。

比較壓縮

您可能會被要求比較有失真壓縮和無失真壓縮，甚至在考試中比較給定的壓縮演算法。要記住的第一點是，有失真壓縮總是比無失真壓縮更好，因為可以更容易地丟棄更多的資料，因為質量會丟失。壓縮檔案和隨後解壓縮檔案需要一定的時間，這些分別稱為壓縮時間和解壓縮時間。為了計算壓縮演算法的效率，我們可以計算“壓縮比”，它是 $CompressionRatio=UncompressedSize/CompressedSize.$

測試

您必須考慮三種類型的測試資料，請參考下表（1-100 是允許的資料）。

測試	意義	示例
正常/有效	這是我們希望使用者輸入的資料型別，它在我們的允許值範圍內。	50
無效	此資料超出了我們接受的範圍，或者完全是不同的資料型別。	200 和“twenty”
邊界/極端	此資料位於我們接受值的邊緣。	1 或 100