3

Есть n-ое количество элементов в словаре:

Dictionary<int, List<int>> dict = new Dictionary<int, List<int>>();

В List лежат ключи связующих словарей. То есть, например, словарь с ключом '1' связывается со словарями с ключами 1, 6, 8, 10. А словарь с ключом 90 связывается со словарями с ключами 8, 3, 92, 138.

dict[1] = new List<int>(){ 87, 6, 8, 10 };
dict[90] = new List<int>() { 8, 3, 92, 138 };

Задача - найти кратчайший путь между словарями dict[1] и dict[90] по их связям. То есть сначала сравнить все элементы в списке словаря с ключом 1 с 90. Потом сравнить по-очереди каждый элемент списка в словаре с ключом '87' с 90, потом каждый элемент списка в словаре с ключом '6' и так далее, пока не будет достигнуто совпадение с 90. Полученный путь нужно запомнить в отдельный List, в котором будут ключи словарей в пути.

Пример:

dict[1] = new List<int>(){ 3, 5 };
dict[3] = new List<int>(){ 1, 8 };
dict[5] = new List<int>(){ 1 };
dict[8] = new List<int>(){ 3, 90 };
dict[90] = new List<int>() { 8 };

Нужно найти кратчайшее расстояние от dict[1] до dict[90]. Сначала сравниваем все элементы в dict[1] с 90. Элемента 90 в списке словаря '1' нет. Ищем дальше: берём первый элемент списка словаря с ключом '1' (3) и сравниваем элементы словаря dict[3] с 90. Элемента 90 в списке словаря '3' нет. Берём следующий элемент списка словаря '1' (5). Там сравниваем всего один элемент и тоже нет совпадений.

Теперь углубляемся и рассматриваем элементы словаря '3' как отдельные словари. Т.е. проверяем dict[1] - ничего нет. Проверяем dict[8] - совпадение. Поиск закончен!

При этом нужно запоминать путь. В качестве вывода использовать

List<int> output = new List<int>();

В который по порядку будут записываться ключи словарей в пути. В примере он будет состоять из элементов:

output.Add(1);
output.Add(3);
output.Add(8);
output.Add(90);

Очевидно, нужно использовать рекурсию для прохождения по всем элементам списков.

8
  • А в чем затык? сами то пробовали?
    – srvr4vr
    25 июн 2018 в 18:27
  • Разумеется, но не понимаю, как написать рекурсию, что передавать в параметрах и как её использовать в цикле?
    – A.Hall
    25 июн 2018 в 18:29
  • А зачем ей цикл? Она сама себе цикл)
    – srvr4vr
    25 июн 2018 в 18:29
  • Я не знаю) пытался и так, и так, но не хватает воображения
    – A.Hall
    25 июн 2018 в 18:31
  • 2
    Так вы пытаетесь через голову прыгнуть - потренеруйтесь на простых примерах, на которых обычно рекурсию и рассматривают. А там и какое-никакое понимание придет. Что бы понять рекурсию - нужно понять рекурсию)
    – srvr4vr
    25 июн 2018 в 18:32

1 ответ 1

3

Рекурсию можно использовать, но не нужно. Задача сводится к обходу графа в ширину. Где словари - это вершины графа. А ключи доступа - ребра. Замечу, что это орграф.

Извиняйте за введение собственной системы ввода данных, писал, чтобы проверить работоспособность. А раз написал, не грех и поделиться.

На вход поступает 2 числа, N - кол-во ключей и M - кол-во записей о этих ключах. В следующих M строках описываются ключи в формате: 1-e число - ключ, последующие через пробел - ключи других словарей. Далее программа требует два числа X и Y. От какого словаря требуется найти путь к другому.

Программа выводит кратчайший путь, если таковой существует, иначе "Don't exist".

        string[] Inp = Console.ReadLine().Split(); // Заносим данные ==>>
        int N = Convert.ToInt32(Inp[0]), M = Convert.ToInt32(Inp[1]);

        Dictionary<int, List<int>> dict = new Dictionary<int, List<int>>();
        for (int i = 0; i < N; i++) dict[i] = new List<int>();

        for (int i = 0; i < M; i++)
        {
            Inp = Console.ReadLine().Split();
            int Temp = Convert.ToInt32(Inp[0]) - 1;
            for (int j = 1; j < Inp.Length; j++)
            {
                dict[Temp].Add(Convert.ToInt32(Inp[j]) - 1);
            }
        }

        Inp = Console.ReadLine().Split();
        int X = Convert.ToInt32(Inp[0]) - 1, Y = Convert.ToInt32(Inp[1]) - 1; // <<== Все еще заносим

        Queue<int> Work = new Queue<int>(); // BFS работает через очередь.
        bool[] Mark = new bool[N]; // Массив, в котором будем помечать посещенные словари
        int[] Log = new int[N]; // Потребуется для вывода найденного пути
        bool Exist = false; // Существует ли наш путь вообще

        Work.Enqueue(X); // см. Алгоритм BFS (обход в глубину)
        Mark[X] = true;
        Log[X] = -1;

        while (Work.Count > 0)
        {
            int v = Work.Dequeue();

            for (int i = 0; i < dict[v].Count; i++)
            {
                if (!Mark[dict[v][i]])
                {
                    if (dict[v][i] == Y) Exist = true;

                    Work.Enqueue(dict[v][i]);
                    Mark[dict[v][i]] = true;
                    Log[dict[v][i]] = v;
                }
            }
        }

        if (Exist)
        {
            List<int> output = new List<int>(); // Восстанавливаем путь
            for (int v = Y; v != -1; v = Log[v]) output.Add(v);

            output.Reverse();

            for (int i = 0; i < output.Count; i++) Console.Write(output[i] + 1 + " ");
            Console.WriteLine();
        }
        else Console.WriteLine("Don't exist");

Вот пример работы:

Входные данные:

100 6
1 2 3 4 5
5 2 3 1
45 42 13
54 42 13
3 45
42 54
1 13

Выходные данные:

1 3 45 13

Надеюсь, помог.

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.