0810------笔试题----------腾讯2012年的一道笔试题

1.题目要求

　　a）b[i] = a[0] *a[1] *a[2]*….a[n-1]/ a[i]，求出数组b；

　　b）要求不能用除法，除循环控制变量以外，不许额外申请其余变量，时间复杂度为O(n),空间复杂度为O(1)。　

2.程序思路

　　a）假设 N = 5，那么 b[0] =      a[1]*a[2]*a[3]*a[4];

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

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

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

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

　　b）这里采用分段法，即以缺少的元素为界限分成两段，先求左边的一段（灰色部分），可以看到除b[0]外是依次相乘的，题目中不让申请其余变量，因此我们可以暂时使用b[0]作为中间变量，存储a中元素相乘后的值，然后在赋值给b，同理右半部分也是这么求解的。

3.程序

#include <stdio.h>

#define N 5
/*
 * b[i] = a[0]*.....*a[N-1]/a[i];
 * 复杂度 分别为O(n) 和  O(1)
 */

int main(int argc, const char *argv[])
{
    int a[N] = {5, 2, 3, 7, 4};
    int b[N];

    //前半段
    b[0] = 1; //以b[0]为中介
    int i;
    for(i = 1; i < N; i++){
        b[0] *= a[i-1];
        b[i] = b[0];
    }

    //后半段
    b[0] = 1;
    for(i = N-2; i > 0; i--){
        b[0] *= a[i+1];
        b[i] *= b[0];
    }
    b[0] *= a[1];

    //输出
    for(i = 0 ; i < N; i++){
        printf("%4d	", b[i]);
    }
    printf("
");

    return 0;
}