文章目录
一、递推方程示例 1
二、递推方程示例小结
一、递推方程示例 1
编码系统使用 8 88 进制数字 , 对信息编码 , 8 88 进制数字只能取值 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 0,1,2,3,4,5,6,70,1,2,3,4,5,6,7 ,
只有当某个编码含有 偶数个 7 77 时 , 该编码才是有效的 ,
求 n nn 位的编码中有效的编码个数 ?
分析 :
n nn 位长的编码 , 可以 由 n − 1 n-1n−1 位长的编码 , 后面加上 一位 8 88 进制数字 构成 ;
对于每个 n − 1 n-1n−1 位长的编码 , 后面加上一位数字 , 使得最终的编码 满足 有效编码的要求 , 即含有偶数个 7 77 , 就可以得到一个有效的 n nn 位长的编码 ;
1 . 设 n nn 位长的有效编码个数是 a n a_na
n
个 ;
则有 n − 1 n-1n−1 位长的有效编码个数是 a n − 1 a_{n-1}a
n−1
个 ;
现在考虑 n nn 位长的编码 与 n − 1 n-1n−1 位长的编码之间的关联关系 ;
( 1 ) 偶数个 7 77 : 假定当前已经有一个 n − 1 n-1n−1 位长的 8 88 进制编码串 , 恰好含有偶数个 7 77 , 即该编码已经满足有效编码的要求 , 在加上一位数字 :
不可以加的数字 : 不能加 7 77 , 加了 7 77 之后 , 就会变成 奇数个 7 77 , 成为无效编码 ;
可以加的数字 : 只能加 0 , 1 , 2 , 3 , 4 , 5 , 6 0,1,2,3,4,5,60,1,2,3,4,5,6 数字 , 这里有 7 77 种方式 ;
由一个 n − 1 n-1n−1 位长的 , 满足要求的编码 , 有 7 77 种方式生成一个 n nn 位长的编码 ;
( 2 ) 奇数个 7 77 : 假定当前已经有一个 n − 1 n-1n−1 位长的 8 88 进制编码串 , 恰好含有奇数个 7 77 , 即该编码不满足有效编码的要求 , 在加上一位数字 :
不可以加的数字 : 不能加 0 , 1 , 2 , 3 , 4 , 5 , 6 0,1,2,3,4,5,60,1,2,3,4,5,6 数字 , 加了以后 , 最终结果还是有奇数个 7 77 , 不满足有效编码的要求 ;
可以加的数字 : 只能加 7 77 , 加了 7 77 之后 , 就会变成 偶数个 7 77 , 成为有效编码 ;
由一个 n − 1 n-1n−1 位长的 , 不满足要求的编码 , 有 1 11 种方式生成一个 n nn 位长的编码 ;
3 . 总个数 8 n − 1 8^{n-1}8
n−1
:
n − 1 n-1n−1 位长的编码的总数是 8 n − 1 8^{n-1}8
n−1
个 , 每个位置都有 8 88 种可能的选择 , 有 n − 1 n-1n−1 个位置 ;
又可以表述成 : n − 1 n-1n−1 位长的包括 , 奇数个 7 77 , 偶数个 7 77 , 的编码总数是 8 n − 1 8^{n-1}8
n−1
编码中如果没有 7 77 , 是 0 00 个 7 77 , 算偶数个 7 77 ;
4 . n − 1 n-1n−1 位编码的有效个数 a n − 1 a_{n-1}a
n−1
:
n − 1 n-1n−1 位中 , 偶数个 7 77 的个数 , 就是有效编码的个数 , 即上述假设的
“设 n nn 位长的有效编码个数是 a n a_na
n
个” , 则有
"n − 1 n-1n−1 位长的有效编码个数是 a n − 1 a_{n-1}a
n−1
个"
5 . n − 1 n-1n−1 位编码的无效个数 8 n − 1 − a n − 1 8^{n-1} - a_{n-1}8
n−1
−a
n−1
:
n − 1 n-1n−1 位长的包括 奇数个 7 77 , 偶数个 7 77 的 编码总数是 8 n − 1 8^{n-1}8
n−1
n − 1 n-1n−1 位中 , 偶数个 7 77 的个数 , 就是 有效编码的个数 , 即上述假设的 a n − 1 a_{n-1}a
n−1
则 n − 1 n-1n−1 位中 , 奇数个 7 77 的个数 , 就是无效编码的个数 , 即上述 总个数减去有效编码个数 , 结果是 :
8 n − 1 − a n − 1 8^{n-1} - a_{n-1}
8
n−1
−a
n−1
6 . 分析第 n nn 项与 n − 1 n-1n−1 项之间的关系 , 即 n nn 位有效编码个数 与 n − 1 n-1n−1 位有效编码个数 :
有效编码个数对应的添加方法数 : n − 1 n-1n−1 位编码的有效个数 a n − 1 a_{n-1}a
n−1
, 含有偶数个 7 77 , 每个有效编码 , 添加一位数字 , 组成 n nn 位有效编码 , 有 7 77 种对应的添加方式 , 即添加 0 , 1 , 2 , 3 , 4 , 5 , 6 0,1,2,3,4,5,60,1,2,3,4,5,6 数字 , 七种方式 ; 方法数是 7 a n − 1 7a_{n-1}7a
n−1
无效编码个数对应的添加方法数 : n − 1 n-1n−1 位编码的无效个数 8 n − 1 − a n − 1 8^{n-1} - a_{n-1}8
n−1
−a
n−1
, 还有奇数个 7 77 , 每个无效编码 , 只能添加一个数字 7 77 , 组成 n nn 位有效编码 , 只有一种方法 ; 方法数是 8 n − 1 − a n − 1 8^{n-1} - a_{n-1}8
n−1
−a
n−1
因此这里可以写出 n nn 位编码的有效个数 a n a_na
n
与 n − 1 n-1n−1 位编码有效个数 a n − 1 a_{n-1}a
n−1
的关系 :
a n a_na
n
= == 7 a n − 1 7a_{n-1}7a
n−1
+ ++ 8 n − 1 − a n − 1 8^{n-1} - a_{n-1}8
n−1
−a
n−1
化简后得到 :
a n a_na
n
= == 6 a n − 1 6a_{n-1}6a
n−1
+ ++ 8 n − 1 8^{n-1}8
n−1
7 . 初值讨论
如果只有 1 11 位编码 , 肯定不能是 7 77 , 这样就含有奇数个 ( 1 11 个 ) 7 77 , 是无效编码 ;
只能是 0 , 1 , 2 , 3 , 4 , 5 , 6 0,1,2,3,4,5,60,1,2,3,4,5,6 这 7 77 种 , 因此有 1 11 位编码时 , 有效编码个数是 7 77 个 ,
产生 递推方程初值 a 1 = 7 a_1 = 7a
1
=7
8 . 最终得到的递推方程 :
递推方程 : a n a_na
n
= == 6 a n − 1 6a_{n-1}6a
n−1
+ ++ 8 n − 1 8^{n-1}8
n−1
初值 : a 1 = 7 a_1 = 7a
1
=7
解上述递推方程的通项公式 : a n = 6 n + 8 n 2 a_n = \cfrac{6^n + 8^n}{2}a
n
=
2
6
n
+8
n
二、递推方程示例小结
该问题是一个具体的计数问题 , 上述问题并不是简单的计数 ,
该计数带参数 n nn ,
这种类型的计数 , 可以看成一个 数列计数结果 ,
如果可以找到该数列 , 后项 , 前项 , 的依赖关系 ,
并且知道 初值 ,
就可以 解出该数列的通项公式 ,
该通项公式就恰好对应该计数结果 ;
