lab01/task2_summ_of_two.cpp - master - Konst_And/Labs_cpp

lab01/task2_summ_of_two.cpp
149 строк6 KB
And Konst
move files
05 мар 2026, 14:57
05 мар 2026, 14:57dc5b7a2
#include <iostream>
#include <chrono>
#include <random>

void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}

// Задание 2: сумма двух

bool two_sum_neup(int* arr, int size, int targ) { // алгоритм для неупорядоченного массива
    for (int i = 0; i < size; ++i) {
        for (int j = i + 1; j < size; ++j) {
            if (arr[i] + arr[j] == targ)
                return true;
        }
    }
    return false;
}

bool two_sum_upor(int* arr, int size, int targ) { // алгоритм для упорядоченного массива
    int left = 0, right = size - 1;
    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == targ)
            return true;
        if (sum < targ)
            ++left;
        else
            --right;
    }
    return false;
}

void task2() {
    std::cout << "\nЗадание 2: сумма двух\n";
    std::default_random_engine rng(2002);
    std::uniform_int_distribution<int> dist(0, 1000000);
    std::uniform_int_distribution<int> too_big(2000000, 3000000);  // заведомо большие суммы
    
    const int iter_neup = 20;    // число итераций для полного перебора
    const int iter_upor = 50000;   // число итераций для двух указателей

    std::cout << "N\t\tПол пер ср\tПол пер худ\tДва ук ср\tДва ук худ\n";

    for (int N = 100; N <= 100000; N *= 2) {
        int* arr_unsort = new int[N];
        for (int i = 0; i < N; ++i)
            arr_unsort[i] = dist(rng);
        
        int* arr_sort = new int[N];
        for (int i = 0; i < N; ++i)
            arr_sort[i] = i * 2;
        
        // худший случай: такой суммы нет
        int targ_worst = -1;
        
        // полный перебор - наихудший
        auto begin = std::chrono::steady_clock::now();
        int notopt = 0;  // чтобы компилятор не оптимизировал
        for (int iter = 0; iter < iter_neup; ++iter) {
            notopt += two_sum_neup(arr_unsort, N, targ_worst);
        }
        auto end = std::chrono::steady_clock::now();
        auto neup_worst_total = std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count();
        double neup_worst = static_cast<double>(neup_worst_total) / iter_neup;
        
        // два указателя - наихудший
        begin = std::chrono::steady_clock::now();
        notopt = 0;
        for (int iter = 0; iter < iter_upor; ++iter) {
            notopt += two_sum_upor(arr_sort, N, targ_worst);
        }
        end = std::chrono::steady_clock::now();
        auto upor_worst_total = std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count();
        double upor_worst = static_cast<double>(upor_worst_total) / iter_upor;
        
        // средний случай
        
        // Полный перебор - средний
        begin = std::chrono::steady_clock::now();
        notopt = 0;
        for (int iter = 0; iter < iter_neup; ++iter) {
            int targ_avg;
            if (iter % 2 == 0) {
                // Существующая сумма
                int i = rng() % N;
                int j;
                do {
                    j = rng() % N;
                } while (j == i);
                targ_avg = arr_unsort[i] + arr_unsort[j];
            } else {
                // Несуществующая сумма - заведомо большое число
                targ_avg = too_big(rng);
            }
            notopt += two_sum_neup(arr_unsort, N, targ_avg);
        }
        end = std::chrono::steady_clock::now();
        auto neup_avg_total = std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count();
        double neup_avg = static_cast<double>(neup_avg_total) / iter_neup;
        
        // Два указателя - средний
        begin = std::chrono::steady_clock::now();
        notopt = 0;
        for (int iter = 0; iter < iter_upor; ++iter) {
            int targ_avg;
            if (iter % 2 == 0) {
                // Существующая сумма для отсортированного массива из четных чисел
                int i = rng() % N;
                int j;
                do {
                    j = rng() % N;
                } while (j == i);
                targ_avg = arr_sort[i] + arr_sort[j];
            } else {
                // Несуществующая сумма
                targ_avg = too_big(rng);
            }
            notopt += two_sum_upor(arr_sort, N, targ_avg);
        }
        end = std::chrono::steady_clock::now();
        auto upor_avg_total = std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count();
        double upor_avg = static_cast<double>(upor_avg_total) / iter_upor;
        
        // чтобы не оптимизировал
        if (notopt == 123456789) {
            std::cout << "Это никогда не выполнится\n";
        }
        
        std::cout << N << "\t\t"
                  << neup_avg << "\t\t\t"
                  << neup_worst << "\t\t\t"
                  << upor_avg << "\t\t\t"
                  << upor_worst << "\n";

        delete[] arr_unsort;
        delete[] arr_sort;
    }
}

// main

int main() {
    task2();
    return 0;
}