算法设计与分析——字符a~h出现的频率恰好是前8个斐波那契数——斐波那契数和霍夫曼编码的关系——数学证明

文章目录

注意我这里写反了，应该是左0右1

题目描述

字符a~h出现的频率恰好是前8个Fibonacci数，它们的哈夫曼编码是什么？将结果推广到n个字符的频率恰好是n个Fabonacci数的情形。

证明过程
前八个斐波那契数规律发现

在这里插入图片描述
在这里插入图片描述

规律的数学证明

如果要保证上面推论，得保证每一个项都是类似的树型结构，映射到数值之间的关系就是下图的结论
在这里插入图片描述
在这里插入图片描述
这里是对推论的样例举例和具体说明，比较好懂！
在这里插入图片描述

在这里插入图片描述

分析与总结
  • 算法设计和分析真的是比较难，还需好好努力，加油！不过挺有意思的！