不用除法运算符的除法

题目描述：

给定一数组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