数的计数 #
- 数的计数函数的定义及介绍
- 斐波那契数列递归的拆解
- 递归的出口
数的计数问题介绍 #
我们要求找出具有下列性质数的个数(包括输入的自然数n)。先输入一个自然数n(0≤n≤100),然后对此自然数按照如下方法进行处理:
例如:输入6 满足条件的数为6,16,26,126,36,136一共6个,对于求解数的计数问题,我们定义函数f(n),返回数的计数个数,n为输入数字
def f(n,k):#f(n)函数功能:返回数的计数个数,n为输入自然数 pass
递归的拆解 #
数的计数问题的拆解我们可以考虑n为奇数和偶数两种情况:
则综合1,2两种情况,我们就得到了递归函数的数学表达式:当n为奇数时,f(n)=f(n-1),当n为偶数时f(n)=f(n-1)+f(n//2)
def f(n): if n%2!=0: return f(n-1) #递归问题的拆解 else return f(n-1)+f(n//2) #递归问题的拆解
递归的出口 #
将数的计数递归问题拆解后,考虑递归的边界情况。当n不断减少时,很容易可以想到n=1时,f(1)=1,当n=0时也是如此即f(0)=0
def f(n): if(n==0 or n==1):#递归问题的出口 return 1 if n%2!=0: return f(n-1) #递归问题的拆解 else: return f(n-1)+f(n//2) #递归问题的拆解
小结 #
习题 #
- 画出上例中f(6)、f(7)递归调用执行过程图
- 请用迭代的方法解决数的计数问题,并与递归方法相比较验证