“数组a，长度为n（索引为0至n-1）。现要求更新数组的各个元素，使新数组的第i个元素等于原数组中除第i个元素之外各元素之积。”

问题：“数组a，长度为n（索引为0至n-1）。现要求更新数组的各个元素，使新数组的第i个元素等于原数组中除第i个元素之外各元素之积。即：

a[0]变为a[1]到a[n-1]的积，a[1]变为a[0]和a[2]到a[n-1]的积，……a[n-1]为a[0]到a[n-2]的积。要求：具有线性复杂度。不能使用除法运算符。”

讨论：最后两项要求恰好排除了最直观的两种方法"两层循环乘法"、“求全部元素的积P，然后New[i] = P / Old[i]”，卡死了思路，完全没想出来

后来参考了 帖子  16楼 qq120848369 的答案才明白。（第一次还没看懂，跳过去了）

倒推出解题思路：新数组每个元素都是前、后两段“部分积”相乘的结果。前方的部分积很容易想到用数组保存结果，在O(n)的时间内计算。

关键是后方的部分积也可以同样算出，只是要反向累乘。逆向思维……

#include <iomanip>
#include <iostream>
using namespace std;

void show(int v[], int n, char const * name)
{
  cout << name << ": ";
  for(int i = 0; i < n; ++i){
    cout << setw(7) << v[i];
  }
  cout << "
";
}

int main()
{
  int a[] = {2, 3, 5, 7, 11}; // 用质数测试保证每个积都唯一。
  int const N = sizeof(a) / sizeof(a[0]);

  int prod_fore[N];
  int prod_back[N];
  prod_fore[0  ] = 1;
  prod_back[N-1] = 1;

  for(int i = 1; i < N; ++i){
    prod_fore[i] = a[i-1] * prod_fore[i-1];
  }

  for(int i = N-2; i >= 0; --i){
    prod_back[i] = a[i+1] * prod_back[i+1];
  }

  show(a        , N, "source   ");

  for(int i = 0; i < N; ++i){
    a[i] = prod_fore[i] * prod_back[i];
  }

  show(prod_fore, N, "prod_fore");
  show(prod_back, N, "prod_back");
  show(a        , N, "result   ");
}