1011 a+b 和 c (15 分)

题目描述：

给定一个十进制正整数 N，写出它在 2 ~ 10 进制下的表现形式。输入格式：每个测试输入包含 1 个测试用例，即给出正整数 N 的值。输出格式：对应每个测试用例，输出 N 分别在 2 ~ 10 进制下的数，共 9 行，格式为：进制:数值，其中进制从 2 到 10。

输入样例：

十进制正整数 N 的值。

输出样例：

进制:数值。

样例：

输入样例：

23

输出样例：

2:10111
3:212
4:113
5:43
6:35
7:31
8:27
9:26
10:23

解题思路：

将十进制正整数 N 转换成 2 ~ 10 进制下的数，可以使用除基取余法，即将 N 不断除以进制数，每次将余数记录下来，最后将余数倒序排列即可得到对应进制下的数。

代码实现：

相关问题

某电文由8个字母组成，字母出现的频率如下表所示，请写出字母的哈夫曼编码。 字母 频率 哈夫曼编码 A 22 B 15 C 4 D 3 E 37 F 10 G 7 H 2 电文总长度（WPL）为 位。

首先，按照频率从小到大排序，得到：

H: 2
D: 3
C: 4
G: 7
B: 15
F: 10
A: 22
E: 37

接下来，我们可以使用贪心算法，即每次选择频率最小的两个字母进行合并，直到只剩下一个节点。

具体步骤如下：

1. 将所有节点放入一个优先队列中，按照频率从小到大排序。
2. 取出频率最小的两个节点进行合并，生成一个新的节点，该节点的频率为这两个节点的频率之和，并将这个新节点插入优先队列中。
3. 重复步骤2，直到队列中只剩下一个节点。

下面是具体的合并过程：

1. 合并 C 和 D，得到频率为 7 的新节点 CD。
2. 合并 G 和 CD，得到频率为 14 的新节点 GCD。
3. 合并 B 和 F，得到频率为 25 的新节点 BF。
4. 合并 A 和 E，得到频率为 59 的新节点 AE。
5. 合并 H 和 GCD，得到频率为 16 的新节点 H-GCD。
6. 合并 BF 和 H-GCD，得到频率为 41 的新节点 BF-H-GCD。
7. 最终得到的树如下所示：

              97
            /    \
           /      \
         41       AE
        /   \
       /     \
  BF-H-GCD   16
            /  \
           /    \
         H      GCD
               /  \
              /    \
             G      CD
                  /  \
                 /    \
                C      D

最后，我们可以根据这棵树来为每个字母生成哈夫曼编码：

A: 1
B: 00
C: 1011
D: 1010
E: 11
F: 010
G: 100
H: 1012

其中，每个字母的哈夫曼编码即为从根节点开始，到达该字母节点的路径上的边所对应的二进制数。注意到，由于哈夫曼编码不允许有任何一个编码是另一个编码的前缀，所以对于 C 和 D，我们需要分别使用 1011 和 1010 来区分它们。

最终，电文总长度为：

$WPL = 22 \times 1 + 15 \times 2 + 4 \times 4 + 3 \times 4 + 37 \times 2 + 10 \times 3 + 7 \times 3 + 2 \times 4 = 224$ 位。

用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码："THIS PROGRAM IS MY FAVORITE"。 字符 A B C DE F G H I J K L M 频度 1866413223210321 154757 1 5 3220 字符N 0 P Q R S T U V WXY Z 频度 57 63 15 1 48 51 80238 18 1 161 2在Java中

首先，根据字符集和频度建立哈夫曼树如下：

                                             +-------+
                                             |total: 1|
                                             +-------+
                                                  |
              +-----------------------------------+----------------+
              |                                                       |
         +----+-----+                                           +----+-----+
         |          |                                           |          |
     +--+--+    +--+--+                                     +--+--+    +--+--+
     |  E  |    |  T  |                                     |  A  |    |  O  |
     +--+--+    +--+--+                                     +--+--+    +--+--+
        |          |                                           |          |
   +----+----+ +---+----+                                +----+----+ +---+----+
   |       1  | |      2 |                                |     3   | |      4 |
   |     C    | |     Y  |                                |    S    | |     B  |
   +----------+ +--------+                                +---------+ +--------+
                                                  

接着，根据哈夫曼树进行编码，得到：

T: 11011
H: 1111
I: 1010
S: 010
 : 0010
P: 11101
R: 0000
O: 1000
G: 111001
A: 1011
M: 111000
Y: 11010
F: 11001
V: 11100000
E: 011

因此，报文 "THIS PROGRAM IS MY FAVORITE" 的编码为：

11011111101110101010001101000110101001000111101110100001010011010100110111100011011111100100011101110101001001101010011001110111000100111110101101001110100010101001111011001010110110111111000

最后，根据哈夫曼树进行译码，得到：

THIS PROGRAM IS MY FAVORITE