《C语言高级语言程序设计(一)第三章 程序设计方法问题分析.ppt》由会员分享，可在线阅读，更多相关《C语言高级语言程序设计(一)第三章 程序设计方法问题分析.ppt（55页珍藏版）》请在三一办公上搜索。
1、高级语言程序设计(一)(C Programming),第三讲：程序设计方法-问题分析,本章目标,了解一般程序设计过程通过实例重点掌握问题分析方法精度计算；输入数据处理；字符串操作,程序设计过程,程序设计过程就是解决问题的过程。程序设计通常包括如下五个步骤：,分析问题：功能：需要弄清楚软件要完成的功能；输入：如果问题有输入，分析输入是什么及输入数据的类型；处理：对输入数据做什么处理；输出：如果有输出，输出什么数据及输出数据的格式；对于复杂问题，可将问题分解为若干子问题，然后再进行上面的分析。,算法设计：设计解决问题的具体方案(步骤)。,编码：将算法用高级语言实现。,测试：运行编译连接后得到的执行
2、程序，以验证程序是否按要求 解决了问题，并没有产生副作用。即程序是否做了该做的事，同时没有做不该做的事。,调试：如果程序经测试发现问题，则通过调试手段找到产生错误的代码并修复它。,算法,任何计算问题的解决都是按指定的顺序执行一系列动作的结果。解决问题的步骤(动作及动作之间的顺序)称为算法（algorithm）。,算法表示,算法既可以用自然语言表述(如前)，也可用用半结构化语言或结构化图形表示，如：read 学生成绩值if 成绩值=60print“Pass”elseprint“Fail”,问题3.1:计算e值,【问题描述】e(自然对数)值计算公式为 1+1/1!+1/2!+1/n!。输入一个整数
3、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;一个双精度浮点变量(Why?),用于存储计算结果,如double e;,问题3.1：算法设计,解决问题3.1的解决过程（算法一）：设计算结果保存
4、在变量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：测试,测试数据的考虑首先选取输入数据区间（0=n=30）的正常值,如问题3.1中所提供的输入样例；输入：12期望（正确）输出：2.7182818283输入：13期望（正确）输出：2.7182818284选取输入数据区间边界附
5、近的值，本例中可选取：n=0，期望输出：1.0000000000n=1，期望输出：2.0000000000n=30，期望输出：2.7182818285,问题3.1：常见问题分析,以整型计算n!，即函数fact返回整数（观察现象what happened?）n=13实际输出：2.7182818288(期望输出：2.7182818284)Why?如何调试?,数据范围与精度,int类型数据范围(对于IA32结构的计算机):-232-1-232-1-1(即-2147483648 2147483647)12!int最大值 13!修改方法：将保存阶乘结果的变量改为double类型，并将fact的返回类型也
6、改为double,0!11!12!23!64!245!1206!7207!50408!403209!36288010!362880011!3991680012!47900160013!1932053504(error!,溢出)(正确应为:6227020800)14!1278945280(error!,溢出)(正确应为: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(“%
7、d”,计算结果为float类型，即float e;（观察现象what happened?）n=12实际输出：2.7182819841(期望输出：2.7182818283)double类型比float类型有更高的精度float尾数：23位，指数：8位double尾数：52位，指数：11位,问题3.1：常见问题分析（续）,问题3.1：另一种方法,观察计算 公式1+1/1!+1/2!+1/n!，可知：若前一次迭代1/(n-1)!计算结果为fn-1，则本次迭代的结果则为fn=fn-1/n因此，没有必要每次迭代都重新计算n!，显然效率会更高。具体算法（解题步骤）为：给双精度浮点变量e和 f 赋初值 1.
8、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=1.0;scanf(“%d”,考虑为什么循环从i=1开始，而不从i=0开始？,17,问题3.2：简易计算器,【问题描述】编程实现简单的交互式计算器，能进行整数的+-*/运算。【输入形式】从键盘读入如下形式的输入行，数据与运算符之间可以用一个或多个空格分隔：120+350【输入形式】对于+,-及*运算，输出形式如下：120+350=470对于/运算，输出形式如下（小数后保留两位）：5/2=2.50,18,问题3.2：
9、问题分析,如何读入数据及运算符？方法一int data1,data2;char op;scanf(“%d%c%d”,不足：数据与运算符之间只能有一个空格分隔,输入时，数据与字符之间不能有空格，否则空格作为字符输入。,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
10、及整数data2;判断op:若为+，则result1=data1+data2;若为-，则result1=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 m
11、ain()int data1,data2,result1;float result2;char op;scanf(“%d%c%d”,测试数据:120+35012 1235*23/2123+12+12123&12,22,问题3.2：思考（一）,本问题程序一次运行只能计算一次。若要能进行多次计算，并用ctrl+c退出程序，如何实现？,/c3_2c.c#include int main()int data1,data2,result1;float result2;char op;for(;)scanf(%d%c%d,无穷循环，可用ctrl+c退出，实际上可以利用ctrl+c终止任何控制台C程序的执行
12、。,continue语句，跳到下一次循环。,本问题程序一次运行只能进行单运行符计算。若要使程序能支持多运算符的混合运算，并输入等号（=）结束输入，如，1+2-3*5/2-3/2=，如何实现？难点：如何读入数据及运算符？如何保证计算时运算符的优先级？更进一步，若要程序支持圆括号来改变计算次序，如，(1+2-3)*(5-3)/2=，如何实现？如果出现错误的输入，例如输入：4+r=，如何过滤掉错误输入，继续程序的运行？,23,问题3.2：思考（二）,利用scanf的返回值,为了保证运算符的优先级，其算法分析:当前datai opi datai+1 是否进行是由opi+1决定。当 opi+1为+,-,
13、=时，立即进行当前运算，否则先进行下一步运算，以此迭代。部分伪代码如下：scanf(“%d%c”,其它方法?,输入串可表示为data1 op1 datai opi opi为+,-,*,/,=因此可采用如下方式读入数据和运算符:scanf(“%d%c”,格式化输入函数,int scanf(“.”,)该函数根据格式化字符串中的格式控制字符，将输入流中的信息转换成相应的数据类型；返回成功转换并赋值的输入项个数；若格式完全匹配失败，则返回0；若遇到输入结束，则返回EOF；将过滤掉出现的空白字符（空格、制表符、换行符）。,一次性读入所有数据：num=scanf(“%d%c%d”,根据num的值判断各种情
14、况。利用getchar输入函数循环读入一行字符，逐个分析各个字符进行数据组装和判断；利用gets函数读入一行字符串，逐个分析各个字符进行数据组装和判断。,问题3.2：其它读取方法,问题3.3 扩展字符,【问题描述】编写程序将含有缩记符号的字符串扩展为等价的完整字符串，例如将a-d扩展为abcd。该程序可以处理大小写字母和数字，并可以处理a-b-c、a-z0-9与-a-z等类似的情况。要求扩展符-两边的字符只要右边的大于左边就扩展（即Z-b情况也要扩展），并且-两边不能有空格。【输入形式】从键盘输入包含扩展符的字符串，字符串中可以包含空格【输出形式】输出扩展后的字符串【输入样例1】a-c-u-B
15、【输出样例1】abcdefghijklmnopqrstu-B【输入样例2】a-b-c a-a 0-4【输出样例2】abc a-a 01234【样例说明】扩展输入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
16、(char s)从标准输入读取完整的一行，将读取的内容存入s字符数组中，并用字符串结束符0取代行尾的n。若读取错误或遇到输入结束则返回NULL。行输出函数int puts(char s)将字符数组s中的内容输出到标准输出上，并自动在末尾添加一个换行符。,问题3.3 问题分析,if s1i+1=-&s1is1i+2,先将要扩展的字符串读到一个字符数组(s1)中；设另一个字符数组用于存放扩展后的字符串(s2)；依次检查所读入字符串(s1)中字符；,将s1i原封不动的写到s2中；当s1i+1=-&s1i s1i+2时，将s1i至s1i+2之间的字符展开到s2中,问题3.3 算法,设字符数组s1用来读
17、入字符串，s2用来存放扩展后字符串；从标准输入中读入字符串到s1中；while s1i!=0将s1当前字符放到s2中，即s2j=s1i;if s1i+1=-,i初始化为0；,j初始化为0；,问题3.3 程序实现,#include#define MAXLINE 512int main()char c,s1MAXLINE,s2MAXLINE;int i,j;i=j=0;gets(s1);while(s1i!=0)s2j+=s1i;if(s1i+1=-,问题3.3：测试,测试数据期望结果数据类型a-dabcd正常a-c-u-B abcdefghijklmnopqrstu-B 特殊a-d d-aabc
18、d 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：常见问题及分析（续）,用a-d,a-b,a-d-g作输入观察下面程序现象。如何调试？,/c3_3a.c#include#define MAXLINE 512int main()char c,s1MAXLINE,s2MAXLINE;int i
19、,j;i=j=0;gets(s1);,while(s1i!=0)s2j+=s1i;if(s1i+1=-,问题3.3：其它方法,其实在上述代码实现中，数组s2可以省略，如：,/c3_3b.c#include#define MAXLINE 512int main()char c,s1MAXLINE;int i=0;gets(s1);while(s1i!=0)putchar(s1i);if(s1i+1=-,其它方法？,问题3.3：思考,若要求扩展符-两边的字符为同类(即均为小写字母、大写字母或数字字符），即 出现Z-b、8-B这种情况将不扩展，程序如何修改？,其实在扩展字符操作前if(s1i+1=-
20、,isupper,islower,isdigit均为系统标准库函数。使用前要加：#include,#includeint 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)si=getchar();-i;expand(s,i);for(k=0;kj;+k)printf(%c,ak);,问题3.3 一位同学的程序实例,问题3.4 多项式相加,【问题描述】编写一个程序实现两个一元多项式相加的运算。【输入形式】从标准输入中读入两行以空格分
21、隔的整数，每一行代表一个多项式，且该多项式中各项的系数均为0或正整数，最高幂次不超过50。对于多项式 anxn+an-1xn-1+a1x1+a0 x0（n50）的表示方法如下：an n an-1 n-1 a1 1 a0 0 即相邻两个整数分别表示表达式中一项的系数和指数。在输入中只出现系数不为0的项。【输出形式】将运算结果输出到屏幕。将系数不为0的项按指数从高到低的顺序输出，每次输出其系数和指数，均以一个空格分隔。在行的末尾也输出一个空格符，并且最后要求换行。,问题3.4 多项式相加（续）,【样例输入】54 8 2 6 7 3 25 1 78 0 43 7 4 2 8 1【样例输出】54 8
22、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 问题分析,如何读取输入的数据？输入的数据个数未知（不超过100）每行数据输入时没有结束标志如何保存输入的多项式系数和指数,问题3.4：问题分析（续）,如何读取输入的数据？方法一：设变量a,n分别存储读入项和相应项系数；while(1)scanf(“%d%d%c”,54 8 2 6 7 3 25 1 78 0,break语句，用于跳出循环。,do_while循环
23、，一种在循环尾部进行判断的循环。,缺点是回车之前不能有空格.,问题3.4：问题分析（续）,如何读取输入的数据？方法二,部分伪代码：gets(buf);i=0;while(bufi!=0)if(bufi=0,54 8 2 6 7 3 25 1 78 0,问题3.4：问题分析（续）,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 2 3 n-2 n-1 n,将an保存在下标为n的数组元素中，数组长度为51(050),即arrayn=a;,如何保存输入的多项式系数和指数？,问题3.4：算法设计,1
24、.令：int array151,int array251;分别用来存储第一个多项式和第二个多项式；2.初始化数组array1和array2元素值均为0；3.读入第一行数据保存在数组array1中；4.读入第二行数据保存在数组array2中；5.依次将数组array1和array2相应元素相加，并将结果放到array1中，即array1i=array1i+array2i；6.依次从后往前输出数组array1中不为0的元素。,用一个函数来分别读入两个多项式的系数和指数，如，void getExp(int a);,问题3.4：代码实现,/c3_4.c#include#define LENGTH 51
25、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”,初始化数组,从标准输入中读数据到数组中,两多项式相应项相加,输出多项式系数不为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
26、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：常见问题分析,未初始化数组（观察下面用正常测试数据程序运行时现象，如何调试？）,/c3_4a.c#include#define LENGTH 51void getExp(int array);int main()int array1LENGTH,array2LENGT
27、H,i;getExp(array1);getExp(array2);for(i=0;i=0;i-)if(array1i0)printf(%d%d,array1i,i);printf(n);,问题3.4：常见问题分析（续）,最后一对数据没有读入，例如：（观察用正常测试数据程序运行时现象，如何调试？）,/*c3_4b.c*/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;sca
28、nf(%d%d,问题3.4：思考,其它输入方法及算法？,例如：链表,问题3.4实现了两个多项式相加运算，如何实现两个多项式相乘？,第三讲：程序设计方法-问题分析,50,问题3.5：超长正整数加法,【问题描述】编写程序实现两个超长正整数（每个最长80位数字）的加法运算。【输入形式】从键盘读入两个整数，不考虑输入高位可能为0的情况。1.第一行是超长正整数A；2.第二行是超长正整数B；【输出形式】输出只有一行，是两个长整数的运算结果，从高到低依次输出各位数字。各位数字紧密输出。【输入样例】134098703578230056234098【输出样例】134098703578464154【样例说明】进行
29、两个正整数加法运算，134098703578230056+234098=134098703578464154。,第三讲：程序设计方法-问题分析,51,问题3.5：问题分析,如何读入和存储超长整数？（为何不能用长整数类型long int n;scanf(“%ld”,其它方法？,52,问题3.5：解题思路,在程序中数组是从左至右方式存储的，而整数相加是从右至左（从低位到高位），同时由于被加数长短不一，造成计算和转换非常不方便。一种解决方法是整数相加前将两个整数位串首尾颠倒，与计算机存储方式一致。如何进行超长整数加？无论以什么方式存储超长整数，每位相加结果和进位计算方式为：dighti=(digit
30、1i+digit2i+carry)%10（carry为上一次计算产生的进位）carry=(digit1i+digit2i+carry)/10（得到新的进位）注意：若以字符串方式存储超长整数，则在计算每位加和进位时，应考虑数字字符和整数数字之间的转换。应考虑进位传递问题当较短整数最后一位加完后仍有进位情况，如123456789+678；当较长整数最后一位处理完后仍有进位情况，如9999999+1;,第三讲：程序设计方法-问题分析,53,问题3.5：算法设计,基于上述分析，假设以字符串形式存储整数，其超长整数相加算法如下：char istr181,istr281;int carry,sum;/*c
31、为进位*/（假设istr1中存放的为较长的整数）将istr1和istr2串首尾颠倒；While istr2i!=0 sum=istr1i-0+istr2i-0+carry;istr1i=sum%10+0;carry=sum/10;While istr1i=0 If carry0istr1i=c+0；将istr1串首尾颠倒；,以较短整数为基准，两个整数相加。,考虑较短整数最后一位加完后仍有进位产生。,考虑极端情况较长整数最后一位处理完后仍有进位。如999999999+1,第三讲：程序设计方法-问题分析,54,问题3.5：代码实现,void addLInt(char s1,char s2)int
32、i=0,tmp,c=0;char sLENGTH;if(strlen(s1)strlen(s2)strcpy(s,s1);strcpy(s1,s2);strcpy(s2,s);reverse(s1);reverse(s2);while(s2i!=0)tmp=s1i-0+s2i-0+c;s1i=tmp%10+0;c=tmp/10;i+;while(s1i!=0,/*主函数*/#include#include#define LENGTH 81void reverse(char s)int i,j,c;for(i=0,j=strlen(s)-1;ij;i+,j-)c=si;si=sj;sj=c;void addLInt(char s1,char s2);int main()char intstr1LENGTH,intstr2LENGTH;scanf(%s%s,intstr1,intstr2);addLInt(intstr1,intstr2);printf(%s,intstr1);return 0;,第三讲：程序设计方法-问题分析,55,问题3.5：思考,考虑其它解决方法？在此基础上进一步考虑如何实现超长整数相减、相乘及相除？,
