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