Главная Промышленная автоматика. 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.0019 |