程序設(shè)計(jì)與算法問(wèn)題求解概要

會(huì)計(jì)學(xué)1程序設(shè)計(jì)與算法問(wèn)題求解概要程序的基本組成：輸入、處理與輸出計(jì)算機(jī)解題示例程序設(shè)計(jì)的一般步驟2.1利用計(jì)算機(jī)解題，首先需要確定得到什么樣的“輸出”結(jié)果；其次是確定為了成功地獲得相應(yīng)的結(jié)果，需要提供的數(shù)據(jù)，或者稱為“輸入”；最后，就是需要確定如何“處理”輸入的數(shù)據(jù)，才能獲得相應(yīng)的“輸出”結(jié)果。第1頁(yè)/共21頁(yè)計(jì)算機(jī)解題示例 例如，需要利用計(jì)算機(jī)求一個(gè)三角形的面積首先，可以確定程序的輸出就是一個(gè)三角形的面積值。并確定面積單位。接著，要確定求三角形面積所需輸入的數(shù)據(jù)。已知三邊長(zhǎng)度已知相鄰兩邊長(zhǎng)度以及相鄰邊的夾角以上兩種方法選其一，確定數(shù)據(jù)的輸入類型以及單位2.1第2頁(yè)/共21頁(yè)當(dāng)a+b>c且a+c>b且b+c>a時(shí)，三角形存在，其面積式中：

p=(a+b+c)/2已知三角形三個(gè)邊的長(zhǎng)度，設(shè)計(jì)求此三角形面積的程序?qū)嵗绦虼a2.1第3頁(yè)/共21頁(yè)計(jì)算機(jī)的處理步驟可設(shè)a=3cm,b=4cm,c=5cm輸入a、b、c的值，計(jì)算p=(3+4+5)/2=6cm得到計(jì)算機(jī)解題過(guò)程圖示已知三角形三個(gè)邊的長(zhǎng)度，設(shè)計(jì)求此三角形面積2.1Input(輸入)Output(輸出)Processing(處理)第4頁(yè)/共21頁(yè)程序設(shè)計(jì)的一般步驟1.分析：?jiǎn)栴}定義2.設(shè)計(jì)：計(jì)劃解題3.選擇與創(chuàng)建界面：選擇和確定界面對(duì)象4.編碼：用程序設(shè)計(jì)語(yǔ)言描述算法5.測(cè)試與調(diào)試：查找并排除程序中的任何錯(cuò)誤6.完成文檔：整理和阻止描述程序的所有資料2.1第5頁(yè)/共21頁(yè)算法與編程工具

被包含在窗體或標(biāo)準(zhǔn)模塊中的一個(gè)個(gè)過(guò)程有機(jī)地組合在一起，就構(gòu)成一個(gè)完整的應(yīng)用程序。 在設(shè)計(jì)程序前，根據(jù)實(shí)際問(wèn)題的特點(diǎn)和需求，同時(shí)考慮到計(jì)算機(jī)的工作特性，確定解決該問(wèn)題所需要的方法和步驟稱為“算法設(shè)計(jì)”。

算法的概念算法示例算法的特征算法的描述基本算法結(jié)構(gòu)2.2第6頁(yè)/共21頁(yè)算法的概念廣義而言，算法就是解決某個(gè)問(wèn)題或處理某件事的方法和步驟。狹義而言，算法是專指用計(jì)算機(jī)解決某一問(wèn)題的方法和步驟。計(jì)算機(jī)算法可以分為兩大類：一類是數(shù)值計(jì)算算法；另一類是非數(shù)值計(jì)算算法。研究解決各種特定類型問(wèn)題的算法已成為一個(gè)稱為“計(jì)算方法”的專門學(xué)科。對(duì)于同一問(wèn)題的求解，往往可以設(shè)計(jì)出多種不同的算法。一般而言，評(píng)價(jià)一個(gè)算法的好壞優(yōu)劣，主要看算法是否正確、運(yùn)行的效率及占用系統(tǒng)資源的多少等。第7頁(yè)/共21頁(yè)算法示例【例2-1】算法1【例2-2】算法2第8頁(yè)/共21頁(yè)算法1求兩個(gè)自然數(shù)的最大公約數(shù)的算法

