首页 › 题库 › Python编程考级 › 3.2 递推

Python编程四级 题库

共 25 道题 ,第 1 / 2 页 · 按题型筛选,点「查看答案」核对解析
1 单选题 适中 Python编程考级 ·Python编程四级 · 3.2 递推

有 2*n的一个长方形方格,用一个1*2的骨牌铺满方格,当n=5时,铺法总数为多少?( )

A
5
B
6
C
7
D
8
答案与解析
正确答案:D

对一般的n,要求xn可以这样来考虑,若第一个骨牌是竖排列放置,剩下有n-1个骨牌需要排列,这时排列方法数为xn-1;若第一个骨牌是横排列,整个方格至少有2个骨牌是横排列(1*2骨牌),因此剩下n-2个骨牌需要排列,这是骨牌排列方法数为xn-2。从第一骨牌排列方法考虑,只有这两种可能,所以有: 

 xn=xn-1+xn-2 (n>2) 

 x1=1 

 x2=2 

 xn=xn-1+xn-2就是问题求解的递推公式,任给n都可以从中获得解答。例如n=5, 

 x3=x2+x1=3 

 x4=x3+x2=5 

 x5=x4+x3=8


题目详情
2 单选题 适中 Python编程考级 ·Python编程四级 · 3.2 递推

设某算法的计算时间表示为递推关系式T(n)=T(n-1)+n(n为正整数)及T(0)=1,该算法的时间复杂度为以下哪一项?( )

A
O(log2n)
B
O(nlog2n)
C
O(n)
D
O(n2)
答案与解析
正确答案:D

T(n) = T(n-1)+n 

T(n) = (T(n-2) + n-1) + n 

T(n) = T(0) .... n-2+ n-1 + n = n * (n+1)/2,当n趋近于无穷大的时候,T(n) =n*n。

题目详情
3 单选题 适中 Python编程考级 ·Python编程四级 · 3.2 递推

有一头母牛,它每年年初生一头小母牛。每头小母牛从第四个年头开始,每年年初也生一头小母牛。问第n年的时候,共有多少头母牛?

由递推法可推测,当年数小于等于4的时候,第几年就是有几头牛,即a[1]=1;a[2]=2;a[3]=3;a[4]=4。当n大于4的时候,这时候第一年出生的那个小母牛就也可以生出小母牛了,也就是该考虑小母牛是否可以生了,所以n>4的时候,a[n]=?

A
a[n-1]+a[n-3]
B
a[n-1]+a[n-4]
C
a[1]+a[3]
D
a[-1]+a[-3]
答案与解析
正确答案:A

前四年共有四只,从第五年开始,第二年出生的小母牛也会生一只母牛(而且以后每年初都会生一只母牛),加上第一年那只母牛生的小母牛,共有六只母牛;第六年的时候得加上第三年那只母牛生的母牛,共九只母牛;依次类推。

题目详情
4 单选题 适中 Python编程考级 ·Python编程四级 · 3.2 递推

小方的妈妈分苹果方法如下,第一天分掉其中一半加一个苹果,第二天分掉剩下的一半加一个苹果,以后每天都分掉剩下的一半加一个苹果。到第8天的时候妈妈发现只剩一个苹果了。请问小方妈妈一开始有多少个苹果? 这个问题我们可以用以下什么算法解决?

A
查找
B
递推
C
枚举
D
排序
答案与解析
正确答案:B

从第8天往前计算第7天剩余的苹果数,然后再计算第6天的,依次递推解决问题。这是递推问题

题目详情
5 单选题 适中 Python编程考级 ·Python编程四级 · 3.2 递推
自然界的规律:花瓣的个数大多数花瓣的个数有1、1、2、3、5、8、13、21、......,仔细观察这些数的顺序,会发现这些数的排列是有规律的,即斐波那契数列。小李同学编写程序求该数列的第n项的值。方框中的代码由以下三部分组成:① a=b  ② b=c  ③ c=a+b,下列选项中代码顺序正确的是?
A
①②③
B

