tceic.com
学霸学习网 这下你爽了
赞助商链接
当前位置:首页 >> IT/计算机 >>

国家集训队2008论文集 码之道


etc.
?
? ?

周梦宇 Moony Chou 成都七中 zmy90320@gmail.com

信息

信息论
? ? ? ? ?

?

电报、电话、广播、遥控、雷达…… 无所不在的比特——小小的0和1 都是信息的传输系统 The Mathematical Theory of Communication 信息论的研究对象 《通信的数学理论》 理论模型——通信系统模型 By Claude E. Shannon (香农) 为信息论奠定了基础

通信系统模型
信 源
消 息

编 码 器

信 号

信 道

信 号 干 扰

译 码 器

消 息

信 宿

+

信源编码 加密编码 信道编码

干 扰

信道译码 解密译码 信源译码

噪声源

THE TAO OF CODING

码之道
浅谈信息学竞赛中的编码与译码问题

编码译码常用思想与方法
给出一个字符集S(|S|!小于263) ? 【问题一】求S上的所有全排列中字典序第 k小的排列。 ? 【问题二】给出S的一个全排列,求它是字 典序第几小的。

对S元素排序得出字典序最小排列
不断求出相邻较大排列 (可调用STL中的next_permutation算法)

O(|S|*k) k可高达|S|!
【问题二】——编码 【问题一】——译码

调用(k-1)次便可得到目标字符串 需要不断调用并比较

更优算法
?

?

?

问题二:对字符串编码,既是求“不大于x 的物体有多少个”,是一个计数问题。 字典序顺序的确定:由从前往后第一个不 一样的位确定的。 我们可以考虑用分类思想,一位一位地累 加出编码。

”42153”的编码
?????

1????

2????

3???? 41???

4???? 42???

4!*3=72 3!*1=6 0!*2=2 ∑=80

421?? 42135 42153

?
? ?

2) O(nm
? ? ?

所求字符串长度为n 字符集大小为m 每处理一位字符需要累加最多m个 字符 每次累加需要进行分类模板计数, 时间复杂度为O(m) 每处理一位字符需要O(m2)的时间 总复杂度为O(m2n)。

O(n*n!)

编码译码常用思想与方法
?
?

数论、组合计数几类数学思想
[Twofive, IOI 2001][Hexadecimal Numbers, CEOI 1997]…

?

递推动态规划、枚举搜索、排序、 贪心和构造
[CUDAK, COCI 2007/2008 #3][Zip, Zhejiang OI 2001][A decorative fence, CEOI 2002]…

?

?
?

堆、树状数组等特殊的数据结构
[Huffman][Prüfer]…

编码译码具体应用例举
? ? ?

?

Huffman Code(哈夫曼编码) Gray Code(格雷码) Prüfer Code(普吕弗编码) Hash Function(哈希(散列)函数)

Prüfer编码
? ?

?

标号树:顶点标号为1至n的有n个顶点的树 Cayley定理:不同的标号树的数量是nn-2 1889 “A Theorem on Trees.” Prüfer编码:德国数学家Heinz Prüfer 1918年另一个建设性的证明 Prüfer序列(编码)。

编码过程
? ?

?

?

n个结点的标号树T 不断从T中移除当前标号最小的叶子,直到 T只剩下两个结点。 第i次移除叶子的相邻点的标号即为Prüfer 序列的第i项。 Prüfer编码提供了n结点标号树与每个元素 在[1,n]内的长(n-2)的整数序列的一个双射。

1

2 3

4

6 5 7

{} ,}2,}1,}3,}3,}5} 1

8

Prüfer编码应用
【树的计数, HNOI2004 Day2】 一个有n个结点的树,设它的结点分别为v1, v2, …, vn,已知第i个结点vi的度数为di,问满 足这样的条件的不同的树有多少棵。

Prüfer编码应用
?

注意到一棵标号树的Prüfer编码中标号i会 出现(di-1)次,于是每个点度数已知的n结点 生成标号树的个数为:

(n - 2)! (d1 - 1)!(d2 - 1)!...(d - 1)! n

总结
编码译码就如同水一样:水是生命 之源,编码译码是信息之源;水亦 柔亦刚,编码译码也同样灵动。

道可道,非常道。


推荐相关:

国家集训队2008论文集 论文.pdf

本章通过两道例题, 阐述如何通过深入的问题分析, 合 理运用"周期性"这一特点...国家集训队2008论文集 码... 23页 免费 国家集训队2008论文集浅... 29...

国家集训队2008论文集浅谈信息学中状态的合._图文.ppt

国家集训队2008论文集浅谈信息学中状态的合._职高对口_职业教育_教育专区。国家集训队2008论文集浅谈信息学中状态的合. 浅谈信息学中状态的合理设计与应用 福建省...