S1.輸入兩個(gè)自然數(shù)M、N；S2.求M除以N的余數(shù)R；S3.使M=N，即用N代換M；S4.使N=R，即用R代換N；S5.若R≠0，則重復(fù)執(zhí)行S2、S3、S4（循環(huán)），否則轉(zhuǎn)S6；S6.輸出M，M即為M和N的最大公約數(shù)。本算法是由古希臘數(shù)學(xué)家歐幾里德提出的，所以又稱為“歐幾里德算法”。算法中的S1、S2、S3…叫作算法步驟，每個(gè)算法步驟明確規(guī)定所要進(jìn)行的操作及處理對(duì)象的特性（M、N為自然數(shù)）。歐幾里德算法是求兩個(gè)自然數(shù)最大公約數(shù)的經(jīng)典算法。證明第9頁(yè)/共21頁(yè)算法1求兩個(gè)自然數(shù)的最大公約數(shù)的算法證明：兩個(gè)自然數(shù)M、N，假設(shè)M和N的最大公約數(shù)RM可表示成M=kN+R，則R=M–kN；假設(shè)a是M和N的公約數(shù)，即a|M，a|N，則a|R；所以a也是N和R的公約數(shù)；同理假設(shè)a是N和R的公約數(shù)，即a|N，a|R，則a|M；所以a也是M和N的公約數(shù)；所以M、N、R的公約數(shù)是一樣的。第10頁(yè)/共21頁(yè)算法2在N個(gè)字符數(shù)據(jù)集合中，查找有無(wú) 特定的字符串存在

S1.輸入字符數(shù)據(jù)的個(gè)數(shù)N和要查找的數(shù)據(jù)S；S2.使I=1，I用于計(jì)數(shù)；S3.從字符數(shù)據(jù)集合中讀取一個(gè)數(shù)據(jù)X；S4.若X=S，輸出“找到S”的信息，算法結(jié)束，否則轉(zhuǎn)S5；S5.使I=I+1，計(jì)數(shù)器計(jì)數(shù)；S6.若I≤N；則重復(fù)執(zhí)行S3、S4、S5（循環(huán)）；否則轉(zhuǎn)S7；S7.輸出“找不到S”信息，算法結(jié)束。本算法也稱為“順序查找算法”，也是在處理非數(shù)值信息時(shí)最常用的一種算法。第11頁(yè)/共21頁(yè)算法的特征從上述算法的示例可以看出，作為算法，應(yīng)具備以下特征：1）確定性--算法的每個(gè)步驟都應(yīng)確切無(wú)誤，沒有歧義性。2）可行性--算法的每個(gè)步驟都必須是計(jì)算機(jī)能夠有效執(zhí)行、可以實(shí)現(xiàn)的，并可得到確定的結(jié)果。3）有窮性--一個(gè)算法包含的步驟必須是有限的，并在一個(gè)合理的時(shí)間限度內(nèi)可以執(zhí)行完畢。4）輸入性--執(zhí)行算法時(shí)可以有多個(gè)輸入，但也可以沒有輸入（0個(gè)輸入）。5）輸出性--一個(gè)算法必須有1個(gè)或多個(gè)輸出。第12頁(yè)/共21頁(yè)算法的描述算法可以采用多種方式來(lái)表示。比如使用人們的自然語(yǔ)言像英語(yǔ)、漢語(yǔ)等來(lái)描述；使用某種代碼符號(hào)來(lái)描述或者使用特定的圖形來(lái)描述等等。由于圖形的描述方法既形象，又直觀，所以得到廣泛的應(yīng)用。用于描述算法的圖形使用較多的是所謂的流程框圖，簡(jiǎn)稱流程圖。它是使用規(guī)定的圖形符號(hào)來(lái)描述算法的。流程圖使用的圖形符號(hào)見表2-1。圖2-2和圖2-3分別是上一節(jié)兩個(gè)算法示例的流程圖。圖框內(nèi)的文字用于說(shuō)明具體的操作內(nèi)容。顯而易見，使用流程圖比使用自然語(yǔ)言描述算法優(yōu)越地多。

第13頁(yè)/共21頁(yè)圖形符號(hào)名稱代表的操作輸入/輸出數(shù)據(jù)的輸入與輸出處理各種形式的數(shù)據(jù)處理判斷判斷選擇，根據(jù)條件滿足與否選擇不同路徑起止流程的起點(diǎn)與終點(diǎn)特定過(guò)程一個(gè)定義過(guò)的過(guò)程流程線連接各個(gè)圖框，表示執(zhí)行順序連接點(diǎn)表示與流程圖其他部分相連接表2-1第14頁(yè)/共21頁(yè)NM第15頁(yè)/共21頁(yè)基本算法結(jié)構(gòu)“結(jié)構(gòu)化程序設(shè)計(jì)方法”的核心是規(guī)定了算法的三種基本結(jié)構(gòu)：順序結(jié)構(gòu)、分支結(jié)構(gòu)和循環(huán)結(jié)構(gòu)。

第16頁(yè)/共21頁(yè)順序結(jié)構(gòu)第