構(gòu)建乘積數(shù)組

給定一個(gè)數(shù)組A[0,1,...,n-1],請(qǐng)構(gòu)建一個(gè)數(shù)組B[0,1,...,n-1],其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法。

這題的意思是 B數(shù)組的元素是A數(shù)組中所有元素的乘積，但是要排除掉當(dāng)前元素

A數(shù)組在i元素左右分成兩部分，分別相乘

left數(shù)組是 A[0]...A[n-1], right數(shù)組是A[1]...A[n]

組合出新的數(shù)組

1. $A=array(1,2,3,4); 
2.   
3. multiply($A); 
4.   
5. function multiply($numbers){ 
6.   
7.     $len=count($numbers); 
8.   
9.     $res=array(); 
10.   
11.     //1. 組合左邊數(shù)組 
12.   
13.     $left=array(); 
14.   
15.     $left[0]=1; 
16.   
17.     for($i=1;$i<$len;$i++){ 
18.   
19.         $left[$i]=$left[$i-1]*$numbers[$i-1]; 
20.   
21.     }   
22.   
23.    
24.   
25.     //2. 組合右邊數(shù)組 
26.   
27.     $right=array(); 
28.   
29.     $right[$len-1]=1; 
30.   
31.     for($j=$len-2;$j>=0;$j--){ 
32.   
33.         $right[$j]=$right[$j+1]*$numbers[$j+1]; 
34.   
35.     }   
36.   
37.    
38.   
39.     //3. 組合新數(shù)組，整好可以實(shí)現(xiàn)A[0]*A[i-1]*A[i+1]*A[n-1]排除當(dāng)前i元素 
40.   
41.     for($i=0;$i<$len;$i++){ 
42.   
43.         $res[$i]=$left[$i]*$right[$i]; 
44.   
45.     }  //Vevb.com 
46.   
47.     return $res; 
48.   
49. }