ortem_kats

salibek_lab5

Feb 29th, 2020
312
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <functional>
  3. #include <string>
  4. #include <vector>
  5. #include <map>
  6. #include <locale>
  7.  
  8. const int start = 4, end = 27;
  9. const std::vector<int> restrictions = { 7, 17 };
  10.  
  11. template<typename T>
  12. std::string vector_to_string(const std::vector<T>& vec)
  13. {
  14.     std::string res;
  15.     bool first = true;
  16.     for (auto& el : vec)
  17.     {
  18.         if (!first)
  19.             res += ", ";
  20.         res += std::to_string(el);
  21.         first = false;
  22.     }
  23.     return res;
  24. }
  25.  
  26. int main()
  27. {
  28.     setlocale(LC_ALL, "rus");
  29.  
  30.     // Прямой ход
  31.     std::cout << "===Прямой ход===" << std::endl;
  32.     std::cout << "Начало: " << start << ", конец: " << end << ". Операции: +1, *2-1" << std::endl << std::endl;
  33.  
  34.     int branchCount = 0;
  35.  
  36.     std::function<void (int, int, std::string)> calc = [&calc, &branchCount](int x, int fin, std::string way)
  37.     {
  38.         branchCount++;
  39.         if (x < fin)
  40.         {
  41.             calc(x + 1, fin, way + "+1");
  42.             if (x != 0)
  43.                 calc(x * 2-1, fin, way + "*2-1");
  44.         }
  45.         else if (x == fin)
  46.             std::cout << way << std::endl;
  47.     };
  48.    
  49.     calc(start, end, "");
  50.     std::cout << "Количество ветвлений:" << branchCount << std::endl;
  51.  
  52.  
  53.  
  54.     // Прямой ход с контрольными точками. Траектория должна проходить через хотя бы одно из чисел-ограничителей
  55.     std::cout << std::endl << "===Прямой ход с контрольными точками===" << std::endl;
  56.     std::cout << "Начало: " << start << ", конец: " << end << ". Контрольные точки = " << vector_to_string(restrictions) <<
  57.         ". Операции: +1, *2-1" << std::endl << std::endl;
  58.  
  59.     branchCount = 0;
  60.  
  61.     std::function<void (int, int, std::string, const std::vector<int>&, bool, std::vector<int>)> calc_restricted =
  62.         [&calc_restricted, &branchCount]
  63.         (int x, int fin, std::string way, const std::vector<int>& restrictions, bool okToPrint, std::vector<int> metConditions)
  64.     {
  65.         branchCount++;
  66.  
  67.         for (auto& el : restrictions)
  68.             if (x == el) // Если путь проходит через одно из значений - ограничений
  69.             {
  70.                 okToPrint = true;
  71.                 metConditions.push_back(el);
  72.             }
  73.  
  74.         if (x < fin)
  75.         {
  76.             calc_restricted(x + 1, fin, way + "+1", restrictions, okToPrint, metConditions);
  77.             if (x != 0)
  78.                 calc_restricted(x * 2-1, fin, way + "*2-1", restrictions, okToPrint, metConditions);
  79.         }
  80.         else if (x == fin && okToPrint)
  81.             std::cout << way << ", путь прошел через " << vector_to_string(metConditions) << std::endl;
  82.     };
  83.  
  84.     calc_restricted(start, end, "", restrictions, false, std::vector<int>());
  85.     std::cout << "Количество ветвлений:" << branchCount << std::endl;
  86.  
  87.  
  88.  
  89.     // Обратный ход
  90.     std::cout << std::endl << "===Обратный ход===" << std::endl;
  91.     std::cout << "Начало: " << end << ", конец: " << start << ". Операции: -1, (+1)/2" << std::endl;
  92.  
  93.     branchCount = 0;
  94.  
  95.     std::function<void (int, int, std::string)> calc_reverse = [&calc_reverse, &branchCount](int x, int fin, std::string way)
  96.     {
  97.         branchCount++;
  98.         if (x > fin)
  99.         {
  100.             calc_reverse(x - 1, fin, way + "-1");
  101.             if (x != 0 && x % 2) //порверка на деление
  102.                 calc_reverse((x+1)/2, fin, way + "(+1)/2");
  103.         }
  104.         else if (x == fin)
  105.             std::cout << way << std::endl;
  106.     };
  107.  
  108.     calc_reverse(end, start, "");
  109.     std::cout << "Количество ветвлений:" << branchCount << std::endl;
  110.  
  111.  
  112.  
  113.     // Прямой ход с выводом фазового пространства
  114.     std::cout << std::endl << "===Прямой ход с выводом фазового пространства===" << std::endl;
  115.     std::cout << "Начало: " << start << ", конец: " << end << ". Операции: +1, *2-1" << std::endl << std::endl;
  116.  
  117.     branchCount = 0;
  118.     std::map<int, int> phase;
  119.  
  120.     std::function<int (int, int)> calc_with_phase = [&calc_with_phase, &branchCount, &phase](int x, int fin)
  121.     {
  122.         branchCount++;
  123.  
  124.         if (x == fin)
  125.             phase[x] = 1;
  126.  
  127.  
  128.         if (phase.count(x))
  129.             return phase[x];
  130.        
  131.         if (x < fin)
  132.         {
  133.             phase[x] = calc_with_phase(x + 1, fin) + calc_with_phase(x * 2-1, fin);
  134.             return phase[x];
  135.         }
  136.         return 0;
  137.     };
  138.  
  139.     calc_with_phase(start, end);
  140.  
  141.     std::cout << "Вектор фазового пространства:" << std::endl;
  142.     for (auto& el : phase)
  143.     {
  144.         std::cout << el.first << " - " << el.second << std::endl;
  145.     }
  146.     std::cout << "Количество ветвлений:" << branchCount << std::endl;
  147.    
  148.     return 0;
  149. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×