兩個數組a[N]，b[N]，其中A[N]的各個元素值已知，現給b[i]賦值，b[i] = a[0]*a[1]*a[2]…*a[N-1]/a[i]

兩個數組a[N]，b[N]，其中A[N]的各個元素值已知，現給b[i]賦值，b[i] = a[0]*a[1]*a[2]…*a[N-1]/a[i]

【問題】

1、不用除法運算

兩個數組a[N]，b[N]，其中A[N]的各個元素值已知，現給b[i]賦值，b[i] = a[0]*a[1]*a[2]...*a[N-1]/a[i]； 要求：

• 1.不准用除法運算
• 2.除了循環計數值，a[N],b[N]外，不准再用其他任何變量（包括局部變量，全局變量等）
• 3.滿足時間復雜度O(n)，空間復雜度O(1)。 【分析】

  提示：題目要求b[i] = a[0]*a[1]*a[2]...*a[N-1]/a[i] ，相當於求：a[0]*a[1]*a[2]*a[3]...a[i-1]*a[i+1]..*a[N-1]，等價於除掉當前元素a[i]，其他所有元素(a[i]左邊部分，和a[i]右邊部分)的積。

  記left[i]=∏a[k], (k=1...i-1); right=∏a[k], (k=i+1...n)，根據題目描述b[i]=left[i] * right[i]， 對於每一個b[i]初始化為1，left[i]和right[i]兩部分可以分開兩次相乘，即對於循環變量i=1...n, b[i]=left[i];b[n-i]=right[n-i]， 循環完成時即可完成計算。

  【代碼】

  #include 
  #include 
  
  void Multiplication(int *a, int *b, int length)
  {
  	int i;
  	b[0] = 1;
  	for (i = 1; i < length; i ++) {
  		b[0] *= a[i - 1];
  		b[i] = b[0];
  	}
  	b[0] = 1;
  	for (i = length - 2; i > 0; i--) {
  		b[0] *= a[i + 1];
  		b[i] *= b[0];
  	}
  	b[0] = a[1] * b[0];
  }
  
  int main(void) 
  {
  	int i;
  	int a[] = {2, 2, 3, 4, 5};
  	int b[5];
  	int length = sizeof(a) / sizeof(int);
  	Multiplication(a, b, length);
  	for (i = 0; i < length; i++)
  		printf("%d\t", b[i]);
  	return 0;
  }