首页 / 软件开发 / 数据结构与算法 / 经典算法（14） 腾讯2012年实习生笔试加分题

经典算法（14） 腾讯2012年实习生笔试加分题2014-01-03 csdn MoreWindows之前参加2012年腾讯实习生笔试时，在考场中遇到一道加分题，当时灵光一闪，直接挥笔就解决这道题目 。今天看到学校论坛上有师弟师妹们在询问这题的解法，就写篇博客来分享我的解法吧，也欢迎大家讨论其 它解法。

首先来看题目描述：

三 、加分题

28）给定一数组a[N]，我们希望构造数组b [N]，其中b[j]=a[0]*a[1]…a[N-1] / a[j]，在构造过程中，不允许使用除法：

要求O（1）空间复杂 度和O（n）的时间复杂度；

除遍历计数器与a[N] b[N]外，不可使用新的变量（包括栈临时变量、堆 空间和全局静态变量等）；

实现程序（主流编程语言任选）实现并简单描述。

这道题目最为 独特的要求就是除去遍历计算器外不能申请其它新的变量。怎么解决了？首先不考虑这个条件，代码如下：

// 腾讯2012年实习生笔试加分题//http://blog.csdn.net/morewindows/article/details/8742666//By MoreWindows（ http://blog.csdn.net/MoreWindows ）#include <stdio.h>void PrintfArray（int a[], int n）{for （int i = 0; i < n; i++） printf（"%5d ", a[i]）;putchar（"
"）;} int main（）{printf（"腾讯2012年实习生笔试加分题
"）;printf（" - http://blog.csdn.net/morewindows/article/details/8742666 -
"）;printf（" -- By MoreWindows（ http://blog.csdn.net/MoreWindows ） --

"）; const int MAXN = 5;int a[MAXN] = {1, 3, 5, 7, 9};int b[MAXN];printf（"数组a为:
"）;PrintfArray（a, MAXN）;b[0] = 1;int i;for （i = 1; i < MAXN; i++）b[i] = b[i - 1] * a[i - 1];int temp = 1;for （i = MAXN - 2; i >= 0; i--）{temp *= a[i + 1];b[i] *= temp;}printf（"数组b为:
"）;PrintfArray（b, MAXN）;return 0;}

解释下代码，设有数组大小为5。

对于第一个for循环

第一步：b[0] = 1;

第二步： b[1] = b[0] * a[0] = a[0]

第三步：b[2] = b[1] * a[1] = a[0] * a[1];

第四步：b[3] = b[2] * a[2] = a[0] * a[1] * a[2];

第五步：b[4] = b[3] * a[3] = a[0] * a[1] * a[2] * a [3];

然后对于第二个for循环

第一步

temp *= a[4] = a[4];

b[3] = b[3] * temp = a[0] * a[1] * a[2] * a[4];

第二步

temp *= a[3] = a[4] * a[3];

b[2] = b[2] * temp = a[0] * a[1] * a[4] * a[3];

第三步

temp *= a[2] = a[4] * a[3] * a[2];

b[1] = b[1] * temp = a[0] * a[4] * a[3] * a[2];

第四步

temp *= a[1] = a[4] * a[3] * a[2] * a[1];

b[0] = b[0] * temp = a[4] * a[3] * a[2] * a[1];

由此可以看出从b[4]到b[0]均已经 得到正确计算。