Используя рекурсию, определить, можно ли по дорогам попасть из 1-го пункта в N-ый - C (СИ)
Формулировка задачи:
Имеется 10 населенных пунктов. Дана последовательность пар чисел пар чисел I и J (I<J), указывающих, что I –ый J-ый пункты соединены дорогой. Признак конца этой последовательности - пара нулей. Используя рекурсию, определить, можно ли по этим дорогам попасть из 1-го пункта в N-ый.
Помогите, пожалуйста.
Решение задачи: «Используя рекурсию, определить, можно ли по дорогам попасть из 1-го пункта в N-ый»
textual
Листинг программы
#include <stdio.h> #define MAXVERTICES 100 #define MAXEDGES 100 enum { NO, YES }; int n; int found = NO; int used[MAXVERTICES + 1] = { NO }; int edges[MAXEDGES + 1][2]; void walk(int vtx); int main() { int i, j, cnt; printf("enter n:\n"); scanf("%d", &n); if (n <= 0 || n > MAXVERTICES) return 1; printf("enter edges:\n"); cnt = 0; while (cnt < MAXEDGES && scanf("%d %d", &i, &j) == 2 && i && j) { edges[cnt][0] = i; edges[cnt][1] = j; cnt++; } edges[cnt][0] = edges[cnt][1] = 0; walk(1); printf("one can%s\n", found ? "" : "not"); return 0; } #define isnotused(vtx) (used[(vtx)] == NO) void walk(int vtx) { int i; used[vtx] = YES; if (vtx == n || found == YES) { found = YES; return; } for (i = 0; edges[i][0] != 0; i++) if (edges[i][0] == vtx && isnotused(edges[i][1])) walk(edges[i][1]); else if (edges[i][1] == vtx && isnotused(edges[i][0])) walk(edges[i][0]); }
Объяснение кода листинга программы
В этом коде реализована функция, которая с помощью рекурсии проверяет, можно ли по дорогам попасть из 1-го пункта в N-ый. Для этого в коде представлены следующие элементы:
- Объявлены следующие переменные: n - количество вершин в графе, которое вводится пользователем. found - флаг, который указывает, можно ли добраться до последней вершины. used - массив, который отслеживает, была ли уже посещена та или иная вершина. edges - массив, который содержит информацию о ребрах графа.
- С помощью функции
walk(int vtx)
происходит обход графа. - В функции
main()
пользователю предлагается ввести количество вершин и информацию о ребрах графа. - После сбора данных происходит вызов функции
walk(1)
, которая начинает обход графа с первой вершины. - Результатом работы программы будет сообщение о том, можно ли добраться до последней вершины или нет.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д