1、高級語言程序設計(一)(C Programming),第三講：程序設計方法-問題分析,本章目標,了解一般程序設計過程 通過實例重點掌握問題分析方法 精度計算； 輸入數據處理； 字符串操作,程序設計過程,程序設計過程就是解決問題的過程。程序設計通常包括如下五個步驟：,分析問題： 功能：需要弄清楚軟件要完成的功能； 輸入：如果問題有輸入，分析輸入是什么及輸入數據的類型； 處理：對輸入數據做什么處理； 輸出：如果有輸出，輸出什么數據及輸出數據的格式； 對于復雜問題，可將問題分解為若干子問題，然后再進行上面的分析。,算法設計： 設計解決問題的具體方案(步驟)。,編碼： 將算法用高級語言實現。,測試：

2、運行編譯連接后得到的執(zhí)行程序，以驗證程序是否按要求 解決了問題，并沒有產生副作用。即程序是否做了該做的事，同時沒有做不該做的事。,調試： 如果程序經測試發(fā)現問題，則通過調試手段找到產生錯誤的代碼并修復它。,算法,任何計算問題的解決都是按指定的順序執(zhí)行一系列動作的結果。解決問題的步驟(動作及動作之間的順序)稱為算法（algorithm）。,算法表示,算法既可以用自然語言表述(如前)，也可用用半結構化語言或結構化圖形表示，如： read 學生成績值 if 成績值 = 60 print “Pass” else print “Fail”,問題3.1: 計算e值,【問題描述】 e(自然對數)值計算公式為

3、 1 + 1/1! + 1/2! + + 1/n!。輸入一個整數n（0=n=30），計算相應e近似值 。 【輸入形式】 從控制臺輸入整數n（0=n=30）。 【輸出形式】 控制臺輸出計算結果，要求小數點后保留10位。 【樣例輸入1】 12 【樣例輸出1】 2.7182818283 【樣例輸入2】 13 【樣例輸出2】 2.7182818284,問題3.1：問題分析,輸入：一個整數（整型）； 處理：計算 公式1 + 1/1! + 1/2! + + 1/n! ； 輸出：以%.10f格式輸出(小數后保留10位) 變量： 一個整型變量, 用于存儲所讀入的整數, 如, int n; 一個雙精度浮點變量(

4、Why?), 用于存儲計算結果, 如 double e;,問題3.1：算法設計,解決問題3.1的解決過程（算法一）： 設計算結果保存在變量e中； 讀入一個整數到變量n; for(i=0; i=n; i+) e = e + 1/i!; 輸出e值;,e=1 + 1/1! + 1/2! + + 1/n!,問題3.1：代碼實現,#include int fact(int n) int f, i; f = 1; for(i=2;i=n;i+) f *= i; return f; int main() int n,i; double e=0.0; scanf(%d, ,問題3.1：測試,測試數據的考慮 首

5、先選取輸入數據區(qū)間（0=n=30）的正常值,如問題3.1中所提供的輸入樣例； 輸入：12 期望（正確）輸出： 2.7182818283 輸入：13 期望（正確）輸出： 2.7182818284 選取輸入數據區(qū)間邊界附近的值，本例中可選?。?n=0， 期望輸出：1.0000000000 n=1， 期望輸出：2.0000000000 n=30，期望輸出： 2.7182818285,問題3.1：常見問題分析,以整型計算n!，即函數fact返回整數（觀察現象what happened?） n=13 實際輸出： 2.7182818288 (期望輸出：2.7182818284) Why? 如何調試?,數據