国家集训队2008论文集 pálya计数法的应用_图文.ppt

国家集训队2008论文集 pálya计数法的应用_IT/计算机_专业资料。国家集训队2008论文集 Pólya计数法的应用南京外国语学校 陈瑜希 问题描述 ? 06年江苏上海选拔赛 ?...

国家集训队2008论文集 肖汉骏论文.pdf

反之, 若能广泛地了解他人对同一道问题的思路, 则有 助于更加灵活地分析问题...国家集训队2008论文集 论... 35页 免费 国家集训队2008论文集 码... ...

中国国家集训队论文集目录(1999-2009).txt

国家集训队2008论文集 Day1 1.曹钦翔《数据结构的提炼与压缩》 2.郑暾《平衡...周梦宇《码之道浅谈信息学竞赛中的编码与译码问题》 6.肖汉骏《例谈信息...

国家集训队2008论文集浅谈信息学中状态的合.doc

国家集训队2008论文集浅谈信息学中状态的合_IT/计算机_专业资料。国家集训队

国家集训队2008论文集 计算几何中的二分思.doc

这道题目就属于"易而繁"的类型,算法本身并不困难,而计算和编程十分 繁琐.对于...国家集训队2008论文集 码... 23页 免费 国家集训队2008论文集 一... ...

国家集训队2008论文集非完美算法初探任.doc

算法和上面的贪心算法相同,随机算法也是使用较多的一种算法.下面我们来 看一道...国家集训队2008论文集 码... 23页 免费 国家集训队2008论文集浅... 21...

国家集训队2008论文集余林韵_运用化归思想_图文.ppt

则有常数A,B使得: Fkm=A*F(k-1)m+B, N O(M+log 2 ) M 其余三道...国家集训队2008论文集 论... 35页 免费 国家集训队2008论文集 码... ...

国家集训队2008论文集 对块状链表的一点研.doc

首先分析题目: 这道题的命令其实只有两类:1.定位;2.添加或删除. 这两类操作...国家集训队2008论文集 肖... 23页 免费 国家集训队2008论文集 码... ...

国家集训队2008论文集部分贪心在信息学竞赛.doc

正文在我们详细介绍部分贪心算法之前,首先要知道一些比较基础的东西: 1. 2. 3...国家集训队2008论文集 码... 23页 免费 国家集训队2009论文集信... 26...

国家集训队2008论文集 一类算法复合的方法.doc

1.5 小结 对这道题, 我们先经过初步思考, 得出了两个朴素算法: 算法 1.0 ...国家集训队2008论文集 码... 23页 免费 国家集训队2008论文集浅... 21页...

NOI国家集训队论文分类(至2008)(摘抄自C博客).doc

NOI国家集训队论文分类(至2008)(摘抄自C博客)_学科竞赛_高中教育_教育专区。...《码之道浅谈信息学竞赛中的编码与译码问题》 对策问题 2002 - 骆骥:《浅析...

国家集训队2008论文集部分贪心在信息学竞赛_图文.ppt

国家集训队2008论文集部分贪心在信息学竞赛_IT/计算机_专业资料。国家集训队2008论文集 部分贪心在信息学竞赛中的应用 北京市清华附中 高逸涵 引言 ? 引入 ...

国家集训队2008论文集 slide.pdf

国家集训队2008论文集 slide_IT/计算机_专业资料。国家集训队2008论文集 ZJTSC'05 ZJTSC'05 ZJTSC'05 ZJTSC'05 ZJTSC'05 N G2 [a, b] = i =1 G [...

国家集训队2008论文集浅谈随机化思想在几何_图文.ppt

国家集训队2008论文集浅谈随机化思想在几何_IT/计算机_专业资料。国家集训队

国家集训队2008论文集 计算几何中的二分思_图文.ppt

国家集训队2008论文集 计算几何中的二分思 - 计算几何中的二分思想 贵阳市第

国家集训队论文分类整理.pdf

码之道浅谈信息学竞赛中的编码与译码问题》 2002 - 骆骥:《浅析解“对策...国家集训队2009论文集数... 22页 免费 2013集训队论文集 137页 5下载券 ...

国家集训队2008论文集 附件数学相关知识.pdf

国家集训队2008论文集 附件数学相关知识_IT/计算机_专业资料。国家集训队2008论文集 数学相关知识余林韵 2008 年 1 月 22 日 1 数列的定义 按照一定的次序排列的...

国家集训队2008论文集 一类算法复合的方法.pdf

.本 1.5 小结 对这道题, 我们先经过初步思考, 得出了两个朴素算法: 算法 1...国家集训队2008论文集 码... 23页 免费 国家集训队2008论文集浅... 21页...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com