---

#include <iostream>
#include <vector>
using namespace std;

void program1() {
    int n;

    cout << "n = ";
    while (cin >> n && n <= 0)
        cout << "n>0" << endl << "n = ";
    cout<<endl;

    int matrix1[n][n], matrix2[n][n], result[n][n];

    cout<<"Matrix1:"<<endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
         matrix1[i][j]=rand()%20-10;
         cout << matrix1[i][j] << " ";
        }
        cout<<endl;
    }
    cout<<endl;

     cout<<"Matrix2:"<<endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
         matrix2[i][j]=rand()%20-10;
         cout << matrix2[i][j] << " ";
        }
        cout<<endl;
    }
    cout<<endl;

    //заполнение результ матрицы нулями
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            result[i][j] = 0;
    }

    //перемножение матриц
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++)
                result[i][j] += matrix1[i][k] * matrix2[k][j];
        }
    }

    cout << "Result:" << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            cout << result[i][j] << " ";
        cout << endl;
    }
}

//2/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

//функция для метода трапеций
double trapez(double (*func)(double), double a, double b, int n) {
    double h = (b - a) / n;
    double integral = 0.5 * (func(a) + func(b));

    for (int i = 1; i < n; ++i)
        integral += func(a + i * h);

    integral *= h;
    return integral;
}

//рекурсивно методом трапеций
double trapezRecursive(double (*func)(double), double a, double b, int n) {
    if (n == 1)
        return 0.5 * (func(a) + func(b)) * (b - a);
    else {
        double h = (b - a) / n;
        return trapezRecursive(func, a, b - h, n - 1) + 0.5 * (func(a + (n - 1) * h) + func(b)) * h;
    }
}

//функция для метода прямоугольников (левый)
double rectan(double (*func)(double), double a, double b, int n) {
    double h = (b - a) / n;
    double integral = 0;

    for (int i = 0; i < n; ++i)
        integral += func(a + i * h) * h;

    return integral;
}

//рекурсивно методом прямоугольников
double rectanRecursive(double (*func)(double), double a, double b, int n) {
    if (n == 1)
        return func(a) * (b - a);
    else {
        double h = (b - a) / n;
        return rectanRecursive(func, a, b - h, n - 1) + func(a + (n - 1) * h) * h;
    }
}

//пример функции для интегрирования
double myFunction(double x) {
    return x * x;
}

void program2() {
    double a = 0; //начало интервала
    double b = 1; //конец интервала
    int n; //количество делений
    cout << "n = ";
    while (cin >> n && n <= 0)
        cout << "n>0" << endl << "n = ";
    cout<<endl;

    cout << "Trapez (iter): " << trapez(myFunction, a, b, n) << endl;
    cout << "Trapez (rec): " << trapezRecursive(myFunction, a, b, n) << endl;
    cout << "Rectan (iter): " << rectan(myFunction, a, b, n) << endl;
    cout << "Rectan (rec): " << rectanRecursive(myFunction, a, b, n) << endl;
}

//3/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

void program3() { 
    int rows, cols;
    
    cout << "a = ";
    while (cin >> rows && rows <= 0)
        cout << "a>0" << endl << "a = ";
    cout << "b = ";
    while (cin >> cols && cols <= 0)
        cout << "b>0" << endl << "b = ";
    cout<< endl;

    cout << "Matrix1:" << endl;
    int matrix1[rows][cols];
    for (int i = 0; i < rows; i++){
        for(int j = 0; j < cols; j++){
         matrix1[i][j]=rand()%200-100;
         cout << matrix1[i][j] << " ";
        }
        cout<<endl;
    }
    cout << endl;

    int matrix2[rows][cols];

    //процесс копирования с использованием буферной переменной
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            //использую временную переменную для хранения значения
            int buffer = matrix1[i][j];
            matrix2[i][j] = buffer;
            cout << "Buffer[" << i << "][" << j << "]: " << buffer << "; ";
        }
        cout << endl;
    }
    cout << endl;

    cout << "Matrix2:" << endl;
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j)
            cout << matrix2[i][j] << " ";
        cout << endl;
    }
}

