Маҳсулоти массив ба ғайр аз худ


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Accolite Amazon DE Шо Morgan Stanley Опера
тартиботи ҳарбӣ Матем

Изҳороти мушкилот

Масъалаи "Маҳсулоти массив, ба истиснои худ", қайд мекунад, ки ба шумо массиви [] дода мешавад. Чопи дигар асал p [] -и ҳамон андоза, ба тавре ки қимат дар шохиси i'-и массиви p ба ҳосили ҳамаи элементҳои массиви аслӣ, ба истиснои унсури индекси i'-и массиви а, баробар аст.

мисол

Маҳсулоти массив ба ғайр аз худ

a [ ] = {1, 2, 3}
{6, 3, 2}

Шарҳ: Азбаски андозаи массив 3. аст. Агар мо унсури 2 ва 3-ро зарб кунем, ҳосили он 6 аст. Ҳамин тавр, мо инро барои унсурҳои индекси 2 ва 3 мекунем. Ҳамин тариқ, натиҷа {6, 3, 2} мебошад.

a [ ] = {4, 6, 1, 2}
{12, 8, 48, 24}

Истифодаи усули шӯъба

Ин усул танҳо дар ҳолате муассир аст, ки агар ҳамаи элементҳои массив ҳамеша аз 0 бузургтар бошанд.

Алгоритм

1. Initialize an array a[] of size n.
2. Initialize a variable prod and store product of all the elements of the array a[] in it.
3. Create another array p[] to store products of all elements except self.
4. Traverse through array a[] and update the value of array p[] such that p[i] is equal to the division of a[i] and prod.
5. Print the array p[].

Агар мо барои тағир додани ҳосили ҳамаи ададҳо (унсурҳои массив, вуруд) тағирёбандаро истифода барем, масъала ҳал карда мешавад. Пас ҷавоби ҳар як унсурро ёфтан мумкин аст, агар унсури ҷориро аз зарбкунии куллӣ тақсим кунед (яъне ҳосили ҳамаи элементҳо).

рамз

C ++ Барнома барои маҳсулоти массив, ба истиснои худ

#include <bits/stdc++.h>
using namespace std;

void prodArray(int a[], int n){
    int p[n], prod=1;
    
    //Find product of all elements of a[]
    for(int i=0; i<n; i++){
        prod = prod * a[i];
    }
    
    //Create array p[] to store
    //product except self
    for(int i=0; i<n; i++){
        p[i] = prod / a[i];
    }
    
    for(int i=0; i<n; i++){
        cout<<p[i]<<" ";
    }
}

int main() {
  int a[] = {4, 6, 1, 2};
  int n = sizeof(a)/sizeof(a[0]);
  prodArray(a,n);
  return 0;
}
12 8 48 24

Барномаи Java барои маҳсулоти массив, ба истиснои худ

class product{
    
    void prodArray(int a[], int n){
        int p[] = new int[n], prod=1;
        
        //Find product of all elements of a[]
        for(int i=0; i<n; i++){
            prod = prod * a[i];
        }
        
        //Create array p[] to store
        //product except self
        for(int i=0; i<n; i++){
            p[i] = prod / a[i];
        }
        
        for(int i=0; i<n; i++){
            System.out.print(p[i] + " ");
        }
    }
    
    public static void main(String[] args){
        product pro = new product();
    	int a[] = {4, 6, 1, 2};
    	int n = a.length;
    	pro.prodArray(a,n);
    }
}
12 8 48 24

Таҳлили мураккабӣ

Мураккабии вақт

O (N), ки дар он шумораи элементҳо N мебошанд, зеро дар ин ҷо мо аввал массиви гузаштем, ки алгоритмро дар вақти O (N) иҷро мекунад.

Мураккабии фазо

О (1), зеро мо фазои иловагии доимиро истифода мебурдем. Аммо барнома дар маҷмӯъ фазои O (N) -ро мегирад, зеро мо вурудро захира кардем.

Бе усули тақсимот

Алгоритми маҳсулоти массив, ба истиснои мушкилоти худ

1. Initialize an array a[] of size n and a variable prod as 1.
2. Create another array p[] of the same size with all the elements as 1.
3. Traverse all the values from starting index to last index and update the values of array p[] such that p[i] = prod and prod = prod * a[i].
4. Initialize prod as 1 again and start traversing the array from last index to starting index.
5. Update array p[] such that p[i] = prod and prod = prod * a[i].
6. Print the array p[].

рамз

C ++ Барнома барои маҳсулоти массив, ба истиснои худ

#include <bits/stdc++.h>
using namespace std;

void prodArray(int a[], int n){
        
    if(n == 1) { 
        cout<<"0"; 
        return; 
    } 

    int prod = 1; 
    int p[n]; 

    /* Initialize the product array p[] as 1 */
    for(int j=0; j<n; j++) 
        p[j] = 1; 

    /* prod variable contains product of 
       elements on left side excluding a[i] */
    for(int i=0; i<n; i++) { 
        p[i] = prod; 
        prod *= a[i]; 
    } 

    /* Initialize prod to 1 for product on right side */
    prod = 1; 

    /* prod variable contains product of 
       elements on right side excluding a[i] */
    for(int i=n-1; i>=0; i--) { 
        p[i] *= prod; 
        prod *= a[i]; 
    } 
    for(int i=0; i<n; i++) 
        cout<<p[i]<<" ";

    return; 
}

int main() {
  int a[] = {4, 6, 1, 2};
  int n = sizeof(a)/sizeof(a[0]);
  prodArray(a,n);
  return 0;
}
12 8 48 24

Барномаи Java барои маҳсулоти массив, ба истиснои худ

class product{
    
    void prodArray(int a[], int n){
        
        if(n == 1) { 
            System.out.print("0"); 
            return; 
        } 
  
        int prod = 1; 
        int p[] = new int[n]; 
  
        /* Initialize the product array p[] as 1 */
        for(int j=0; j<n; j++) 
            p[j] = 1; 
  
        /* prod variable contains product of 
           elements on left side excluding a[i] */
        for(int i=0; i<n; i++) { 
            p[i] = prod; 
            prod *= a[i]; 
        } 
  
        /* Initialize prod to 1 for product on right side */
        prod = 1; 
  
        /* prod variable contains product of 
           elements on right side excluding a[i] */
        for(int i=n-1; i>=0; i--) { 
            p[i] *= prod; 
            prod *= a[i]; 
        } 
        for(int i=0; i<n; i++) 
            System.out.print(p[i] + " ");
  
        return; 
    }
    
    public static void main(String[] args){
        product pro = new product();
    	int a[] = {4, 6, 1, 2};
    	int n = a.length;
    	pro.prodArray(a,n);
    }
}
12 8 48 24

Таҳлили мураккабӣ

Мураккабии вақт

O (N), зеро дар ин ҷо мо аз массиви дорои андозаи N гузаштем.

Мураккабии фазо

О (1), зеро мо танҳо массиви аввалро иваз кардем ва танҳо фазои иловагии доимиро истифода кардем. Барнома дар маҷмӯъ фазои O (N) -ро мегирад, аммо худи алгоритм танҳо фазои O (1) -ро мегирад.