①③②

C

③②①

D

③①②

答案与解析
正确答案:D

递推法求斐波那契数列,选D。

题目详情
6 单选题 适中 Python编程考级 ·Python编程四级 · 3.2 递推

有一根绳子,第一次剪去一半多2米,第二次剪去剩下的一半多2米,第三次剪去剩下的一半多2米,第四次剪去剩下的一半多2米,第五次剪去剩下的一半多2米,此时绳子还剩2米。这根绳子长几米?想解决这个问题的话,可以采用以下哪种算法?( )

A
排序
B
递推
C
解析
D
枚举
答案与解析
正确答案:B

题目中的绳子长度是按相同的规律剪掉的,所以从后向前,可以按照这个规律来递推计算绳子的长度。

题目详情
7 单选题 适中 Python编程考级 ·Python编程四级 · 3.2 递推

实现递推算法的核心程序结构通常是使用?( )

A
顺序结构
B
自定义函数
C
循环结构
D
分支结构
答案与解析
正确答案:C

递推算法通常包含循环结构。

题目详情
8 单选题 适中 Python编程考级 ·Python编程四级 · 3.2 递推
下列关于递推算法思想的描述正确的是?
A
将一个大问题分解为若干子问题,且子问题与大问题是相同的问题,构成递推算法思想
B
递推算法思想需要有明确的终止条件
C
递推算法思想需要有明确的递推公式
D
任何问题都可以用递推算法解决
答案与解析
正确答案:C

递推算法思想需要有明确的递推公式。

题目详情
9 单选题 适中 Python编程考级 ·Python编程四级 · 3.2 递推
某农户养了若干只鸡。第一天卖掉其中一半加一只,以后每天都卖掉剩下的一半加一只。到第8天的时候发现只剩一只鸡了。请问该农户一开始有多少只鸡? 这个问题用下列什么算法解决?
A
递推
B
解析
C
枚举
D
分治
答案与解析
正确答案:A

这个问题体现了递推思想。

题目详情
10 单选题 适中 Python编程考级 ·Python编程四级 · 3.2 递推
已知递推公式 f(n) = f(n-1) + 2*n,且 f(1) = 2。请问 f(3) 的值是多少?( )
A
4
B
8
C
12
D
16
答案与解析
正确答案:C
根据递推公式 f(n) = f(n-1) + 2*n 和初始条件 f(1) = 2,从 n = 2 开始逐层计算:先代入 n = 2 得到 f(2) 的表达式,再将 f(2) 代入 n = 3 的递推式中,依次完成每一步的数值替换与算术运算。每一步均依赖前一项的结果,且每次计算需明确执行加法和乘法操作,最终完成 f(3) 的求解过程。
题目详情
11 单选题 适中 Python编程考级 ·Python编程四级 · 3.2 递推

小明有一堆糖果,他每天吃掉一半加一颗。如果小明连续吃了5天,糖果正好吃完,请问小明最初有多少颗糖果?求解该问题使用的算法思想是?( )

A
查找
B
递推
C
排序
D
枚举
答案与解析
正确答案:B

递推方式解决该问题。

题目详情
12 单选题 适中 Python编程考级 ·Python编程四级 · 3.2 递推

小兔子有一堆胡萝卜,它每天都会吃掉原来的一半再多吃一根。 这样连续吃了3天,发现只剩下1根胡萝卜了。小兔子想知道第一天有多少根胡萝卜并且递推公式是什么,请选择正确的选项?( )

A
10, a[n-1] = (a[n]-1) * 2
B
10, a[n-1] = (a[n]+1) * 2
C
10, a[n-1] = a[n] * 2 - 1
D
10, a[n-1] = a[n] * 2 + 1
答案与解析
正确答案:B

根据题意,小兔子第三天剩下1根胡萝卜,第二天胡萝卜是(1+1)*2=4, 第一天是(4+1)*2=10

递推公式是:a[n-1] = (a[n]+1) * 2

