发布时间 : 星期日 文章算法与程序设计（高中选修）复习资料更新完毕开始阅读992b92d20b4c2e3f5627631d
年龄问题：有5个人，第5个人的年龄比第4个的年龄大2岁，第4个人的年龄比第3个的年龄大2岁，第3个人的年龄比第2个的年龄大2岁，第2个人的年龄比第1个的年龄大2岁，第1个的年龄10岁。问第5个人年龄多大？
算法分析：
要想知道第5个人的年龄就必须知道第4个人的年龄，要想知道第4个人的年龄就必须知道第3个人的年龄，要想知道第3个人的年龄就必须知道第2个人的年龄，要想知道第2个人的年龄就必须知道第1个人的年龄，
第1个人年龄是10岁，所以第2个人年龄就是10+2=12岁，第2个人年龄是12岁，所以第3个人年龄就是12+2=14岁，第3个人年龄是14岁，所以第4个人年龄就是14+2=16岁，第4个人年龄是16岁，所以第5个人年龄就是16+2=18岁。
设计算法：
设n为第几个人，显然当n=1时，问题的解为10，而当n〉1时，问题的解可以转化为：2+f(n-1)
编写程序：
定义一个递归函数f(n)
Function f(n as integer) as integer Dim f as integer If n=1 then f=10 Else
f=2+f(n-1) Endif
End function
调用递归函数f(n)
Privat sub command1_click() Dim f, n as integer n=inputbox() f=f(n) print f Endsub
【递归算法总结】：
能采用递归描述的算法通常有这样的特征：为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特别地，当规模N=1时，能直接得解。
递归算法的执行过程分递推和回归两个阶段。在递推阶段，把较复杂的问题（规模为n）的求解推到比原问题简单一些的问题（规模小于n）的求解。例如上例中，求解f(n)，把它推到求解f(n-1)。也就是说，为计算f(n)，必须先计算f(n-1)，而计算f(n-1)，又必须先计算f(n-3)。依次类推，直至计算f(1)，能立即得到结果10。在递推阶段，必须要有终止递归的情况。例如在函数f中，当n为1的情况。
在回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解，例如得到f(1)后，返回得到f(2)的结果，……，在得到了f(n-1)的结果后，返回得到f(n)的结果。 在编写递归函数时要注意，函数中的局部变量和参数知识局限于当前调用层，当递推进入“简单问题”层时，原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问题”层，它们
各有自己的参数和局部变量。 由于递归引起一系列的函数调用，并且可能会有一系列的重复计算，递归算法的执行效率相对较低。
同步集训 单选题
8、 使用枚举法解决问题，在列举问题可能解的过程中，＿＿＿＿。 A．不能遗漏，但可以重复 B．不能遗漏，也不应重复 C．可以遗漏，但不应重复 D．可以遗漏，也可以重复
9、 鸡、兔共笼问题，有腿共60条，问鸡、兔各有多少只？下面鸡和兔只数最合理的范围是＿＿＿＿。(范围确定了循环的起始值和终止值) A．鸡：1到28，兔：1到14 B．鸡：2到28，兔：1到14 C．鸡：1到28，兔：2到14 D．鸡：2到28，兔：2到14
3. 采用盲目的搜索方法，在搜索结果的过程中，把各种可能的情况都考虑到，并对所得的结果逐一进行判断，过滤掉那些不合要求的，保留那些合乎要求的结果，这种方法叫做＿＿＿＿。
A．递推法 B．枚举法 C．选择法 D．解析法
4.以下算法中，需通过多重循环一一列举出解决问题所有可能解，并在逐一列举的过程中，检验每个可能的解是否是问题的真正解的是 。而需要从实际问题中归纳出反映事物内在联系的数学公式，就此设计出合适的算法的是 。
A.解析法穷举法 B.递归法解析法
C.穷举法解析法 D.穷举法递归法
5． 有5个人，问第5人年龄，说比前面第4人小3岁。问第4、3、2人，都说比前面人小3岁，问第1人，说他的年龄为38岁。问第5人的年龄多大。用递归法解决此问题的正确步骤是（）
A ①定义age(n)函数 ②函数中当n>1时返回函数值age(n-1)当n=1返回函数值为38 B ①定义age(n)函数 ②函数中当n>1时返回函数值age(n-1)-3当n=1返回函数值为38
C ①定义age(n)函数 ②函数中不断调用age(n-1)-3 D ①定义age(n)函数 ②函数中不断调用age(n)函数自己
6.我们在用计算机解决问题时，常采用的算法有解析法、穷举法、递归法、冒泡排序法、选择排序法等，分析下列问题应采用哪种算法解决？
一个数除以5余1，除以6余5，除以7余4，除以11余10，求符合这些条件的最小的数是多少？
7．某学校图书管理系统中有10万条图书资料记录（已经索引排序），假设从中取出一条记录与待查项进行比较所花的时间为10毫秒，则用对分法在该系统中查找任意一本指定图书最多花费的时间约为()
A．100万毫秒 B．10万毫秒
C．10毫秒 D．170毫秒
8.二分法查找（对半查找）算法，下列正确的是 （ ） （A）先将数据按降序或升序排列 （B）数据依输入顺序排列 （C）应先将数据由小到大排列 （D）数据的个数为奇数个
9.编程求解1000以内的所有素数，下列算法中最适用的是 A二分法 B穷举法 C．解析法 D冒泡排序法 二、填空题
1.随机产生10个1－100之间的正整数，按从小到大的次序排序并输出。为了实现 这一目标，完善下面的VB程序，在划线处填入合适的语句或表达式，完成程序设计 Sub Command1_Click() Const n = 10
Dim i As Integer, j As Integer, t As Integer Dim a(1 To 100) As Integer For i = 1 To 10
a(i) = 100 * Rnd(1) + i Next i
For i = 1 To n - 1
For j = i + 1 To n
If _______________ Then
k = a(j-1): a(j-1) = a(j): a(j) = k End If Next j Next i
For i = 1 To 10
List1.AddItem Str(a(i)) Next i End Sub
2. 有一张单据上有一个5位数的号码67□□8，其中百位和十位上的数字看不清了，但知道该数能够被78整除，也能被67整除，下面是用穷举法求出该号码的程序段：
Dim a As Integer, b As Integer Dim n As Long For a = 0 To 9 For b = 0 To ①
n = 67008 + ② * 100 + b * 10
If n Mod 78 = 0 ③ n Mod 67 = 0 Then Print ④ End If Next b Next a
请将应填写的内容写在下面相应的空格内并运行程序写出该号码(每空3分，共12分)。 ①_____________ ②_____________
③_____________ ④ _____________
3. 有一个数组DATA存放了N个数据，现从中删除了一个元素，其余的元素依次向前递补（假设删除的是第3个元素，则要将第4个元素移到第3个元素处，第5个元素移到第4个元素处，以此类推），然后输出数组内容。填写程序中的空缺 Private Sub Command1_Click() Dim data(10) As Integer Dim I, N, T As Integer N = 10
For I = 1 To N data(I) = I * 2 Next I
T = InputBox(\删除第几个元素\For I = ____________________ data(I - 1) = data(I) Next I
__________________ For I = 1 To N Print data(I); Next I End Sub
4.写出下列程序的输出结果
Private Sub Command1_Click() Print f(100, 8) End Sub
Public Function f(ByVal n%, ByVal r%) If n <> 0 Then f = f(n \\ r, r) Print n Mod r End If
End Function
主题三 算法与程序实现 同步集训答案 一选择题：
1、B 2、B 3、B4、C5、B6、穷举法7、D8、A11、B11、D 填空题 1、a(j-1)>a(j)
2、9 a and n 3、t+1 to n n=n-1 4、4 4 1