习题课程序设计题.ppt

第1页,程序设计的一般步骤,分析题意，明确问题的性质数值计算/事务处理/逻辑分析/等建立问题的描述模型数学模型/过程模型设计/确定算法数学问题：分析解/数值解的求解算法非数学问题：数据结构/算法分析与设计一般方法：穷举/递推/递归/分治/回溯/.编程调试分析运行结果，如有必要，进一步优化,穷举法编程思路,第2页,数学模型适宜进行穷举的数学模型决定程序是否正确穷举的范围一般用多重循环方式注意控制每重循环的边界,第3页,典型数值问题-例6,例4：百钱百鸡问题。中国古代数学家张丘建在他的算经中提出了著名的“百钱百鸡问题”：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，翁、母、雏各几何?问题分析与算法设计设：要买x只公鸡，y只母鸡，z只小鸡，可得到方程:x+y+z=1005x+3y+z/3=100取值范围：0=x、y、z=100可以采用穷举法求解。,将变量x、y、z的所有取值可能代入方程进行计算,第4页,典型数值问题-例6,穷举法基本思路当x=0,y=0,z=0时：是否满足方程z=1时：是否满足方程z=2时：是否满足方程.z=100时：是否满足方程当x=0,y=1,z=0时：是否满足方程z=1时：是否满足方程.z=100时：是否满足方程当x=0,y=2,z=0时：是否满足方程.当x=100,y=100,z=100时：.,z=100,z+,z=0,y=100,y+,y=0,x=100,x+,x=0,开始,结束,第5页,典型数值问题-例6,程序,#includevoidmain()intx,y,z,j=0;for(x=0;x=100;x+)for(y=0;y=100;y+)for(z=0;z=100;z+)if(x+y+z=100,第6页,典型数值问题-例6,#includevoidmain()intx,y,z,j=0;for(x=0;x=100;x+)for(y=0;y=100;y+)for(z=0;z=100;z+)if(x+y+z=100,x,运行结果：1:cock=0hen=25chicken=752:cock=3hen=20chicken=773:cock=4hen=18chicken=784:cock=7hen=13chicken=805:cock=8hen=11chicken=816:cock=11hen=6chicken=837:cock=12hen=4chicken=84,例C3,第7页,典型数值问题-例6,丢失重要条件：z应该能够被整除。#includevoidmain()intx,y,z,j=0;for(x=0;x=20;x+)for(y=0;y=33;y+)for(z=0;z=100;z+)if(z%3=0运行程序，正确的结果：1:cock=0hen=25chicken=752:cock=4hen=18chicken=783:cock=8hen=11chicken=814:cock=12hen=4chicken=84,第8页,典型数值问题-例6,优化程序：for(x=0;x=20;x+)for(z=0;z100;z+=3)y=100-x-z;if(5*x+3*y+z/3=100)printf(%2d:cock=%2dhen=%2dchicken=%2dn,+j,x,y,z);优化程序：for(x=0;x=20;x+)for(y=0;y=(100-5*x)/3;y+)z=100-x-y;if(z%3=0,第9页,趣味程序百例20：一个奇异三位数,问题一个自然数的七进制表达式是一个三位数，而这个自然数的九进制表示也是一个三位数，且这两个三位数的数码顺序正好相反，求这个三位数。问题分析与算法设计设七进制数形式为kji：则九进制表示的形式就为ijk。取值范围：1=i、k=60=j=6将9进制数转化为十进制：,将7进制数转化为十进制：,i*9*9+j*9+k,i+j*7+k*7*7,使用穷举法,第10页,趣味程序百例20：一个奇异三位数,程序说明与注释voidmain()inti,j,k;for(i=1;i7;i+)/*穷举9进制的第1位数*/for(j=0;j7;j+)/*穷举9进制的第2位数*/for(k=1;k7;k+)/*穷举9进制的第3位数*/if(i*9*9+j*9+k=i+j*7+k*7*7)printf(%d%d%d(7)=%d%d%d(9)=%d(10)n,k,j,i,i,j,k,i*9*9+j*9+k);运行结果503(7)=305(9)=248(10),例C100_20,第11页,趣味程序百例21：4位反序数,问题设N是一个4位数，它的9倍恰好是其反序数，求N。反序数就是将整数的数字倒过来形成的整数。例如：1234的反序数是4321。问题分析与算法设计设整数的千、百、十、个位为i、j、k、l，则满足：(i*103+j*102+10k+l)*9=(l*103+k*102+10j+i)程序说明与注释main()inti;for(i=1002;i0)则i为整数的平方。可以采用试探的方法：令m从1开始逐步增加进行试探。,m=m+1,成立,不成立,输入一个整数i,输出m和i,开始,结束,设试探初值m=1,成立,不成立,第13页,典型数值问题-例2,scanf(”%d”,inti,m;,第14页,典型数值问题-例2,#include”stdio.h”intmain()inti,m;scanf(”%d”,for(m=1;m*mi;m+)；,如果采用for语句该如何修改？,表达式1,表达式2,表达式3,for语句的循环体是什么？,循环体为空语句,第15页,典型数值问题-例3,例3：某地，车牌4位数字，首位非0.一辆卡车违犯交通规则逃逸。现场3人目击但都没有记住车号，只记得一些特征。甲说：牌照的前两位数字是相同的；乙说：牌照的后两位数字是相同的，但与前两位不同；丙是位数学家，他说：四位的车号刚好是一个整数的平方。请根据以上线索尝试找出车号。问题分析与算法设计按照题目的要求造出一个前两位数(i)相同、后两位数(j)相同且相互间又不同的整数。0=31）,第16页,典型数值问题-例3,0=31）,i=9?,j=0,成立,不成立,i=1,k=1100*i+11*j,i!=j?,成立,不成立,k是平方?,成立,不成立,输出：k，i，j,j+,j=9?,成立,不成立,i+,结束,for(i=1;i=9;i+),for(j=0;j=9;j+),if(i!=j),k=1100*i+11*j;判断k是否平方;,第17页,典型数值问题-例3,#include”stdio.hvoidmain()inti,j,k,m;for(i=1;i=9;i+)/*i:车号前二位的取值*/for(j=0;jm10的整数采用穷举法求解。,第19页,典型数值问题-例4-IQ游戏,voidmain()intx,y,m,flag;/*flag：标志变量*/for(x=0,flag=1;flag;x+)/*穷举x*/y=100+x;/*计算y*/for(m=1;m*my;m+);if(m*m=y)/*判断y是否为一个数的平方*/for(;m*my+68;m+);if(m*m=y+68)/*判断y+68*/printf(%dn,x);flag=0;/*flag置0，结束循环*/,例200-IQ,第20页,典型数值问题-例4-IQ游戏1,voidmain()inty,m,flag;/*flag：标志变量*/for(y=101,flag=1;flag;y+)/*穷举y*/for(m=1;m*my;m+);if(m*m=y)/*判断y是否为一个数的平方*/for(;m*my+68;m+);if(m*m=y+68)/*判断y+68*/printf(”%dn”,y-100);flag=0;/*flag置0，结束循环*/,例200-IQ1,第21页,典型数值问题-例4-IQ游戏2,#includevoidmain()intm,n,flag;/*flag：标志变量*/for(m=10,flag=1;flag;m+)/*通过穷举m，直接构造平方数y*/for(n=1;n*nm*m+68;n+);/*判断m*m+68是否为平方数*/if(n*n=m*m+68)printf(”%dn”,m*m-100);flag=0;/*flag置0，结束循环*/,例200-IQ2,第22页,典型数值问题-百例8：借书方案知多少?,问题小明有5本新书，要借给、三位小朋友，若每人每次只能借一本，则可有多少种不同的借法？问题分析与算法设计这是一个排列问题，即求从中取的排列数。对5本书从1至5编号，假设三个人分别借这5本书中的1本。当a=i时，表示a借了编号为i的书。当3个人所借的书的编号都不相同时，就是满足题意的一种借阅方法。假设：三个人为a、b、c，则它们的取值范围为：1=a、b、c=5且当：a!=bfor(a=1;a=5;a+)for(b=1;b=5;b+)for(c=1;a!=b/*60种*/,例C100_8,第24页,趣味程序百例40：三色球问题,问题若一个口袋中放有12个球，其中有3个红的，3个白的和6个黑的，问从中任取8个共有多少种不同的颜色搭配？问题分析与算法设计设：任取的红球个数为i，白球个数为j，则黑球个数为：8-i-j据题意红球i和白球j个数的取值范围是03，在红球和白球个数确定的条件下，黑球个数取值应为8-i-j=6。,第25页,趣味程序百例40：三色球问题,程序说明与注释voidmain()inti,j,count=0;printf(REDBALLWHITEBALLBLACKBALLn);printf(-n);for(i=0;i=3;i+)/*任取红球的个数03*/for(j=0;j=3;j+)/*任取白球的个数03*/if(8-i-j)=6)printf(%2d:%d%d%dn,+count,i,j,8-i-j);,例C100_40,第26页,趣味程序百例48：新娘和新郎,问题三对情侣参加婚礼，三个新郎为、，三个新娘为、。有人不知道谁和谁结婚，于是询问了六位新人中的三位，但听到的回答是这样的：说他将和结婚；说她的未婚夫是；说他将和结婚。这人听后知道他们在开玩笑，全是假话。请编程找出谁将和谁结婚。问题分析与算法设计设：a、b、c三人用1、2、3表示，将x和a结婚表示为x1，将y不与a结婚表示为y!=1。则：x!=1不与结婚x!=3的未婚夫不是z!=3不与结婚题意还隐含：x!=y且x!=z且y!=z,第27页,趣味程序百例48：新娘和新郎,程序与说明voidmain()intx,y,z;for(x=1;x=3;x+)/*穷举X的全部可能配偶*/for(y=1;y=3;y+)/*穷举Y的全部可能配偶*/for(z=1;z=3;z+)/*穷举Z的全部可能配偶*/if(x!=1,例C100_48,字符输出图形编程思路,从具体输入值入手，寻找规律运用分支语句或循环语句，控制程序流程,第28页,第29页,典型非数值(图型)问题-例1,例1：在一行中输出m个*号。要求：从键盘输入m值，输出一行m个*号。例：输入m=4，输出的图形如下：*,基本语句：输出一个*号：ptintf(”*”);或putchar(*);基本算法：1.输入m2.重复输出m个*；3.输出一个n,scanf(”%d”,第30页,典型非数值(图型)问题-例1,#includeintmain()intm;scanf(”%d”,#includevoidmain()intm;scanf(”%d”,C语言中的一行都是以n为标志,第31页,典型非数值(图型)问题-例2,例2：输出边长为m的正方型要求：从键盘输入m值，输出m行每行m个*号。例：输入m=4，输出的图形如下：*算法分析与设计：1.输入m，2.重复输出m行，每行输出m个*；细化1：1.输入m；2.for(k=1;k=m;k+)输出一行中的m个*；,第32页,典型非数值(图型)问题-例2,细化2：1.输入m；2.for(k=1;k=m;k+)输出m个*；换新行;细化3：1.输入m；2.for(k=1;k=m;k+)for(j=1;j=m;j+)printf(”*”)；printf(”n”);,第33页,典型非数值(图型)问题-例2,整理，得到程序如下：#includevoidmain()intk,m,j；scanf(”%d”,j+)/*输出一行中的m个*号*/printf(”*”)；printf(”n”)；分析方法逐步求精法对于比较复杂问题，不可能一下得到程序，可以先将简单的部分明确出来，再逐步对复杂部分进行细化，一步一步推出完整程序。,例C3_2,第34页,典型非数值(图型)问题-例3,例3：输出边长为m的菱型例：输入m=4，输出的图形如下：*,算法分析与设计：在正方型每行*号的前面先多输出若干个空格。对于第k行，0km，则应先输出个空格。,m-k,第35页,典型非数值(图型)问题-例2,输出正方型程序：#includeintmain()intk,m,j；scanf(”%d”,for(i=1;i=m-k;i+)printf(”);,inti;,第36页,典型非数值(图型)问题-例2,输出菱型程序：#includeintmain()intk,m,j,i；scanf(”%d”,第37页,典型非数值(图型)问题-例3,例3：从键盘输入h值，输出h行用*号组成等腰三角形。例：输入h=4，输出的图形如下：*,1*2*3*4*,要输出个空格和个*,分析：1、按行输出。输出h行。2、程序的关键是：找出每一行中要输出空格的数量和*的数量3、对于图形中的第k行(1=k=h)：,h-k,2k-1,第38页,典型非数值(图型)问题-例3,分析：要输出h-k个空格和2k-1个*算法设计1.输入h;2.重复打印h行。对于第k行，每行h-k个空格和2k-1个*对第2步进行加细：2.0for(k=1;k=h;k+)/*h行*/重复打印h-k个空格；重复打印2k-1个*；换行；,第39页,典型非数值(图型)问题-例3,程序：#includevoidmain()inth,k,j;scanf(”%d”,例C3_7302,怎样输出一个等腰梯型？,第40页,典型非数值(图型)问题-例3,*h=4换一个思路分析：对于第k行(1=k=h)：需要输出h+k-1个字符（空格或*号）对第k行的第j个字符，若j=h-k输出空格其它情况输出*算法设计for(k=1;k=h;k+)/*重复打印h行*/for(j=1;j=h+k-1;j+)/*输出一行内的字符*/if(j=h-k)打印空格；else打印*号；换行；,第41页,典型非数值(图型)问题-例3,程序：#includevoidmain()inth,k,j;scanf(”%d”,例C3_73021,第42页,典型非数值(图型)问题-例4,例4：从键盘输入h值，输出用*号组成的正菱形。例：输入h=4，输出的图形如下：*,分析：1.h为上三角形的高度，总行数为。2.对于第j行，若要输出m个空格和n个*号。3.当j=h时，为上三角，则：m=,n=4.当时，为下三角，则：m=n=,1234567,空格数量3*号数量1231507152331,2h-1h-j2j-1hj=2h-1j-h总宽度-空格=2h-1-2(j-h)=4h-1-2j,第43页,典型非数值(图型)问题-例4,算法设计for(j=1;j=2*h-1;j+)控制打印行若为上三角j=h则：m=h-j；n=2j-1否则：m=j-h；n=4h-1-2j重复打印m个空格重复打印n个*；换行；加细循环体if(j=h)m=h-j;n=2*j-1;elsem=j-h;n=4*h-1-2*j;for(k=1;k=m;k+)printf();for(k=1;k=n;k+)printf(*);printf(n);,第44页,典型非数值(图型)问题-例4,程序：#includevoidmain()inth,k,j,m,n;printf(EnterH:);scanf(%d,例C3_7303,第45页,典型非数值(图型)问题-例4,程序2：#includevoidmain()inth,k,j,m,n;printf(EnterH:);scanf(%d,第46页,典型非数值(图型)问题-例4,例4：从键盘输入h值，输出用*号组成的正菱形。例：输入h=4，输出的图形如下：*,分析：1.h为上三角形的高度，行范围。2.对于第j行，若要输出m个空格和n个*号。3.则：m=,n=,-3-2-10123,空格数量3*号数量1231507152331,-(h-1)h-1|j|2(h-m)-1,第47页,典型非数值(图型)问题-例4,程序3：#includevoidmain()inth,k,j,m,n;printf(EnterH:);scanf(%d,例C3_73032,第48页,例5：打印数字魔方。要求：从键盘输入m，输出m行的数字方阵。例：输入m=5，输出的图形如下：1234523451345124512351234分析：1.重复打印m行。,典型非数值(图型)问题-例5,2.第i行的第一个数字为i，之后依次递增，但以m为模：aij=(i+j-2)%m+1,输出项aij与行i、列j的关系,第49页,典型非数值(图型)问题-例5,程序：#includevoidmain()inti,j,m;printf(EnterM:);scanf(%d,例C3_7304,第50页,例6：打印回形方阵要求：从键盘输入边长m，输出回形方阵。例：输入m=5，m=6，输出的图形如下：11111111111122211222211232112332112221m=5123321m=611111122221111111分析：关键是找出aij与行i和列j的关系,典型非数值(图型)问题-例6,第51页,将图形分为四个区：11111111111122211222211232112332112221m=5123321m=611111122221111111,典型非数值(图型)问题-例6,1.i(m+1)/2min(m-i+1,m-j+1),第52页,#definemin(x,y)(x)=1),例：a21=a11+1=1+1=2,a61=a51+5=11+5=163.若:已知ai,1，则：ai,j+1=,ai,1+i,例：a22=a21+2+1=2+2+1=5,a23=a22+2+2=5+2+2=9a62=a61+6+1=16+6+1=23,a63=a62+6+2=23+6+2=31,ai,j+i+j,123456,123456,递推公式a1,1=1当：i,j=1时ai+1,1=ai,1+iai,j+1=ai,j+i+j,第54页,递推公式：a1,1=1ai+1,1=ai,1+i(i,j=1)ai,j+1=ai,j+i+j程序voidmain()inti,j,m,n,k=1;/*k是第一列元素的值*/scanf(%d,/*计算下一行中第1个元素*/,典型非数值(图型)问题-例7,例C3_7306,第55页,例8：打印0-360度的sin(x)曲线-*-|*|*|*|*|*|*|*|*|*|*|*|*|*|*|*|*|*|*|*|*|*|*|*|*|*|*|*|*|*|*|*|*|*|*,典型非数值(图型)问题-例8,程序的关键在于：设计图形,第56页,算法分析：1、坐标的x轴沿列自顶向下，y轴自左向右增加2、屏幕每行为80列，y轴以第40列为0点3、sin(x)的值在-11之间，图形中对应以40列为中心的1070列4、将角度0360度以10度为一个步长等分，只考察37个点sin(x)函数对应点的位置，即图形总共打印37行算法设计：设定义i、j分别控制行和列1、则行对应的角度为：i*10/180*PAI2、每行打印四种字符：空格、|、*、n3、行对应的sin值的位置，及*的位置为：40+30*sin（i*10/180*PAI）|在40列n要视*、|的位置决定（取“最远”的值）,典型非数值(图型)问题-例8,第57页,典型非数值(图型)问题-例8,#definePAI3.14159voidmain()doublex;inty,i,yy;for(i=1;iy?40:y;/*下一行要打印的字符总数*/for(i=1;i=-1;y-=0.1)/*y为列方向，1到-1*/m=acos(y)*10;/*计算y对应的弧度m*/for(x=1;xm;x+)printf();printf(*);/*控制打印左侧的*号*/for(;x=-10;y-)/*圆的半径为10*/m=2*sqrt(100-y*y);/*计算行y对应的列坐标m*/for(x=1;x0时#includemain()intx,n;printf(x=?n=?);scanf(%d%d,例C8-12,共84页第70页,数值型问题的递归求解一般方法从数学公式入手：推导出问题的递归定义；确定问题的边界条件；再得到问题的递归算法和递归结束条件例C8-13：求自然数1到n之和。建立问题的递归定义：f(n)=1当n=1时f(n)=n+f(n-1)当n1时程序：sum(n)intn;if(n=1)return(1);/*递归结束条件*/if(n1)return(n+sum(n-1);,递归结束条件,递归算法,例C8-13,共84页第71页,例C8-14：求菲波那奇序列：1，1，2，3，5，8，13，21，34，建立问题的递归定义：f(n)=1当n=1或n=2时f(n)=f(n-1)+f(n-2)当n2时程序：f(n)intn;if(n=1|n=2)return(1);/*结束条件*/if(n2)return(f(n-1)+f(n-2);elsereturn(-1);/*返回-1表示出错*/,递归结束条件,递归算法,共84页第72页,例C8-15：打印杨辉三角型：11112113311464115101051建立问题的递归定义对于第x行的第y个值，建立如下数学模型：c(x,y)=1x=0，y=1或y=x+1c(x,y)=c(x-1,y-1)+c(x-1,y)其它程序：intc(x,y)/*求第x行第y列的值*/intx,y;if(x=0,共84页第73页,例C8-16.C：请用递归的方法计算下列函数的值：px(x,n)=x-x2+x3-x4+.(-1)n-1xnn0已