我正在解决CLRS"算法简介"中的练习2.1-4。
该问题描述为：
考虑添加两个 n 位二进制整数的问题，存储在两个 n 元素数组 A 和 B 中。两个整数的总和应以二进制形式存储在元素数组 C 中。
这个问题的循环不变性是什么？我对这个问题有一些想法，并将它们作为评论写在我的这个问题的解决方案中，用 golang 写的。
package additoin_binary
/*
Loop invariant:
At the start of each iteration of the loop digits in the subarray r[len(r) - 1 - i:] are
a[len(a) - 1 - i:] + b[len(b) - 1 - i:] + carry | provided that (len(a) - 1 - i) and (len(b) - 1 - i) are positive
a[len(a) - 1 - i:] + carry | provided that (len(a) - 1 - i) is positive and (len(b) - 1 - i) is negative
carry | provided that (len(a) - 1 - i) and (len(b) - 1 - i) are negative
*** carry for i = a[(len(a) - 1) - i - 1] + b[(len(b) - 1) - i - 1] == 2 ? 1 : 0
*/
func BinaryAddition(a, b []int) []int {
// a and b can have arbitrary number of digits.
// We should control a length of the second term. It should be less or equal to a length of first term.w
// Other vise we swap them
if len(b) > len(a) {
b, a = a, b
}
// loop invariant initialization:
// before first loop iteration (i=0) index b_i is out of the array range (b[-1]), so we don't have second term and sum = a
// another way of thinking about it is we don't get b as argument and then sum = a, too
if len(b) == 0 {
return a
}
// result array to store sum
r := make([]int, len(a)+1)
// overflow of summing two bits (1 + 1)
carry := 0
// loop invariant maintenance:
// we have right digits (after addition) in r for indexes r[len(r) - 1 - i:]
for i := 0; i < len(r); i++ {
a_i := len(a) - 1 - i // index for getting a last digit of a
b_i := len(b) - 1 - i // index for getting a last digit of b
r_i := len(r) - 1 - i // index for getting a last digit of r
var s int
if b_i >= 0 && a_i >= 0 {
s = a[a_i] + b[b_i] + carry
} else if a_i >= 0 {
s = a[a_i] + carry
} else { // all indexes run out of the game (a < 0, b < 0)
s = carry
}
if s > 1 {
r[r_i] = 0
carry = 1
} else {
r[r_i] = s
carry = 0
}
}
// loop invariant termination:
// i goes from 0 to len(r) - 1, r[len(r) - 1 - ([len(r) - 1):] => r[:]
// This means, that for every index in r we have a right sum
//*At i=0, r[i] a sum can be equal to 0, so we explicitly check that before return r
if r[0] == 0 {
return r[1:]
} else {
return r
}
}
编辑1：我扩展了原始问题。所以现在数组 A 和 B 可以有任意长度，分别是 m 和 n。 示例 A = [1,0,1]， B = [1,0] (m=3， n=2(
考虑添加两个 n 位二进制整数的问题，存储在两个 n 元素数组 A 和 B 中。两个整数的总和应以二进制形式存储在元素数组 C 中。
该问题保证 A 和 B 是 n 元素数组，我认为这是一个可以减少代码工作的重要条件。
什么是循环不变量？
简单来说，循环不变量是某个谓词(条件(，它对循环的每次迭代都成立。
在这个问题中，如果假设len = len(C)，在[0, len)中迭代i，循环不变性是r[len-1-i:len]总是a[len-2-i:len-1]和b[len-2-i:len-1]在低位i + 1的总和。因为每次循环后，你都会做出一个正确的位，它可以证明算法是正确的。
循环不变条件可以作为尚未添加到n - p的位数(假设您首先从右到左添加 lsb 位(，其中p我已将当前位有效位置nAugend 和 Addend 位序列的大小。