Question

求解：给定一个数组a[N],我们希望构造数组b[N]，其中b[i]=a[0]*a[1]*...*a[N-1]/a[i]。 下面是完整题目

给定一个数组a[N],我们希望构造数组b[N]，其中b[i]=a[0]*a[1]*...*a[N-1]/a[i]。在构造过程：
不允许使用除法；
要求O(1)空间复杂度和O(n)时间复杂度；
除遍历计数器与a[N] b[N]外，不可使用新的变量(包括栈临时变量、对空间和全局静态变量等)；
请用程序实现并简单描述。

Answer 1

void array()

{

    const int N = 8;

int a[N] = {1, 2, 3, 4, 5, 6, 7, 8};

int b[N] = {1, 1, 1, 1, 1, 1, 1, 1};

for (int i = 0; i < N; i++)

{

    for (int j = 0; j < N; j++)

if (i == 0)

                b[i] *= a[j];

else if (i < j || i > j)

b[i] *= a[j];

}

cout << endl;

for (int t = 0; t < N; t++)

cout << "b[" << t << "] = " <<b[t] << endl;

Answer 2

int main(){
const int n = 8;
int a[n] = {1,2,3,4,5,6,7,8};
int b[n];
b[n-1] = 1;
for (int i=n-2;i>=0;i--)
b[i] = b[i+1]*a[i+1];

int c = 1;
for(int i=1;i<n;i++)
{
c*=a[i-1];
b[i] *= c;
}
for (int i=0;i<n;i++)
cout << b[i] << endl;

}

追问

可是，要求说了不能使用中间变量啊，“int c=1”不符合要求啊

追答

int main(){
const int n = 8;
int a[n] = {1,2,3,4,5,6,7,8};
int b[n];
b[n-1] = 1;
for (int i=n-2;i>=0;i--)
b[i] = b[i+1]*a[i+1];

for(int i=1;i<n-1;i++)
{
b[n-1]*=a[i-1];
b[i] *= b[n-1];
}
b[n-1]*=a[n-2];
for (int i=0;i<n;i++)
cout << b[i] << endl;

}
这字眼扣的真没意义。这下没有中间变量了。

追问

运行结果：
40320
20160
13440
10080
8064
6720
5760
5040

Answer 3

今天的笔试题。。。