不用除法运算符的除法

题目描述：

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

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

除遍历计数器与a[N] b[N]外，不可使用新的变量（包括栈临时变量、堆空间和全局静态变量等）；实现程序（主流编程语言任选）实现并简单描述。

代码：

#include <stdio.h>
void PrintfArray(int a[], int n)
{
for (int i = 0; i < n; i++)
printf("%5d ", a[i]);
putchar('n');
}
int main()
{
const int MAXN = 5;
int a[MAXN] = {1, 3, 5, 7, 9};
int b[MAXN];
printf("数组a为:n");
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为:n");
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];

代码修改为：

把

 for (i = MAXN - 2; i >= 0; i--)
{
temp *= a[i + 1];
b[i] *= temp;
}

改为

for (i = MAXN - 1; i >= 1; i--)
{
b[i] *= b[0];
b[0] *= a[i];
}

参考转自：http://blog.csdn.net/morewindows/article/details/8742666