計(jì)算機(jī)科學(xué)導(dǎo)論實(shí)驗(yàn)指導(dǎo)書-609

1、計(jì)算機(jī)科學(xué)導(dǎo)論實(shí)驗(yàn)指導(dǎo)實(shí)驗(yàn)1 SimpSim模擬器環(huán)境及Visual C+編譯調(diào)試環(huán)境1實(shí)驗(yàn)2數(shù)據(jù)操作10實(shí)驗(yàn)3結(jié)構(gòu)化程序設(shè)計(jì)12實(shí)驗(yàn)4遞歸與迭代14實(shí)驗(yàn)5算法綜合練習(xí)16實(shí)驗(yàn)6算法復(fù)雜度分析*21實(shí)驗(yàn)7背包問題與啟發(fā)式算法*23實(shí)驗(yàn)1 SimpSim模擬器環(huán)境及Visual C+編譯調(diào)試環(huán)境【實(shí)驗(yàn)?zāi)康摹?了解自然語言到機(jī)器語言的翻譯過程2熟悉Simple Simulator模擬器環(huán)境，掌握使用Simple Simulator模擬程序的執(zhí)行。3掌握SimpSim的單步運(yùn)行方法，學(xué)會單步運(yùn)行時(shí)對存儲單元和各寄存器中值的進(jìn)行 觀察。4熟悉Visual C+編譯調(diào)試環(huán)境，掌握C語言源程序的建立、編輯

2、、修改、保存。5掌握C語言程序的編譯和程序調(diào)試。【實(shí)驗(yàn)準(zhǔn)備】(1) 自然語言到機(jī)器語言的翻譯過程任何計(jì)算機(jī)內(nèi)部都是用0和1的序列來表示的，這可以很容易地被汁算機(jī)理解，但人 們卻不容易理解，另一方而，無論什么時(shí)候，在用像Visual C+這樣高級語言編寫程序的 時(shí)候，我們使用了能被程序員所理解的一組指令或命令，但計(jì)算機(jī)卻不容易理解。為了在人 和機(jī)器之間搭建通信的橋梁，制立一個翻譯過程是很有必要的。因?yàn)槊颗_計(jì)算機(jī)只能理解它 自己的語言(機(jī)器語言)，所以最終必須將每個程序翻譯為用機(jī)器語言書寫的等價(jià)程序，這 樣計(jì)算機(jī)就能夠理解并執(zhí)行程序所指左的指令。執(zhí)行這個翻譯過程的汁算機(jī)程序叫做翻譯 器，如圖1所示

3、。翻譯器通常對指立的語言進(jìn)行工作。也就是說，C程序的翻譯器不能 翻譯Java語言程序，反之亦然。有兩種特龍類型的翻譯器用來執(zhí)行髙級語言的轉(zhuǎn)換過程： 編譯器和解釋器。圖1.1翻譯器的基本作用編譯器翻譯過程本身包含一系列對輸入語言的轉(zhuǎn)換。圖1.2顯示了編譯器的通用階段。雖然 對包含在每個階段的行為的具體討論超出了本書的范圍，但了解翻譯過程的一些方面，以及 如何與編寫的程序進(jìn)行聯(lián)系，有利于對計(jì)算機(jī)程序編譯調(diào)試過程的理解。在將程序遞交到任何翻譯器前，需要使用編輯器或文字處理程序來創(chuàng)建源程序。大部 分翻譯器需要文件擴(kuò)展名，將程序保存為特定的類型。例如C編譯器要求包含C程序的文 件以“.C”作為擴(kuò)展需。如

4、果提交給翻譯器的程序沒有這個程序沒有這個擴(kuò)展名，編譯器就 不會對它進(jìn)行翻譯。一旦創(chuàng)建了程序，它就被遞交給預(yù)處理程序。正如其名字所指明的一樣，該程序在“處 理器”或編譯器之前進(jìn)行工作。它可能是一個獨(dú)立于編譯器的程序，也可能是具有不同需稱 的相同的編譯器。預(yù)處理程序執(zhí)行這樣的任務(wù)，例如將一個或多個文件的內(nèi)容合并入程序中, 并在整個程序中用一個字符串取代另一個字符串。預(yù)處理程序掃描整個源代碼，尋找“預(yù)處 理指令二這些指令以特左的字符或字符組合開始。例如，C編譯器當(dāng)遇到# include時(shí)就將 文件并入。同樣的編譯器在遇到像#define這樣的常量左義時(shí)就執(zhí)行字符串替換操作。圖1.2編譯過程以及連接和

