salibek_lab5

#include <iostream>
#include <functional>
#include <string>
#include <vector>
#include <map>
#include <locale>

const int start = 4, end = 27;
const std::vector<int> restrictions = { 7, 17 };

template<typename T>
std::string vector_to_string(const std::vector<T>& vec)
{
    std::string res;
    bool first = true;
    for (auto& el : vec)
    {
        if (!first)
            res += ", ";
        res += std::to_string(el);
        first = false;
    }
    return res;
}

int main()
{
    setlocale(LC_ALL, "rus");

    // Прямой ход
    std::cout << "===Прямой ход===" << std::endl;
    std::cout << "Начало: " << start << ", конец: " << end << ". Операции: +1, *2-1" << std::endl << std::endl;

    int branchCount = 0;

    std::function<void (int, int, std::string)> calc = [&calc, &branchCount](int x, int fin, std::string way)
    {
        branchCount++;
        if (x < fin)
        {
            calc(x + 1, fin, way + "+1");
            if (x != 0)
                calc(x * 2-1, fin, way + "*2-1");
        }
        else if (x == fin)
            std::cout << way << std::endl;
    };

    calc(start, end, "");
    std::cout << "Количество ветвлений:" << branchCount << std::endl;



    // Прямой ход с контрольными точками. Траектория должна проходить через хотя бы одно из чисел-ограничителей
    std::cout << std::endl << "===Прямой ход с контрольными точками===" << std::endl;
    std::cout << "Начало: " << start << ", конец: " << end << ". Контрольные точки = " << vector_to_string(restrictions) <<
        ". Операции: +1, *2-1" << std::endl << std::endl;

    branchCount = 0;

    std::function<void (int, int, std::string, const std::vector<int>&, bool, std::vector<int>)> calc_restricted =
        [&calc_restricted, &branchCount]
        (int x, int fin, std::string way, const std::vector<int>& restrictions, bool okToPrint, std::vector<int> metConditions)
    {
        branchCount++;

        for (auto& el : restrictions)
            if (x == el) // Если путь проходит через одно из значений - ограничений
            {
                okToPrint = true;
                metConditions.push_back(el);
            }

        if (x < fin)
        {
            calc_restricted(x + 1, fin, way + "+1", restrictions, okToPrint, metConditions);
            if (x != 0)
                calc_restricted(x * 2-1, fin, way + "*2-1", restrictions, okToPrint, metConditions);
        }
        else if (x == fin && okToPrint)
            std::cout << way << ", путь прошел через " << vector_to_string(metConditions) << std::endl;
    };

    calc_restricted(start, end, "", restrictions, false, std::vector<int>());
    std::cout << "Количество ветвлений:" << branchCount << std::endl;



    // Обратный ход
    std::cout << std::endl << "===Обратный ход===" << std::endl;
    std::cout << "Начало: " << end << ", конец: " << start << ". Операции: -1, (+1)/2" << std::endl;

    branchCount = 0;

    std::function<void (int, int, std::string)> calc_reverse = [&calc_reverse, &branchCount](int x, int fin, std::string way)
    {
        branchCount++;
        if (x > fin)
        {
            calc_reverse(x - 1, fin, way + "-1");
            if (x != 0 && x % 2) //порверка на деление
                calc_reverse((x+1)/2, fin, way + "(+1)/2");
        }
        else if (x == fin)
            std::cout << way << std::endl;
    };

    calc_reverse(end, start, "");
    std::cout << "Количество ветвлений:" << branchCount << std::endl;



    // Прямой ход с выводом фазового пространства
    std::cout << std::endl << "===Прямой ход с выводом фазового пространства===" << std::endl;
    std::cout << "Начало: " << start << ", конец: " << end << ". Операции: +1, *2-1" << std::endl << std::endl;

    branchCount = 0;
    std::map<int, int> phase;

    std::function<int (int, int)> calc_with_phase = [&calc_with_phase, &branchCount, &phase](int x, int fin)
    {
        branchCount++;

        if (x == fin)
            phase[x] = 1;


        if (phase.count(x))
            return phase[x];

        if (x < fin)
        {
            phase[x] = calc_with_phase(x + 1, fin) + calc_with_phase(x * 2-1, fin);
            return phase[x];
        }
        return 0;
    };

    calc_with_phase(start, end);

    std::cout << "Вектор фазового пространства:" << std::endl;
    for (auto& el : phase)
    {
        std::cout << el.first << " - " << el.second << std::endl;
    }
    std::cout << "Количество ветвлений:" << branchCount << std::endl;

    return 0;
}