程式設計基礎輔導材料

2022-05-24 06:42:02 字數 3609 閱讀 9003

用流程圖描述演算法時,一般要注意以下幾點:

(1)應根據解決問題的步驟從上至下順序地畫出流程圖,各圖框中的文字要盡量簡潔。

(2)為避免流程圖的圖形顯得過長,圖中的流程線要盡量短。

(3)用流程圖描述演算法時,流程圖的描述可粗可細,總的原則是:根據實際問題的複雜性,流程圖達到的最終效果應該是,依據此圖就能用某種程式語言實現相應的演算法(即完成程式設計)。

n-s結構化流程圖主要特點是取消了流程線,全部演算法由一些基本的矩形框圖順序排列組成乙個大矩形表示,即不允許程式任意轉移,而只能順序執行,從而使程式結構化。

n-s圖也是流程圖的一種很好的表示方法,對應於三種基本結構的n-s圖如圖6.2所示。

(1)順序結構2)選擇結構

3)迴圈結構

圖6.2 n-s圖的三種基本控制結構

圖中「s1」或「s2」既可以是簡單功能的操作,如資料賦值、資料的輸入或輸出等,也可以是三種基本控制結構中的1種。

在我們的教材中有一些簡單的例題,比較詳細地示範了如何使用這些演算法的描述方法進行演算法描述,請大家認真進行自學,通過例題,體會一下這些常用的演算法描述方法。

6.2 演算法設計中的基本方法

人們希望計算機求解的問題是千差萬別的,所設計的求解演算法也千差萬別,一般來說,演算法設計沒有什麼固定的方法可循。但是通過大量的實踐,人們也總結出某些共性的規律,其中包括遞迴方法、分治方法、貪心法、回溯法、動態規劃法以及平衡原則等等。

在我們的課程中不可能對每一種演算法都進行深入的講解,我們只選擇最基本、最典型的的窮舉法進行一些討論,以使大家對於演算法和演算法設計方法有乙個初步的了解。

我們在拿到問題之後,不可能馬上就動手程式設計解決問題,要經歷乙個思考、程式設計的過程,對於一般的小問題,我們可以進行簡單處理,按照下面給出的5步進行求解:

第1步:明確問題的性質,分析題意

我們可以將問題簡單地分為:數值型問題和非數值型問題。不同型別的問題可以有針對性地採用不同的方法進行處理。

第2步:建立問題的描述模型

對於數值型問題,我們可以建立數學模型,通過數學模型來描述問題。對於非數值型問題,我們一般可以建立乙個過程模型,通過過程模型來描述問題。

第3步:設計/確定演算法

對於數值型的問題,我們可以採用數值分析的方法進行處理。在數值分析中,有許多現成的固定演算法,我們可以直接使用,當然我們也可以根據問題的實際情況設計演算法。

對於非數值型問題,我們可以通過資料結構或演算法分析與設計進行處理。也可以選擇一些成熟的方法進行處理,例如:窮舉法,遞推法,遞迴法,分治法,回溯法等。

在演算法確定之後,我們要使用上一節中介紹的演算法描述方法對演算法進行描述。

第4步:程式設計除錯

根據演算法,採用一種程式語言程式設計實現,然後上機除錯,得到程式的執行結果。

第5步:分析執行結果

對於執行結果要進行分析,看看執行結果是否符合預先的期望,如果步符合,要進行判斷問題出在什麼地方,找出原因對演算法或程式進行修正,直到得到正確的結果。

下面我們採用窮舉法對數值型問題進行求解,讓大家首先來體會一下求解數值問題的思考過程。

窮舉法也叫列舉法或蠻幹法。其基本思想是根據面臨的問題,逐一列舉各種可能的情況,並判斷每種情況是否滿足題設條件。這種方法的好處是最大限度考慮了各種情況,從而為求出最優解創造了條件。

例1:百錢百雞問題。中國古代數學家張丘建在他的《算經》中提出了著名的「百錢百雞問題」:雞翁一,值錢五;雞母一,值錢三;雞雛三,值錢一;百錢買百雞,翁、母、雛各幾何?

● 問題分析與演算法設計

這是乙個典型的數值型問題,我們要首先建立這個問題的數學模型,數學模型也就是我們平時說的數學方程。

假設:我們要買x只公雞,y只母雞,z只小雞,根據題目的意思可以得到兩個方程:

x+y+z=100

5x+3y+z/3=100 ②

根據題目的意思,我們可以確定x和y的取值範圍:0 <= x、y、z <= 100。