5、裝載當(dāng)預(yù)處理程序完成英任務(wù)后，編譯器開始執(zhí)行。編譯器的第一個階段（詞法分析階段） 檢查源程序中每個單獨(dú)的字符并將它們組合成叫著token或Lexem的邏輯單元。例如，當(dāng) C編譯器讀取下而的一系列字符時(shí)If （ab）a+;編譯器讀取到序列后緊跟著在遇到左圓括號后就是一個叫著“if的邏借單元，這個 “if”和后而的每個字符都被識別并翻譯為預(yù)左義的數(shù)字代碼集。這一階段的邏輯允許編譯 器識別C程序中每個可能的有效序列。從程序員的角度來看，這一階段是很重要的，因?yàn)?在這里編譯器會產(chǎn)生類似“unidentified characters/ （不可識別的字符）這樣的錯誤。例如， 考慮在C程序中，程序員輸入類

6、似，這樣不符合字母表的字符。當(dāng)編譯器“看到”這 個字符時(shí)，會產(chǎn)生一個錯誤，通知程序員已經(jīng)發(fā)現(xiàn)了一個不可識別的符號。這種類型的錯誤 屬于“fatal errors ” （致命的錯誤），因?yàn)樵跈z測到這樣的錯誤后編譯器就停止處理程序 并退出。在這一階段編譯器產(chǎn)生的苴他錯誤還有：“program too big*, unexpected end of file”。后一個錯誤通常是由于多行注釋語句沒有結(jié)朿。編譯器的第二階段由語法分析器來執(zhí)行，從程序員的角度來看也是很有意義的，因?yàn)樵?這時(shí)編譯器要尋找C代碼的任何語法錯誤?？梢园堰@一階段看作是英文的語法檢查功能。 例如，假泄程序員想要輸入賦值語句a=b：但

7、是卻輸入成了 a+b：語法分析的內(nèi)置邏輯就 會把這看作是“無效表達(dá)式”并產(chǎn)生錯誤。在這一階段遇到的其他錯誤還有“missing;缺 少分號） *Unmatched number of parentlessM （圓括號數(shù)不匹配）,“missing funcution prototype M （沒有函數(shù)原型等）。編譯器的語義分析階段，作為一個單獨(dú)的階段顯示在圖1.2中，該階段有時(shí)和語法分析 階段結(jié)合在一起。在這一階段編譯器鑒別語句，看是否雖然語法上正確，但卻在語言中沒有 意義。例如，若a是一個布爾類型的變量，則賦值語句“a=a+2”，在語法上說是正確的， 而在語義上是沒有意義的。代碼產(chǎn)生器和代碼優(yōu)

8、化器將最終翻譯的程序成為響應(yīng)的機(jī)器語言。根據(jù)編譯環(huán)境中缺 省的或已設(shè)置的選項(xiàng)，可以在大小方而或速度方面對生成的代碼進(jìn)行優(yōu)化。大部分編譯器喜 歡提髙速度勝于提高縮短代碼。但是，對于編譯器來說試圖去尋找這兩個不兼容選項(xiàng)之間的 平衡很尋常。編譯器最后的階段是目標(biāo)文件。該文件具有與源文件相同的名字，但擴(kuò)展劃是.obj”。 這個目標(biāo)文件通常需要涉及駐留在系統(tǒng)中的程序庫。就這點(diǎn)而言，程序并沒有有做好運(yùn)行的 準(zhǔn)備，因?yàn)樗€有缺少的部分。換句話說，目標(biāo)文件“知道”仍然需要那些部分但不知逍在 那里可以找到它們。解決這個問題是另一個系統(tǒng)工具的任務(wù)。這個工具叫做連接程序，它找 出這些缺少的部分并將其放在合適的地址處