题目详情
13 单选题 适中 Python编程考级 ·Python编程四级 · 3.2 递推

小明和小红在玩一种数字游戏。游戏规则如下:

(1)小明先从整数1开始写下一个数字;

(2)接下来,小红会将当前数字加3后写下新的数字;

(3)然后小明会将当前数字乘以2后写下新的数字;

(4)两人轮流按照这个规则操作,直到写下的数字第一次超过100为止。

请根据游戏规则模拟推理游戏结果?( )

A
小明 102
B
小红 106
C
小明 106
D
小红 102
答案与解析
正确答案:C

这是一个交替操作的递推问题,我们可以通过模拟每一步的操作来递推结果

小明写下第1个数字:1

小红操作:1 + 3 = 4

小明操作:4 × 2 = 8

小红操作:8 + 3 = 11

小明操作:11 × 2 = 22

小红操作:22 + 3 = 25

小明操作:25 × 2 = 50

小红操作:50 + 3 = 53

小明操作:53 × 2 = 106

最后结果:小明 106

题目详情
14 单选题 适中 Python编程考级 ·Python编程四级 · 3.2 递推

小明每天做俯卧撑,第1天做10个,之后每天比前一天多2个。可以计算5天总训练量的Python递推程序是下列哪个选项?( )

A
total = 0  
for day in range(1,6):  
   total += 8 + 2*day
B
total = 10  
for _ in range(4):  
   total += total + 2
C
total = 10  
current = 10  
for _ in range(4):  
   current += 2  
   total += current
D
def push_up(n):  
   return 10*n + 2*(n-1)
答案与解析
正确答案:C

初始10个,之后每天+2(第2天12,第3天14...总训练量=10+12+14+16+18)。

题目详情
15 单选题 适中 Python编程考级 ·Python编程四级 · 3.2 递推

小明每天跑步距离是前一天的两倍,下列哪个选项可表示第n天距离?( )

A
dis[n] = dis[n-1] * 2
B
dis[n] = dis[n-1] + 2
C
dis[n] = 2^n
D
dis[n] = n * 2
答案与解析
正确答案:A

每天距离是前一天的2倍,递推关系为乘法。

题目详情
16 单选题 适中 Python编程考级 ·Python编程四级 · 3.2 递推

图1是一个水平摆放的小正方体木块,图2,图3是由这样的小正方体木块叠放而成的,按照这样的规律放下去,第七个叠放的图形有多少个正方形木块?这个问题我们可以用以下什么算法解决?( )

A
查找
B
递推
C
排序
D
选择
答案与解析
正确答案:B

分别观察正方体的个数为:1,1+5,1+5+9,…从图2开始,正方形方格的数量为s[n]=s[n-1]+(n-1)*4+1。这是递推问题。

题目详情
17 判断题 偏易 Python编程考级 ·Python编程四级 · 3.2 递推

对于斐波那契数列:1,1,2,3,5,……,我们只能采用迭代公式以递推的方式求解。

A
对
B
错
答案与解析
正确答案:错

斐波那契数列可以用多种方式求解。

题目详情
18 判断题 偏易 Python编程考级 ·Python编程四级 · 3.2 递推

如下图代码,最后运行结果将会打印出数值6,请问对吗?

A
对
B
错
答案与解析
正确答案:对

最基本的递推,循环3次,每次累加2,答案为6,正确。

题目详情
19 判断题 偏易 Python编程考级 ·Python编程四级 · 3.2 递推

在定义一个函数时,如果出现调用自身的成分,则称为递推。( )

A
对
B
错
答案与解析
正确答案:错

调用自身的成分是递归的特征。

题目详情
20 判断题 偏易 Python编程考级 ·Python编程四级 · 3.2 递推

递推是按照一定的规律计算序列中的每一项,通常是通过计算前面的一些项来计算后一项的值。( )

A
对
B
错
答案与解析
正确答案:对

递推是按照一定的规律计算序列中的每一项,通常是通过计算前面的一些项来计算后一项的值。

题目详情