Указать пары таких элементов последовательности, что их сумма равна m

@Translater757 · Регистрация: 18.10.2019

Студворк — интернет-сервис помощи студентам

Дана последовательность N целых чисел и целое число m.
Указать пары чисел этой последовательности таких, что их
сумма равна m. Провести тестирование программы
при пользовательском вводе элементов массива и при генерации
элементов массива из диапазона [0; k], где k – номер студента
в списке группы. k=17

@_Ivana · 19.10.2019, 01:29

Сообщение от liv

алгоритм такой:
Организовываем два вложенных цикла по элементам массива. Складываем пары чисел и сравниваем с m. Если равно - выводим.

Комментарий не для ТС: фиговый алгоритм. N^2. Надо N*log(N).

@liv · 19.10.2019, 01:33

_Ivana, разве N^2? Так было бы, если бы было каждый с каждым.

@_Ivana · 19.10.2019, 01:43

А сколько по-вашему?

Добавлено через 7 минут
ЗЫ N*(N-1)/2 = N^2 в смысле О большого. и если будет эта задача на сайте олимпиадных задач, то там обязательно будут тесты, которые этот алгоритм не пройдет.
Как сделать за N*log(N) и пройти тесты: сортируем массив за N*log(N). Потом внешний цикл по элементам массива, а второй элемент ищем бинарным поиском - ибо если сумма уже больше чем надо, то нет смысла проверять бОльшие элементы, и наоборот. Итого второе N*log(N), итого 2*N*log(N) = N*log(N). Тесты пройдены, профит!

@liv · 19.10.2019, 01:46

_Ivana, ну прямо задачка для новичка...

Никто не ставил задачу решить олимпиадную задачу...
Тут как бы хоть что-нибудь понять...

@_Ivana · 19.10.2019, 01:49

Поэтому я и написал

Сообщение от _Ivana

Комментарий не для ТС:

А для участника с репой под 2000 и полуторотысячной оценкой вполне подойдет

@liv · 19.10.2019, 01:55

_Ivana, ладушки, с комментарием, разумеется, согласен.

@Translater757 · 19.10.2019, 15:25 **[ТС]**

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include "stdafx.h"
#include <time.h>
#include<stdlib.h>
#include<locale.h>
#include <iostream>
using namespace std;
 
int main()
{
    setlocale(LC_ALL, "RUS");
    const int size = 5 ;
    int size, M, i,j, array[size], Summ;
 
    cout << "Введите число M: ";
    cin >> M;
 
    srand(time(NULL));
    for (i = 0; i < size; i++)
        array[i] = rand() % 18;
 
    int* array = new int[size];
 
    cout << "Введите элементы для массива: " << endl;
 
    for (int i = 0; i < size; i++)
        cin >> array[i];
 
    for (int i = 0; i < size; i++)
        cout << array[i] << " ";
 
    cout << endl;
    cout << "M = " << M;
    cout << endl;
 
    int count = 0; // на случай если ни одна пара не совпадёт вывести сообщение об этом
 
    for (int i = 0; i < size - 1; i++)
    {
        for (int j = i + 1; j < size; j++)
        {
            // ищем пару которая даёт M && исключаем совпадение элемента самим с собой
            if (array[i] + array[j] == M && i != j)
            {
                cout << "Пара " << array[i] << " " << array[j] << " из массива = M";
                cout << endl;
                count++;
            }
        }
    }
 
    if (count == 0)
    {
        cout << "Нет ни одной подходящей пары.";
    }
 
    delete[]array;
 
    return 0;
}

Хочу сделать , чтобы числа автоматически выставлялись. Что-то не получается.

@liv · 20.10.2019, 12:21

Translater757, показывай, как делал...
Ты ж сам начал с этого... Посмотри ещё раз тобою же приведенный код

@lemegeton · 20.10.2019, 13:32

Можно не проходить по элементам, чьи значения больше целевого числа.
Перед вторым for можно поставить "if (array[i] > M) continue;".

C++
1
if (array[i] + array[j] == M && i != j)

Лишнее сравнение i!=j. Они никогда не будут равны.

Сообщение от Translater757

Хочу сделать , чтобы числа автоматически выставлялись. Что-то не получается.

Непонятно, что это означает.

В целом, можно сделать проще. Если сразу отсортировать массив чисел, можно пройтись по той его части, которая меньше половины целевого значения и для каждого числа i искать число M-i. Если есть -- пара.

Немного сложный код, O(N*log(N)):

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <random>
#include <string>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <iterator>
#include <vector>
 
template<typename T>
std::ostream &operator<<(std::ostream &out, const std::pair<T, T> &v) {
    return out << "{" << v.first << "; " << v.second << "}";
}
 
template<typename T>
std::ostream &operator<<(std::ostream &out, const std::vector<T> &v) {
    for (auto i = v.begin(); i != v.end(); ++i) {
        out << *i << " ";
    }
    return out;
}
 
