Алгоритм поиска 3 чисел сумма которых будет ровна 2021 на С++

Question

Вопрос заключается в создании алгоритма который найдет 3 числа, сумма которых будет 2021. Входные данные - есть рандомный ряд только положительных чисел (количество чисел в ряду тоже рандомное); все числа в ряду меньше чем 2021. Самый простой алгоритмм О(n^3). Можно без кода, просто описать. Буду очень благодарен!

Answer 1

Самый простой, как и просили:
Если можно использовать одно и тоже число. Т.е. arr[0]+arr[0]+arr[0] == 2021:

for(int i=0; i<arr_size; ++i)
    for(int j=0; j<arr_size; ++j)
        for(int k=0; k<arr_size; ++k)
            if(arr[i]+arr[j]+arr[k] == 2021)
                cout << arr[i] << ' ' << arr[j] << ' ' << arr[k] << '\n';

Если нельзя

for(int i=0; i<arr_size; ++i)
    for(int j=0; j<arr_size; ++j)
        for(int k=0; k<arr_size; ++k)
            if(i!=j && i!=k && j!=k && arr[i]+arr[j]+arr[k] == 2021)
                cout << arr[i] << ' ' << arr[j] << ' ' << arr[k] << '\n';

Ввод массива можно сделать так, например:

std::vector<int> vec{std::istream_iterator<int>(std::cin), std::istream_iterator<int>()};

Однако стоит учитывать, что для того, чтобы завершить ввод нужно нажать Ctrl+Z, а после Enter.

Answer 2

Через итераторы, можно использовать для суммы более 3 чисел:

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

int main() {
    std::set<int> s = {2019, 1, 2018, 2, 43, 32, 38, 63, 31, 97, 70, 3, 19, 18, 20, 29, 23};
    int check_sum = 2021;

    for(int a : s) {
        std::cout << a << " ";
    }
    std::cout << std::endl;

    int N = 3;
    std::vector<std::set<int>::iterator> it;
    for(int i = 0; i < N; ++i) {
        it.push_back(s.begin());
    }

    for (auto itit = it.begin(); itit != it.end();) {
        for ( ; *itit != s.end(); ++(*itit)) {
            int sum = 0;
            for(auto itits = it.begin(); itits != it.end(); ++itits) {
                sum += **itits;
            }
            if (sum == check_sum) {
                // print sum
                auto itits = it.begin();
                std::cout << sum << " = " << **itits;
                ++itits;
                for(; itits != it.end(); ++itits) {
                    std::cout << " + " << **itits;
                }
                std::cout << std::endl;
            } 
        }

        for(;itit != it.end(); ++itit) {
            if (*itit == s.end()) {;
                *itit = s.begin();
            }else {
                ++(*itit);
                if(*itit != s.end()) {
                    itit = it.begin();
                }
                break;
            }
        }
    }


}

Вывод:

1 2 3 18 19 20 23 29 31 32 38 43 63 70 97 2018 2019 
2021 = 2019 + 1 + 1
2021 = 2018 + 2 + 1
2021 = 2 + 2018 + 1
2021 = 1 + 2019 + 1
2021 = 2018 + 1 + 2
2021 = 1 + 2018 + 2
2021 = 2 + 1 + 2018
2021 = 1 + 2 + 2018
2021 = 1 + 1 + 2019

БЛОГ НА HUSL

Алгоритм поиска 3 чисел сумма которых будет ровна 2021 на С++

Ответы (2 шт):