C+语言程序设计第十讲.ppt

1、例1：输入两个正整数a和n，求a+aa+aaa+aaaa+aaaa（n个a）之和。例如，输入2和3，则求2+22+222=246。,输入a和n,for i=0 to n-1,sum+=t,输出sum,t=0,t=t*10+a,#include void main( ) int sum, a, n, i, t; coutan; t=0; sum=0; for(i=0; in; i+) t=t*10+a; sum+=t; coutsum=sumendl; ,sum=0,例1：输入两个正整数a和n，求a+aa+aaa+aaaa+aaaa（n个a）之和。例如，输入2和3，则求2+22+222=246。

2、,#include #include void main( ) int sum, a, n, i, t; coutan; sum=0; t=0; for(i=0; in; i+) t=t+a*pow(10,i); sum+=t; coutsum=sumendl; ,输入a和n,for i=0 to n-1,sum+=t,输出sum,t=0,t=t*10+a,sum=0,t+=a*pow(10,i),例2：输入一个正整数n，计算 的值。,#include #include void main() int n,i; float jc, s; coutn; jc=1; s=1; for(i=1;i=

3、n;i+) jc=jc*i; s+=1.0/jc; couts=setiosflags(ios:fixed) setprecision(3)sendl; ,输入n,for i=1 to n,s+=1.0/jc,输出s,jc=1,jc=jc*i,s=1,例2：输入一个正整数n，计算 的值。,输入n,for i=1 to n,s+=1.0/jc,输出s,jc=1,s=1,jc=jc*j,for j=1 to i,?,?,?,#include void main( ) int n, i, j; float jc, s; printf(Input n:); scanf(%d, ,#include vo

4、id main( ) int i, b, s, g; for(i=100; i1000; i+) b=i/100; s=i/10%10; g=i%10; if(b*b*b+s*s*s+g*g*g=i) couti ; ,例3：打印出所有的水仙花数。所谓水仙花数是指一个3位数，其各位数字的立方和等于该数本身。,for i=100 to 999,s=i/10%10,b=i/100,g=i%10,b3+s3+g3=i,T,输出i,F,153 370 371 407,例3：打印出所有的水仙花数。所谓水仙花数是指一个3位数，其各位数字的立方和等于该数本身。,for b=1 to 9,n=100*b+10

5、*s+g,b3+s3+g3=n,T,输出n,F,#include void main( ) int n, b, s, g; for(b=1; b=9; b+) for(s=0; s=9; s+) for(g=0; g=9; g+) n=100*b+10*s+g; if(b*b*b+s*s*s+g*g*g=n) coutn ; ,for s=0 to 9,for g=0 to 9,例4：输入若干个正整数，以0或负数结束，将其中个位不为0的数输出，并统计满足条件的数据个数。,#include void main( ) int a100, x, n=0, count=0, i; cinx; whil

6、e(x0) an=x;n+; cinx; for(i=0; in; i+) if(ai%10!=0) coutai ; count+; cout个数是：count; ,cinx;,输入x,n=0,count+,for i=0 to n-1,ai%10!=0,T,输出ai,F,x0,an=x,count=0,n+,输入x,输出count,例5：用公式/41-1/3+1/5-1/7+求的近似值，直到最后一项的绝对值小于10-6为止。,#include void main( ) float s=0, t; int n=1, f=1; t=1.0/n; while(t=1e-6) s+=f*t; f=

7、-f; n+=2; t=1.0/n; coutPI=4*sendl; ,s=0,t=10-6,f=-f,输出4*s,t=1.0/n,s+=f*t,n=1,f=1,n+=2,t=1.0/n,while(t=1e-6);,do,例6：输入两个正整数m和n，输出m和n之间的所有素数，每行输出5个。,for i=m to n,for j=2 to i-1,count=0,leap=1,i%j=0,T,leap=0,F,leap=1,T,输出i,F,count+,1不是素数,习 题,例7：编写程序找出1000以内的所有完数。一个数恰好等于它的因子之和，这个数就称为“完数”。例如，6的因子为1、2、3，而