template<typename FIter, typename T>
std::vector<std::pair<T, T>> findPairs(FIter begin, FIter end, const T &target) {
    auto last = std::upper_bound(begin, end, target / 2);
    auto greater = std::upper_bound(begin, end, target);
    std::vector<std::pair<T, T>> result;
    for (auto i = begin; i != greater; ++i) {
        int additional = target - *i;
        auto j = std::lower_bound(i + 1, greater, additional);
        for (; j != greater && *j == additional; ++j) {
            result.push_back(std::pair<T, T>(*i, *j));
        }
    }
    return result;
}
 
auto randomNumber = [](int low, int high) {
    auto generator = [distribution = std::uniform_int_distribution<int>(low, high), engine = std::mt19937{ std::random_device{}() }]() mutable {
        return distribution(engine);
    };
    return generator;
};
 
int main() {
    const int size = 10;
    std::vector<int> numbers(size);
 
    std::generate(numbers.begin(), numbers.end(), randomNumber(0, 18));
    std::cout << numbers << std::endl;
 
    std::sort(numbers.begin(), numbers.end());
    std::cout << numbers << std::endl;
 
    const int target = 20;
 
    std::vector<std::pair<int, int>> result = findPairs(numbers.begin(), numbers.end(), target);
 
    if (result.empty()) {
        std::cout << "No pairs found to form " << target << "." << std::endl;
    } else {
        std::cout << result << std::endl;
    }
    return 0;
}

Добавлено через 9 минут
C комментариями:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <random>
#include <string>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <iterator>
#include <vector>
 
// чтобы можно было просто выводить std::pair в std::cout
template<typename T>
std::ostream &operator<<(std::ostream &out, const std::pair<T, T> &v) {
    return out << "{" << v.first << "; " << v.second << "}";
}
 
// чтобы можно было просто выводить вектор в std::cout
template<typename T>
std::ostream &operator<<(std::ostream &out, const std::vector<T> &v) {
    for (auto i = v.begin(); i != v.end(); ++i) {
        out << *i << " ";
    }
    return out;
}
 
template<typename FIter, typename T>
std::vector<std::pair<T, T>> findPairs(FIter begin, FIter end, const T &target) {
    // место первого элемента в массиве, которое больше половины целевого значения
    // дальше этого места искать первый элемент пары бессмысленно
    auto last = std::upper_bound(begin, end, target / 2);
    // поиск первого элемента, большего, чем целевое значение
    // дальше этого места искать второй элемент пары бессмысленно
    auto greater = std::upper_bound(begin, end, target);
    std::vector<std::pair<T, T>> result; // сюда будет сохраняться результат
    // идем по всем значениям до половины целевого значения
    for (auto i = begin; i != greater; ++i) {
        // для каждого числа *i...
        // находим то число, которое в сумме составит целевое
        int additional = target - *i; 
        auto j = std::lower_bound(i + 1, greater, additional); //находим его позицию в массиве
        // пока оно есть
        for (; j != greater && *j == additional; ++j) { 
            // добавляем в результат
            result.push_back(std::pair<T, T>(*i, *j));
        }
    }
    return result;
}
 
// это я так случайные числа генерирую
auto randomNumber = [](int low, int high) {
    auto generator = [distribution = std::uniform_int_distribution<int>(low, high), engine = std::mt19937{ std::random_device{}() }]() mutable {
        return distribution(engine);
    };
    return generator;
};
 
int main() {
    // количество чисел
    const int size = 1000;
    std::vector<int> numbers(size);
 
    // это я так случайные числа генерирую
    std::generate(numbers.begin(), numbers.end(), randomNumber(0, 18));
    std::cout << numbers << std::endl;
 
    // сортируем значения
    std::sort(numbers.begin(), numbers.end());
    std::cout << numbers << std::endl;
 
    // целевое значение
    const int target = 20;
 
    // ищем пары, дающие в сумме целевое значение
    std::vector<std::pair<int, int>> result = findPairs(numbers.begin(), numbers.end(), target);
 
    if (result.empty()) {
        std::cout << "No pairs found to form " << target << "." << std::endl;
    } else {
        std::cout << result << std::endl;
    }
    return 0;
}

@D_i_n_e_r_0 · 08.10.2022, 15:37

сможете прислать готовую прогу?

@lemegeton · 08.10.2022, 16:57

Да легко. Держи. С комментариями:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <random>
#include <string>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <iterator>
#include <vector>
 
// чтобы можно было просто выводить std::pair в std::cout
template<typename T>
std::ostream &operator<<(std::ostream &out, const std::pair<T, T> &v) {
    return out << "{" << v.first << "; " << v.second << "}";
}
 
// чтобы можно было просто выводить вектор в std::cout
template<typename T>
std::ostream &operator<<(std::ostream &out, const std::vector<T> &v) {
    for (auto i = v.begin(); i != v.end(); ++i) {
        out << *i << " ";
    }
    return out;
}
 