9、。如果連接程序找不到相關(guān)的程序，就會產(chǎn)生錯 誤，通知用戶并將這一個錯誤看作是致命的錯誤，于是中止連接過程。如果連接過程成功了， 連接程序輸出一個與源文件具有同樣名字的文件，但擴(kuò)展名是cxc”。這個文件叫做可執(zhí) 行鏡象或執(zhí)行文件。執(zhí)行程序時(shí)程序及其所需要駐留在內(nèi)存中，這是一個叫做裝載程序的另一個系統(tǒng)工具 的任務(wù)，它在內(nèi)存中尋找一個區(qū)域并把程序裝進(jìn)來。通常把這個過程稱為“裝載”可執(zhí)行鏡 像到內(nèi)存中。最后，裝載程序給CPU發(fā)一個信號，于是程序開始執(zhí)行。當(dāng)程序在運(yùn)行時(shí)，可能會出項(xiàng)“run time（運(yùn)行時(shí)）錯誤。這是最難發(fā)現(xiàn)的錯誤，因?yàn)橐?般來說，這是程序邏輯中的錯誤。這種類型中最通常的錯誤時(shí)訪問數(shù)組

10、的地址超過了數(shù)組的 最后一個地址，或者除數(shù)是0,根據(jù)編譯器所提供的支持不同，這些錯誤可能很容易發(fā)現(xiàn), 也可能很難發(fā)現(xiàn)。在程序編譯、連接或運(yùn)行中出現(xiàn)錯誤時(shí)，程序員應(yīng)該糾正特泄的錯誤所造成的問題。 在計(jì)算機(jī)術(shù)語中，我們把這個過程稱為調(diào)試。一旦程序員已經(jīng)找到了錯誤所在，就需要在編 譯器中修改源程序，并重新開始編譯過程。解釋器除了編譯器，還有叫做解釋器的翻譯程序。從操作的角度來看，它們之間的主要不同 是編譯器在程序執(zhí)行前翻譯整個程序。但列一方而，解釋器每翻譯一條程序語句就執(zhí)行一條 語句。至于考慮這兩個翻譯器執(zhí)行的內(nèi)部處理過程，它們的任務(wù)很相似。解釋器相對于翻譯 器的優(yōu)點(diǎn)是由于編譯程序只被翻譯一次，所以

