首页 > 代码库 > 两个数组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]

2024-07-17 19:38:44   220人阅读

【问题】

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 <stdio.h>
#include <stdlib.h>

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;
}


联系
我们