267 数的计数

数的计数

1. 数的计数函数的定义及介绍
2. 斐波那契数列递归的拆解
3. 递归的出口

数的计数问题介绍

我们要求找出具有下列性质数的个数（包括输入的自然数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.当输入为奇数时，能够比价容易想到1~(n//2)的范围其实和1~(n-1)//2所包含的整数范围其实是一样的，那么我们可以有f(n)=f(n-1)

2.当输入为偶数时，{1~(n-1)//2,n//2}的整数范围是一致的,那么我们可以有f(n)=f(n-1)+f(n//2)

则综合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) #递归问题的拆解

小结

根据数的计数的递归算法，理解递归算法的三要素

掌握数的计数的递归算法

习题

1. 画出上例中f(6)、f(7)递归调用执行过程图
2. 请用迭代的方法解决数的计数问题，并与递归方法相比较验证