11、編譯的程序運(yùn)行速度快。為了描述這兩個程序 的不同，考慮假想語言編寫的循環(huán)：While （aini r aLor|tti RegistersPC IR冷 Qpcn P.O R102 (MR2m;R33R403R503R603R703R803R903RA03RB0RC3RD03REOTRFm.c .0.BMain Memory.567.0 1D ci 妙.0303OJ03OJOJ030303030303030J030388om0303sOJ8o038mOJ0303 0303OD0303ODODOJOD030303(rlol0309 o o o o OOOOODOOOOOO o o o.u oooo

12、oooooon-o 丄ri厶一宀il十 丨。厶_ DDOO OODDDDDDOOOD o o o o o o oo o o o o on- OO s o o o OOOOODOOOOOO o o o o oooooooooooo 120 0 0 oooooooooooo A o o Q o o o o o o o Q Q o o o 2 000 000000000000 3000000000000 000 1 o o o oooooooooooo o o Q fl OOOOOOOQOOOOAlmcocommgmcommmcocomm Hmcocommcococococomcom m Msmms

13、ssss&8 m ro m roI1O88 8888888IO28IQJSS8 (U1OB 如405oe07o8393MB0CDDOE0FOSZ,O1st ore P2Z(A2ICO “00 halt0106OC:00,00invalidK:oozooinvalid r m、 AAddexz 161 Mocilisd 卜卅匕 d圖1.3實(shí)驗(yàn)結(jié)果（5）單擊Clear.彈岀如圖1.4的對話框，清空所有數(shù)據(jù)。圖1.4清空數(shù)據(jù)（6）單擊Open,打開剛剛保存的test.prg文件。得到圖1.2的界而。（7）單擊Step,程序單步運(yùn)行，觀察每一次PCJR的變化及RO. RK R2、A2的值。2. Vis

14、ual C卄編譯調(diào)試環(huán)境（1）進(jìn)入Visual C+壞境后，選擇File-New菜單彈出New對話框，在Project頁面中 選擇 Win32 Console Application 項(xiàng)，在 Location 處選擇工程保存路徑 E:VCProject,在 Project name中填入工程需HelloWorld, Location處的路徑會自動添加為E:VCProjectHelloWorld 如圖1.5,單擊0K繼續(xù)。圖1.5創(chuàng)建新控制臺工程(2) 在出現(xiàn)如圖1.6所示的Win32 Console Application Step 1 of 1對話框后，單擊 Finish按鈕岀現(xiàn)如圖1.7的

15、New Project Information對話框，單擊Ok按鈕完成工程創(chuàng)建。圖 1.6 Win32 Console Application Step 1 of 1 對話框圖 1.7 New Project Information 對話框(3) 選擇File-New菜單，在New對話框的File頁選擇C+ Source File,在File編 輯框中輸入文件名hello.6如圖1.8所示。He圖1.8在工程中加入hello.c源程序(4)單擊0K按鈕，開始對源文件進(jìn)行編寫，輸入如下代碼。ttinclude i,stdio .hvoid main()Build菜單項(xiàng)或按F7鍵進(jìn)行編譯，系統(tǒng)將會

16、在Output窗口給出所有岀錯 和警告信息。當(dāng)調(diào)試無錯誤后，選擇Build-Execute菜單項(xiàng)，或Ctrl+F5執(zhí)行程序，得到如 圖1.9的DOS窗口圖1.9 Hello World實(shí)驗(yàn)結(jié)果實(shí)驗(yàn)2數(shù)據(jù)操作【實(shí)驗(yàn)?zāi)康摹坷斫庵噶钕到y(tǒng)的組成掌握機(jī)器指令的格式理解程序的執(zhí)行過程【實(shí)驗(yàn)準(zhǔn)備】（1）認(rèn)真閱讀教材3.7.2小節(jié)的內(nèi)容，回答以下問題： 一條機(jī)器指令由幾部分組成，分別代表什么含義？ 存儲器中的數(shù)據(jù)是否能直接進(jìn)行運(yùn)算，如不能該如何操作？ CPU中的程序寄存器和指令寄存器在程序的執(zhí)行過程中分別起什么作用？ 請簡述程序的執(zhí)行過程。（2）熟悉教材第70頁表3.1的內(nèi)容（機(jī)器指令集），對照指令集回答以下

17、問題： 表3.1中的第二條指令和第三條指令都用來“存放”數(shù)據(jù)，它們之間的區(qū)別是什么？ 確窪能夠讀懂此表，試解釋23B2、4013、5356所表示的意思?！緦?shí)驗(yàn)內(nèi)容】（1）驗(yàn)證教材課后習(xí)題3.21,要求單步運(yùn)行，記錄每一步寄存器或存儲器值的變化（2）設(shè)計(jì)機(jī)器代碼，完成以下功能，并在SimpSim上進(jìn)行驗(yàn)證：機(jī)器代碼的首地址從B0開始，單元地址為2F的值為03,寄存器R2的值為05,將 2F中的值與R2中的值進(jìn)行OR運(yùn)算，結(jié)果存入4F中?！緦?shí)驗(yàn)步驟】(1)打開Simpsim.exe,將習(xí)題3.21中的機(jī)器碼及初值輸入模擬器中，如圖2.1Sisolatorile d)t fiiui Help.0 .

18、1Main Memory3 .Q . .5 “6 . 7Registersoooooooooo012 34 56?89550:18030:13030:130311000000000000000000L68COCO8COCO8COCOB1o:l303o:l0D0Doj0D0D00000000000000000000CO8COCO8COCO10COCOmcoco 000000 0303們 rococo 000000 030303 Icoco!co ODO ABCC03C0000000030D0JCOCOLO000000100303Locolco o o o def03J03003030J0303O

