题目219：不相等定价编码
Skew-cost codingLet A and B be bit strings (sequences of 0's and 1's).
If A is equal to the leftmost length(A) bits of B, then A is said to be a prefix of B.
For example, 00110 is a prefix of 001101001, but not of 00111 or 100110.
A prefix-free code of size n is a collection of n distinct bit strings such that no string is a prefix of any other. For example, this is a prefix-free code of size 6:
0000, 0001, 001, 01, 10, 11
Now suppose that it costs one penny to transmit a '0' bit, but four pence to transmit a '1'.
Then the total cost of the prefix-free code shown above is 35 pence, which happens to be the cheapest possible for the skewed pricing scheme in question.
In short, we write Cost(6) = 35.
What is Cost(109) ?
题目：
定义 A 和 B 为 比特字符串（即 0 和 1 组成的串）
如果，B 的前 length(A) 比特与 A 相同，则 A 就是 B 的一个前缀。
比如，00110 就是 001101001 的一个前缀，但不是 00111 或 100110 的前缀
所谓大小为 n 的无前缀编码，指的就是 n 条不同的比特串，任意两条之间不存在前缀关系。下面就是大小为 6 的无前缀编码的一个例子：
0000, 0001, 001, 01, 10, 11
现在假设，传送一位‘0’的话，需要 1 美分，而传送一位 '1'，则需要 4 美分。
则上面的的无前缀编码例子的总花费就是 35 美分，在不相等定价方案中（即 0 和 1 的花费不同）这正好是花费最小的做法。
因此，我们定义 Cost(6) = 35。
请问 Cost(109) 等于多少 ?
页:
[1]