8、6=1+2+3，因此6是完数。,例8：输入一个正整数n和任意数x，计算s的值。,例9：将一笔钱换算成1分、2分和5分的硬币组合。输入金额，问有几种换算方法？针对每一种换算方法，输出各种面值的硬币数量，要求每种硬币至少有一枚。,例10：打印出菱形图案，要求用循环嵌套实现，其中n的值（边长）从键盘输入。,* * * * * * *,习 题,输入n,di=0,for i=1 to n-1,adiai,T,di=i,F,for i=0 to n-1,输入ai,xi=0,axiai,T,xi=i,F,例1：从任意n个数构成的数列中找出最大的数和最小的数，将最大的数和最后一个数互换，最小的数和第一个数互换

9、。,for i=0 to n-1,输出ai,axia0,adian-1,输入x,n=0,for i=0 to n-1,ai=ave,T,count+,F,x0,an=x,ave=0,例2：从键盘输入任意一个大于0的实数，存入一个数组中，统计并输出其中大于等于平均值的实数个数。,输出count,ave/=n,n+,输入x,for i=0 to n-1,ave+=ai,count=0,#include void main() float a100, x, ave; int i, n, count; n=0; ave=0; cinx; while(x0) an=x; ave+=an; n+; cin

10、x; ave/=n;,count=0; for(i=0;iave) count+; coutcountendl; ,例3：找出1100之间能被7或11整除的所有整数，将这些整数放在数组中然后输出，要求一行输出10个数。,for i=1 to 100,n=0,i%7=0|i%11=0,T,an=i,F,n+,for i=0 to n-1,输出ai,(i+1)%10=0,T,换行,F,#include void main( ) int a100, n, i; n=0; for(i=1; i=100; i+) if(i%7=0|i%11=0) an=i; n+; for(i=0; in; i+) c

11、outai ; if(i+1)%10=0) coutendl; ,例4：将任意一个互不相同且非0 的整数组成的数列输入到 数组中(0结束)，然后查找某个数是否在这个数列中。若在，就输出该数在数列中的位置；若不在，就输出相关信息。,输入x,n=0,for i=0 to n-1,ai=y,T,break,F,x!=0,an=x,输入y,n+,输入x,in,T,在,F,输出i,不在,#include void main( ) int a100, n=0, i, x, y; cinx; while(x!=0) an=x; n+; cinx; ciny; for(i=0; in; i+) if(ai=y

12、) break; if(in) coutyes:iendl; else coutno; ,例5：查找一个数是否在一个数列（由非0整数构成）中，若在，从数列中删除这个数。,输入y,for i=0 to n-1,ai=k,T,for j=i+1 to n-1,F,for i=0 to n-1,输出ai,输入一组非0整数,aj-1=aj,n-,i-,#include void main( ) int a100, n=0, i, j, x, y; cinx; while(x!=0) an=x;n+; cinx; ciny; for(i=0; in; i+) if(ai=y) for(j=i+1; jn

13、; j+) aj-1=aj; n-;i-; for(i=0; in; i+) coutai ; ,基本思想：假设数组a已经按由小到大的顺序排好序，设三个变量low, high和mid分别代表首元素，最后一个元素以及中间元素的下标，初值分别为：low=0、high=n-1、mid=(low+high)/2。从中间元素开始查找，用x和amid比较，此时有三种情况：,1) 若x = amid ，则查找成功；,2) 若x amid ，则令high=mid-1,3) 若x amid ，则令low=mid+1,折半查找法,例：数组元素为：5, 13, 19, 21, 37, 56, 64, 75, 80,

14、 88, 92,1.查找x=21 的情况,(1) low=0; high=10; mid=(0+10) / 2=5,因为amidx，所以向左找，令high=mid-1=4,(2) low=0; high=4; mid=(0+4) / 2=2,因为amidx，所以向右找，令low=mid+1=3,(3) low=3; high=4; mid=(3+4) / 2=3,因为amid=x，查找成功，所查元素的下标为mid,0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5,6,7,8,9,10,(1) low=0; high=10; mi

15、d=(0+10) / 2=5,因为amidx，所以向右找，令low=mid+1=6,(2) low=6; high=10; mid=(6+10) / 2=8,因为amidx，所以向右找，令low=mid+1=9,(3) low=9; high=10; mid=(9+10) / 2=9,因为amidx，所以向左找，令high=mid-1=8,2.查找x=85 的情况,此时lowhigh，查找失败,0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5,6,7,8,9,10,#include void main() int a100, i

