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

文章目录

题目描述

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

证明过程

前八个斐波那契数规律发现

规律的数学证明

如果要保证上面推论，得保证每一个项都是类似的树型结构，映射到数值之间的关系就是下图的结论

这里是对推论的样例举例和具体说明，比较好懂！

分析与总结

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