[原]算法导论习题2.1-4

#-*- coding:utf-8 -*- '''
Exercises 2.1-4：
Consider the problem of adding two n-bit binary integers, stored in two n-element arrays A and B. The sum of the two integers should be stored in binary form in an (n + 1)-element array C. State the problem formally and write pseudocode for adding the two integers. 算法思想：
我们可以将两个数组看做是两个逻辑运算单元的寄存器。
寄存器中的数相加的时候需要一个寄存器保存进位，实际
中相加的数有三个，即两个数组中的数和进位寄存器中的
进位。相加结果如果大于1，则必须进位，即进位寄存器
里的数要加1。 ''' def sum_binary(A, B, n): count = 0 C = [0] * (n + 1) for i in range (n - 1, -1, -1): C[i + 1] = A[i] + B[i] + count if C[i + 1] <= 1: count = 0 elif C[i + 1] == 2 : C[i + 1] = 0 count = 1 elif C[i + 1] ==3 : C[i + 1] =1 count = 1 #C数组的第一位存入最后一步运算得到的进位值 C[0] = count return C a = [1, 0, 0, 1, 1, 1]
b = [0, 1, 1, 1, 0, 1]
print u'A数组保存的二进制数是:',a
print u'B数组保存的二进制数是:',b
print u'数组二进制数之和为:', sum_binary(a, b, len(a))