我們可以採用窮舉法進行求解。對於變數x,y,z的不同組合,看它們是否滿足上面的兩個方程,如果滿足了,就是問題的乙個解。如果不滿足,就不是問題的解。

我們可以採用三重巢狀的迴圈對變數x,y,z進行組合。我們可以寫出程式1。

程式1:

#include <>

main( )

執行上面的程式,可以得到執行結果:

1: cock= 0 hen=25 chicken=75

2: cock= 3 hen=20 chicken=77

3: cock= 4 hen=18 chicken=78

4: cock= 7 hen=13 chicken=80

5: cock= 8 hen=11 chicken=81

6: cock=11 hen= 6 chicken=83

7: cock=12 hen= 4 chicken=84

分析程式的執行結果,我們應該可以注意到有有三組解有問題,第2、4、6組解中,小雞的數量不能被3整除。問題到底出在什麼地方呢?我們進行進一步分析,將這些解代入方程②:

5x+3y+z/3=100,可以看到:

5*3+3*20+77/3=15+60+25.67=100.67≠100

5*7+3*13+80/3=35+39+26.67=100.67≠100

5*11+3*6+83/3=55+18+27.67=100.67≠100

顯然,這三組解不滿足數學方程,但由於我們在c語言中,進行int型除法時,77/3的結果就是25,80/3的結果就是26,83/3的結果就是27,這也是計算機在處理整型資料時的特點,在進行除法運算時,對於商的小數部分不再進行處理,直接截斷。所以就造成了在數學上本來不成立的方程,在計算機中成立了。

產生這個問題的根本原因就是我們在分析問題的過程中忽略了乙個重要條件,變數z要能夠被3整除。為了解決這個問題我們要在原來兩個方程的基礎上增加乙個判斷條件:

z%3==0

經過修改後,我們可以得到新的程式2:

程式2:

#include <>

main( )

再次執行程式,可以得到正確的結果:

1: cock= 0 hen=25 chicken=75

2: cock= 4 hen=18 chicken=78

3: cock= 8 hen=11 chicken=81

4: cock=12 hen= 4 chicken=84

為了保證變數z能夠整除3,我們還可以換乙個思路,在與z有關的for迴圈上作文章。程式2的迴圈中變數z每次+1,這樣z就很可能不時3的倍數,我們可以對此進行優化,讓變數z每次迴圈不是加1,而是加3,這樣就可以保證變數z一定是3的倍數,因此我們就可以省略判斷z是否可以被3整除的過程。

按照這樣的思路,我們可以得到程式3。

程式3:

#include <>

main( )

執行程式3,也可以得到正確的結果。

進一步分析程式3,我們還可以看到:窮舉變數x的取值範圍過大了,x的取值範圍只應該在0~20之間,並且,一旦確定了變數x和變數z的值,我們就可以利用方程①直接計算出變數y的值,這樣就可以去掉對變數y的窮舉過程。

於是我們可以得到程式4。

程式4:

#include <>

main( )

很顯然,程式4的迴圈減少了一層,變數x的窮舉範圍也減少了。

我們進一步分析程式,變數z的窮舉次數還是太多,我們可以對變數y進行窮舉。

分式輔導材料

輔導材料 分式 班級姓名座號 1 下列各有理式中 1 2 x y 3 4 5 6 7 8 屬於整式的有屬於分式的有寫序號 2 當x 時,分式有意義。當x 時,分式有意義。3 當x 時,分式無意義。4 當x 時,分式的值為零 當x 時,分式的值為零 5 某工廠原計畫a天完成b件產品,若現在需要提前x天...

城建110基礎知識輔導材料

一 城市道路的組成及分類 城市道路的組成 道路兩側建築紅線之間的空間範圍為道路用地。包括 1 供各種車輛行駛的車行道。其中有供汽車 電車 電單車等行駛的機動車道 供自行車 三輪車 平板車等行駛的非機動車道。2 行人路。專供行人步行交通的通行帶。3 綠化帶。布置在道路 或道路兩側種植樹木花草的地帶,具...

專案管理輔導材料

1 專案所包含的三層含義?第一 專案是一項有待完成的任務,具有特定的環境要求 第 二 專案是在一定的組織機構內,利用有限的資源 人力 物力 財力等 在規定的時間內所要完成的任務 第 三 專案所要完成的任務應滿足特定的效能 質量 數量和技術指標等要求。專案側重於過程,它是乙個動態概念,我們可以把一條高...