演算法与程式语言

1、演算法與程式語言計算機概論演算法設計演算法(Algorithm)解決問題的方法以虛擬程式碼(Pseudo code)描述解題的步驟與方法演算法必須具備的五大條件：輸入、輸出、明確性、有限性和效率性。包括明確的輸出入資料和詳細且有限的執行步驟algorithm GCD input larger, smaller while smaller 0 do remainder = larger mod smaller larger = smaller smaller = remainder end while output largerend GCD示範題目：求兩整數之最大公約數(GCD)程式語言簡介程

2、式(Program)一系列指令(instruction)或敘述(statement)的組合為了解決某些問題或為了完成某些任務而指揮電腦執行一系列工作的處理程序與步驟Dim i%, j%, k%, M%, N%For i%=1 To 9 For j%=0 To 9 For k%=0 To 9 M% = i% * 100 + j% * 10 + k% N% = i% 3 + j% 3 + k% 3 If M% = N% Then Print M% Next k% Next j%Next i%電腦軟體(Software) 泛指電腦中可以執行之所有程式軟體的分類軟體依其使用的性質可區分為：系統軟體(S

3、ystem Software) - 維繫電腦正常運作的軟體，如作業系統(Operating System) MS-DOS, Windows, OS/2, UNIX, VMS。應用軟體(Application Software) - 針對某些特殊應用而設計的軟體，如文書處理(Word Processing)軟體 Microsoft Word, AmiPro。程式語言(Programming Language) 人與電腦溝通的語言人能寫得來，電腦能認得來、做得來。程式語言的演進第一代程式語言：機器語言(Machine Language)第二代程式語言：組合語言(Assembly Language)

4、第三代程式語言：高階語言(High Level Language)FORTRAN, COBOL, BASIC, PASCAL, C機器語言(Machine Language)由0與1等二進位數字所組成的語言。每一指令都是中央處理單元直接可以判讀的語言。機器語言(Machine Language)機器語言的指令是由運算碼(Operation Code)與運算元(Operand)合成。意謂各個指令基本上乃是“以運算元的資料作運算碼的動作”。組合語言(Assembly Language)將機器語言的運算碼改成簡單易懂的符號或文數字 1001 JMP 1111 HALT一台簡單的電腦將介紹的是虛擬的一

5、台架構簡單的電腦，雖然現實世界中不可能有這麼簡單的電腦存在，但是它的基本結構與真實的電腦類似，用它來解說電腦最深層的運作狀況，是非常能夠幫助我們得到基本的概念。以下先逐一說明它的架構（系統設定與元件內容），再以一段小程式的程式碼設計與執行過程解說中央處理單元一步步處理的程序。一台簡單的電腦電腦處理單位word執行一次處理程序運作的資料量（固定長度位元） 設定為16位元為了記錄上便利性，通常我們會將二進位制的位元值換成十六進位制表示法十六進位表示法每四位數的二進位制位元值（如”1010”）可對應轉換成一位數的十六進位制位元值（如”A”）。一個電腦處理單位(Word)二進位制十六位數（如” 100

6、1 0001 1010 0111”）可對應轉換成十六進位制四位數（如”91A7”） 。十六進位表示法資料格式一個電腦處理單位(Word)可能用作整數數值的儲存，設定其資料格式為第一個位元作為正負號，其餘15個位元是大小值（絕對值）部分。0000 0000 0000 0101 +51000 0000 0000 0101 -5指令格式一個電腦處理單位(Word)也可能用來代表指令，將16個位元區分成“運算碼”4個位元與“運算元”12個位元兩部分。運算碼(operation code)是電腦中央處理單元具有之各項功能指令的代碼，使用4個位元，代碼總數最多只有16個(24) 。運算元可以說是運算碼的參

7、數，依據個別指令的設定，這個參數可能是主記憶體的位址編號，以對應欲處理之資料，也可能直接對應為一個數值進行處理，有些運算碼可能不需要任何參數。（實際的電腦可能有些運算碼不只一個參數，即運算元可能多個！）主記憶體架構主記憶體是暫存程式及資料的地方，中央處理單元在執行過程中，會不斷地到主記憶體擷取資料或將資料存入主記憶體，每次都是存或取一個Word，主記憶體的儲存空間需要設定位址編號，以下稱記憶體位址 。搭配運算元大小為12個位元，主記憶體的位址編號即是以12個位元作設定，意即主記憶體最大容量是4096(212)。中央處理單元架構中央處理單元內部有三個元件：中央處理單元之元件累加器(Accumul

8、ator)擔任運算工作的元件，一個運算基本上需要兩個步驟完成：將運算元載入(Load)累加器與另一運算元執行運算（加、減、乘、除、數值比較）運算結果置於累加器（數值比較則改變狀態指示器之值）狀態指示器(Condition code register)表示累加器進行數值比較結果的狀態指令位址暫存器(Instruction address register)又稱程式計數器(Program counter)將擷取之下一個指令之記憶體位址中央處理單元架構運算碼的設定載入指令載入指令 load-accumulator instruction, LDA LDA 004 將記憶體位址004之內容載入累加器儲

9、存指令儲存指令 store-accumulator instruction, STA STA 004將累加器之內容儲存在記憶體位址004示範程式：求兩整數之最大公約數(GCD)流程圖演算法示範程式：求兩整數之最大公約數(GCD)演算法在主記憶體編排之程式與資料範例：求 18, 6 之最大公約數程式執行：範例：求 18, 6 之最大公約數程式執行：範例：求 18, 6 之最大公約數程式執行：高階語言(High-level Language)與人類日常生活用語相近，簡單易學、撰寫方便的電腦語言。高階語言必須先經過編譯器(Compiler)或釋譯器(Interpreter)加以翻譯成機械語言後，才能

10、被執行。高階語言(High-level Language)FORTRAN FORmula TRANslation，適用於解決數學、工程及科學上的問題。COBOL Common Business Oriented Language，適用於商業資料處理。BASIC Beginners All-purpose Symbolic Instruction Code，簡單、易學、易用的一般性多用途程式語言。高階語言(High-level Language)PASCAL 語法嚴謹，符合結構化程式設計的精神，並擴充了資料結構和資料型態的能力。C語言結構嚴密，可呼叫組合語言，並提供許多低階函數，可攜性高，執行速度快。C+ 物件導向式語言。編