【文章內(nèi)容簡介】 46 開 始 判 斷 任 意 數(shù) n 是 否 為 素 數(shù) 的 算 法 2 224。 i 。 1 224。 i s p r i m初 始 化 設(shè) 置 ； i 是 存 放 除 數(shù) 因 子的 變 量 。 i s p r i m 表 示 是 否 為 素 數(shù)的 變 量 , 0 代 表 非 素 數(shù) , 1 代 表 素 數(shù)i n 并 且 i s p r i m = 1n m o d i 224。 r 。 結(jié) 束打 印 “ n 不是 素 數(shù) ”NYi + 1 224。 i 。 n 除 以 i 的 余 數(shù) 賦 值 給 r讀 入 整 數(shù) n 讀 入 任 意 正 整 數(shù) n 。 n 2 。打 印 “ n 是素 數(shù) ”YN如 果 余 數(shù) 為 0 , 則 說 明 n存 在 因 子 , n 不 是 素 數(shù)此 處 是 當(dāng) 型 循 環(huán) , 表 示 如 果 除數(shù) i 不 是 因 子 并 且 除 數(shù) i 小 于 n ,就 一 直 重 復(fù) 做 下 面 操 作 。r = 00 224。 i s p r i mi s p r i m = 0YN如 果 余 數(shù) 不 為 0 ,則 因 子 i 加 1 。圖 4 . 2 1 判 斷 任 意 數(shù) n 是 否 為 素 數(shù) 的 算 法 流 程 圖 ( 結(jié) 構(gòu) 化 )改進(jìn)后的流程圖：單入單出 設(shè)置標(biāo)志位 isPrim 47 ? 傳統(tǒng)流程圖的弊端 – 對流程線的使用沒有嚴(yán)格限制，閱讀困難； – – 不能保證算法結(jié)構(gòu)的單入單出特性； – – 占用篇幅較多 ； 算法的描述方法 － NS流程圖 必須限制箭頭的濫用，讓流程只能順序執(zhí)行下去！ 保證結(jié)構(gòu)化原則的流程描述工具－ NS圖 48 ? 基本結(jié)構(gòu) 算法的描述方法 － NS流程圖 ABA B成 立不 成立P 圖 4 ． 1 5 順 序 結(jié) 構(gòu) 圖 4 ． 1 6 選 擇 結(jié) 構(gòu)當(dāng) P 1 成 立 時A 圖 4 ． 1 7 當(dāng) 型 循 環(huán) 結(jié) 構(gòu) 圖 4 ． 1 8 直 到 型 循 環(huán) 結(jié) 構(gòu)直 到 P 1 成 立Ap、 p1表示的是判斷條件； A、B框是操作； 注意： A、 B框可以是一個簡單的操作（如讀入數(shù)據(jù)或打印輸出等），也可以是三種基本結(jié)構(gòu)之一 順序結(jié)構(gòu) 選擇結(jié)構(gòu) 當(dāng)型循環(huán)結(jié)構(gòu) 直到型循環(huán)結(jié)構(gòu) 49 例 1 求 10!的 NS流程圖 算法的描述方法 － NS流程圖 當(dāng) i ≤ 1 0 時1 224。 p 。 2 224。 i 。 初 始 化 設(shè) 置 ； p 存 放 乘 積 ， i 存 放 乘 數(shù)p ╳ i 224。 p 。 i + 1 224。 i 。 P 保 存 累 計 的 乘 積乘 數(shù) i 每 次 加 1輸 出 結(jié) 果 p圖 4 . 1 9 求 1 0 ! 并 輸 出 結(jié) 果 的 算 法 N S 流 程 圖 50 例 2 打印學(xué)生成績 NS流程圖 算法的描述方法 － NS流程圖 i 223。 1 。 W h i l e ( i ≤ 1 2 0 )讀 入 （ n u m , s c o r e )s c o r e ≥ 6 0 i + 1 224。 i 。 YN打 印( n u m , s c o r e )初 始 化 設(shè) 置 ； i 表 示 當(dāng) 前 處 理 學(xué) 生 的 序 號 ；此 處 是 當(dāng) 型 循 環(huán) , 用 于 對 1 2 0 個 學(xué) 生 逐 個處 理 ；讀 入 當(dāng) 前 學(xué) 生 的 學(xué) 號 及 成 績 ；打 印 輸 出 滿 足 條 件 學(xué) 生的 學(xué) 號 及 成 績圖 4 . 2 0 打 印 及 格 學(xué) 生 的 學(xué) 號 及 成 績 51 例 3 判斷質(zhì)數(shù)的NS流程圖 算法的描述方法 － NS流程圖 2 224。 i 。 1 224。 i s p r i m初 始 化 設(shè) 置 ； i 是 存 放 除 數(shù) 因 子 的 變量 。 i s p r i m 表 示 是 否 為 素 數(shù) 的 變 量 , 0代 表 非 素 數(shù) , 1 代 表 素 數(shù)n 除 以 i 的 余 數(shù) 賦 值 給 r讀 入 任 意 正 整 數(shù) n 。 n 2 。如 果 余 數(shù) 為 0 , 則 說 明 n 存 在 因子 , n 不 是 素 數(shù) ； 退 出 循 環(huán)此 處 是 當(dāng) 型 循 環(huán) , 表 示 如 果 除 數(shù) i 不是 因 子 并 且 除 數(shù) i 小 于 n , 就 一 直 重復(fù) 做 下 面 操 作 。讀 入 整 數(shù) ni n 并 且 i s p r i m = 1n m o d i 224。 r 。 r = 00 224。 i s p r i mi + 1 224。 i 。 YNi s p r i m = 0N Y打 印 “ n 是 素 數(shù) ”打 印 “ n 不 是 素數(shù) ”如 果 余數(shù) 不 為0 , 則 因子 i 加1 。圖 4 . 2 3 判 斷 任 意 數(shù) n 是 否 為 素 數(shù) 的 算 法 流 程 圖 ( 結(jié) 構(gòu) 化 ) 52 算法的描述方法 － 偽碼描述 ? 流程圖和 NS圖畫起來比較費事，適合于表示算法，而在算法設(shè)計中使用不是很理想。 ? 偽碼 用 介于自然語言和程序設(shè)計語言之間的文字和符號來描述算法。 【 返回 】 IF x is positive THEN print x ELSE print y WHILE i＝ 120 { input score。 IF score60 THEN print score i加 1 } 53 算法的描述方法 例 4：利用泰勒級數(shù)： … ... … ... + + + + = + )! 1 2 ( ) 1 ( ! 7 ! 5 ! 3 sin 1 2 1 7 5 3 n x x x x x x n n 計算正弦的值，直到最后一項絕對值小于 106 時為止。 被除數(shù) 除數(shù) 符號 n＝ 1 n＝ 2 n＝ 3 ?分析：求 n項和的算法思路 ?Sum(a1)=a1 ?Sum(a1,a2)=Sum(a1)+a2 =a1+a2 ?Sum(a1,a2, a3)=Sum(a1,a2)+a3 ?Sum(a1,a2,? ,an)=Sum(a1,a2,? ,an1)+an 54 算法的描述方法 ? 算法的核心操作是求兩數(shù)之和，其中第一個操作數(shù)是前一次求得的和。如何求第二個操作數(shù)？ ? 算法 1： n決定了第 n項因子的值，即第二個操作數(shù)；因此每一次可根據(jù)當(dāng)前 n的值計算出第二個操作數(shù)。 ? 請用 N－ S圖描述出算法 1。 55 求 sin(x)算法 1 | p | 1 0 的 － 6 次s u m ＝ s u m ＋ pp = x , s u m = 0 , i = 1i = i + 1p = ( 1 ) 的 ( i + 1 ) 次 x 的( 2 i 1 ) 次 / ( 2 i 1 ) !i代表下一個 p是第幾項，因此初值是 1 變量抽象： x：存儲未知數(shù) x的值； sum：存儲和 ； p：存儲當(dāng)前待加的因子； i：當(dāng)前待加的是第幾個因子 ... ... ... ... + + + + = + )! 1 2 ( ) 1 ( ! 7 ! 5 ! 3 sin 1 2 1 7 5 3 n x x x x x x n n 56 問題：任何數(shù)據(jù)類型只能表示一定范圍內(nèi)的數(shù)，當(dāng)試圖往變量中存儲在范圍之外的數(shù)，數(shù)據(jù)無法正確存儲。求 x的 n次方和 (2n1)!時可能會導(dǎo)致結(jié)果太大而溢出。 解決方法： (2n1)!的結(jié)果 —算法 2 57 算法的描述方法 = pi 1 )! 3 2 ( ) 1 ( 3 2 i x i i = Pi + )! 1 2 ( ) 1 ( 1 2 1 i x i i Pi Pi pi 1 ... ... … ... + + + + = + )! 1 2 ( ) 1 ( ! 7 ! 5 ! 3 sin 1 2 1 7 5 3 n x x x x x x n n 算法 2：設(shè)第 i項因子表示為 ，考察 和 的關(guān)系。 = *(1)* x2 /((2i1)*(2i2)) Pi pi 1 58 請用 N－ S圖描述算法 2。 算法的描述方法 ? 【 源程序演示 】 | p | 1 0 的 － 6 次s u m ＝ s u m ＋ pp = x , s u m = 0 , i = 1i = i + 1p = p * 1 * x 的 平 方 / ( 2 i 1 ) ( 2 i 2 )i代表下一個 p是第幾項，因此初值是 1 59 include include main() { int i。 float x。 double sum,p。 //p用于存放待加的那一項 printf(input x:)。 scanf(%f,amp。x)。 /*變量初始化 */ sum=。 i=1。 p=x。 /*求解 */ while(fabs(p)1e8){ sum=sum+p。 i=i+1。 p=p*x*x/((2*i2)*(2*i1))。 } printf(sin(%f) = %lf\n,x,sum)。 system(pause)。 return 0。 } 60 算法的概念 算法的三種基本結(jié)構(gòu) 算法的描述方法 結(jié)構(gòu)化程序設(shè)計方法 算法設(shè)計實例研究 提綱 61 ? 源自于對 goto語句的爭論 ? goto語句詳見 《 程序設(shè)計教程 》 436頁 結(jié)構(gòu)化程序設(shè)計方法 62 include main() { int count=1。 start: //標(biāo)號 ,是跟有冒號的標(biāo)識符 if (count10) goto end。 printf(%d ,count)。 count=count+1。 goto start。 end: printf(\n)。 system(pause)。 return 0。 } 1 2 3 4 5 6 7 8 9 10 請按任意鍵繼續(xù) . . . 運行效果： 63 結(jié)構(gòu)化程序設(shè)計方法 ? 用三種基本結(jié)構(gòu)組成的程序必然是 結(jié)構(gòu)化 的程序，這種程序便于編寫、閱讀、修改和維護(hù) 。 ? 結(jié)構(gòu)化程序設(shè)計強(qiáng)調(diào) 程序設(shè)計風(fēng)格 和 程序結(jié)構(gòu)的規(guī)范化 ，提倡清晰的結(jié)構(gòu) 。