Главная Полное построение алгоритма [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [ 49 ] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] PROGRftH BFSPAN CI№UT.0UTPyT.TAPE6=0UTPUT,TApe5slNPUTI •с ПРОГРАММА НАХОДИТ ОСТОВНОЕ ДЕРЕВО В НЕВЗВЕШЕННОИ СЕТИ G, t ИСПОЛЬЗУЯ ПОДПРОГРАММУ CFS, В КОТОРОЙ ПРИМЕНЯЕТСЯ С МЕТОД ПОИСКА В ШИРИНУ. С ПЕРЕМЕННАЯ СПИСАНИЕ С *0Л1! МАССИВЫ для Р СВЯЗАННЫХ СПИСКОВ ВЕРШИН, е NEXTUI СМЕЖНЫХ с ДАННОЙ. с Р ВЕРШИНЫ G ПОМЕЧЕНЫ 1,2...., Р .С Н.М СЧИТЫВАЕМОЕ РЕБРО G. ЕСЛИ М<0»- С БОЛЬШЕ РЕБЕР НЕГ- С V НАЧАЛЬНАЯ ВЕРШИНА, ИЗ КОТОРОЙ НАЧИНАЕТСЯ С ПОИСК В ШИРИНУ. " INTEGER AOJ(IOOO). NEXTtlDOOl INTEGER V. P С СЧИТЫВАНИЕ ЧИСЛА ВЕРШИН. PEAD (5.1000! Р ХОйЯ FORHAT ( 14. If I 1 = Р + 1 с ИНИЦИАЛИЗАЦИЯ МАССИВОВ ADJ И NEXT. С DO 50 11 S 1.Р ADJ(II) =0 NEXTdlJ = О 50 CONTINUE С СЧИТЫВАНИЕ РЕБЕР G. С 10В READ tS.lOOO) H.N IF { м .UT. О ) GO TO гоо rjEXT(I) = NEXT(M! ADJII) s N MEXT(HJ = I 1 = 1 + 1 NEXT(I) = NEXTINI ADJ(I) = n rjEXT(N) = I 1 = 1 + 1 GD TO 100 С СЧИТЫВАНИЕ ВЕРШИН V И БЫЗОВ BFS. 800 READ (5.18001 V CALL BFS (V« AOJt NCXTt P 1 STOP SUBROUTINE BFS IV. ADJ. ЫЕХГ. P ) С ПОДПРОГРАММА РЕАЛИЗУЕТ АЛГОРИТМ ПОИСКА В ШИРИНУ С ДЛЯ НАХОЖДЕНИЯ остовного ДЕРЕВА В НЕВЗВЕШЕННОИ СЕТИ. С «** ФОРНАЛЬНЫЕ ПАРАМЕТРЫ **♦ С V БСРШИНА, ИЗ КОТОРОЙ НАЧИНАЕТСЯ с ЛОИСК В ШИРИНУ. Рис 3.5.9. Реализация алгоритма BFS на Фортране (Текст в операторе 2000: «Вектор остовного дерева».) AOJtNEXT КАССИВЫ ДЛЯ ПРЕДСТАВЛЕНИЯ СЕТИ С СВЯЗАННЫМ СПИСКОМ. Р ЧИСЛО ВЕРШИН В С. *** ЛОКАЛЬНЫЕ ПЕРЕМЕННЫЕ*** LABLEd) МАССИВ, ИСПОЛЬЗУЕМЫЙ ТОЛЬКО ДЛЯ ПЕЧАТИ ОСТОВНОГО ДЕРЕВА. VECTORrI) ЕСЛИ VECTOR(I) = J, ТО РЕБРО В ОСТОенОМ ДЕРЕВЕ. VSITIJIsI ОЗНАЧАЕТ, ЧТО ВЕРШИНА БЫЛА 1-Й, ПРОСМОТРЕННОЙ ВПЕРВЫЕ. VISIT(.V) = 0 ОЗНАЧАЕТ, ЧТО V ЕЩЕ НЕ ПРОСМОТРЕНА. LJSTdJ LIST-МАССИВ ВЕРШИН, КОТОРЫЕ НУЖНО ПРОСМОТРЕТЬ ВПЕРВЫЕ. n ИНДЕКС, ПРОБЕГАЮЩ,ИЙ МАССИВ LIST. I ИНДЕКС ДЛЯ ДОБАВЛЕНИЯ ВЕРШИН К МАССИВУ LIST. PTR ИНДЕКС, ПРОБЕГАЮШ.ИЙ СВЯЗАННЫЙ СПИСОК СМЕЖНОСТЕЙ. INTEGER ADJ(ICOO). NEXTdOOO) INTEGER VECTORdOOIt ViSITIlOOJ INTEGER LABELdOOr . INTEGER LISTdcO) INTEGER V» Pt PTR ИНИЦИАЛИЗАЦИЯ МАССИВОВ. CO го I = i.p LABELdI = I LISTd) = 0 VISITd) = 0 VECTOR d) = 0 10 CONTINUE LIST(P+1 = 0 1 = 1 N = 1 ВЕРШИНА V ПРОСМОТРЕНА ВПЕРВЫЕ. LISTd) = V VECTORrV) = 0 visiT(v) = 1 СЛЕДУЮШ,АЯ НЕПРОСМОТРЕННАЯ ВЕРШИНА М. 50 Н = LIST(N) PTR = М ПРОВЕРКА СМЕЖНЫХ С М ВЕРШИН. 100 PTR = NEXTIPTR) IF ( PTR .EQ. О ! ео TO 150 J = ADJ(PTR) ПРОВЕРКА, ПРОСМОТРЕНА ЛИ ВЕРШИНА. IF ( VISIT(J) .NE. о I GO TO 100 Рис. 3.5.9. Продолжение с УБАВЛЕНИЕ ВЕРШИНЫ К СПИСКУ И ОСТОВНОМУ ДЕРЕВУ. С 1 = 1 + 1 LIST(I) = J VISIT(J)= I VECTOR(J) s M eo TO 10.O ISO f = N + i IF ( LIST(N) .NET. 0 } 60 TO So WRITE (6,3000) ILABEL(K).K=i,p) SIOO FORMAT (IHQ. Ч0131-RETURN ENO Рис.3.5.9. Продсажение. Наша точка зрения состоит просто в том, что рекурсия - это естественный метод представления алгоритмов решения множества математических и вычислительных задач и что это метод, о котором не следует забывать. Как только алгоритм рекурсивно сформулирован, возникает несколько вариантов реализации. Первый и наиболее очевидный - реализовать его на языке программирования, допускающем рекурсию. Второй вариант - реализовать его на нерекурсивном языке, моделируя стек, как мы делали в алгоритме DFS. Третья возможность - обратиться за помощью к литературе по разным «автоматическим» процедурам преобразования рекурсивного алгоритма в итеративный. Наконец, можно пересмотреть задачу с тем, чтобы выяснить, действительно ли рекурсия необходима, т. е. можно построить новый алгоритм. Упражнения 3.5 3.5.1. Факториалы. Что произойдет, если попытаться вычислить Л! на Фортране, пользуясь определением рекурсии, данным в начале этого раздспа? 3.5.2. Биномиальные коэффициенты. Напишите рекурсивный алгоритм для вычисления биномиальных коэффициентов: для птО. т\ (п-т)\ Реализуйте ваш алгоритм, если вы знаете язык, допускающий рекурсивные обращения. *3.5.3. Пусть G(n) обозначает число /г-значных последовательностей нулей и единиц, в которых ие содержится двух или более единиц подряд. Выразите рекурсивно G(n). Сравните С(п) с числами Фибоначчи. 3.5.4. Поиск в глубину. Используя поиск в глубину, найдите остовное дерево для полной двусвязной сети /Сз g (см. упр. 2.2.12). 3.5.5. Поиск в ширину. Используя поиск в ширину, найдите остовное дерево для полной двусвязной сети Ks, з- Сравните это дерево с деревом, найденным в упр. 3.6.4. 3.5.6. Разбиения целых чисел. Напишите машинную программу вычисления Р (Л?) для Л=1, 2, 3, . , . , 50. [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [ 49 ] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] 0.0017 |