问答题
4. 给定一个数组a[N]，希望构造一个新的数组b[N]，其中，b[i]=a[0]*a[1]*…*a[N-1]/a[i]。在构造数组的过程中，有如下几点要求：
(a)不允许使用除法；
(b)要求O(1)空间复杂度和O(N)时间复杂度；
(c)除遍历计数器与a[N]、b[N]外，不可以使用新的变量(包括栈临时变量、堆空间和全局静态变量等)；
(d)请用程序实现并简单描述。
【正确答案】如果没有时间复杂度与空间复杂度的要求，算法将非常简单，首先遍历一遍数组a，计算数组a中所有元素的乘积，并保存到一个临时变量tmp中，然后再遍历一遍数组a并给数组赋值：b[i]=tmp/a[i]，但是这种方法使用了一个临时变量，因此，不满足题目的要求，下面介绍另外一种方法。
在计算b[i]的时候，只要将数组a中除了a[i]以外的所有值相乘即可。这种方法的主要思路为：首先遍历一遍数组a，在遍历的过程中对数组b进行赋值：b[i]=a[i-1]*b[i-1]，这样经过一次遍历后，数组b的值为b[i]=a[0]*a[1]*…*a[i-1]。此时只需要将数组中的值b[i]再乘以a[i+1]*a[i+2]*…a[N-1]，实现方法为逆向遍历数组a，把数组后半段值的乘积记录到b[0]中，通过b[i]与b[0]的乘积就可以得到满足题目要求的b[i]，具体而言，执行b[i]=b[i] *b[0](首先执行的目的是为了保证在执行下面一个计算的时候，b[0]中不包含与b[i]的乘积)，接着记录数组后半段的乘积到b[0]中：b[0]*=b[0]*a[i]。
实现代码如下：
def calculate(a,b):
b[0]=1
N=len(a)
i=1
while i＜N:
b[i]=b[i-1]*a[i-1] #正向计算乘积
i+=1
b[0]=a[N-1]
i=N-2
while i＞=1:
b[i]*=b[0]
b[0]*=a[i] #逆向计算乘积
i-=1
if __name__=="__main__":
a=[1,2,3,4,5,6,7,8,9,10]
b=[None]*len(a)
calculate(a,b)
i=0
while i＜len(b):
print b[i],
i+=1
程序的运行结果为：
3628800 1814400 1209600 907200 725760 604800 518400 453600 403200 362880