6、范圍與精度,int類型數據范圍(對于IA32結構的計算機): -232-1 - 232-1 - 1 (即-2147483648 2147483647 ) 12! int最大值 13! 修改方法： 將保存階乘結果的變量 改為double類型，并將 fact的返回類型也改為double,0!1 1!1 2!2 3!6 4!24 5!120 6!720 7!5040 8!40320 9!362880 10!3628800 11!39916800 12!479001600 13!1932053504(error!, 溢出) (正確應為:6227020800) 14!1278945280(error!,

7、 溢出) (正確應為:87178291200),問題3.1：修改后的程序,#include double fact(int n) int i; double f=1.0; for(i=1; i=n; i+) f *= i; return f; int main() int n,i; double e = 0.0; scanf(“%d”, ,計算結果為float類型，即float e; （觀察現象what happened?） n=12 實際輸出： 2.7182819841 (期望輸出：2.7182818283) double類型比float類型有更高的精度 float 尾數：23位，指數：8位

8、 double 尾數：52位，指數：11位,問題3.1：常見問題分析（續(xù)）,問題3.1：另一種方法,觀察計算 公式1 + 1/1! + 1/2! + + 1/n!，可知： 若前一次迭代1/(n-1)!計算結果為fn-1，則本次迭代的結果則為fn = fn-1 /n 因此，沒有必要每次迭代都重新計算n!，顯然效率會更高。 具體算法（解題步驟）為： 給雙精度浮點變量e和 f 賦初值 1.0; for(i=1; i=n; i+) f = f/i; e = e+f; 輸出e,問題3.1：另一種方法（代碼）,#include int main() int n,i; double e ,f e = f =