16、, n, x, low, high, mid; cinn; for(i=0; iai; cinx; low=0;high=n-1; while(low=high) mid=(low+high)/2; if(x=amid)break; else if(xamid)high=mid-1; elselow=mid+1; if(x=amid) coutYES:mid; else coutNO; ,例：将任意n个数由大到小排序。,排 序,#include void main( ) int a100, i, j, n, di, temp; cinn; for(i=0; iai; for(i=0; in-1

17、; i+) di=i; for(j=i+1; jn; j+) if(adiaj) di=j; if(i!=di) temp=ai; ai=adi; adi=temp; for(i=0; i=n-1; i+) coutai ; ,选择排序法,#include void main( ) int a100, i, j, n, temp; cinn; for(i=0; iai; for(i=0; in-1; i+) for(j=i+1; jn; j+) if(aiaj) temp=ai; ai=aj; aj=temp; for(i=0; i=n-1; i+) coutai ; ,例：用冒泡法对n个数进

18、行排序（从小到大）,排序过程： （1）比较第一个数与第二个数，若为逆序a0a1，则交换；然后比较第二个数与第三个数；依次类推，直至第n-1个数和第n个数比较为止第一趟冒泡排序，结果最大的数被安置在最后一个元素位置上; （2）对前n-1个数进行第二趟冒泡排序，结果使次大的数被安置在第n-1个元素位置; （3）重复上述过程，共经过n-1趟冒泡排序后，排序结束。,相邻两数比较，大数 小数,38421,38421,38421,34821,34281,34218,第一趟,34218,34218,32418,32148,第二趟,32148,23148,21348,第三趟,21348,12348,第四趟,a

19、1 a2 a3 a4 a5,j=1 to 4,j=1 to 3,j=1 to 2,j=1 to 1,由小到大排序,#include void main( ) int a100, n, i, j, temp; scanf(%d, ,例： 求费波纳契数列中前n项的值，其中n值从键盘输入。,#include void main( ) int a100, sum, i, n; cinn; a1=1; a2=1; for(i=3; i=n; i+) ai=ai-1+ai-2; for(i=1; i=n; i+) coutai ; ,举 例,输入n,for i=3 to n,ai=ai-1+ai-2,fo

20、r i=1 to n,输出ai,a1=1 a2=1,费波纳契数列,一般而言，兔子在出生两个月后就有了繁殖能力。一对兔子每个月能生出一对小兔子，如果所有兔子都不死，那么一年后可以繁殖多少对兔子？ 费波纳契数列指的是这样一个数列： 1、1、2、3、5、8、13、21、 这个数列从第三项开始，每一项都等于前两项之和。,1349 8523 5246 7621,a0,a1,a2,a3,0123,a00a01a02a03 a10a11a12a13 a20a21a22a23 a30a31a32a33,二维数组的基本概念,类型名 数组名常量1 常量2;,例如：,int a34;,整型二维数组,名字为a,3行,

21、a0,a0,存储结构,逻辑结构,a00,数组a,数组的定义,4列,共12个元素,a0,a0,a10,a11,a12,a13,a20,a21,a22,a23,是一个矩阵或一张表格,第0行,第1行,第2行,第0列,第1列,第2列,第3列,a01,a02,a03,a10,a11,a12,a13,a20,a21,a22,a23,按行存储,a0,a1,a2,0,1,2,3,一维数组个数,一维数组中元素的个数,分行初始化,例 int a23=1,2,4;,例 int a 3=1,2,4;,部分初始化,行长度可以省略,例 int a23=1,2,3,4,5,6;,1,2,3,4,5,6,全部初始化,1,2,0,4,0,0,按存储顺序初始化,例 int a23=1,2,4;,例 int a23=1,2,3,4,5,6;,全部初始化,部分初始化,例 int a 3=1,2,3,4,5;,行长度可以省略,1,2,3,4,5,6,1,2,4,0,0,0,1,2,3,4,5,0,1 0 9 7,4 6 8 3,12 3 3 5,二维