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