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


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Accolite Amazon Фараж
тартиботи ҳарбӣ Хашм Ҷустуҷӯ

Мо додаем асал ададҳо ва адади додашуда бо номи 'сум'. Дар баёни масъала хоҳиш карда мешавад, ки сегонае пайдо карда шавад, ки ба рақами додашудаи "сум" илова карда шавад.

мисол

Қайд:

arr [] = {3,5,7,5,6,1}

сум = 16

Натиҷа:

(3, 7, 6), (5, 5, 6)

Шарҳ:

Сегонае, ки ба маблағи додашуда баробар аст.

Қайд:

arr [] = {3,4,1,5,4}

сум = 20

Натиҷа:

Ҳеч сегоникҳое нестанд, ки бо рақами додашуда сохта шаванд

Алгоритм

  1. Массиви додашударо ҷобаҷо кунед.
  2. Тағирёбандаи логикии isFound -ро ба false таъин кунед.
  3. Дар ҳоле ки i = 0 ба i
    1. J = i + 1, k = n-1 -ро таъин кунед.
    2. Дар ҳоле ки j <k
      1. Санҷед, ки оё се элемент дар якҷоягӣ ба маблағи додашуда ҳамроҳ мешаванд.
        1. Агар рост бошад, пас ҳар се рақамро чоп кунед ва isFound to true -ро таъин кунед.
      2. Дигарро санҷед, агар маблағи се унсур аз сум зиёдтар бошад.
        1. Агар рост бошад, пас арзиши k-ро ба 1 кам кунед.
      3. Санҷед, ки оё маблағи се унсур (унсурҳои массиви ҷорӣ) камтар аз сум аст.
        1. Агар рост бошад, пас арзиши j-ро 1 зиёд кунед.
  4. Санҷед, ки isFound дурӯғ боқӣ мондааст, ба хулосае омад, ки сегонаҳо ба вуҷуд омада наметавонанд.

Шарҳ

Мо мешавем нависед массив аввал барои он ки арзишҳо бо тартиби зиёд мешаванд, зеро мо истифода бурдани а ҷустуҷӯи бинарӣ наздик шавед, каме. Мо мехоҳем эълон кунем Тағирёбандаи мантиқӣ ва арзиши онро бардурӯғ дар аввал гузоштед, мо пас аз пайдо кардани сегона онро навсозӣ мекунем. Ин бояд боварӣ ҳосил кард, ки агар мо ягон сегонаеро пайдо накунем, ки унсурҳояшон ба адади додашуда ҷамъ шаванд, арзиши isFound ҳамон тавре боқӣ мемонад, ки мо танҳо ҳангоми пайдо кардани сегона онро ҳақиқӣ мекунем, бо ҳамин , мо метавонем ба хулоса оем, ки ягон сегона ёфт нашуд.

Пас аз ҷобаҷогузории массив, аз ҳалқаи лона сар карда, мо массивро то дарозии n-1 тай хоҳем кард. Муқаррар кардани яке аз қиматҳои тағирёбанда ҳамчун i + 1, арзиши дигар ба n-1. Дар ҳалқаи дарунӣ, мо тамоми арзишҳои массивро тай намуда, санҷем, ки шумораи додаи 'сум' ба суммаи се унсури массиви ҷорӣ (arr [i] + arr [j] + arr [k ]) баробар аст ё не. Агар шарт иҷро шавад, мо ҳама қиматҳои ҷории массивро чоп мекунем ва арзиши isFound-ро ба true муқаррар мекунем, ки ин набояд арзиши бардурӯғро баргардонем.

Агар ҷамъи се қимати ҷории массив ба адади додашуда баробар набошад, мо месанҷем, ки агар ҷамъи се унсури ҷорӣ аз ҳосили додашуда камтар бошад, агар аз ҳосили он камтар бошад, мо арзиши онро зиёд хоҳем кард аз j маънои нишоннамои чапи моро дорад, ки аз чап нишон медиҳад гузариш зиёд аст ва агар ин шарт низ қонеъ набошад, мо тафтиш хоҳем кард, ки оё маблағ аз сум зиёдтар аст, агар рост бошад, пас арзиши k-ро коҳиш медиҳем.

То он даме ки ҳамаи арзишҳои массив убур мешаванд, идома хоҳад ёфт. Ва мо арзиши isFound-ро бармегардонем, ки он метавонад ба сурати ҳақиқӣ баргардонида шавад, агар ягон сегона пайдо кунем ва дурӯғе, агар надидем.

татбиќи

Барномаи C ++ барои ҳама сегонаҳои сегона, ки арзиши додашударо ҷамъбаст мекунанд

#include<iostream>
#include<algorithm>

using namespace std;

int getTripletOfSum(int arr[], int n, int sum)
{
    int i, j, k;
    bool isFound=false;
    sort(arr, arr + n);
    for(i = 0; i < n - 2; i++)
    {
        j = i + 1;
        k = n - 1;

        while(j < k)
        {
            if(arr[i] + arr[j] + arr[k] == sum)
            {
                cout<<"["<<arr[i]<<" "<<arr[j]<<" "<<arr[k]<<"]"<<endl;
                j++;
                k--;
                isFound=true;
            }
            else if(arr[i] + arr[j] + arr[k] > sum)
                k--;
            else
                j++;
        }
    }
    return isFound;
}
int main()
{
    int nums[] = {3,5,7,5,6,1};
    int n = sizeof(nums) / sizeof(nums[0]);
    int sum = 16;
    if(!getTripletOfSum(nums, n, sum))
        cout << "There are no triplets that can be formed with the given number";

    return 0;
}
[3 6 7]
[5 5 6]

Барномаи Java барои ҳама сегоникҳои беназире, ки арзиши додашударо ҷамъбаст мекунанд

import java.util.Arrays;

public class TripletsWithSum
{
    public static boolean getTripletOfSum(int arr[], int sum)
    {
        Arrays.sort(arr);

        boolean isFound=false;

        for (int i = 0; i < arr.length - 2; i++)
        {
            int j = i + 1;
            int k = arr.length - 1;
            while (j < k)
            {
                if (arr[i] + arr[j] + arr[k] == sum)
                {
                    System.out.println("["+arr[i] + " " + arr[j] +" " +arr[k]+"]");
                    j++;
                    k--;
                    isFound=true;
                }
                else if (arr[i] + arr[j] + arr[k] < sum)
                    j++;

                else
                    k--;
            }
        }
        return isFound;
    }
    public static void main(String[] args)
    {
        int arr[] = {3,5,7,5,6,1};
        int sum = 16;
        if (!getTripletOfSum(arr, sum))
        {
            System.out.println("There are no triplets that can be formed with the given number");
        }
    }
}
[3 6 7]
[5 5 6]

Таҳлили мураккабӣ барои ҳама сегоникҳои беназире, ки арзиши додашударо ҷамъбаст мекунанд

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

О (н2ки дар "Н" шумораи унсурҳои массив аст.

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

Эй (н) ки дар "Н" шумораи унсурҳои массив аст.