Чоргоникҳоро аз чор массиви ҷудошуда ҳисоб кунед, ки ҷамъашон ба арзиши додашудаи х баробар аст  


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Акколити Фараж Озмоишгоҳҳои Moonfrog Synopsys
тартиботи ҳарбӣ Ҷустуҷӯи бинарӣ Хаш Ҷустуҷӯ Sorting

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

Масъалаи "Чоргоникҳоро аз чор массиви мураттаб ҳисоб кунед, ки ҷамъашон ба арзиши додашудаи х баробар аст" изҳор медоранд, ки ба шумо чор массиви бутун дода мешавад ва қимате бо номи х. Дар гузориши масъала хоҳиш карда мешавад, ки муайян карда шавад, ки чӣ қадар чоргоникҳо ташкил кардан мумкин аст, ки кадом суммаи унсурҳои ҳар як чаҳоргона ба арзиши додашудаи х баробар баробар илова дошта метавонанд.

мисол  

int arr1[] = { 2, 5, 6, 9 };

int arr2[] = { 1, 3, 7, 11 };

int arr3[] = { 1, 5, 6, 8 };

int arr4[] = { 2, 3, 5, 10 };

Sum=32
5

Шарҳ: 5 чаҳоргоникҳо мавҷуданд, ки метавонанд ба онҳо арзиши зарурии x = 5 -ро ҷамъбаст кунанд.

 

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

1. Set the value of count to 0.
2. Declare a map.
3. Traverse the first and second list and store the sum of each pair that can be formed with the two lists into the map along with their frequency.
4, Traverse the other two arrays.
    1. Pick a sum of each pair from the two arrays and check if the x-sum is present in a map.
        1. If present then gets their frequency and add it to the value of count.
5. Return count.

Шарҳ

Мо чор массиви бутун ва адади х додем. Вазифаи мо иборат аз он аст, ки шумораи умумии чоргоникҳоеро ташкил диҳем, ки ба х баробар бошанд. Барои ин, мо истифода бурданием тарошидан. Мо бо истифода аз харита барои ин, ба ин тариқ, он муносибати самарабахши ҳалли ин саволро фароҳам меорад.

ҳамчунин нигаред
Графика ва тасвири он

Қимати ҳисобро ба 0 таъин кунед, ин тағирёбандаи ҳисоб шумораи чаҳоргоникро нигоҳ медорад. Мо харитаро эълон хоҳем кард. Гузариши ду массиви аввалро оғоз кунед ва маблағи ҳар як ҷуфти ду массиви аввалро ҳамчун харита дар харита нигоҳ доред ва басомади ҳар як суммаро ҳамчун арзиши калид ба харита гузоред. Агар мо як ҷуфти дигари арзиши ба ин монандро пайдо кунем. Мо танҳо арзиши басомади маблағро зиёд мекунем. Пас аз гузашти пурраи ду массиви аввал, мо аз ду массиви аввал ҷуфт дорем.

Ҳоло мо ба трафики боз ду массиви дигар меравем, ки аз массиви ду элементи ҳар як ҷуфтро мегирем. Як рақам аз як массив ва як рақам аз дигар. Он гоҳ мо тафтиш мекунем, ки оё фарқи х ва суммаи ин ҷуфт дар харита мавҷуд аст. Он гоҳ мо басомади он ҷуфтро аз харита мегирем. Агар мавҷуд бошад, мо арзиши ҳисобро бо илова кардани ин басомад ба ҳисоб зиёд хоҳем кард, яъне маънои онро дорад, ки мо аз ҳамаи массивҳо як чаҳоргонак пайдо кардем. Сабаб ин аст, ки агар мо 10 + 20 = 30 дошта бошем, пас мо метавонем яке аз қиматҳоро пайдо кунем, зеро 30-10 он аст, ки бо ин ҳалли ба ин монанд рух медиҳад ва дар ниҳоят, мо арзиши ҳисобро бармегардонем.

Чоргоникҳоро аз чор массиви ҷудошуда ҳисоб кунед, ки ҷамъашон ба арзиши додашудаи х баробар астпайвандак

рамз  

Коди C ++ барои ҳисоб кардани чоргоникҳо аз чор массиви ҷудошуда, ки ҷамъашон ба арзиши додашудаи х баробар аст

#include <iostream>
#include<unordered_map>

using namespace std;

int getNumberOfQuadruples(int arr1[], int arr2[], int arr3[],int arr4[], int n, int x)
{
    int count = 0;

    unordered_map<int, int> MAP;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            MAP [arr1[i] + arr2[j]]++;

    for (int k = 0; k < n; k++)
        for (int l = 0; l < n; l++)
        {
            int p_sum = arr3[k] + arr4[l];

            if (MAP.find(x - p_sum) != MAP.end())
                count += MAP [x - p_sum];
        }

    return count;
}
int main()
{
    int arr1[] = { 2, 5, 6, 9 };
    int arr2[] = { 1, 3, 7, 11 };
    int arr3[] = { 1, 5, 6, 8 };
    int arr4[] = { 2, 3, 5, 10 };

    int n = sizeof(arr1) / sizeof(arr1[0]);
    int x = 32;
    cout << "Count = "<< getNumberOfQuadruples (arr1, arr2, arr3, arr4, n, x);
    return 0;
}
Count = 3

Рамзи Java барои ҳисоб кардани чоргоникҳо аз чор массиви ҷудошуда, ки ҷамъашон ба арзиши додашудаи х баробар аст

import java.util.HashMap;

class QuadrupletsSum
{
    public static int getNumberOfQuadruples (int arr1[], int arr2[], int arr3[], int arr4[], int n, int x)
    {
        int count = 0;

        HashMap<Integer,Integer> MAP = new HashMap<>();

        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if(MAP.containsKey(arr1[i] + arr2[j]))
                    MAP.put((arr1[i] + arr2[j]), MAP.get((arr1[i] + arr2[j]))+1);
                else
                    MAP.put((arr1[i] + arr2[j]), 1);

        for (int k = 0; k < n; k++)
            for (int l = 0; l < n; l++)
            {
                int p_sum = arr3[k] + arr4[l];

                if (MAP.containsKey(x - p_sum))
                    count += MAP.get(x - p_sum);
            }

        return count;
    }
    public static void main(String[] args)
    {
        int arr1[] = { 2, 5, 6, 9 };
        int arr2[] = { 1, 3, 7, 11 };
        int arr3[] = { 1, 5, 6, 8 };
        int arr4[] = { 2, 3, 5, 10 };

        int n = arr1.length;
        int x = 32;
        System.out.println("Count = "
                           + getNumberOfQuadruples (arr1, arr2, arr3, arr4, n, x));
    }
}
Count = 3

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

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

О (н2ки дар "Н" шумораи унсурҳои массив аст. Мо мураккабии вақти полиномии N ^ 2-ро ба даст овардем, зеро ҳар дафъа танҳо аз элементҳои ду массив мегузаштем.

ҳамчунин нигаред
Унсури зуд-зуд дар як массив

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

О (н2ки дар "Н" шумораи унсурҳои массив аст. Азбаски миқдори элементҳои дар HashMap ҳифзшаванда унсурҳои ду массив мебошанд. Мо ба мураккабии фазои квадратӣ ноил мешавем.