19、T0303J03038.9.A.B,.c.D.E.FOD00D3OD00w00000000OJ0000030000OD00ro0000JOD0000ao03OD000300000000OJ0000OJ0000OD0003OD000OD0000aoM00GOm00000000030000OJ0000OD00M0000w000000aoM0000M00000000OT0000OT0000OD00OTOD0003OD000000M0000M0000OD00ro00aoOD000000D3000003OD0000000000(B0000RF卜 fiun |tin曲皿ROcoR1COR2coR3coR4

20、coR5coR6coR?coRScoR9coRAcoRBcoRCcoRDcoREcoD ripen.D 0I 00：10ZOEload105z oz：1105Load P.lr 105104：BlOOjnpxq R12R0,DO06：COzOOnalt08：OOzOOinvalidox：叫00LnuAlid冷Sekcted 7建 轡 DiosxnAdd彩：7Modfed圖2.1習(xí)題6（2）不斷單擊Step,觀察PC、IR中值的變化（3）單擊Run,觀察模擬器的運(yùn)行。（4）單擊Break終止運(yùn)行，解釋程序不能終止的原因。（5）單擊Clear.淸空所有存儲單元和寄存器的值（6）填寫如下機(jī)器碼中【代

21、碼1】部分，并輸入到SimpSim中112F【代碼1】334FC000（7）將PC的值設(shè)為B0,將2F的值設(shè)為03,將R2的值設(shè)為05,如圖2.2fileg KelpRegistersROFC I BO-D|R1IR |C(COR2R3R4IS Elrw-R5 zKbR7R8R9|R4zIRBRCRDGORED Cler .RFcocoiilcococoCOCOCOCO8 8COcococoMain Memory.0 “2 .3 7 .5 .6 .7 .8 .9 A .8 C D .E .FOOOOOOOOOOODODOOOOOOODOOOOODOOOD邏l亦逐|Dimmo o o o -u

22、o o o o o o o0000000000000000000000000000000000000000000000000000cocorocococoC0C08 8 8 8 3cococoOOOOOOOOOOODODOOOOOOODOOOOODOOODo o o o .u oo 0 0 0 0 0000000ODOOOOODODOOm 8888COOOOOOOOOOOODOOOOOOOOOOODmcoscoLOm0D1D2O3D4O50rom raw WK w OOOOODOOODIHIOD com 8 8C04FC0000000000039000000000000co0000ODOD00

23、2FODCO8CO8CO11CO6D7D8O9OM8O03ODOOODcococoODOOOD000000ODDnV o oIcom 8 )00 D DEF29:0000invalidAZA：0000invalKlZCt0000Invftlidex：0003invalid30:0000invalid32:f 0000r* oanvolLd 7Add 倫谿 182;Sekcled 102圖2.2（8） 單步運(yùn)行程序，直到程序結(jié)束，記錄PC、IR、各寄存器值的變化。實(shí)驗(yàn)3結(jié)構(gòu)化程序設(shè)計(jì)【實(shí)驗(yàn)?zāi)康摹渴煜ろ樞?、選擇、循環(huán)3種程序結(jié)構(gòu)掌握C語言編寫選擇、循環(huán)語句的方法【實(shí)驗(yàn)準(zhǔn)備】（1 認(rèn)真閱讀教材2.4

24、小節(jié)、4.2小節(jié)的內(nèi)容，了解算法的有關(guān)內(nèi)容（2）將圖3所示的流程圖片段轉(zhuǎn)換為C語言在屏幕上分別打印 出a和b的值在屏幕上打印圖31(3) 根據(jù)下而的C語言程序，畫出其流程圖# include stdio.hmain()int sum = 0;int i = 0;while(i10)sum = sum+i;i卄；【實(shí)驗(yàn)內(nèi)容】編寫程序，求數(shù)組a=5,348566中最大的數(shù)？【實(shí)驗(yàn)步驟】（1）新建 Win32 Console Application 工程，工程名為 Exp3_l（2）在Exp3工程中，新建cxp3c（3）填寫【代碼1】【代碼2】后，編譯.運(yùn)行并調(diào)試源程序#includc Hstdio

25、.hM main（）int a =5,34,&56,6;int i=O;int max=O;while（【代碼1】）if（【代碼2】） max = ai;i+；primf（”數(shù)組a5中最大的數(shù)是%dnmax）;16實(shí)驗(yàn)4遞歸與迭代【實(shí)驗(yàn)?zāi)康摹?加深理解遞歸及迭代的槪念 掌握用C語言編寫遞歸及迭代程序的方法 能夠區(qū)別遞歸和迭代之間的差別【實(shí)驗(yàn)準(zhǔn)備】(1) 認(rèn)真閱讀教材5.6小肖的內(nèi)容，理解遞歸和迭代的概念，回答以下問題： 遞歸和迭代方法，哪一個的時(shí)間復(fù)雜度高？ 遞歸和迭代方法是否可以相互轉(zhuǎn)換，轉(zhuǎn)換的意義何在？(2) 斐波那契數(shù)列是一個描述了動物繁殖數(shù)量、植物花序變化等自然規(guī)律的經(jīng)典數(shù)學(xué)問 題。認(rèn)

