Главная Промышленная автоматика.

writeln{weights[candidate]) ; candidate:- candidate - 1; . POP (S) end

else if target = 0 then begin { решение найдено } win flag: = true; candidate:= candidate - 1; POP(S)

else if (( (target < 0) and (TOP(S) = none))

or (candidate > n)) then begin { решения нет } candidate: candidate - 1; ГОР (S)

else { решеыия пока нет,

рассматривается статус текущего кандидата } if TOP(S) = доле then begin

{ первая попытка включить кандидата } target:= target - weights [candidate] ; candidate := candidate + 1; POP(S>; PUSH (included, S) ; PUSH(nofie, S)

else if TOP(S) = 1лс1ийей then begin

{ попытка исключить кандидата } target := target + weights [candidate] ; candidate: candidate + 1; POP(S); PUSH (excluded, S) ; РиЗН(лоле, S)

else begin { TOP(S) = excluded;

отказ от текущего выбора }

POP(S);

candidate: = candidate - 1

until EMPTY (S) end; { knapsack )

Упражнения

2.1. Напишите с помощью операторов списка программу печати элементов списка.

2.2. Напишите программы вставки, удаления и поиска элементов отсортированного списка, используя для реализапии списка

а) массив;

б) указатели;

в) курсоры.

Каково время выполнения каждой из этих программ?

2.3. Напишите программу для слияния

а) двух отсортированных списков;

б) и отсортированных списков.

2.4. Напишите программу объединения списков в один список.

2.5. Рассмотрим многочлены вида р(х) = с,*" + сх + -vcjc", где ej > вг > ... > е„ > 0. Такой многочлен можно представить в виде связанного списка, где каждая ячейка имеет три поля: одно - для коэффипиента с,, второе - для показателя



степени е,-, третье - для указателя на следующую ячейку. Для описанного представления многочленов напишите программу их дифференцирования.

2.6. Напишите программу сложения и умножения многочленов, используя их цредставление, описанное в упражнении 2.5,

*2.7. Пусть ячейки объявлены следующим образом: type

celltype = record bit: 0..1; next: T celltype

end;

Двоичное число 6163...6„, где каждое 6; = О, 1 имеет десятичное значение

Ь,2 \ Это число можно представить в виде списка 61, 62. Ь„. Данный 1=1

список, в свою очередь, представим как связанный список ячеек типа ceHtype, определенного выше. Напишите процедуру increment(bnumber), которая прибавляет 1 к двоичному числу ЬпитЬег. Совет: сделайте процедуру increment рекурсивной.

2.8. Напишите процедуру обмена элементами в позициях р и NEXT(p) для простого связанного списка.

*2.9. Следующая процедура предназначена для удаления всех вхождений элемента X в списке L. Найдите причину, по которой эта процедура будет выполняться не всегда, и устраните ее.

procedure delete ( х: elementtype; var L: LIST ) ; var

p: position; begin

p: = FIRST (L) ;

while p <> END(L) do begin

if RETRIEVE (p, = X then

DELETE (p, L) ; p: = NEXT (p, L)

end; { delete }

2.10. Необходимо сохранить список в массиве А, чьи ячейки содержат два поля: data - для элементов и поле position - для позиций (целых чисел) элементов. Целочисленная переменная last (последний) используется для указания того, что список содержится в ячейках отА[1] до j4[tos«] массива Д. Тип LIST определен следующим образом:

type

LIST = record

last: integer;

elements: array[1. .inaxlength] of record data: elementtype; position; integer;

end;

Напишите процедуру DELETE(p, L) для удаления элемента в позиции р. Включите в процедуру все необходимые проверки на "внештатные" ситуации.

2.11. Пусть L - это список типа LIST, р, <? и г - позиции. Определите как функцию от и (длины списка L) количество выполнений функций FIRST, END и NEXT в следующей программе

УПРАЖНЕНИЯ 73



р: = FIRST(L);

while p <> END(I.) do begin q:= p;

while <5Г <> END(L) do begin q: = NEXT (qr, h) ; r:= FIRST (1.) ;

while r <> g do

r:= NEXT(r, L)

end;

p:= NEXT(p, L)

end;

2.12. Перепишите код операторов, выполняемых над списками LIST, в предположении, что реализуются однонаправленные списки.

2.13. Добавьте необходимые проверки на ошибки в процедуры листинга 2.6.

2.14. Еше одна реализация списков посредством массивов совпадает с описанной в разделе 2.2 за исключением того, что при удалении элемента он заменяется значением "удален", которое другим способом в списке появиться не может. Перепишите операторы списка для этой реализации. Какие достоинства и недостатки этой реализации списков по сравнению с исходной?

2.15. Предположим, что мы хотим использовать логическую переменную при реализации очереди для указания того, что очередь пуста. Измените объявления и операторы в реализации очередей Посредством циклических массивов для использования этой переменной. Что можно ожидать от такой рационализации?

2.16. Очередь с двусторонним доступом - это список, в котором добавлять и удалять элементы можно с обоих концов. Разработайте реализации для таких очередей с использованием массивов, указателей и курсоров.

2.17. Определите АТД, поддерживаюшие операторы ENQUEUE, DEQUEUE (см. раздел 2.4) и ONQUEUE. ONQUEUE(jr) - функция, возврашаюшая значения true или false в зависимости от того, присутствует или нет элемент х в очереди.

2.18. Как реализовать очередь, если элементами являются символьные строки произвольной длины? Сколько времени необходимо для операции вставки такого элемента в очередь?

2.19. В одной возможной реализации очередей посредством связанных списков не используется ячейка заголовка, а указатель front указывает непосредственно на первую ячейку. Если очередь пуста, тогда front = rear = nil. Напишите необходимые операторы для этой реализации очередей. Сравните эту реализацию с реализацией, описанной в разделе 2.4, по критериям времени выполнения, требуемого объема памяти и лаконичности (краткости и понятности) кода.

2.20. В одном варианте реализации очередей посредством циклических массивов записываются позиция первого элемента и длина очереди.

а) необходимо ли в этой реализации ограничивать длину очереди числом maxlength - 1?

б) напишите пять операторов, выполняемых над очередями, для этой реализации;

в) сравните эту реализацию с реализацией посредством циклических массивов, описанной в разделе 2.4.

2.21. Возможно хранение двух стеков в одном массиве, если один располагается в начале массива и растет к концу массива, а второй располагается в конце массива и растет к началу. Напишите процедуру РиЗЩл;, S) вставки элемента х в стек S, где S - один или другой стек из этих двух стеков. Включите все необходимые проверки в эту процедуру.





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 118 119 120 121 122 123

0.0038