Лаба 4 ЯМП

/*
* Задача 17.
Даны целые M и N и вектор действительных чисел X[1..N].
Найти целое число i (1<=i<=N-M), для которого сумма x[i]+...+x[i+M] ближе всего к нулю.
*/

#include <iostream>
#include <vector>
#include <fstream>
#include <Windows.h>
#include <ctime>

using namespace std;

void MergeSort(vector<double>&, int, int);
void Merge(vector<double>&, int, int);

int main()
{
    int exit;

    do
    {
        SetConsoleOutputCP(1251);
        SetConsoleCP(1251);

        srand(static_cast<unsigned int>(time(0)));

        vector<double> X, S;

        int M, N, i = -1;
        cout << "Введите M:" << endl;
        cin >> M;
        cout << "Введите N:" << endl;
        cin >> N;

        cout << "Вектор X:" << endl;
        for (int j = 0; j < N; j++)
        {
            X.push_back((rand() % 100 + (rand() % 100)/100.0));
            cout << X[j] << '\t';
            if (!((j + 1) % 20))
                cout << endl;
        }
        cout << endl;

        double S1;

        cout << "Вектор сумм:" << endl;
        for (int j = 0; j < N - M; j++)
        {
            S1 = 0;
            for (int k = j; k <= j + M; k++)
            {
                S1 += X[k];
            }
            S.push_back(S1);
            cout << S[j] << '\t';
            if (!((j + 1) % 20))
                cout << endl;
        }
        cout << endl;

        double min = S[0];

        for (int j = 1; j < N - M; j++)
        {
            if (min > S[j])
            {
                min = S[j];
                i = j;
            }
        }

        cout << endl << "i = " << i << endl;

        cout << endl << endl << endl << "////////////Второй способ решения////////////" << endl << endl << endl << endl;


        MergeSort(X, 0, N-1);

        for (int j = 0; j < N; j++)
        {
            cout << X[j] << '\t';
            if (!((j + 1) % 20))
                cout << endl;
        }
        cout << endl;

        cout << "Следовательно i = 0" << endl;

        cout << "0. Выход" << endl;
        cin >> exit;
    } while (exit != 0);
}

void MergeSort(vector<double>& array, int left, int right)
{
    if (left < right)
        if (right - left == 1)
        {
            if (array[left] > array[right])
                swap(array[left], array[right]);
        }
        else
        {
            MergeSort(array, left, left + (right - left) / 2);
            MergeSort(array, left + (right - left) / 2 + 1, right);
            Merge(array, left, right);
        }
}

void Merge(vector<double>& array, int begin, int end)
{
    int i = begin,
        mid = begin + (end - begin) / 2,
        j = mid + 1,
        k = 0;
    double d[1000];

    while (i <= mid && j <= end)
    {
        if (array[i] <= array[j])
        {
            d[k] = array[i];
            i++;
        }
        else
        {
            d[k] = array[j];
            j++;
        }
        k++;
    }

    while (i <= mid)
    {
        d[k] = array[i];
        i++;
        k++;
    }

    while (j <= end)
    {
        d[k] = array[j];
        j++;
        k++;
    }

    for (i = 0; i < k; i++)
        array[begin + i] = d[i];
}