26、真閱讀教材423小節(jié)斐波那契問題及5.6小節(jié)，思考如何用遞歸和迭代來 求解斐波那契數(shù)列?！緦?shí)驗(yàn)內(nèi)容】(1) 用遞歸的方法求解斐波那契數(shù)列(2) 用迭代的方法求解斐波那契數(shù)列【實(shí)驗(yàn)步驟】(1) 新建 Win32 Console Application 工程，工程名為 Exp4_l(2) 在Exp3_l工程中，新建cxp4.c(3) 填寫【代碼1】后，編譯、運(yùn)行并調(diào)試源程序include Mstdio.hHunsigned long F(int n)if(n=l)return n;else【代碼1】；main()int n;unsigned long sum;printfCn=);scanf(H%

27、du.&n);sum = F(n);printf(Hwhen n=%d, sum=%dnn,sum);(4) 新建 Win32 Console Application 工程，工程乞?yàn)?Exp4_2(5) 在Exp4_2工程中，新建cxp4_2c(6) 填寫【代碼2】【代碼3】【代碼4】后，編譯.運(yùn)行并調(diào)試源程序include Hstdio.hHunsigned long F(int n)int i;unsigned long a = 0. b = 1, c;if (n = 1)【代碼2】elsefor(【代碼3】)c = a + b;a = b; 【代碼4】return c;main()(in

28、t n;unsigned long sum:printf(,n=H); scanf(N%d&n); sum = F(n);printf(Hwhen n=%d, sum=%dn,n,sum);實(shí)驗(yàn)5 算法綜合練習(xí)【實(shí)驗(yàn)?zāi)康摹渴煜そY(jié)構(gòu)化程序設(shè)計(jì)在算法中的應(yīng)用理解二分查找法的思想【實(shí)驗(yàn)準(zhǔn)備】（1）復(fù)習(xí)結(jié)構(gòu)化程序設(shè)計(jì)（2）復(fù)習(xí)遞歸的思想和編寫方法（3）掌握二分查找法二分査找法又稱折半査找法，是一種效率較高的在有序數(shù)組中査找特左元素的方 法。二分査找法的查找方法是：設(shè)有序的為數(shù)組aO.n-l（這里我們假設(shè)為遞增，遞 減的情況與此類似），要査詢的元素為x,令m = L（n-l）/2，將x與數(shù)組中間的數(shù)am

29、 進(jìn)行比較，若x=am,則査找成功；若xam,則只需在數(shù)組的后半段（即區(qū)間m+l,nl 中）用同樣的方法查找x。當(dāng)相等時(shí)，則查找成功；當(dāng)不相等時(shí)，則把下一次査找的區(qū) 間劃分成兩半，根據(jù)大于和小于的不同情況在不同的區(qū)間查找。知道出現(xiàn)區(qū)間長度為1 的情況時(shí)，算法終止。例1已知如下11個元素的數(shù)組：a0.nl=4,5,8,10,13,17,20,40,43,48,50,現(xiàn)在要查找元素 10 和 45。假設(shè)指針low和high分別指示待查元素所在范圉的下界和上界，指針mid指示區(qū) 間的中間位置，即mid = L （low+high）/2。在此例中,low和high的初值分別為1和 11。下面給出x=1

30、0的查找過程：4 5 8 10 1317 20 40 43 48 50tttlowmidhigh首先amid與査詢值10進(jìn)行比較，此時(shí)amid=17, amidx,說明待査元素若存在 一定在amid的左邊，于是縮小范圍，將high指到mid-1的位置，重新計(jì)算中間位置，此 時(shí)，amid=8o4 5 810 13 17 20 40 43 48 50tt tlow midhigh將amid與查詢值10進(jìn)行比較，an】idx,說明待查元素若存在一泄在amid的右 邊，于是縮小范圍,將low指到mid+1的位置，重新計(jì)算中間位置，此時(shí)amid=104 5 8 10 1317 20 40 43 48 5

