演算法與程式語言

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

2、式(Program)一系列指令(instruction)或敘述(statement)的組合為了解決某些問題或為了完成某些任務(wù)而指揮電腦執(zhí)行一系列工作的處理程序與步驟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) 泛指電腦中可以執(zhí)行之所有程式軟體的分類軟體依其使用的性質(zhì)可區(qū)分為：系統(tǒng)軟體(S

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

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

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

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

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

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

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

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