template<typename FIter, typename T>
std::vector<std::pair<T, T>> findPairs(FIter begin, FIter end, const T &target) {
    // место первого элемента в массиве, которое больше половины целевого значения
    // дальше этого места искать первый элемент пары бессмысленно
    auto last = std::upper_bound(begin, end, target / 2);
    // поиск первого элемента, большего, чем целевое значение
    // дальше этого места искать второй элемент пары бессмысленно
    auto greater = std::upper_bound(begin, end, target);
    std::vector<std::pair<T, T>> result; // сюда будет сохраняться результат
    // идем по всем значениям до половины целевого значения
    for (auto i = begin; i != greater; ++i) {
        // для каждого числа *i...
        // находим то число, которое в сумме составит целевое
        int additional = target - *i; 
        auto j = std::lower_bound(i + 1, greater, additional); //находим его позицию в массиве
        // пока оно есть
        for (; j != greater && *j == additional; ++j) { 
            // добавляем в результат
            result.push_back(std::pair<T, T>(*i, *j));
        }
    }
    return result;
}
 
// это я так случайные числа генерирую
auto randomNumber = [](int low, int high) {
    auto generator = [distribution = std::uniform_int_distribution<int>(low, high), engine = std::mt19937{ std::random_device{}() }]() mutable {
        return distribution(engine);
    };
    return generator;
};
 
int main() {
    // количество чисел
    const int size = 1000;
    std::vector<int> numbers(size);
 
    // это я так случайные числа генерирую
    std::generate(numbers.begin(), numbers.end(), randomNumber(0, 18));
    std::cout << numbers << std::endl;
 
    // сортируем значения
    std::sort(numbers.begin(), numbers.end());
    std::cout << numbers << std::endl;
 
    // целевое значение
    const int target = 20;
 
    // ищем пары, дающие в сумме целевое значение
    std::vector<std::pair<int, int>> result = findPairs(numbers.begin(), numbers.end(), target);
 
    if (result.empty()) {
        std::cout << "No pairs found to form " << target << "." << std::endl;
    } else {
        std::cout << result << std::endl;
    }
    return 0;
}

Новые блоги и статьи Все статьи Все блоги /
Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .	Вывод данных в справочнике через динамический список Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .	Функция заполнения текстового поля в реквизите формы документа Maks 01.04.2026 Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .	К слову об оптимизации kumehtar 01.04.2026 Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .
Идея фильтра интернета (сервер = слой+фильтр). Hrethgir 31.03.2026 Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .	Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем	10 пpимет, которые всегда сбываются Maks 31.03.2026 1. Чтобы, наконец, пришла маршрутка, надо закурить. Если сигарета последняя, маршрутка придет еще до второй затяжки даже вопреки расписанию. 2. Нaдоели зима и снег? Не надо переезжать. Достаточно. . .	Перемещение выделенных строк ТЧ из одного документа в другой Maks 31.03.2026 Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .

@Translater757 0 / 0 / 0 Регистрация: 18.10.2019 Сообщений: 51

	Указать пары таких элементов последовательности, что их сумма равна m 18.10.2019, 15:07. Показов 3709. Ответов 50 Метки нет (Все метки) Дана последовательность N целых чисел и целое число m. Указать пары чисел этой последовательности таких, что их сумма равна m. Провести тестирование программы при пользовательском вводе элементов массива и при генерации элементов массива из диапазона [0; k], где k – номер студента в списке группы. k=17 0

@liv 5120 / 4574 / 855 Регистрация: 07.10.2015 Сообщений: 9,462
	19.10.2019, 01:33
	_Ivana, разве N^2? Так было бы, если бы было каждый с каждым. 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	19.10.2019, 01:43
	А сколько по-вашему? Добавлено через 7 минут ЗЫ N(N-1)/2 = N^2 в смысле О большого. и если будет эта задача на сайте олимпиадных задач, то там обязательно будут тесты, которые этот алгоритм не пройдет. Как сделать за Nlog(N) и пройти тесты: сортируем массив за Nlog(N). Потом внешний цикл по элементам массива, а второй элемент ищем бинарным поиском - ибо если сумма уже больше чем надо, то нет смысла проверять бОльшие элементы, и наоборот. Итого второе Nlog(N), итого 2Nlog(N) = N*log(N). Тесты пройдены, профит! 0

@liv 5120 / 4574 / 855 Регистрация: 07.10.2015 Сообщений: 9,462
	19.10.2019, 01:46
	_Ivana, ну прямо задачка для новичка... Никто не ставил задачу решить олимпиадную задачу... Тут как бы хоть что-нибудь понять... 0

@liv 5120 / 4574 / 855 Регистрация: 07.10.2015 Сообщений: 9,462
	19.10.2019, 01:55
	_Ivana, ладушки, с комментарием, разумеется, согласен. 0

@liv 5120 / 4574 / 855 Регистрация: 07.10.2015 Сообщений: 9,462
	20.10.2019, 12:21
	Translater757, показывай, как делал... Ты ж сам начал с этого... Посмотри ещё раз тобою же приведенный код 0

@D_i_n_e_r_0 0 / 0 / 0 Регистрация: 08.10.2022 Сообщений: 1
	08.10.2022, 15:37
	сможете прислать готовую прогу? 0