31、0low hightmid將amid與查詢值10進(jìn)行比較，結(jié)果相等，查找成功。再看x=45的査找過程：4 5 810 1317 20 40 43 48 50tttlowmidhigh首先amid與查詢值45進(jìn)行比較，此時(shí)an】id=17, amidx，說明待查元素若存在一 定在afmid的右邊，于是縮小范國，將low指到mid+1的位置，重新汁算中間位置，此時(shí), amid=43o4 5 8101317 20 40 43 48 50t ttlowmidhigh再次將amid與查詢值45進(jìn)行比較，amidx,說明待査元素若存在一左在amid的左邊，于是縮小范I丙將high指 到mid-1的位宜，此

32、時(shí)因?yàn)橄陆鏻ov上界high,則說明表中沒有元素等于45,查找不成功。4 5 810 13 17 20 40 43 48 50high low【實(shí)驗(yàn)內(nèi)容】編寫二分査找的C語言程序并進(jìn)行調(diào)試運(yùn)行【實(shí)驗(yàn)步驟】(1) 新建 Win32 Console Application 工程，工程名為 Exp5_l(2) 在Exp5工程中，新建cxp5c(3) 填寫【代碼1】【代碼2】后，編譯、運(yùn)行并調(diào)試源程序include Hstdio.hM#include 兀tring.hint BSearch(int xjnt n)int lowjiigh.mid:low = 0;high = n-1:whi

33、le(low=high)mid = (low+high)/2;if(amid=x)return mid;else if【代碼1 )low = mid+1:else【代碼2】；return -1;main()int a=4,5,8,103,17,20.40.43,48.50;int x=40;int bn;printf(請輸入要査詢的數(shù)字.x=“);scanf(”cf,&x);bn = BSearch(a,x J1);if(bn=-l)printf(N%d在數(shù)組a中不存在!nx);elseprintf(%d為數(shù)組a的第d個元素n”,x,bn);(4) 輸入不同的數(shù)，單步運(yùn)行，觀察low、high

34、、mid值如何變化。.11111! 2! 3! 4!試用C語言求解c的近似值。#include Hstdio.hHint Factor(int N) / 求解 N!if(N=l)return 1;elsereturn N*Factor(N-l );double f(int n) / 求解 e= 1 + 1/1 !+l/2!+. + l/n!int i;double x;x=1.0;for(i=l;i=n;i+)x= x+1.0/Factor(i);return(x);int main(void)int n;double e;printf(Hplease enter n:M); scanf(H%

35、d&n);e=f(n);printf(HThe value of e is about:%fe);例3若氐N為兩個整數(shù)，試用C語言實(shí)現(xiàn)求乩N的最大公因子。 include int Gcd(int max, int min) /*求 max 與 min 最大公因數(shù)*/int temp;if(max 認(rèn)真閱讀教材2.3.2小節(jié)、2.3.3小節(jié)，了解算法中的難解性問題，明確用遞歸方法 求解梵天塔問題屬于哪類問題。(2)復(fù)習(xí)遞歸的求解思想【實(shí)驗(yàn)內(nèi)容】(1) 用遞歸的方法，編寫C程序，求解梵天塔問題(2) 通過運(yùn)行程序，直觀上理解算法的時(shí)間復(fù)雜性【實(shí)驗(yàn)步驟】(1) 新建 Win32 Console Ap

36、plication 工程，工程名為 Exp6_l(2) 在Exp6_l工程中，新建exp6_l.c(3) 填寫【代碼1】【代碼2】后，編譯、運(yùn)行并調(diào)試源程序#includc ustdio.hM#includc 吐imc.h”void move(char x,char y)primf(%cn”,x,y);void hanoi(int nxhar onexhar two,char three)/*將n個盤從one座借助two座，移到three座*/if(n=l)【代碼1】;elsehanoi(n-1 ,one,three,two);move(one,three);【代碼2】main()int n;

37、clockj start.finish;double time:printf(Hinput the number of diskes:”)；scanf(H%d&n);printf(HThe step to moving %3d diskes:n,n);start = clock();hanoi(n；A,/B,；C,);finish = clock();time = (doub!e)(finish-start)/CLOCKS_PER_SEC;printfCMoving Finished!】”)；printf(HThe program is cost %f seconds】”,time);(4)

