artemgf

Классификатор Тимуса

Sep 13th, 2017
187
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.53 KB | None | 0 0
  1. #define _USE_MATH_DEFINES
  2. #include <iostream>
  3. #include <conio.h>
  4. #include <string>
  5. #include <set>
  6. #include <map>
  7. #include <algorithm>
  8. #include <string>
  9. #include <math.h>
  10. #include <vector>
  11. #include <cmath>
  12. #include <sstream>
  13. #include <queue>
  14.  
  15. using namespace std;
  16.  
  17. struct top // структура вершины дерева
  18. {
  19.     string num; // номер префикса
  20.     string name; // название задачи
  21.     map <string, top*> next; // ссылке на следующие префиксы ниже рангом
  22. };
  23.  
  24. top* Newtop(string num, string name) // создания новой вершины дерева
  25. {
  26.     top* Top = new top();
  27.  
  28.     Top->num = num;
  29.     Top->name = name;
  30.  
  31.     return Top;
  32. }
  33.  
  34. string addtree(queue<string>parag, string name, map <string, top*> coren) /* добавляем в дерево новую тему и узнаем список с ей и её родителями*/
  35. {
  36.     top* topWhat = new top(); // итоговая вершина данной темы
  37.     top* proms = new top(); // промежуточная вершина дерева
  38.     string d = "";//список с темой и её родителями
  39.  
  40.     proms = coren[parag.front()];//узнаём ссылку на корневой элемент дерева
  41.     parag.pop();// удаляем этот префикс из очереди
  42.  
  43.     d += proms->name + ".";// добавляем корневую тему в список
  44.  
  45.     while (parag.size()!=1) // бежим пока не останется вставляемая тема
  46.     {
  47.         proms = proms->next[parag.front()]; // движемся по дереву к следующему префиксу
  48.         d += proms->name + "."; // добавляем родителей темы в список
  49.         parag.pop();//вновь освобождаем место у кассы)
  50.     }
  51.  
  52.     topWhat = Newtop(parag.front(), name); // ссылка на вставляемую в дерево тему
  53.     d += name;// добавляем саму тему в список
  54.  
  55.     proms->next[parag.front()] = topWhat;//добавляем тему в дерево
  56.  
  57.     return d;//возражающем список
  58. }
  59.  
  60. set<string> finds(map <int, set <string>> exc, string nums, set<string>* proms) /* проверяем не встретились ли нам задачи с одинаковым количеством и названием тем (список с номерами задач и темами к ним, номер задачи, и список со всеми использованными задачами*/
  61. {
  62.     set<string> num;//номера с одинаковым количеством и названием тем
  63.     set<string> prom;//промежуточный список тем у данной задачи
  64.  
  65.     num.insert(nums);// добавляем данную задачу в совпадающие
  66.     proms->insert(nums);// добавляем данную задачу в использованные
  67.     prom = exc[atoi(nums.c_str())]; // узнаем список тем с которым надо сравнить
  68.  
  69.     for (auto i = exc.begin(); i != exc.end(); i++) // проверяем
  70.     {
  71.         if (i->first != atoi(nums.c_str()))//проверка не та ли эта задача с которой сравниваем
  72.         {
  73.             if (prom == i->second) // проверяем совпадает ли список тем
  74.             {
  75.                 num.insert(to_string(i->first)); // если да, то впихиваем этот номер задачи в совпадающие и в использованные
  76.                 proms->insert(to_string(i->first));
  77.             }
  78.         }
  79.     }
  80.  
  81.     return num;
  82. }
  83.  
  84. int main()
  85. {
  86.     map <string, top*> coren; // дерево префиксов
  87.     map <int, set <string>> exc; // номера задач с списком из тем и их родителей
  88.     string prom;//промежуточная строка префикса
  89.     string name;// название темы
  90.     string promi="10";// промежуточный номер задач
  91.     bool d = true;
  92.     cin >> prom;
  93.  
  94.     while (d)
  95.     {
  96.         string toprom="";//список из этой темы и её родителей
  97.         queue<string>parag;
  98.         d = false;
  99.        
  100.         int i=0;
  101.         int last=0;
  102.  
  103.         while (i != prom.size()) // создаем очередь префиксов, чтобы было проще находить предка
  104.         {
  105.             if (prom[i] == '.')//следовательно число закончилось, ведь оно может быть двузначным
  106.             {
  107.                 parag.push(prom.substr(last, i - last));
  108.                 i++;
  109.                 last = i;
  110.             }
  111.             else
  112.                 i++;
  113.         }
  114.  
  115.         getline(cin, name); // ввод темы
  116.         name = name.substr(1, name.size() - 1);//так как там пробел есть
  117.  
  118.         if (parag.size() == 1) // если это корневой префикс
  119.         {
  120.             top* t = new top();
  121.             t = Newtop(parag.front(), name);
  122.             coren[parag.front()] = t;
  123.             toprom = t->name;
  124.         }
  125.         else
  126.         {
  127.             toprom = addtree(parag, name, coren);//иначе идём до него и заодно пишем путь его и родителей
  128.         }
  129.        
  130.         while (cin >> promi)//ввод номеров задач
  131.         {
  132.             if (promi[1] == '.' || promi[2] == '.')//если пошёл ввод следующей темы
  133.             {
  134.                 prom = promi;
  135.                 d = true;
  136.                 break;
  137.             }
  138.             else
  139.             {
  140.                 exc[atoi(promi.c_str())].insert(toprom); // ввод в номер задачи список из этой темы и её родителей
  141.             }
  142.         }
  143.  
  144.         toprom = "";
  145.     }
  146.  
  147.     set<string>* proms=new set<string>();//использованные задачи
  148.     set < string> promd;
  149.  
  150.     for (auto i = exc.begin(); i != exc.end(); i++) // вывод
  151.     {
  152.         string num;
  153.         num = to_string(i->first); // номер текущей задачи
  154.  
  155.         if (proms->find(to_string(i->first)) == proms->end()) // проверка не использовали ли мы эту задачу ранее
  156.         {
  157.             promd = finds(exc, num, proms);//проверка есть ли ещё задачи с такими же темами, как данная
  158.  
  159.             for (auto j = promd.begin(); j != promd.end(); j++)//вывод номеров задач
  160.             {
  161.                 if (++j != promd.end())
  162.                 {
  163.                     j--;
  164.                     cout << *j << ", ";
  165.                 }
  166.                 else
  167.                 {
  168.                     j--;
  169.                     cout << *j << " : ";
  170.                 }
  171.             }
  172.  
  173.             for (auto j = i->second.begin(); j != i->second.end(); j++) //вывод тем
  174.             {
  175.                 if (++j != i->second.end())
  176.                 {
  177.                     j--;
  178.                     cout << *j << ", ";
  179.                 }
  180.                 else
  181.                 {
  182.                     j--;
  183.                     cout << *j << endl;
  184.                 }
  185.             }
  186.  
  187.         }
  188.  
  189.     }
  190.  
  191.     _getch();
  192.     return 0;
  193. }
Advertisement
Add Comment
Please, Sign In to add comment