程序员人生 网站导航

《剑指offer》:[52]构建乘积数组

栏目:php教程时间:2016-07-08 16:08:33
题目:给定1个数组A[0,1,2...N⑴],请构建1个数组B[0,1,2,...N⑴],使B中的元素B[i]=A[0]*A[1]*...*A[i⑴]*a[i+1]*...*a[n⑴],不能使用除法。
解决思路:通过正反两次来求B[i];  
          正着:B[i]=A[0]*...A[i⑴];
          反着:temp = B[N]*...B[i+1];
 最后通过B[i]*temp就能够求出结果了。  
以A[0,1,2,3,4],求B[0,1,2,3,4]为例:
步骤分析:
第1步:b[0] = 1;  
第2步:b[1] = b[0] * a[0] = a[0]  
第3步:b[2] = b[1] * a[1] = a[0] * a[1];  
第4步:b[3] = b[2] * a[2] = a[0] * a[1] * a[2];  
第5步:b[4] = b[3] * a[3] = a[0] * a[1] * a[2] * a[3];  
然后对第2个for循环  
第1步:
temp *= a[4] = 1*a[4];   
b[3] = b[3] * temp = a[0] * a[1] * a[2] * a[4];  
第2步:  
temp *= a[3] = a[4] * a[3];  
b[2] = b[2] * temp = a[0] * a[1] * a[4] * a[3];  
第3步: 
temp *= a[2] = a[4] * a[3] * a[2];   
b[1] = b[1] * temp = a[0] * a[4] * a[3] * a[2];  
第4步: 
temp *= a[1] = a[4] * a[3] * a[2] * a[1];   
b[0] = b[0] * temp = a[4] * a[3] * a[2] * a[1];  
具体实现代码以下:
#include <iostream> using namespace std; #include <vector> vector<int> array1; vector<int> array2(5); void multiply(const vector<int> &array1,vector<int> &array2) { int length1=array1.size(); int length2=array2.size(); if(length1==length2 && length2>1) { array2[0]=1; for(int i=1;i<length1;i++) { array2[i]=array2[i⑴]*array1[i⑴]; } double temp=1; for(int i=length1⑵;i>=0;i--) { temp*=array1[i+1]; array2[i]*=temp; } } } int main() { for(int i=0;i<5;i++) array1.push_back(i+1); multiply(array1,array2); vector<int>::iterator it1; vector<int>::iterator it2; cout<<"A数组为:"; for(it1=array1.begin();it1!=array1.end();it1++) cout<<*it1<<" "; cout<<endl; cout<<"B数组为:"; for(it2=array2.begin();it2!=array2.end();it2++) cout<<*it2<<" "; cout<<endl; system("pause"); return 0; }

主要是利用中间结果变量。运行结果:


------分隔线----------------------------
------分隔线----------------------------

最新技术推荐