关于洛谷SCP-J12024第8题

S_Z_Xcoco · 2024-08-27 16:33:42 · 算法·理论

众所周知

洛谷的比赛赛题质量一向很好，但rt的这题貌似出了点问题。

表达一下个人观点

这道题，题目没有问题，而选项错了，没有正确答案。

原题在此
8. 假设有一组字符{g,h,i,j,k,l}，它们对应的频率分别为 8%,14%,17%,20%,23%,18%。
请问以下哪个选项是字符 g,h,i,j,k,l 分别对应的一组哈夫曼编码？（ ）
A. g: 1100, h: 1101, i: 111, l: 10, k: 00, j: 01
B. g: 0000, h: 001, i: 010, l: 011, k: 10, j: 11
C. g: 111, h: 110, i: 101, l: 100, k: 01, j: 00
D. g: 110, h: 111, i: 101, l: 100, k: 0, j: 01

原因分析

相信很多人像我一样会产生疑问，这道题答案不是选C吗？这是因为，大家在理解哈夫曼编码（包括做这道题时）就已经发生了错误。

相信大家做这道题时，一定会先画出如下的这棵树。
              100%
            0/     \1
           43%      57%
         0/  \1   0/   \1
       20%   23% 35%    22%
                0/ \1  0/  \1
               18% 17% 8%  14%
然后，对所有的字母进行编码验证，得出了正确答案。

大家可以想一想，你是怎么画出这个树的呢？相信你的回答一定是：每次取频率最低的两个字母进行合成，再不断根据合成的频率继续合成子树的根节点，最后得到100%并进行编码。

但是，这是错误的，所以才会导致一向质量很好的洛谷出现问题。

大家可以结合着1952年哈夫曼发表的哈夫曼编码原文来看，第三页的开头及其文字明确表示：我们在合成频率时，不需要按照先叶子，后子树的顺序。也就是说，在合成时，不管他是不是叶子结点，只要是当前所出现的频率中，最低的两个频率，就直接合成。

那么，我们的树就会变成这样
              100%
            0/     \1
           58%      42%
         0/  \1   0/   \1
       35%   23% 20%    22%
      0/ \1            0/  \1
     17% 18%          8%  14%
所以，正确答案为:
g:110 h:111 i:000 l:001 k:01 j:10

ps

如果觉得我说的有道理：就帮我点个关注再走吧！

关于洛谷SCP-J12024第8题

众所周知

表达一下个人观点

原因分析

相关问题

ps