38、有文曲星的同學(xué)可以試著根據(jù)程序給出的結(jié)果，看看效果如何(5) 記錄n=5, n=10, n=15, n=20的運(yùn)行時(shí)間,他們是線性增長的嗎？30實(shí)驗(yàn)7背包問題與啟發(fā)式算法*【實(shí)驗(yàn)?zāi)康摹苛私馐裁词菃l(fā)式算法；了解貪婪算法求解背包問題的不同準(zhǔn)則；【實(shí)驗(yàn)準(zhǔn)備】（1）認(rèn)真閱讀教材23.7小節(jié)的內(nèi)容，理解什么是背包問題：（2）認(rèn)真閱讀教材2.3.7小節(jié)的內(nèi)容，理解什么是貪婪算法：（3）認(rèn)貞閱讀教材2.3.7小節(jié)的內(nèi)容，理解用貪婪算法求解背包問題的三種準(zhǔn)則：【實(shí)驗(yàn)內(nèi)容】給左n種物品和一個背包，物品i的重量為W“英價(jià)值背包的重量容量為C, 要求在重量容星的限制下，盡可能使裝入的物品總價(jià)最大，這就是背包問題。

39、背包問題是一 個典型的NP復(fù)雜性問題，也是一個在算法設(shè)讓與分析”教學(xué)中，一般都要提到的一個典 型問題。為便于討論，本試驗(yàn)所指的是一類物品不可分割的背包問題，即0/1背包問題，在 這類問題中，物品只有裝入和不裝入兩種情況。貪婪算法是一種傳統(tǒng)的啟發(fā)式算法，它采用逐步構(gòu)造最優(yōu)解的方法，即在算法的每個階 段，都作出在當(dāng)時(shí)看上去最好的決策，以獲得最大的“好處S換言之，就是在每一個決策 過程中都要盡可能的“貪S 直到算法中的某一步不能繼續(xù)前進(jìn)時(shí)，算法才停止。在算法的過程中，“貪”的決策一旦作出，就不可再更改，作出“貪”的決策的依據(jù)稱 為貪婪準(zhǔn)則。用貪婪算法解決背包問題，有以下3種常用的貪婪準(zhǔn)則（1）每次都

40、選擇價(jià)值最大的物品裝包：（2）每次都選擇重量最小的物品裝包。（3）每次都選擇V: /Wx值（價(jià)值密度）最大的物品裝 請利用C語言實(shí)現(xiàn)上述三種貪婪準(zhǔn)則求解背包問題?！緦?shí)驗(yàn)步驟】1、每次都選擇價(jià)值最大的物品裝包（1）新建 Win32 Console Application 工程，工程名為 Exp7_l（2）在Exp6_l工程中，新建cxp7.c（3）填寫【代碼1】后，編譯、運(yùn)行并調(diào)試源程序#includc #dcfine MAX 100typcdcf stnictffloat w; /*物體的重量*/float v; /*物體的價(jià)值勺 Object;void sort( Object aJJnt

41、n) /*按照物體的價(jià)值v的降序的排列物體旬 int i,j;Object temp;for(i=0;in;i+)for(j=n-l;ijy-)if(aj-l.vaj.v)temp=aj;aUJ=ai；ai=temp;float Geedy_knapsack(Object a,int x(,float M Jnt n) int i;float m=M.value=0;for(i=0;in;i+)xi=O;sort(a.n);primf(放入背包中物體的價(jià)值分別是:n);for(i=0;in;i+)if(ai.w=m)printf(,%fnai.v);x(i=l；m=m-ai.w;else break;for(i=0;in;i+)value=value+(ai.v*xi);return value;)niain()int n,i,xMAXJ;Object aMAX;float M;/背包的總重量；float SumValue; /背包的總價(jià)值： printf(輸入背包的總重量：n)； scanf(,r%f&M);printf(輸入物體的個數(shù)：n); s