低級程序設計語言與偽代碼

Pep/9

虛擬機是一種假想的機器，是為了包含我們想展示的真實計算機所具備的重要特性而設計。Pep9具有40條機器語言指令，內存單元由65536字節的存儲空間，字長為兩字節，有七個寄存器【eg：程序計數器（PC）、指令寄存器（IR）、累加器（A）】。

指令格式

三個字節，第一個為指令說明符，后兩個字節為操作數說明符。

第一個字節中，前四位為操作代碼，即表述這個操作是做什么。第五位為參與的寄存器（eg：A、B）；后三位為尋址模式，000（立即尋址）:操作數以數據的形式被利用；001（直接尋址）:操作數表示地址，運用地址內的數據。

一些指令：

• 1100 將操作數（字）載入寄存器
• 1101 將字節載入寄存器：立即尋址：看第二個字節的數據；直接尋址：看第一個字節表示的地址。
• 1110 將寄存器中的字存到操作數代表的地址中
• 1111 將寄存器中的字節存到地址中，前八位會被忽略。
• 0110 將操作數（或地址）加到寄存器中。
• 1000 從寄存器中減去操作數。

Pep/9輸入設備在地址FC15，輸出設備在地址FC16

匯編語言

助記碼 操作數，i（d）

其中i表示立即尋址，d表示直接尋址

匯編器指令（偽操作）：END、ASCII、WORD、BLOCK。

分支命令：DECI（讀入十進制數字，放進操作數位置）、DECO（寫操作數、寫操作數地址上的十進制數）、STRO（寫操作數位置上的字符串）、BR（轉到操作數位置）、BRLT（如果累加器小于零，轉到操作數位置）、BREQ（若累加器為0，轉到操作位置）、CPWA（比較操作數位置和累加器中存儲的字。）

匯編語言中的循環：先讀循環次數，然后再一個一個輸入累加器進行加法

偽代碼

變量、賦值、輸入/輸出、選擇、重復

變量：表示存儲值或從中提取值的指定位置

賦值：把值存入變量

重復（迭代、循環）：只要條件滿足，就重復執行一條或多條語句。

if-then選擇：條件滿足則執行縮進語句，不符合則跳過

if-then-else：條件滿足，執行then；不滿足，執行else。

偽代碼寫完之后需要翻譯成pep9的語句才能使用

比如說讀取輸入數據：.ASCII "Enter numberx00"

測試

即執行程序

代碼覆蓋測試法：用例確保每條語句都能被執行，又叫明箱測試法。

數據覆蓋測試法：用例確保包括允許使用的數據的邊界值，暗箱測試法

測試計劃實現要運行測試計劃中列出的所有測試用例，并記錄運行結果。

問題求解與算法設計

計算機問題求解包括四個階段：分析和說明階段、算法開發階段、實現階段、維護階段。

分析問題-列出主要任務-編寫其余部分-根據需要進行重組和改寫。

選擇算法

if

else if（到達第二個if的方式是不滿足第一個）

循環算法

技術控制循環

通過指定過程重復的次數，使用特殊的變量（循環控制變量）。初始化，測試，增量。

while循環被稱為前測試循環，永不終止的循環被稱為無限循環

事件控制循環

循環中重復的次數是有循環體自身內發生的事件控制循環。while 控制時，事件必須被初始化、測試、更新。選擇+控制可以做篩選。

平方根計算

數除以4作為guess初始值，然后設置epsilon為guess平方與原數值的差距，取guess和原數值的平均數。

需要進一步擴展的步驟叫抽象步驟，不需要擴展的叫具體步驟。

數組

項目在集合中的位置叫做索引，通過數組名[position]來訪問每一個數

記錄

記錄是異構項目的有名集合，通過名字單獨訪問其中的項目，異構集合中的項目不必為同種類型。

搜索算法

順序搜索

一次查找每一個元素并將其與我們所需要搜索的元素進行比較（像是有兩個結束條件的循環）。運用AND（所有表達式都為真時返回值才為TRUE）或OR（所有表達式都為假時返回值才為FALSE）found is false可以運用not簡化。

有序數組時，先用length確認項目數

二分檢索

在有序數列中查找項目的操作，取中間項對比，1/2、1/4……減少工作量

排序

選擇排序

缺陷：需要完整的兩個列表的空間，類似于看到最小的然后復制到最前面。

冒泡排序

對相鄰兩個進行比較，小的放上面，大的放下面。冒泡排序可以通過是否需要發生交換判斷是否為有序。

插入排序

每次插入的元素找到合適的位置，和原本該位置的項目比較大小，每次放入后位于相對位置。

遞歸算法

在某種程度中使用它自己，運用選擇語句來確定是否重復。

確定尺寸系數；如果問題涉及的是數值，尺寸系數可能是數值本身。問題涉及結構，尺寸系數可能就是結構的尺寸。

子程序

程序的多個部分使用同一個名稱，命名代碼出現的地方被稱為調用單元。

一種是只執行特定任務的命名代碼（語句），另一種不僅執行任務，還返回給調用單元一個值（表達式）。

遞歸階乘

尺寸系數=要計算階乘的數

基本情況：為1

一般情況：N項=Nx（N-1）項

遞歸二分檢索：以第一個數為界，小于第一個數的放左邊，大于的放右邊，然后交換第一個數和分界數的位置，于是分界數位于正確的位置。

重要思想們

• 信息隱蔽：對特定分層設計時，只考慮與之相關的細節
• 抽象
  • 數據抽象（把數據的邏輯視圖和實現分開）
  • 過程抽象（把動作的邏輯視圖和實現分離）
  • 控制抽象（把控制結構的邏輯視圖和實現分離）
• 事物命名（標識符）
• 測試