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

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

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

Дана последовательность 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;
}

Новые блоги и статьи Все статьи Все блоги /
Создаем утилиты CLI с помощью Node.js run.dev 07.03.2025 Помню те времена, когда командная строка считалась уделом гиков и сисадминов. Они давно прошли. Но история повторяется и интерфейс командной строки (CLI) снова ягодка опять в средах разработки и стал. . .	Тестирование в JavaScript: как использовать Jest и Cypress run.dev 07.03.2025 Когда DOM-дерево рассыпается от одной неверной строчки кода, а асинхронные операции превращают отлаженный компонент в источник головной боли, тесты помогут спасти ситуацию. Два инструмента особенно. . .	Управление версиями Python с помощью pyenv py-thonny 07.03.2025 Знакома ли вам ситуация, когда вы начинаете новый проект, а он требует Python 3. 8, в то время как на вашей системе установлен Python 3. 10? Или когда вы пытаетесь запустить старый скрипт, а он выдаёт. . .	Обработка двоичных данных в Python py-thonny 07.03.2025 При работе с данными мы можем встретиться с двумя совершенно разными типами: текстовыми и двоичными. Хотя с текстом мы взаимодействуем постоянно, именно бинарные данные лежат в основе всех цифровых. . .	Сайт компании Red-Star-Soft переехал на новый хостинг! Etyuhibosecyu 06.03.2025 Как и советовал Rius, я покинул хостинг от "Ru-Center" и перенес сайт red-star-soft. com на хостинг с более позитивными отзывами (спойлер: найти его было далеко не просто) (чтобы прочитать текст,. . .
Альтернативная сериализация в Java: сравнение Kryo, Protobuf и Avro Jamaican 06.03.2025 Сериализация — один из краеугольных процессов в Java-разработке. Превращение объектов в поток байтов для хранения или передачи по сети с последующим восстановлением звучит просто, но реализация этого. . .	Битва Java-кешей: Сравниваем Ehcache, Caffeine и Hazelcast Jamaican 06.03.2025 Производительность — вечный Святой Грааль для Java-разработчиков. Мы оптимизируем алгоритмы, настраиваем JVM, распараллеливаем процессы, но неизменно приходим к одному и тому же средству ускорения —. . .	Параметры подтверждения сообщения Kafka Jamaican 06.03.2025 Среди распределённых систем и высоконагруженных приложений Apache Kafka занимает особое место. Эта платформа потоковой обработки данных давно стала стандартом де-факто для организаций, которым. . .	Оптимизация времени запуска Spring Boot Jamaican 06.03.2025 Вы когда-нибудь сидели, барабаня пальцами по столу, пока ваше Spring Boot приложение медленно поднимается? Этот момент, когда вы успеваете сходить за кофе, пообщаться с коллегами и вернуться, а. . .	Деплой Kubernetes в Java: масштабирование Spring Boot приложений Jamaican 06.03.2025 Когда ваше Spring Boot приложение внезапно получает всплеск трафика или требует плавного обновления без простоя — традиционные методы деплоя часто пасуют. Именно здесь на сцену выходит Kubernetes —. . .

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

@_Ivana 4820 / 2286 / 287 Регистрация: 01.03.2013 Сообщений: 5,970 Записей в блоге: 30
	19.10.2019, 01:29	41
	Сообщение от liv алгоритм такой: Организовываем два вложенных цикла по элементам массива. Складываем пары чисел и сравниваем с m. Если равно - выводим. Комментарий не для ТС: фиговый алгоритм. N^2. Надо N*log(N). 0

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

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

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

@_Ivana 4820 / 2286 / 287 Регистрация: 01.03.2013 Сообщений: 5,970 Записей в блоге: 30
	19.10.2019, 01:49	45
	Поэтому я и написал Сообщение от _Ivana Комментарий не для ТС: А для участника с репой под 2000 и полуторотысячной оценкой вполне подойдет 0

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

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

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