《C语言程序设计基本方法.ppt》由会员分享,可在线阅读,更多相关《C语言程序设计基本方法.ppt(54页珍藏版)》请在金锄头文库上搜索。
1、高级语言程序设计高级语言程序设计(一一)(C Programming)第三讲:程序设计方法第三讲:程序设计方法-问题分析问题分析本章目标本章目标n了解一般程序设计过程了解一般程序设计过程n通过实例重点掌握问题分析方法通过实例重点掌握问题分析方法l精度计算;精度计算;l输入数据处理;输入数据处理;l字符串操作字符串操作程序设计过程程序设计过程n程序设计过程就是解决问题的过程。程序设计通程序设计过程就是解决问题的过程。程序设计通常包括如下五个步骤:常包括如下五个步骤:问题问题分析分析编码编码算法设计算法设计程序设计步骤程序设计步骤测试测试调试调试有问题有问题无问题无问题分析问题:分析问题:功能功能
2、:需要弄清楚软件要完成的功能;输入输入:如果问题有输入,分析输入是什么及输入数据的类型; 处理处理:对输入数据做什么处理; 输出输出:如果有输出,输出什么数据及输出数据的格式;对于复杂问题,可将问题分解为若干子对于复杂问题,可将问题分解为若干子问题,然后再进行上面的分析。问题,然后再进行上面的分析。算法设计:算法设计: 设计解决问题的具体方案(步骤)。编码:编码: 将算法用高级语言实现。测试:测试: 运行编译连接后得到的执行程序,以验证程序是否按要求 解决了问题,并没有产生副作用。即程序是否做了该做的事,同时没有做不该做的事。调试:调试: 如果程序经测试发现问题,则通过调试手段找到产生错误的代
3、码并修复它。算法算法n任何计算问题的解决都是按指定的顺序执行一系任何计算问题的解决都是按指定的顺序执行一系列动作的结果。解决问题的步骤列动作的结果。解决问题的步骤(动作及动作之间动作及动作之间的顺序的顺序)称为算法(称为算法(algorithm)。)。算法表示算法表示n算法既可以用自然语言表述算法既可以用自然语言表述(如前如前),也可用用半结,也可用用半结构化语言或结构化图形表示,如:构化语言或结构化图形表示,如:read学生成绩值学生成绩值if成绩值成绩值=60print“Pass”elseprint“Fail”读学生成绩值读学生成绩值成绩值成绩值=60输出输出”Fail”输出输出”Pass
4、”真真假假流程图流程图问题问题3.1:计算计算e值值【问题描述问题描述】e(自然对数自然对数)值计算公式为值计算公式为 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:问题分析:问题分析n输
5、入:一个整数(输入:一个整数(整型)整型);n处理:计算处理:计算 公式公式1+1/1!+1/2!+1/n!;n输出:以输出:以%.10f格式输出格式输出(小数后保留小数后保留10位位)n变量:变量:l一个整型变量一个整型变量,用于存储所读入的整数用于存储所读入的整数,如如,intn;l一个双精度浮点变量一个双精度浮点变量(Why?),用于存储计算结果用于存储计算结果,如如doublee;问题问题3.1:算法设计:算法设计n解决问题解决问题3.1的解决过程(算法一):的解决过程(算法一):设计算结果保存在变量设计算结果保存在变量e e中;中;读入一个整数到变量读入一个整数到变量n;n;for(
6、i=0; i=n; i+)for(i=0; i=n; i+) e = e + 1/i!;e = e + 1/i!;输出输出e e值值; ;e=1+1/1!+1/2!+1/n!问题问题3.1:代码实现:代码实现#includeintfact(intn)intf,i;f=1;for(i=2;i=n;i+)f*=i;returnf;intmain()intn,i;doublee=0.0;scanf(%d,&n);for(i=0;i=n;i+)e+=1.0/fact(i);printf(%.10f,e);return0;问题问题3.1:测试:测试n测试数据的考虑测试数据的考虑1.首先选取输入数据区间(
7、首先选取输入数据区间(0=n=30)的正常值)的正常值,如问题如问题3.1中所提供的输入样例;中所提供的输入样例;输入:输入:12期望(正确)输出:期望(正确)输出:2.7182818283输入:输入:13期望(正确)输出:期望(正确)输出:2.71828182842.选取输入数据区间边界附近的值,本例中可选选取输入数据区间边界附近的值,本例中可选取:取:ln=0,期望输出:期望输出:1.0000000000ln=1,期望输出:期望输出:2.0000000000ln=30,期望输出:,期望输出:2.7182818285问题问题3.1:常见问题分析:常见问题分析n以整型计算以整型计算n!,即函数
8、,即函数fact返回整数(观察现象返回整数(观察现象whathappened?)n=13实际输出:实际输出: 2.7182818288(期望输出:期望输出:2.7182818284)Why?如何调试如何调试?数据范围与精度数据范围与精度nint类型数据范围类型数据范围(对于对于IA32结构的计算机结构的计算机):-232-1-232-1-1(即即-21474836482147483647)12!int最大值最大值 13!n修改方法:修改方法:将保存阶乘结果的变量将保存阶乘结果的变量改为改为double类型,并将类型,并将fact的返回类型也改为的返回类型也改为double0!11!12!23!
9、64!245!1206!7207!50408!403209!36288010!362880011!3991680012!47900160013!1932053504(error!,溢出溢出)(正确应为正确应为:6227020800)14!1278945280(error!,溢出溢出)(正确应为正确应为:87178291200)问题问题3.1:修改后的程序:修改后的程序#includedoublefact(intn)inti;doublef=1.0;for(i=1;i=n;i+)f*=i;returnf;intmain()intn,i;doublee=0.0;scanf(“%d”,&n);for
10、(i=0;i=n;i+)e+=1.0/fact(i);printf(“%.10f”,e);return0;n计算结果为计算结果为float类型,即类型,即floate;(观察现象(观察现象whathappened?)n=12实际输出:实际输出:2.7182819841(期望输出:期望输出:2.7182818283)ndouble类型比类型比float类型有更高的精度类型有更高的精度float尾数:尾数:23位,指数:位,指数:8位位double尾数:尾数:52位,指数:位,指数:11位位问题问题3.1:常见问题分析(续):常见问题分析(续)问题问题3.1:另一种方法:另一种方法n观察计算观察计
11、算 公式公式1+1/1!+1/2!+1/n!,可知:,可知:若前一次迭代若前一次迭代1/(n-1)!计算结果为计算结果为fn-1,则本次迭代的结果则,则本次迭代的结果则为为fn=fn-1/n因此,因此,没有必要每次迭代都重新计算没有必要每次迭代都重新计算n!,显然效率会更高,显然效率会更高。n具体算法(解题步骤)为:具体算法(解题步骤)为:给双精度浮点变量给双精度浮点变量e和和 f赋初值赋初值 1.0;for(i=1;i=n;i+)f=f/i;e=e+f;输出输出e问题问题3.1:另一种方法(代码):另一种方法(代码)#includeintmain()intn,i;doublee,fe=f=1
12、.0;scanf(“%d”,&n);for(i=1;i=n;i+)f=f/i;e+=f;printf(“%.10f”,e);return0;考虑为什么循环从考虑为什么循环从i=1开始,而开始,而不从不从i=0开始?开始?17问题问题3.2:简易计算器:简易计算器【问题描述问题描述】编程实现简单的交互式计算器,能进行整数的编程实现简单的交互式计算器,能进行整数的+-*/运算。运算。【输入形式输入形式】从键盘读入如下形式的输入行,数据与运算符之间可以从键盘读入如下形式的输入行,数据与运算符之间可以用一个或用一个或多个空格分隔多个空格分隔:120+350【输入形式输入形式】对于对于+,-及及*运算,
13、输出形式如下:运算,输出形式如下:120+350=470对于对于/运算,输出形式如下(小数后保留两位):运算,输出形式如下(小数后保留两位):5/2=2.5018问题问题3.2:问题分析:问题分析n如何读入数据及运算符?如何读入数据及运算符?l方法一方法一intdata1,data2;charop;scanf(“%d%c%d”,&data1,&op,&data2);l方法二方法二intdata1,data2;charop;scanf(“%d”,&data1);getchar();op=getchar();scanf(“%d”,&data1);不足:数据与运算符之间只能有一个空格分隔不足:数据与
14、运算符之间只能有一个空格分隔输入时,数据输入时,数据与字符之间不与字符之间不能有空格,否能有空格,否则空格作为字则空格作为字符输入。符输入。19问题问题3.2:问题分析:问题分析n如何读入数据及运算符?如何读入数据及运算符?l方法三方法三intdata1,data2;charop;scanf(“%d%c%d”,&data1,&op,&data2);好处:数据与运算符之间可以有多个空格分隔好处:数据与运算符之间可以有多个空格分隔空格使得跳过两次非空格使得跳过两次非空白输入间的所有空空白输入间的所有空白字符。白字符。20问题问题3.2:算法设计:算法设计intdata1,data2,result1
15、;floatresult2;charop;从标准输入中读入整数从标准输入中读入整数data1,运算符,运算符op及整数及整数data2;判断判断op:若为若为+,则,则result1=data1+data2;若为若为-,则,则result1=data1-data2;若为若为*,则,则result1=data1*data2;若为若为/,则,则result2=data1/data2;若若op为为+,-或或*,输出结果,输出结果result1;若若op为为/,输出结果,输出结果result2;op值加运算+减运算乘运算 除运算-*/多路选择多路选择注意:由于注意:由于data1和和data2为整为整
16、数,结果仍为整数。要用数,结果仍为整数。要用强制强制类型类型转换才能得到小数位。转换才能得到小数位。result2=(float)data1/data2;多路选择,可使用多路选择,可使用if-elseif语句实现。在此,语句实现。在此,更适合更适合switch语句。语句。21问题问题3.2:代码实现:代码实现/c3_2.c#includeintmain()intdata1,data2,result1;floatresult2;charop;scanf(“%d%c%d”,&data1,&op,&data2);switch(op)case+:result1=data1+data2;break;ca
17、se-:result1=data1-data2;break;case*:result1=data1*data2;break;case/:result2=(float)data1/data2;break;default:printf(Inputerror!n);break;if(op=+|op=-|op=*)printf(%d%c%d=%dn“,data1,op,data2,result1);elseif(op=/)printf(%d%c%d=%.2fn“,data1,op,data2,result2);return0;测试数据测试数据:120+350121235*23/2123+12123+1
18、2123&1222问题问题3.2:思考(一):思考(一)n本问题程序一次运行只能计算一次。若要能进行多次计算,并用本问题程序一次运行只能计算一次。若要能进行多次计算,并用ctrl+c退出退出程序,如何实现?程序,如何实现?/c3_2c.c#includeintmain()intdata1,data2,result1;floatresult2;charop;for(;)scanf(%d%c%d,&data1,&op,&data2);switch(op)case+:result1=data1+data2;break;case-:result1=data1-data2;break;case*:res
19、ult1=data1*data2;break;case/:result2=(float)data1/data2;break;default:printf(Inputerror!n);continue;if(op=/)printf(%d%c%d=%.2fn,data1,op,data2,result2);elseprintf(%d%c%d=%dn,data1,op,data2,result1);return0;无穷循环,可用无穷循环,可用ctrl+c退出,实际上可退出,实际上可以利用以利用ctrl+c终止任何控制台终止任何控制台C程序的执程序的执行。行。continue语句,语句,跳到下一次循跳
20、到下一次循环。环。n本问题程序一次运行只能进行单运行符计算。若要本问题程序一次运行只能进行单运行符计算。若要使程序能支持多运算符的使程序能支持多运算符的混合运算混合运算,并输入等号,并输入等号(=)结束输入,如,)结束输入,如,1+2-3*5/2-3/2=,如何实现?,如何实现?难点:难点:l如何读入数据及运算符?如何读入数据及运算符?l如何保证计算时运算符的优先级?如何保证计算时运算符的优先级?n更进一步,若要程序支持圆括号来改变计算次序,更进一步,若要程序支持圆括号来改变计算次序,如,如,(1+2-3)*(5-3)/2=,如何实现?如何实现?n如果出现错误的输入,例如输入:如果出现错误的输
21、入,例如输入:4+r=,如何过滤,如何过滤掉错误输入,继续程序的运行?掉错误输入,继续程序的运行?23问题问题3.2:思考(二):思考(二)利用利用scanf的返回值的返回值为了保证运算符的优先级,其为了保证运算符的优先级,其算法分析算法分析:当前当前datai opi datai+1 是否进行是由是否进行是由opi+1决定。当决定。当opi+1为为+,-,=时,立即进行当前运算,否则先进行下一步运算,以此时,立即进行当前运算,否则先进行下一步运算,以此迭代。部分伪代码如下:迭代。部分伪代码如下:scanf(“%d%c”,&data1,&op1);while(op1!=)scanf(“%d%c
22、”,&data2,&op2);while(op2=*|op2=/)scanf(“%d%c”,&data,&op);data2=data2op2data;op2=op;data1=data1op1data2;op1=op2;其它方法其它方法?输入串可表示为输入串可表示为data1 op1 datai opi opi为为+,-,*,/,=因此可采用如下方式读入数据和运算符因此可采用如下方式读入数据和运算符:scanf(“%d%c”,&data1,&op1);while(op!=).scanf(“%d%c”,&data2,&op2);格式化输入函数格式化输入函数intscanf(“.”,)n该函数根
23、据格式化字符串中的格式控制字符,将该函数根据格式化字符串中的格式控制字符,将输入流中的信息转换成相应的数据类型;输入流中的信息转换成相应的数据类型;n返回返回成功转换并赋值的输入项个数成功转换并赋值的输入项个数;n若格式完全匹配失败,则返回若格式完全匹配失败,则返回0;n若遇到输入结束,则返回若遇到输入结束,则返回EOF;n将过滤掉出现的空白字符(空格、制表符、换行将过滤掉出现的空白字符(空格、制表符、换行符)。符)。n一次性读入所有数据:一次性读入所有数据:num=scanf(“%d%c%d”,&data1,&op,&data2);根据根据num的值判断各种情况。的值判断各种情况。n利用利用
24、getchar输入函数循环读入一行字符,逐个分输入函数循环读入一行字符,逐个分析各个字符进行数据组装和判断;析各个字符进行数据组装和判断;n利用利用gets函数读入一行字符串,逐个分析各个字函数读入一行字符串,逐个分析各个字符进行数据组装和判断。符进行数据组装和判断。问题问题3.2:其它读取方法:其它读取方法问题问题3.3扩展字符扩展字符【问题描述问题描述】编写程序将含有缩记符号的字符串扩展为等价的完整字符串,例如将编写程序将含有缩记符号的字符串扩展为等价的完整字符串,例如将a-d扩展为扩展为abcd。该程序可以处理大小写字母和数字,并可以处理。该程序可以处理大小写字母和数字,并可以处理a-b
25、-c、a-z0-9与与-a-z等等类似的情况。要求扩展符类似的情况。要求扩展符-两边的字符只要右边的大于左边就扩展(即两边的字符只要右边的大于左边就扩展(即Z-b情情况也要扩展),并且况也要扩展),并且-两边不能有空格。两边不能有空格。【输入形式输入形式】从键盘输入包含扩展符的字符串,字符串中可以包含空格从键盘输入包含扩展符的字符串,字符串中可以包含空格【输出形式输出形式】输出扩展后的字符串输出扩展后的字符串【输入样例输入样例1】a-c-u-B【输出样例输出样例1】abcdefghijklmnopqrstu-B【输入样例输入样例2】a-b-ca-a0-4【输出样例输出样例2】abca-a012
26、34【样例说明样例说明】扩展输入扩展输入a-c-u为:为:abcdefghijklmnopqrstu,而,而B比比u值小,所以无法扩展,直值小,所以无法扩展,直接输出。接输出。27问题问题3.3:问题分析:问题分析n如何读入一个包含空格的字符串?(不能用如何读入一个包含空格的字符串?(不能用scanf函数,为什么?)函数,为什么?)l方法一:方法一:charc,s512;for(i=0;(c=getchar()!=n;i+)si=c;si=0;l方法二(简单):使用方法二(简单):使用gets标准库函数标准库函数gets(s);注意注意:不要忘记加:不要忘记加字符串最后的结束字符串最后的结束符
27、(符(0)!)!行输入、输出行输入、输出n行输入函数:行输入函数:char*gets(chars)从标准输入读取完整的一行,将读取的内容存入从标准输入读取完整的一行,将读取的内容存入s字符数组中,并用字符数组中,并用字符串结束符字符串结束符0取代行尾的取代行尾的n。若读取错误或遇到输入结束则返回。若读取错误或遇到输入结束则返回NULL。n行输出函数行输出函数intputs(chars)将字符数组将字符数组s中的内容输出到标准输出上,并中的内容输出到标准输出上,并自动自动在末尾添加一个换行符在末尾添加一个换行符。问题问题3.3问题分析问题分析S1i-S1i+2S2ifs1i+1=-&s1is1i
28、+2先将要扩展的字符串读到一个字符数组先将要扩展的字符串读到一个字符数组(s1)中;中;设另一个字符数组用于存放扩展后的字设另一个字符数组用于存放扩展后的字符串符串(s2);依次依次检查所读入字符串检查所读入字符串(s1)中字符;中字符;将将s1i原封不动的写到原封不动的写到s2中;中;当当s1i+1=-&s1is1i+2时,时,将将s1i至至s1i+2之间的字符展开到之间的字符展开到s2中中问题问题3.3算法算法设字符数组设字符数组s1用来读入字符串,用来读入字符串,s2用来存放扩展后字符串;用来存放扩展后字符串;从标准输入中读入字符串到从标准输入中读入字符串到s1中;中;whiles1i!
29、=0将将s1当前字符放到当前字符放到s2中,即中,即s2j=s1i;ifs1i+1=-&s1is1i+2将将s1i与与s1i+2区间字符写到区间字符写到s2中;中;将当前将当前s1读位置移至读位置移至s1i+2,即即i=i+2;否则否则i i加加1 1;给给s2置结束符,即置结束符,即s2j=0;输出字符串输出字符串s2;i初始化为初始化为0;j初始化为初始化为0;问题问题3.3程序实现程序实现#include#defineMAXLINE512intmain()charc,s1MAXLINE,s2MAXLINE;inti,j;i=j=0;gets(s1);while(s1i!=0)s2j+=s
30、1i;if(s1i+1=-&s1is1i+2)for(c=s1i+1;cs1i+2;c+)s2j+=c;i=i+2;elsei+;s2j=0;puts(s2);return0;问题问题3.3:测试:测试测试数据测试数据期望结果期望结果数据类型数据类型a-dabcd正常a-c-u-Babcdefghijklmnopqrstu-B特特殊殊a-dd-aabcdd-a特特殊殊Z-bZ_ab特殊特殊a-b-cabc边界边界-a-8-a-8非正常a-aa-a非正常问题问题3.3:常见问题及分析:常见问题及分析n处理带空格的输入串处理带空格的输入串l不要用不要用scanf来读输入串,建议用来读输入串,建议用
31、getchar或或gets来读输入串;来读输入串;n字符串没有结束标志字符串没有结束标志l在用在用getchar读入一个字符串及生成扩展字符读入一个字符串及生成扩展字符串串s2时,一定要给字符串置一个结束符时,一定要给字符串置一个结束符(0);(通过实例演示一下现象);(通过实例演示一下现象)问题问题3.3:常见问题及分析(续):常见问题及分析(续)n用用a-d,a-b,a-d-g作输入观察下面程序现象。作输入观察下面程序现象。如何调试如何调试?/c3_3a.c#include#defineMAXLINE512intmain()charc,s1MAXLINE,s2MAXLINE;inti,j;
32、i=j=0;gets(s1);while(s1i!=0)s2j+=s1i;if(s1i+1=-&s1is1i+2)for(c=s1i+1;c=s1i+2;c+)s2j+=c;i=i+3;elsei+;s2j=0;puts(s2);return0;问题问题3.3:其它方法:其它方法n其实在上述代码实现中,数组其实在上述代码实现中,数组s2可以省略,如:可以省略,如:/c3_3b.c#include#defineMAXLINE512intmain()charc,s1MAXLINE;inti=0;gets(s1);while(s1i!=0)putchar(s1i);if(s1i+1=-&s1is1i
33、+2)for(c=s1i+1;cs1i+2;c+)putchar(c);i=i+2;elsei+;putchar(n);return0;其它方法?其它方法?问题问题3.3:思考:思考n若要求扩展符若要求扩展符-两边的字符为同类两边的字符为同类(即均为小写即均为小写字母、大写字母或数字字符),即字母、大写字母或数字字符),即出现出现Z-b、8-B这种情况将不扩展,程序如何修改?这种情况将不扩展,程序如何修改?其实在扩展字符操作前其实在扩展字符操作前if(s1i+1=-&s1is1i+2)增加一个判断扩展符两边的字符是否同类的函数即可。增加一个判断扩展符两边的字符是否同类的函数即可。if(s1i+
34、1=-&s1is1i+2&isCongener(s1i,s1i+2)判断两个字符是否是同类的函数实现如下:判断两个字符是否是同类的函数实现如下:intisCongener(charc1,charc2)if(isupper(c1)&isupper(c2)return1;if(islower(c1)&islower(c2)return1;if(isdigit(c1)&isdigit(c2)return1;return0;isupper,islower,isdigit均为系统标准库均为系统标准库函数。使用前要加:函数。使用前要加:#include#includeinta1000,j;voidexpa
35、nd(ints1000,inti)intk;j=0;for(k=0;ki;+k)if(sk=-&sk-1sk+1)for(;aj-1sk+1;+j)aj=+sk-1;+k;elseaj=sk;+j;main()ints1000,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多项式相加多项式相加【问题描述问题描述】编写一个程序实现两个一元多项式相加编写一个程序实现两个一元多项式相加的运算。的运算。【输入形式输入形式】从标准
36、输入中读入两行以空格分隔的整从标准输入中读入两行以空格分隔的整数,每一行代表一个多项式,且该多项式中各项的系数,每一行代表一个多项式,且该多项式中各项的系数均为数均为0或正整数,最高幂次不超过或正整数,最高幂次不超过50。对于多项式。对于多项式anxn+an-1xn-1+a1x1+a0x0(n50)的表示方)的表示方法如下:法如下:annan-1n-1a11a00即相邻两个整数分别表示表达式中一项的系数和指数。即相邻两个整数分别表示表达式中一项的系数和指数。在输入中只出现系数不为在输入中只出现系数不为0的项。的项。【输出形式输出形式】将运算结果输出到屏幕。将系数不为将运算结果输出到屏幕。将系数
37、不为0的项按指数从高到低的顺序输出,每次输出其系数和的项按指数从高到低的顺序输出,每次输出其系数和指数,均以一个空格分隔。在行的末尾也输出一个空指数,均以一个空格分隔。在行的末尾也输出一个空格符,并且最后要求换行。格符,并且最后要求换行。问题问题3.4多项式相加(续)多项式相加(续)【样例输入样例输入】54826732517804374281【样例输出样例输出】548437267342331780【样例说明样例说明】输入文件的两行分别代表了表达式输入文件的两行分别代表了表达式54x8+2x6+7x3+25x+7843x7+4x2+8x其和为其和为54x8+43x7+2x6+7x3+4x2+33
38、x+78问题问题3.4问题分析问题分析n如何读取输入的数据?如何读取输入的数据?l输入的数据个数未知(不超过输入的数据个数未知(不超过100)l每行数据输入时没有结束标志每行数据输入时没有结束标志n如何保存输入的多项式系数和指数如何保存输入的多项式系数和指数问题问题3.4:问题分析(续):问题分析(续)n如何读取输入的数据?如何读取输入的数据?设变量设变量a,na,n分别存储读入项和相应项系数;分别存储读入项和相应项系数;while(1)while(1)scanf(scanf(“%d%d%c%d%d%c”, &a, &n, &c);, &a, &n, &c);保存保存a a和和n;n;if(c
39、 = if(c = nn) ) break; break; 或或do do scanf(scanf(“%d%d%c%d%d%c”, &a, &n, &c);, &a, &n, &c);保存保存a a和和n;n; while(c != while(c != nn););5482673251780break语句,用语句,用于跳出循环。于跳出循环。do_while循环,一循环,一种在循环尾部进行种在循环尾部进行判断的循环。判断的循环。缺点是回车之前缺点是回车之前不能有空格不能有空格.问题问题3.4:问题分析(续):问题分析(续)0a01a1n-1an-1nan5482673251780a0a1a2a
40、3an-2an-1an0123n-2n-1n将将an保存在下标为保存在下标为n的数组元素中,数组长度为的数组元素中,数组长度为51(050),即即arrayn=a;n如何保存输入的多项式系数和指数?如何保存输入的多项式系数和指数?问题问题3.4:算法设计:算法设计1.1.令:令:int array151,int array251;int array151,int array251;分别用来分别用来存储第一个多项式和第二个多项式;存储第一个多项式和第二个多项式;2.2.初始化数组初始化数组array1array1和和array2array2元素值均为元素值均为0 0;3.3.读入第一行数据保存在
41、数组读入第一行数据保存在数组array1array1中;中;4.4.读入第二行数据保存在数组读入第二行数据保存在数组array2array2中;中;5.5.依次将数组依次将数组array1array1和和array2array2相应元素相加,并将相应元素相加,并将结果放到结果放到array1array1中,即中,即array1i=array1i+array2iarray1i=array1i+array2i;6.6.依次从后往前输出数组依次从后往前输出数组array1array1中不为中不为0 0的元素。的元素。用一个函数来分别读入两用一个函数来分别读入两个多项式的系数和指数,个多项式的系数和指
42、数,如,如,voidgetExp(inta);问题问题3.4:代码实现:代码实现/c3_4.c#include#defineLENGTH51voidgetExp(intarray);intmain()intarray1LENGTH,array2LENGTH,i;for(i=0;iLENGTH;i+)array1i=0;for(i=0;iLENGTH;i+)array2i=0;getExp(array1);getExp(array2);for(i=0;i=0;i-)if(array1i0)printf(%d%d,array1i,i);printf(n);voidgetExp(intarray)i
43、nta,n;charc;doscanf(“%d%d%c”,&a,&n,&c);arrayn=a;while(c!=n);初始化数组初始化数组从标准输入中读从标准输入中读数据到数组中数据到数组中两多项式相应项两多项式相应项相加相加输出多项式系数输出多项式系数不为不为0的项。的项。问题问题3.4:测试:测试n正常数据:正常数据:5482673251780 4374281 期望结果:期望结果:548437267342331780 n边界数据边界数据1:1055023494625121570 2035022482125132912000 期望结果:期望结果:3085023492248672513221
44、12570 n边界数据边界数据2:1250 250 期望结果:期望结果:1250250 问题问题3.4:常见问题分析:常见问题分析n未初始化数组(未初始化数组(观察下面用正常测试数据程序运行时现象,观察下面用正常测试数据程序运行时现象,如何调试?)如何调试?)/c3_4a.c#include#defineLENGTH51voidgetExp(intarray);intmain()intarray1LENGTH,array2LENGTH,i;getExp(array1);getExp(array2);for(i=0;i=0;i-)if(array1i0)printf(%d%d,array1i,i
45、);printf(n);问题问题3.4:常见问题分析(续):常见问题分析(续)n最后一对数据没有读入,例如:(最后一对数据没有读入,例如:(观察用正常测试数据程序观察用正常测试数据程序运行时现象,如何调试?)运行时现象,如何调试?)/*c3_4b.c*/voidgetExp(intarray)inta,n,c;scanf(%d%d,&a,&n);while(c=getchar()!=n)arrayn=a;scanf(%d%d,&a,&n);n 如何修改?修改方法一:修改方法一:voidgetExp(intarray)inta,n,c;scanf(%d%d,&a,&n);while(c=getc
46、har()!=n)arrayn=a;scanf(%d%d,&a,&n);arrayn=a;修改方法二:修改方法二:voidgetExp(intarray)inta,n,c;scanf(%d%d,&a,&n);arrayn=a;while(c=getchar()!=n)scanf(%d%d,&a,&n);arrayn=a;问题问题3.4:思考:思考n其它输入方法及算法?其它输入方法及算法?例如:链表例如:链表n问题问题3.4实现了两个多项式相加运算,如何实现两实现了两个多项式相加运算,如何实现两个个多项式相乘多项式相乘?第三讲:程序设计方法-问题分析49问题问题3.5:超长正整数加法:超长正整数
47、加法【问题描述问题描述】编写程序实现两个超长正整数(每个最长编写程序实现两个超长正整数(每个最长80位数字)的加法运算。位数字)的加法运算。【输入形式输入形式】从键盘读入两个整数,不考虑输入高位可能为从键盘读入两个整数,不考虑输入高位可能为0的情况。的情况。1.第一行是超长正整数第一行是超长正整数A;2.第二行是超长正整数第二行是超长正整数B;【输出形式输出形式】输出只有一行,是两个长整数的运算结果,从高到低依次输出各位数字。输出只有一行,是两个长整数的运算结果,从高到低依次输出各位数字。各位数字紧密输出。各位数字紧密输出。【输入样例输入样例】134098703578230056234098【
48、输出样例输出样例】134098703578464154【样例说明样例说明】进行两个正整数加法运算,进行两个正整数加法运算,134098703578230056 + 234098 = 134098703578230056 + 234098 = 134098703578464154134098703578464154。第三讲:程序设计方法-问题分析50问题问题3.5:问题分析:问题分析n如何读入和存储超长整数?(如何读入和存储超长整数?(为何不能用长整数类型为何不能用长整数类型longintn;scanf(“%ld”,&n);来存储和读入超长整数来存储和读入超长整数?)?)l方法一:用字符串方式来
49、读入和存储超长整数方法一:用字符串方式来读入和存储超长整数charintstr81;scanf(“%s”,intstr);l方法二:用整数数组来存储超长整数,用字符方式依次方法二:用整数数组来存储超长整数,用字符方式依次读入超长整数的每位数字读入超长整数的每位数字intlint80;chard,i=0;while(d=getchar()!=n)linti+=d0;l其它方法?其它方法?51问题问题3.5:解题思路:解题思路n在程序中在程序中数组是从左至右方式存储的数组是从左至右方式存储的,而,而整数相加是从右至左整数相加是从右至左(从低位到高(从低位到高位),同时由于被加数长短不一,造成计算和
50、转换非常不方便。一种解决方位),同时由于被加数长短不一,造成计算和转换非常不方便。一种解决方法是法是整数相加前将两个整数位串首尾颠倒整数相加前将两个整数位串首尾颠倒,与计算机存储方式一致。,与计算机存储方式一致。n如何进行超长整数加?如何进行超长整数加?无论以什么方式存储超长整数,每位相加结果和进位计算方式为:无论以什么方式存储超长整数,每位相加结果和进位计算方式为:dightdighti i = (digit1 = (digit1i i + digit2 + digit2i i + carry) % 10 + carry) % 10 (carrycarry为上一次计算产生的进位)为上一次计算
51、产生的进位)carry = (digit1carry = (digit1i i + digit2 + digit2i i + carry) / 10 + carry) / 10 (得到新的进位)(得到新的进位)注意:注意:l 若以字符串方式存储超长整数,则在计算每位加和进位时,应考虑若以字符串方式存储超长整数,则在计算每位加和进位时,应考虑数字字符和整数字字符和整数数字之间的转换数数字之间的转换。l 应考虑进位传递问题应考虑进位传递问题当当较短整数最后一位加完后仍有进位情况较短整数最后一位加完后仍有进位情况,如,如123456789+678123456789+678;当当较长整数最后一位处理完
52、后仍有进位情况较长整数最后一位处理完后仍有进位情况,如,如9999999+1;9999999+1;第三讲:程序设计方法-问题分析52问题问题3.5:算法设计:算法设计n基于上述分析,假设以字符串形式存储整数,其超长整数相加算法如下:基于上述分析,假设以字符串形式存储整数,其超长整数相加算法如下:char istr181, istr281;int carry,sum; /*cchar istr181, istr281;int carry,sum; /*c为进位为进位* */ /(假设(假设istr1istr1中存放的为较长的整数)中存放的为较长的整数)将将istr1istr1和和istr2ist
53、r2串首尾颠倒;串首尾颠倒;While istr2i != While istr2i != 00 sum = istr1i-sum = istr1i-0 0+istr2i-+istr2i-0 0+carry;+carry;istr1i=sum%10+istr1i=sum%10+0 0; ;carry=sum/10;carry=sum/10;While istr1i=While istr1i=00 & carry & carrysum = istr1i-sum = istr1i-0 0+carry;+carry;istr1i=sum%10+istr1i=sum%10+0 0; ;carry=su
54、m/10;carry=sum/10;If carry0If carry0istr1i=c+istr1i=c+0 0;将将istr1istr1串首尾颠倒;串首尾颠倒;以较短整数为基准,两个整以较短整数为基准,两个整数相加。数相加。考虑较短整数最后一位加完考虑较短整数最后一位加完后仍有进位产生。后仍有进位产生。考虑极端情况较长整数最后考虑极端情况较长整数最后一位处理完后仍有进位。如一位处理完后仍有进位。如999999999+1第三讲:程序设计方法-问题分析53问题问题3.5:代码实现:代码实现voidaddLInt(chars1,chars2)inti=0,tmp,c=0;charsLENGTH;
55、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&c)tmp=s1i-0+c;s1i=tmp%10+0;c=tmp/10;i+;if(c)s1i+=c+0;s1i=0;reverse(s1);/*主函数主函数*/#include#include#defineLENGTH81voidreverse(chars)inti,j,c;for(i=0,j=strlen(s)-1;ij;i+,j-)c=si;si=sj;sj=c;voidaddLInt(chars1,chars2);intmain()charintstr1LENGTH,intstr2LENGTH;scanf(%s%s,intstr1,intstr2);addLInt(intstr1,intstr2);printf(%s,intstr1);return0;第三讲:程序设计方法-问题分析54问题问题3.5:思考:思考n考虑其它解决方法?考虑其它解决方法?n在此基础上进一步考虑如何实现超长整数相减、在此基础上进一步考虑如何实现超长整数相减、相乘及相除?相乘及相除?