Advertisement
Guest User

Untitled

a guest
Feb 17th, 2020
309
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cstring>
  3.  
  4. using namespace std;
  5.  
  6. //!!! P.S. Некоторые проверки в программе не выполняются, для упрощения восприятия
  7.  
  8. /**
  9.  * @brief Генерируем лягушек
  10.  * @param frogs Указатель на массив с лягушками [m + n + 1] размерности
  11.  * @param m T лягушек
  12.  * @param n F лягушек
  13.  **/
  14. void generateFrogs(char *frogs, const int m , const int n) {
  15.     int count = m + n + 1;
  16.     memset(frogs, ' ', count);
  17.  
  18.     for(int i = 0; i < m; i++) {
  19.         frogs[i] = 'T';
  20.     }
  21.     for(int i = m + 1; i < count; i++) {
  22.         frogs[i] = 'F';
  23.     }
  24. }
  25.  
  26. /**
  27.  * @brief Заданные шаблоны поведения лягушек возле свободной ячейки
  28.  */
  29. struct Patterns{
  30. public:
  31.  
  32.     // T1 <-- Цифра - количество шагов
  33.     // ^
  34.     // |
  35.     // Символ - тип лягушки
  36.     /**
  37.      * @brief Задаем шаблоны в конструкторе структуры и записываем указатели в m_list
  38.      */
  39.     Patterns() {
  40.         m_list[0] = "TF FT"; // T2
  41.         m_list[1] = "FT TF"; // F2
  42.  
  43.         m_list[2] = "FF FT"; // F1
  44.         m_list[3] = "TT TF"; // F2
  45.  
  46.         m_list[4] = "FF TF"; // F2
  47.         m_list[5] = "TT FT"; // T1
  48.  
  49.         m_list[6] = "TF FF"; // T2
  50.         m_list[7] = "FT TT"; // T1
  51.  
  52.         m_list[8] = "FT FF"; // F1
  53.         m_list[9] = "TF TT"; // T2
  54.  
  55.         m_list[10] = "FT FT"; // F1 or T1
  56.         m_list[11] = "TF TF"; // lock
  57.  
  58.         m_list[12] = "TT FF"; // F1 or T1
  59.  
  60.         m_list[13] = "FF FF"; // F1;
  61.         m_list[14] = "TT TT"; // T1;
  62.  
  63.         m_list[15] = "FF TT"; // done
  64.     }
  65.     /**
  66.      * @brief Возвращает указатель на заданный шаблон.
  67.      * Нужна лишь для итеративного поиска.
  68.      * @param num Номер шаблона в m_list
  69.      * @return Указатель на заданный шаблон
  70.      */
  71.     const char *pattern(const int &num) {
  72.         // Проверку не стал делать, для упрощения восприятия
  73.         return m_list[num];
  74.     }
  75.     /**
  76.      * @brief Возвращает число шаблонов
  77.      * @return Число шаблонов
  78.      */
  79.     int size() {
  80.         return m_size;
  81.     }
  82.  
  83. private:
  84.     static const int m_size = 16;
  85.     // Массив с указателями на массивы шаблонов
  86.     const char *m_list[m_size];
  87.  
  88. } frog_patterns;
  89.  
  90. /**
  91.  * @brief Получение текущего состояния (шаблона) в массиве с лягушками
  92.  * @param currentPattern Указатель на формируемый массив для записи в него шаблона
  93.  * @param frogs Указатель на массив с лягушками
  94.  * @param count Размер массива с лягушками
  95.  * @param iter Текущее положение пробела
  96.  */
  97. void getCurrentPattern(char *currentPattern, char *frogs, const int &count, const int &iter) {
  98.     //Задаем шаблон текущего положения для последующего сравнения с заданными шаблонами
  99.     memcpy(currentPattern, &frogs[iter - 2], 5); // dangerous !!! Опасно, выходим за рамки заданного массива. Но работает
  100.  
  101.     // Задаем МНИМЫХ лягушек в текущий шаблон для последующего сравнения с заданными шаблонами.
  102.     // Когда символ пробела находится с краю, например: 'FF |' или '|T FF'  (где | край массива)
  103.     // То приходим в несколько неодназначную ситуацию.
  104.     // Проще всего этого избежать добавив МНИМЫХ лягушек в шаблон для сравнения.
  105.     // Для конечных точек характеры следующие МНИМЫЕ лягушки:   Для начального положения(крайнего левого предела) характерна мнимая F
  106.     //                                                          Для последнего положения(крайнего правого предела) характерна мнимая T
  107.     // P.S. МНИМЫЕ лягушки на то и мнимые, они ни как не дополняют исходный массив, они лишь заполняют шаблон для сравнения.
  108.  
  109.     if(iter == 0) {
  110.         currentPattern[0] = 'F';
  111.         currentPattern[1] = 'F';
  112.     }
  113.     if(iter == 1) {
  114.         currentPattern[0] = 'F';
  115.     }
  116.     if(iter == (count - 1)) {
  117.         currentPattern[3] = 'T';
  118.         currentPattern[4] = 'T';
  119.     }
  120.     if(iter == (count - 2)) {
  121.         currentPattern[4] = 'T';
  122.     }
  123. }
  124.  
  125. /**
  126.  * @brief Перемещение лягушки на место пустой ячейки
  127.  * @param frogs Указатель на массив с лягушками
  128.  * @param iter Текущее положение пробела
  129.  * @param type Тип лягушки
  130.  * @param step Шаг для перемещения лягушки
  131.  */
  132. void moveFrog(char *frogs, const int &iter, const char &type, const int &step) {
  133.     if(type == 'F') {
  134.         frogs[iter] = frogs[iter + step];
  135.         frogs[iter + step] = ' ';
  136.     }
  137.     if(type == 'T') {
  138.         frogs[iter] = frogs[iter - step];
  139.         frogs[iter - step] = ' ';
  140.     }
  141. }
  142.  
  143. /**
  144.  * @brief Основной цикл сравнения состояний
  145.  * @param frogs Указатель на массив с лягушками
  146.  * @param m T лягушек
  147.  * @param n F лягушек
  148.  * @param iter Текущее положение пробела
  149.  * @return Возвращает 1, если перемещение всех лягушек завершено. В остальных случаях 0.
  150.  */
  151. int move(char *frogs, const int &m , const int &n, const int &iter) {
  152.     int count = m + n + 1;
  153.  
  154.     char currentPattern[5];
  155.     memset(currentPattern, ' ', 5);
  156.     getCurrentPattern(currentPattern, frogs, count, iter);
  157.  
  158.     // Проходим по всем заданным шаблонам
  159.     for(int i = 0; i < frog_patterns.size(); i++) {
  160.         // Сравниваем
  161.         int rescmp = memcmp(currentPattern, frog_patterns.pattern(i), 5);
  162.         if(rescmp == 0) {
  163.             // При совпадении перемещаем
  164.             switch (i) {
  165.             case 0:
  166.                 moveFrog(frogs, iter, 'T', 2); // T2
  167.                 break;
  168.             case 1:
  169.                 moveFrog(frogs, iter, 'F', 2); // F2
  170.                 break;
  171.             case 2:
  172.                 moveFrog(frogs, iter, 'F', 1); // F1
  173.                 break;
  174.             case 3:
  175.                 moveFrog(frogs, iter, 'F', 2); // F2
  176.                 break;
  177.             case 4:
  178.                 moveFrog(frogs, iter, 'F', 2); // F2
  179.                 break;
  180.             case 5:
  181.                 moveFrog(frogs, iter, 'T', 1); // T1
  182.                 break;
  183.             case 6:
  184.                 moveFrog(frogs, iter, 'T', 2); // T2
  185.                 break;
  186.             case 7:
  187.                 moveFrog(frogs, iter, 'T', 1); // T1
  188.                 break;
  189.             case 8:
  190.                 moveFrog(frogs, iter, 'F', 1); // F1
  191.                 break;
  192.             case 9:
  193.                 moveFrog(frogs, iter, 'T', 2); // T2
  194.                 break;
  195.             case 10:
  196.                 moveFrog(frogs, iter, 'F', 1); // F1 or T1
  197.                 break;
  198.             case 12:
  199.                 if((m % 2) == 0) {
  200.                     moveFrog(frogs, iter, 'T', 1);
  201.                 } else {
  202.                     moveFrog(frogs, iter, 'F', 1);
  203.                 }
  204.                 //moveFrog(frogs, iter, 'F', 1); // F1 or T1 //if m is even use T1
  205.                 break;
  206.             case 13:
  207.                 moveFrog(frogs, iter, 'F', 1);
  208.                 break;
  209.             case 14:
  210.                 moveFrog(frogs, iter, 'T', 1);
  211.                 break;
  212.             case 15:
  213.                 return 1;
  214.                 break;
  215.             }
  216.         }
  217.     }
  218.     return 0;
  219. }
  220.  
  221. /**
  222.  * @brief Запуск цикла алгоритма
  223.  * @param m T лягушек
  224.  * @param n F лягушек
  225.  */
  226. void jumpAlg(const int m , const int n) {
  227.     int count = m + n + 1;
  228.     char frogs[count + 1];      // +1 чтобы добавить символ \0 в конец, для корректного вывода через printf
  229.     frogs[count] = '\0';        // тут и добавим
  230.     generateFrogs(frogs, m, n); // Генерируем массив с лягушками
  231.  
  232.     int counter = 0;
  233.     while(true) {
  234.         printf("%s\n", frogs);
  235.         int ret = 0;
  236.         for(int iter = 0; iter < count; iter++) {
  237.             // При нахождении пробела, входим в Основной цикл сравнения состояний
  238.             if(frogs[iter] == ' ') {
  239.                 ret = move(frogs, m, n, iter);
  240.                 break;
  241.             }
  242.         }
  243.         if(ret == 1) {
  244.             printf("Count steps: %d\n", counter);
  245.             break;
  246.         }
  247.         counter++;
  248.     }
  249. }
  250.  
  251. int main()
  252. {
  253.     //
  254.     // T, F
  255.     jumpAlg(3, 5);
  256.     return 0;
  257. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement