Главная  Полное построение алгоритма 

[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