//4/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        //опорный элемент
        int pivot = arr[high];
        int i = (low - 1);

        for (int j = low; j < high; j++) {
            //если меньше или равен опорному
            if (arr[j] < pivot) {
                i++; //увеличиваем индекс меньшего элемента
                swap(arr[i], arr[j]); //меняем местами
            }
        }
        swap(arr[i + 1], arr[high]); //меняем местами опорный элемент
        int pi = i + 1; //индекс опорного элемента

        //рекурсивно сортируем элементы до и после разбиения
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

void program4() {
    int n;
    cout << "n = ";
    while (cin >> n && n <= 0)
        cout << "n>0" << endl << "n = ";
    cout<<endl;
    
    int arr[n];
    cout << "No sort: ";
    for (int i = 0; i < n; i++) {
        arr[i]=rand()%200-100;
        cout << arr[i] << " ";
    }
    cout << endl;

    quickSort(arr, 0, n - 1);

    cout << "Sort: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

//5/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

//печать числа в двоичном виде
void printBinary(int num) {
    int totalBits = sizeof(int) * 8; // адаптация под длину типа
    for (int i = totalBits - 1; i >= 0; i--) {
        cout << ((num >> i) & 1);
        if (i % 8 == 0) //для читаемости
            cout << " ";
    }
}

//получение i-го бита числа сдвигом
bool getBit(int num, int i) {
    int totalBits = sizeof(int) * 8;
    //инверсия старшего бита 
    if (i == totalBits - 1)
        return !((num >> i) & 1);
    return (num >> i) & 1;
}

//поразрядная сортировка
//отрицательные в двоичном инвертируются по всем битам, кроме младшего, при
//этом старший инвертирован в getBit, так что большее по модулю отрицательное
//при последней проверке (старшего бита) становится меньшим в сортировке
void radixSort(vector<int>& arr) {
    int numBits = sizeof(int) * 8;

    for (int i = 0; i < numBits; i++) {
        vector<int> zeros;
        vector<int> ones;

        for (int num : arr) {
            if (getBit(num, i))
                ones.push_back(num);
            else 
                zeros.push_back(num);
        }

        
        arr.clear();
        arr.insert(arr.end(), zeros.begin(), zeros.end());
        arr.insert(arr.end(), ones.begin(), ones.end());
    }
}

void program5() {
    int n;
    cout << "n = ";
    while (cin >> n && n <= 0) 
        cout << "n > 0" << endl << "n = ";

    vector<int> arr;
    for (int i = 0; i < n; i++)
        arr.push_back(rand() % 200 - 100);
    
    cout << endl << "1. Generated:" << endl;
    for (int num : arr) 
        cout << num << " ";
    cout << endl << endl;

    cout << "2. DEC -> BIN:" << endl;
    for (int num : arr) {
        cout << num << " -> ";
        printBinary(num);
        cout << endl;
    }
    cout << endl;

    radixSort(arr);

    cout << "3. Sorted binary:" << endl;
    for (int num : arr) {
        printBinary(num);
        cout << endl;
    }
    cout << endl;

    cout << "4. Sorted decimal:" << endl;
    for (int num : arr)
        cout << num << " ";
        
    cout << endl;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

int main() {
    int choice;
    while (true) {
        cout << endl << "Menu:" << endl;
        cout << "1: Matrix1 * Matrix2" << endl;
        cout << "2: Integral" << endl;
        cout << "3: Buffer" << endl;
        cout << "4: Quick Sort" << endl;
        cout << "5: Bin" << endl;
        cout << "0: Quit" << endl;
        cout << "Enter number (0-5): ";
        cin >> choice;
        cout << endl;

        if (choice == 0)
            break;  // выход из цикла

        switch (choice) {
            case 1: program1(); break;
            case 2: program2(); break;
            case 3: program3(); break;
            case 4: program4(); break;
            case 5: program5(); break;
            default: cout << "Incorrect input" << endl;
        }
    }
    return 0;
}