密码方阵

说明

实现一种经典的秘密消息编写方法，叫作方阵密码。

给定一段英文文本，输出这段文本的编码版本。

首先，对输入进行规范化：去掉英文文本中的空格和标点符号，并把消息转换为小写。

然后，把规范化后的字符分成若干行。 打印时如果在行与行之间插入换行符，这些行就可以看作组成了一个矩形。

例如，下面这句话

"If man was meant to stay on the ground, god would have given us roots."

会规范化成：

"ifmanwasmeanttostayonthegroundgodwouldhavegivenusroots"

明文应该排成一个尽可能接近正方形的矩形。 矩形的大小由消息的长度决定。

如果 c 是列数，r 是行数，那么对于 r x c 的矩形，找出满足以下条件的最小整数 c：

• r * c >= length of message，
• 且 c >= r，
• 且 c - r <= 1。

规范化后的文本有 54 个字符，对应一个 c = 8、r = 7 的矩形：

"ifmanwas"
"meanttos"
"tayonthe"
"groundgo"
"dwouldha"
"vegivenu"
"sroots  "

编码后的消息是这样得到的：从左到右逐列向下读取。

上面的消息编码后是：

"imtgdvsfearwermayoogoanouuiontnnlvtwttddesaohghnsseoau"

把编码后的文本按块输出，这些块正好填满 (r X c) 的矩形，即 c 个长度为 r 的块，块之间用空格分隔。 如果短语比完美矩形少 n 个字符，就给最后 n 个块各补一个末尾空格。

"imtgdvs fearwer mayoogo anouuio ntnnlvt wttddes aohghn  sseoau "

注意，如果把这些块竖着叠起来，我们就能用肉眼把密文还原成原始消息：

"imtgdvs"
"fearwer"
"mayoogo"
"anouuio"
"ntnnlvt"
"wttddes"
"aohghn "
"sseoau "

---

来源

J Dalbey 的 Programming Practice 习题