9、 1.0; scanf(“%d”, ,考慮為什么循環(huán)從i=1開始，而不從i=0開始？,17,問題3.2：簡易計算器,【問題描述】 編程實現簡單的交互式計算器，能進行整數的 + - * / 運算。 【輸入形式】 從鍵盤讀入如下形式的輸入行，數據與運算符之間可以用一個或多個空格分隔： 120 + 350 【輸入形式】 對于+,-及*運算，輸出形式如下： 120+350=470 對于/運算，輸出形式如下（小數后保留兩位）： 5/2=2.50,18,問題3.2：問題分析,如何讀入數據及運算符？ 方法一 int data1,data2; char op; scanf ( “%d%c%d”, 不足：數據與

10、運算符之間只能有一個空格分隔,輸入時，數據與字符之間不能有空格，否則空格作為字符輸入。,19,問題3.2：問題分析,如何讀入數據及運算符？ 方法三 int data1, data2; char op; scanf(“%d %c %d”, 好處：數據與運算符之間可以有多個空格分隔,空格使得跳過兩次非空白輸入間的所有空白字符。,20,問題3.2：算法設計,int data1,data2, result1; float result2; char op; 從標準輸入中讀入整數data1，運算符op及整數data2; 判斷op: 若為+，則result1 = data1 + data2; 若為-，則r

11、esult1 = data1 - data2; 若為*，則result1 = data1 * data2; 若為/，則result2 = data1 / data2; 若op為+,-或*，輸出結果result1; 若op為/，輸出結果result2;,注意：由于data1和data2為整數，結果仍為整數。要用強制類型轉換才能得到小數位。 result2 = (float)data1/data2;,多路選擇，可使用if-else if語句實現。在此，更適合switch語句。,21,問題3.2：代碼實現,/c3_2.c #include int main() int data1,data2, re

12、sult1; float result2; char op; scanf(“%d %c %d”, ,測試數據: 120 + 350 12 12 35 * 2 3 / 2 123+12 + 12 123 float result2; char op; for(; ;) scanf(%d %c %d, ,無窮循環(huán)，可用ctrl+c退出，實際上可以利用ctrl+c終止任何控制臺C程序的執(zhí)行。,continue語句，跳到下一次循環(huán)。,本問題程序一次運行只能進行單運行符計算。若要使程序能支持多運算符的混合運算，并輸入等號（=）結束輸入，如，1+2-3*5/2-3/2=，如何實現？難點： 如何讀入數據及運

13、算符？ 如何保證計算時運算符的優(yōu)先級？ 更進一步，若要程序支持圓括號來改變計算次序，如，(1+2-3)*(5-3)/2=，如何實現？ 如果出現錯誤的輸入，例如輸入：4+r=，如何過濾掉錯誤輸入，繼續(xù)程序的運行？,23,問題3.2：思考（二）,利用scanf的返回值,為了保證運算符的優(yōu)先級，其算法分析: 當前datai opi datai+1 是否進行是由opi+1決定。當 opi+1為+,-,=時，立即進行當前運算，否則先進行下一步運算，以此迭代。部分偽代碼如下： scanf(“%d %c”, ,其它方法?,輸入串可表示為 data1 op1 datai opi opi為+,-,*,/,= 因

14、此可采用如下方式讀入數據和運算符: scanf(“%d %c”, ,格式化輸入函數,int scanf ( “.”, ) 該函數根據格式化字符串中的格式控制字符，將輸入流中的信息轉換成相應的數據類型； 返回成功轉換并賦值的輸入項個數； 若格式完全匹配失敗，則返回0； 若遇到輸入結束，則返回EOF； 將過濾掉出現的空白字符（空格、制表符、換行符）。,一次性讀入所有數據： num = scanf( “%d %c %d”, 根據num的值判斷各種情況。 利用getchar輸入函數循環(huán)讀入一行字符，逐個分析各個字符進行數據組裝和判斷； 利用gets函數讀入一行字符串，逐個分析各個字符進行數據組裝和判斷

15、。,問題3.2：其它讀取方法,問題3.3 擴展字符,【問題描述】編寫程序將含有縮記符號的字符串擴展為等價的完整字符串，例如將a-d擴展為abcd。該程序可以處理大小寫字母和數字，并可以處理a-b-c、a-z0-9與-a-z等類似的情況。要求擴展符-兩邊的字符只要右邊的大于左邊就擴展（即Z-b情況也要擴展），并且-兩邊不能有空格?！据斎胄问健繌逆I盤輸入包含擴展符的字符串，字符串中可以包含空格【輸出形式】輸出擴展后的字符串【輸入樣例1】a-c-u-B【輸出樣例1】abcdefghijklmnopqrstu-B【輸入樣例2】a-b-c a-a 0-4【輸出樣例2】abc a-a 01234 【樣例說

16、明】擴展輸入a-c-u為：abcdefghijklmnopqrstu，而B比u值小，所以無法擴展，直接輸出。,27,問題3.3 ：問題分析,如何讀入一個包含空格的字符串？（不能用scanf函數，為什么？） 方法一： char c, s512; for(i=0; (c=getchar() != n; i+) si = c; si = 0; 方法二（簡單）：使用gets標準庫函數 gets(s);,注意：不要忘記加字符串最后的結束符（0）！,行輸入、輸出,行輸入函數： char * gets ( char s ) 從標準輸入讀取完整的一行，將讀取的內容存入s字符數組中，并用字符串結束符0取代行尾的

17、n。若讀取錯誤或遇到輸入結束則返回NULL。 行輸出函數 int puts ( char s ) 將字符數組s中的內容輸出到標準輸出上，并自動在末尾添加一個換行符。,問題3.3 問題分析,if s1i+1=- if s1i+1=- ,i初始化為0；,j初始化為0；,問題3.3 程序實現,#include #define MAXLINE 512 int main() char c,s1MAXLINE,s2MAXLINE; int i,j; i = j = 0; gets(s1); while(s1i != 0) s2j+ = s1i; if(s1i+1 = - ,問題3.3 ：測試,測試數據期望

18、結果數據類型 a-dabcd正常 a-c-u-B abcdefghijklmnopqrstu-B 特殊 a-d d-aabcd d-a特殊 Z-b Z_ab 特殊 a-b-cabc邊界 -a-8-a-8非正常 a-aa-a非正常,問題3.3 ：常見問題及分析,處理帶空格的輸入串 不要用scanf來讀輸入串，建議用getchar或gets來讀輸入串； 字符串沒有結束標志 在用getchar讀入一個字符串及生成擴展字符串s2時，一定要給字符串置一個結束符（0）；（通過實例演示一下現象）,問題3.3 ：常見問題及分析（續(xù)）,用a-d, a-b, a-d-g作輸入觀察下面程序現象。如何調試？,/c3_

19、3a.c #include #define MAXLINE 512 int main() char c,s1MAXLINE,s2MAXLINE; int i,j; i = j = 0; gets(s1);,while(s1i != 0) s2j+ = s1i; if(s1i+1 = - ,問題3.3 ：其它方法,其實在上述代碼實現中，數組s2可以省略，如：,/c3_3b.c #include #define MAXLINE 512 int main() char c,s1MAXLINE; int i=0; gets(s1); while(s1i != 0) putchar(s1i); if(s

20、1i+1 = - ,其它方法？,問題3.3 ：思考,若要求擴展符-兩邊的字符為同類(即均為小寫字母、大寫字母或數字字符），即 出現Z-b、8-B這種情況將不擴展，程序如何修改？,其實在擴展字符操作前 if(s1i+1 = - ,isupper, islower, isdigit均為系統標準庫函數。使用前要加： #include ,#include int a1000,j; void expand( int s1000,int i ) int k; j=0; for(k=0;ki;+k) if(sk=- ,main() int s1000,k,i; for(i=0; si-1!=n; +i) s

21、i=getchar(); - i; expand(s,i); for(k=0;kj;+k) printf(%c,ak); ,問題3.3 一位同學的程序實例,問題3.4 多項式相加,【問題描述】編寫一個程序實現兩個一元多項式相加的運算。 【輸入形式】從標準輸入中讀入兩行以空格分隔的整數，每一行代表一個多項式，且該多項式中各項的系數均為0或正整數，最高冪次不超過50。對于多項式 anxn + an-1xn-1+ + a1x1 + a0 x0 （n50）的表示方法如下： an n an-1 n-1 a1 1 a0 0 即相鄰兩個整數分別表示表達式中一項的系數和指數。在輸入中只出現系數不為0的項。 【

22、輸出形式】將運算結果輸出到屏幕。將系數不為0的項按指數從高到低的順序輸出，每次輸出其系數和指數，均以一個空格分隔。在行的末尾也輸出一個空格符，并且最后要求換行。,問題3.4 多項式相加（續(xù)）,【樣例輸入】 54 8 2 6 7 3 25 1 78 0 43 7 4 2 8 1 【樣例輸出】 54 8 43 7 2 6 7 3 4 2 33 1 78 0 【樣例說明】輸入文件的兩行分別代表了表達式 54x8 + 2x6 + 7x3 + 25x + 78 43x7 + 4x2 + 8x 其和為 54x8 + 43x7 + 2x6 + 7x3 + 4x2 + 33x + 78,問題3.4 問題分析,

23、如何讀取輸入的數據？ 輸入的數據個數未知（不超過100） 每行數據輸入時沒有結束標志 如何保存輸入的多項式系數和指數,問題3.4：問題分析（續(xù)）,如何讀取輸入的數據？ 設變量a,n分別存儲讀入項和相應項系數； while(1) scanf(“%d%d%c”, ,54 8 2 6 7 3 25 1 78 0,break語句，用于跳出循環(huán)。,do_while循環(huán)，一種在循環(huán)尾部進行判斷的循環(huán)。,缺點是回車之前不能有空格.,問題3.4：問題分析（續(xù)）,0 a0 1 a1 n-1 an-1 n an,54 8 2 6 7 3 25 1 78 0,a0 a1 a2 a3 an-2 an-1 an,0 1

24、 2 3 n-2 n-1 n,將an保存在下標為n的數組元素中，數組長度為51(050),即arrayn = a;,如何保存輸入的多項式系數和指數？,問題3.4：算法設計,1.令：int array151,int array251;分別用來存儲第一個多項式和第二個多項式； 2.初始化數組array1和array2元素值均為0； 3.讀入第一行數據保存在數組array1中； 4.讀入第二行數據保存在數組array2中； 5.依次將數組array1和array2相應元素相加，并將結果放到array1中，即array1i=array1i+array2i； 6.依次從后往前輸出數組array1中不為0

25、的元素。,用一個函數來分別讀入兩個多項式的系數和指數，如， void getExp(int a );,問題3.4：代碼實現,/c3_4.c #include #define LENGTH 51 void getExp(int array); int main() int array1LENGTH,array2LENGTH,i; for(i=0; i=0;i- ) if(array1i0) printf(%d %d ,array1i, i ); printf(n); ,void getExp(int array) int a,n; char c; do scanf(“%d%d%c”, ,初始化數

26、組,從標準輸入中讀數據到數組中,兩多項式相應項相加,輸出多項式系數不為0的項。,問題3.4：測試,正常數據： 54 8 2 6 7 3 25 1 78 0 43 7 4 2 8 1 期望結果： 54 8 43 7 2 6 7 3 4 2 33 1 78 0 邊界數據1： 105 50 23 49 46 25 12 1 57 0 203 50 22 48 21 25 13 2 9 1 200 0 期望結果： 308 50 23 49 22 48 67 25 13 2 21 1 257 0 邊界數據2： 12 50 25 0 期望結果： 12 50 25 0,問題3.4：常見問題分析,未初始化數組

27、（觀察下面用正常測試數據程序運行時現象，如何調試？）,/c3_4a.c #include #define LENGTH 51 void getExp(int array); int main() int array1LENGTH,array2LENGTH,i; getExp(array1); getExp(array2); for (i=0;i=0;i- ) if(array1i0) printf(%d %d ,array1i, i ); printf(n); ,問題3.4：常見問題分析（續(xù)）,最后一對數據沒有讀入，例如：（觀察用正常測試數據程序運行時現象，如何調試？）,/*c3_4b.c*/

28、 void getExp(int array) int a,n,c; scanf(%d%d, ,如何修改？,修改方法一： void getExp(int array) int a,n,c; scanf(%d%d, ,修改方法二： void getExp(int array) int a,n,c; scanf(%d%d, ,問題3.4：思考,其它輸入方法及算法？,例如：鏈表,問題3.4實現了兩個多項式相加運算，如何實現兩個多項式相乘？,第三講：程序設計方法-問題分析,49,問題3.5：超長正整數加法,【問題描述】編寫程序實現兩個超長正整數（每個最長80位數字）的加法運算。 【輸入形式】 從鍵盤讀

29、入兩個整數，不考慮輸入高位可能為0的情況。1.第一行是超長正整數A；2.第二行是超長正整數B； 【輸出形式】 輸出只有一行，是兩個長整數的運算結果，從高到低依次輸出各位數字。各位數字緊密輸出。 【輸入樣例】134098703578230056234098 【輸出樣例】134098703578464154 【樣例說明】進行兩個正整數加法運算，134098703578230056 + 234098 = 134098703578464154。,第三講：程序設計方法-問題分析,50,問題3.5：問題分析,如何讀入和存儲超長整數？（為何不能用長整數類型long int n; scanf(“%ld”, 其

30、它方法？,51,問題3.5：解題思路,在程序中數組是從左至右方式存儲的，而整數相加是從右至左（從低位到高位），同時由于被加數長短不一，造成計算和轉換非常不方便。一種解決方法是整數相加前將兩個整數位串首尾顛倒，與計算機存儲方式一致。 如何進行超長整數加？ 無論以什么方式存儲超長整數，每位相加結果和進位計算方式為： dighti = (digit1i + digit2i + carry) % 10 （carry為上一次計算產生的進位） carry = (digit1i + digit2i + carry) / 10 （得到新的進位） 注意： 若以字符串方式存儲超長整數，則在計算每位加和進位時，應考慮數字字符和整數數字之間的轉換。 應考慮進位傳遞問題 當較短整數最后一位加完后仍有進位情況，如123456789+678； 當較長整數最后一位處理完后仍有進位情況，如99