[TOC]
** 声明**
该系列文章来自：http://aperiodic.net/phil/scala/s-99/
大部分内容和原文相同,加入了部分自己的代码。
如有侵权，请及时联系本人。本人将立即删除相关内容。
P46 (**) Truth tables for logical expressions.
要求
Define functions and, or, nand, nor, xor, impl, and equ (for logical equivalence) which return true or false according to the result of their respective operations; e.g. and(A, B) is true if and only if both A and B are true.
scala> and(true, true)
res0: Boolean = true
scala> xor(true. true)
res1: Boolean = false
A logical expression in two variables can then be written as an function of two variables, e.g: (a: Boolean, b: Boolean) => and(or(a, b), nand(a, b))
Now, write a function called table2 which prints the truth table of a given logical expression in two variables.
scala> table2((a: Boolean, b: Boolean) => and(a, or(a, b)))
A B result
true true true
true false true
false true false
false false false
代码
按要求，调用方法如and(true, true)更像是工具方法而非类方法，因此将其定义为object的方法即可。
object S99Logic {
def and(a: Boolean, b: Boolean): Boolean = (a, b) match {
case (true, true) => true
case _ => false
}
def or(a: Boolean, b: Boolean): Boolean = (a, b) match {
case (false, false) => false
case _ => true
}
def not(a: Boolean): Boolean = !a
def nand(a: Boolean, b: Boolean): Boolean = not(and(a, b))
def nor(a: Boolean, b: Boolean): Boolean = not(or(a, b))
def equ(a: Boolean, b: Boolean): Boolean = or(and(a, b), and(not(a), not(b)))
def xor(a: Boolean, b: Boolean): Boolean = not(equ(a, b))
def impl(a: Boolean, b: Boolean): Boolean = or(not(a), b)
def table2(f: (Boolean, Boolean) => Boolean) {
println("A B result")
for (
a <- List(true, false);
b <- List(true, false)
) {
printf("%-5s %-5s %-5s\n", a, b, f(a, b))
}
}
}
P47 (*) Truth tables for logical expressions (2).
要求
Continue problem P46 by redefining and, or, etc as operators. (i.e. make them methods of a new class with an implicit conversion from Boolean.) not will have to be left as a object method.
scala> table2((a: Boolean, b: Boolean) => a and (a or not(b)))
A B result
true true true
true false true
false true false
false false false
代码
按要求需要将布尔值隐式转换为该类型对象以支持中缀操作符
class S99Logic(a: Boolean) {
import S99Logic._
def and(b: Boolean): Boolean = (a, b) match {
case (true, true) => true
case _ => false
}
def or(b: Boolean): Boolean = (a, b) match {
case (true, _) => true
case (_, true) => true
case _ => false
}
def equ(b: Boolean): Boolean = (a and b) or (not(a) and not(b))
def xor(b: Boolean): Boolean = not(a equ b)
def nor(b: Boolean): Boolean = not(a or b)
def nand(b: Boolean): Boolean = not(a and b)
def impl(b: Boolean): Boolean = not(a) or b
}
object S99Logic {
implicit def boolean2S99Logic(a: Boolean): S99Logic = new S99Logic(a)
//...
}
P49 (**) Gray code.
要求
格雷码
An n-bit Gray code is a sequence of n-bit strings constructed according to certain rules. For example,
n = 1: C(1) = ("0", "1").
n = 2: C(2) = ("00", "01", "11", "10").
n = 3: C(3) = ("000", "001", "011", "010", "110", "111", "101", "100").
Find out the construction rules and write a function to generate Gray codes.
scala> gray(3)
res0 List[String] = List(000, 001, 011, 010, 110, 111, 101, 100)
See if you can use memoization to make the function more efficient.
代码
P50 (***) Huffman code.
霍夫曼码
要求
First of all, consult a good book on discrete mathematics or algorithms for a detailed description of Huffman codes!
We suppose a set of symbols with their frequencies, given as a list of (S, F) Tuples. E.g. (("a", 45), ("b", 13), ("c", 12), ("d", 16), ("e", 9), ("f", 5)). Our objective is to construct a list of (S, C) Tuples, where C is the Huffman code word for the symbol S.
scala> huffman(List(("a", 45), ("b", 13), ("c", 12), ("d", 16), ("e", 9), ("f", 5)))
res0: List[String, String] = List((a,0), (b,101), (c,100), (d,111), (e,1101), (f,1100))
