首页 > 代码库 > 0810------笔试题----------腾讯2012年的一道笔试题

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

2024-07-16 19:50:27   222人阅读

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\t", b[i]);    }    printf("\n");    return 0;}

 

　　


联系
我们