资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,程序设计的常用算法,一、计数、求和、求阶乘等简单算法,此类问题都要使用循环，要注意根据问题确定循环变量的初值、终值或结束条件，更要注意用来表示计数、和、阶乘的变量的初值。,一般情况下：,（,1,）计数、累加的变量的初值为,0,；,（,2,）累积、求阶乘的变量的初值为,1,例,1,：用随机函数产生,100,个,0,，,99,范围内的随机整数，分别求出偶数的和，奇数的和，并打印出来所有的数据，及其偶数的和值，奇数的和值。,算法思想,:,重复执行,100,次，每次要：产生,1,个,0-99,之间的整数，如果是偶数，则偶数和累加，否则,奇数和累加,.,变量的定义,:,a,：利用随机函数产生的一个整数，,X,：存放“偶数”的和，,Y,：存放“奇数”的和，,i,：用于控制,100,次；,处理步骤：,（,1,）置初值：,X=0,，,Y=0,（,2,）,i,从,1,到,100,重复执行,产生一个,a,；,如果,a,是偶数，则,X=,X+a,；,否则,Y=,Y+a,；,输出,a,；,下一次（下一个,i,）,（,3,）输出,X,，,Y,值,程序代码：,Private Sub Command1_Click(),Dim a%,x%,y%,i%,x=0,y=0,Randomize,For i=1 To 20 Step 1,a=Int(Rnd(1)*100),If a Mod 2=0 Then,x=x+a,Else,y=y+a,End If,Print a;,Next i,Print,Print,偶数和为,:;x,Print,奇数和为,;y,End Sub,每次运行产生的序列不同,产生,0-99,之间的整数,演示,401,例,2,：,用随机函数产生,100,个,100,，,200,范围内的随机整数，分别求出偶数平均值，奇数的平均值，并打印有关的数据。,算法思想,:,重复执行,100,次，每次要：产生,1,个,100-200,之间的整数，如果是偶数，则偶数和累加，并统计个数，否则,奇数和累加，并统计个数,.,当够,100,次后，分别计算平均值，并输出,变量的定义,:,a,：利用随机函数产生的一个整数，,X,：存放“偶数”的和，,Y,：存放“奇数”的和，,m:,存放偶数的个数,n:,存放奇数的个数,i,：用于控制,100,次；,b:,存放偶数的平均值,c:,存放奇数的平均值,处理步骤：,（,1,）置初值：,X=0,，,Y=0,m=0.n=0,（,2,）,i,从,1,到,100,重复执行,产生一个,a,；,如果,a,是偶数，,则,x=,X+a,m,=m+1,；,否则,Y=,Y+a,n,=n+1,；,输出,a,；,下一次（下一个,i,）,（,3,）计算,b,C,的值,（,4,）输出,b,，,c,的值,程序代码：,Private Sub Command1_Click(),Dim a%,x%,y%,i%,m,n,b,c,x=0:,m=0,y=0:,n=0,Randomize,For i=1 To 20 Step 1,a=Int(Rnd(1)*100),If a Mod 2=0 Then,x=x+a,m=m+1,Else,y=y+,a:,n,=n+1,End If,Print a;,Next I,b=X/m:c=,y/n,Print,Print,偶数和为,:;x,Print,奇数和为,;y,End Sub,演示,402,例,3,：,求,10,的阶乘,即,:,求,T=1,23456,78910,的值,算法思想,:,公式,:T=,Ti,乘数,i,从,1,到,10,连续乘,当够,10,次后，输出结果,变量的定义,:,T,：存放积，,i,：用于乘数,从,1,到,10,；,处理步骤,：,（,1,）置初值：,T=1,（,2,）,i,从,1,到,10,重复执行,T=T*i,；,下一次（下一个,i,）,（,3,）输出,T,的值,程序代码：,Private Sub Command1_Click(),Dim t As Long,Dim i As Integer,t=1,For i=1 To 10,t=t*i,Next i,Print 10,的阶乘值为,:;t,End Sub,演示,403,长整型,思考,1:,求,n,的阶乘,(n!),即,:,求,T=n!=1,2,n,的值,提示,:,在例,3,的基础上,增加一个提供给,n,值的语句,.,变量的定义,:,n:,要求阶乘的值,T,：存放积，,i,：用于乘数,从,1,到,10,；,处理步骤,：,（,1,）输入一个,n,值,(,利用,inputbox,函数,),（,2,）置初值：,T=1,(3)i,从,1,到,n,重复执行,T=T*i,；,下一次（下一个,i,）,（,4,）输出,T,的值,程序代码：,Private Sub Command1_Click(),dim n as Integer,Dim t As Long,Dim i As Integer,n=,val(inputbox(“input,n”),t=1,For i=1 To,n,t=t*i,Next i,Print,n;,的阶乘值为,:;t,End Sub,思考,2:,求,S=1!+2!+,+10!,的值,提示,:,重复,10,次求和,而每一次求和之前,都需要先求出一个加数,(,一个阶乘值,);,二、求两个整数的最大公约数,分析：求最大公约数的算法思想：,(1),对于已知两数,m,，,n,，使得,mn,；,(2)m,除以,n,得余数,r,；,(3),mn,，,nr,，,(4),若,r,0,，则重复执行,(2),、（,3,）,（,5,）当结束循环时，,m,为求得的最大公约数，,（,6,）算法结束；,例如,:,求,m=14,n=6,的最大公约数,2.,r m n,开始,14 6,（,1,）,2 6 2,（,2,）,0 2 0,(1),对于已知两数,m,，,n,，使得,mn,；,(2)m,除以,n,得余数,r,；,(3),mn,，,nr,，,(4),若,r,0,，则重复执行,(2),、（,3,）,（,5,）当结束循环时，,m,为求得的最大公约数，,（,6,）算法结束；,变量的定义,:,m,n,:,两个整数,R,：余数,处理步骤,：,(1),输入两数,m,，,n,(2),如果,n,小于,m,，则交换,m,和,n;,使得,mn,；,(3)m,除以,n,得余数,r,；,(4),mn,，,nr,，,(5),若,r,0,，则重复执行,(3,和,4,）,(6),当结束循环时，,m,为求得的最大公约数，输出,(7),算法结束；,程序代码：,Private Sub Command1_Click(),m=,InputBox(m,=),n=,InputBox(n,=),If m m-1 Then,Print,该数是素数,Else,Print,该数不是素数,End If,End Sub,例,5,：,求出,100,到,200,之间所有的素数,并输出,算法思想,:,对于一个数据,M,是否是素数,前一个算法,已实现,那么,当求,100-200,之间的素数时,实际上需要,M,从,100,到,200,重复处理即可,.,变量的定义,:,M:,要判定的值,(,从,100,到,200),i,：用于除数,从,1,到,M-1,；,处理步骤,：,（,1,）,M,从,100,到,200,重复执行,（,a,）置初值：,I=2,(b),当,i,不到,M-1,并且,M,不被,I,整除,重复执行,下一个,i(,除数,),（,c,）如果,I,到,M,则输出,M,(2),下一个,m,程序代码：,Private Sub Command1_Click(),for m=100 to 200,i=2,Do While i 0,i=i+1,Loop,If i m-1 Then Print m,next m,End Sub,验证哥德巴赫猜想：,（任意一个大于等于,6,的偶数都可以分解为两个素数之和）,基本思想,：,n,为大于等于,6,的任一偶数，可分解为,n1,和,n2,两个数，分别检查,n1,和,n2,是否为素数，如都是，则为一组解。如,n1,不是素数，就不必再检查,n2,是否素数。,先从,n1=3,开始，检验,n1,和,n2,（,n2=N-n1,）是否素数。然后使,n1+2,再检验,n1,、,n2,是否素数，,直到,n1=n/2,为止。,四、验证哥德巴赫猜想,作为思考，学生自己独立完成！,五、图形表的输出,利用循环，打印输出下列图形：,A,AAA,AAAAA,AAAAAAA,AAAAAAAAA,AAAAAAAAAAA,AAAAAAAAAAAAA,基本思想,：,（,1,）确定要输出图形的行数；,（,2,）确定每行要输出的开始位置；,（,3,）每行要输出字符的个数；,（,4,）每行输出完后要换行；,变量的定义,:,i:,用于控制行数,从,1,到,7;,j,：用于控制每行中要输出的字符数；,假设,第一行的开始位置为,30,则第,i,行的开始位置为,:31-i;,处理步骤,：,（,1,）,i,从,1,到,7,重复执行,（,a,）定位第,i,行,TAB(31-i);,(b),J=1 TO 2*i-1,重复执行,输出一个字符”,A”;,（,c,）换行,;,(2),下一行,程序代码：,For i=1 To 7 Step 1,Print Tab(31-i);,For j=1 To 2*i-1,Print A;,Next j,Print,Next i,End Sub,思考,:,利用循环，打印输出下列图形：,A,AAA,AAAAA,AAAAAAA,AAAAAAAAA,AAAAAAAAAAA,AAAAAAAAAAAAA,AAAAAAAAAAA,AAAAAAAAA,AAAAAAA,AAAAA,AAA,A,验证哥德巴赫猜想问题,:,（任意一个大于等于,6,的偶数都可以分解为两个素数之和）,基本思想,：,n,为大于等于,6,的任一偶数，可分解为,n1,和,n2,两个数，分别检查,n1,和,n2,是否为素数，如都是，则为一组解。如,n1,不是素数，就不必再检查,n2,是否素数。,先从,n1=3,开始，检验,n1,和,n2,（,n2=N-n1,）是否素数。然后使,n1+2,再检验,n1,、,n2,是否素数，,直到,n1=n/2,为止。,六、验证哥德巴赫猜想,作为练习,同学自己实现,注意要给出算法步骤描述。,算法思想：对于一个问题的求解,x,，可由给定的一个初值,x0,，根据某一迭代公式得到一个新的值,x1,，这个新值,x1,比初值,x0,更接近要求的值,x,；再以新值作为初值，即：,x1x0,重新按原来的方法求,x1,重复这一过和直到,|x1-x0|(,某一给定的精度,),。此时可将,x1,作为问题的解。,例：方程求根问题。,七、迭代法,作为练习,同学自己实现,注意要给出算法步骤描述。,八、穷举法,穷举法（又称“枚举法”）,基本思想是：一一列举各种可能的情况，并判断哪一种可能是符合要求的解，这是一种“在没有其它办法的情况的方法”，是一种最“笨”的方法，然而对一些无法用解析法求解的问题往往能奏效，通常采用循环来处理穷举问题。,例：将一张面值为,100,元的人民币等值换成,100,张,5,元、,1,元和,0.5,元的零钞，要求每种零钞不少于,1,张，问有哪几种组合？,作为练习,同学自己实现,注意要给出算法步骤描述。,
展开阅读全文