А. шень Издание шестое, дополненное Москва
 Скачать 1.62 Mb.
|
|
хранить подмножества множества {1 . . . 𝑛}? Операции Число действий Сделать пустым 𝐶𝑛 Проверить принадлежность 𝐶 Добавить 𝐶 Удалить 𝐶 Минимальный элемент 𝐶𝑛 Проверка пустоты 𝐶𝑛 Решение. Храним множество как array [1..n] of Boolean. 112 6. Типы данных 6.3.2. То же, но проверка пустоты должна выполняться за время 𝐶. Решение. Храним дополнительно количество элементов. 6.3.3. То же при следующих ограничениях на число действий: Операции Число действий Сделать пустым 𝐶𝑛 Проверить принадлежность 𝐶 Добавить 𝐶 Удалить 𝐶𝑛 Минимальный элемент 𝐶 Проверка пустоты 𝐶 Решение. Дополнительно храним минимальный элемент множе- ства. 6.3.4. То же при следующих ограничениях на число действий: Операции Число действий Сделать пустым 𝐶𝑛 Проверить принадлежность 𝐶 Добавить 𝐶𝑛 Удалить 𝐶 Минимальный элемент 𝐶 Проверка пустоты 𝐶 Решение. Храним минимальный, а для каждого | следующий и пре- дыдущий по величине. Множества целых чисел В следующих задачах величина элементов множества не ограничена, но их количество не превосходит 𝑛. 6.3.5. Память 𝐶𝑛. Операции Число действий Сделать пустым 𝐶 Число элементов 𝐶 Проверить принадлежность 𝐶𝑛 Добавить новый (заведомо отсутствующий) 𝐶 Удалить 𝐶𝑛 Минимальный элемент 𝐶𝑛 Взять какой-то элемент 𝐶 6.3. Множества 113 Решение. Множество представляем с помощью переменных a:array [1..n] of integer, k: 0..n; множество содержит k элементов a[1], . . . a[k]; все они различны. По существу мы храним элементы множества в стеке (без повторений). С тем же успехом можно было бы воспользоваться очередью вместо стека. 6.3.6. Память 𝐶𝑛. Операции Число действий Сделать пустым 𝐶 Проверить пустоту 𝐶 Проверить принадлежность 𝐶 log 𝑛 Добавить 𝐶𝑛 Удалить 𝐶𝑛 Минимальный элемент 𝐶 Решение. См. решение предыдущей задачи с дополнительным усло- вием a[1] < . . . < a[k]. При проверке принадлежности используем дво- ичный поиск. В следующей задаче полезно комбинировать разные способы. 6.3.7. Используя описанные способы представления множеств, най- дите все вершины ориентированного графа, доступные из данной по рёбрам. (Вершины считаем числами 1 . . . n.) Время не больше 𝐶 · (общее число рёбер, выходящих из доступных вершин). Решение. (Другое решение см. в главе о рекурсии, задача 7.4.6 ) Пусть num[i] | число рёбер, выходящих из i, а out[i][1], . . . . . . , out[i][num[i]] | вершины, куда ведут рёбра из вершины i. procedure Доступные (i: integer); {напечатать все вершины, доступные из i, включая i} var X: подмножество 1..n; P: подмножество 1..n; q, v, w: 1..n; k: integer; begin ...сделать X, P пустыми; writeln (i); ...добавить i к X, P; 114 6. Типы данных {(1) P = множество напечатанных вершин; P содержит i; (2) напечатаны только доступные из i вершины; (3) X - подмножество P; (4) все напечатанные вершины, из которых выходит ребро в ненапечатанную вершину, принадлежат X} while X непусто do begin ...взять какой-нибудь элемент X в v; for k := 1 to num [v] do begin w := out [v][k]; if w не принадлежит P then begin writeln (w); добавить w в P; добавить w в X; end; end; end; end; Свойство (1) не нарушается, так как печать происходит одновре- менно с добавлением в P. Свойство (2): раз v было в X, то v доступно, поэтому w доступно. Свойство (3) очевидно. Свойство (4): мы удали- ли из X элемент v, но все вершины, куда из v идут рёбра, перед этим напечатаны. 6.3.8. Покажите, что можно использовать и другой инвариант: P | напечатанные вершины; X ⊂ P; осталось напечатать вершины, доступ- ные из X по ненапечатанным вершинам. Оценка времени работы. Заметим, что изъятые из X элементы боль- ше туда не добавляются, так как они в момент изъятия (и, следователь- но, всегда позже) принадлежат P, а добавляются только элементы не из P. Поэтому тело цикла while для каждой доступной вершины вы- полняется не более, чем по разу, при этом тело цикла for выполняется столько раз, сколько из вершины выходит рёбер. Для X надо использовать представление со стеком или очередью (см. выше), для P | булевский массив. 6.3.9. Решите предыдущую задачу, если требуется, чтобы доступ- ные вершины печатались в таком порядке: сначала заданная вершина, потом её соседи, потом соседи соседей (ещё не напечатанные) и т. д. [Указание. Так получится, если использовать очередь для хранения X в приведённом выше решении: докажите индукцией по 𝑘, что существу- ет момент, в который напечатаны все вершины на расстоянии не боль- ше 𝑘, а в очереди находятся все вершины, удалённые ровно на 𝑘.] 6.4. Разные задачи 115 Более сложные способы представления множеств будут разобраны в главах 13 (хеширование) и 14 (деревья). 6.4. Разные задачи 6.4.1. Реализуйте структуру данных, которая имеет все те же опе- рации, что массив длины n, а именно ∙ начать работу; ∙ положить в i-ю ячейку число x; ∙ узнать, что лежит в i-й ячейке; а также операцию ∙ указать номер минимального элемента (точнее, одного из минимальных элементов). Количество действий для всех операций должно быть не более 𝐶 log n, не считая операции «начать работу» (которая требует не более 𝐶n действий). Решение. Используется приём, изложенный в разделе о сортировке деревом. Именно, надстроим над элементами массива как над листьями двоичное дерево, в каждой вершине которого храним минимум элемен- тов соответствующего поддерева. Корректировка этой информации, а также прослеживание пути из корня к минимальному элементу тре- буют логарифмического числа действий. 6.4.2. Приоритетная очередь | это очередь, в которой важно не то, кто встал последним (порядок помещения в неё не играет роли), а кто главнее. Более точно, при помещении в очередь указывается приоритет помещаемого объекта (будем считать приоритеты целыми числами), а при взятии из очереди выбирается элемент с наибольшим приорите- том (или один из таких элементов). Реализуйте приоритетную очередь так, чтобы помещение и взятие элемента требовали логарифмического числа действий (от размера очереди). Решение. Следуя алгоритму сортировки деревом (в его окончатель- ном варианте), будем размещать элементы очереди в массиве x[1..k], поддерживая такое свойство: x[i] старше (имеет больший приоритет) своих сыновей x[2i] и x[2i+1], если таковые существуют | и, сле- довательно, всякий элемент старше своих потомков. (Сведения о при- оритетах также хранятся в массиве, так что мы имеем дело с масси- вом пар ⟨элемент, приоритет⟩.) Удаление элемента с сохранением этого 116 6. Типы данных свойства описано в алгоритме сортировки. Надо ещё уметь восстана- вливать свойство после добавления элемента в конец. Это делается так: t:= номер добавленного элемента {инвариант: в дереве любой предок приоритетнее потомка, если этот потомок - не t} while t - не корень и t старше своего отца do begin поменять t с его отцом end; Если очередь образуют граждане, стоящие в вершинах дерева, т. е. за каждым стоит двое, а перед каждым (кроме первого) | один, то смысл этого алгоритма ясен: встав в конец, приоритетный гражданин начинает пробираться к началу, вытесняя впереди стоящих | пока не встретит более приоритетного. Замечание. Приоритетную очередь естественно использовать при моделировании протекающих во времени процессов. При этом элемен- ты очереди | это ожидаемые события, а их приоритет определяется временем, когда они произойдут. 7. РЕКУРСИЯ 7.1. Примеры рекурсивных программ При анализе рекурсивной программы возникает, как обычно, два вопроса: (а) почему программа заканчивает работу? (б) почему она работает правильно, если заканчивает работу? Для (б) достаточно проверить, что (содержащая рекурсивный вы- зов) программа работает правильно, предположив, что вызываемая ею одноимённая программа работает правильно. В самом деле, в этом слу- чае в цепочке рекурсивно вызываемых программ все программы рабо- тают правильно (убеждаемся в этом, идя от конца цепочки к началу). Чтобы доказать (а), обычно проверяют, что с каждым рекурсивным вызовом значение какого-то параметра уменьшается, и это не может продолжаться бесконечно. 7.1.1. Напишите рекурсивную процедуру вычисления факториала целого положительного числа 𝑛 (т. е. произведения 1 · 2 · · · 𝑛, обознача- емого 𝑛!). Решение. Используем равенства 1! = 1, 𝑛! = (𝑛 − 1)! · 𝑛. procedure factorial (n: integer; var fact: integer); {положить fact равным факториалу числа n} begin if n=1 then begin fact:=1; end else begin {n>1} factorial (n-1, fact); {fact = (n-1)!} fact:= fact*n; end; end; 118 7. Рекурсия С использованием процедур-функций можно написать так: function factorial (n: integer): integer; begin if n=1 then begin factorial:=1; end else begin {n>1} factorial:= factorial (n-1)*n; end; end; Обратите внимание на некоторую двойственность использования име- ни factorial внутри описания функции: оно обозначает как перемен- ную, так и вызываемую рекурсивно функцию. К счастью, в нашем слу- чае они различаются по скобкам после имени, но если бы функция была без параметров, то дело было бы плохо. (Стандартная, но трудно нахо- димая ошибка возникает, если автор программы на паскале полагает, что он использует значение переменной, а компилятор в этом месте видит рекурсивный вызов.) 7.1.2. Обычно факториал определяют и для нуля, считая, что 0! = 1. Измените программы соответственно. 7.1.3. Напишите рекурсивную программу возведения в целую нео- трицательную степень. 7.1.4. То же, если требуется, чтобы глубина рекурсии не превосхо- дила 𝐶 log 𝑛, где 𝑛 | показатель степени. Решение. function power (a,n: integer): integer; begin if n = 0 then begin power:= 1; end else if n mod 2 = 0 then begin power:= power(a*a, n div 2); end else begin power:= power(a, n-1)*a; end; end; 7.1. Примеры рекурсивных программ 119 7.1.5. Что будет, если изменить программу, приведённую в решении предыдущей задачи, заменив строку power:= power(a*a, n div 2) на power:= power(a, n div 2)* power(a, n div 2)? Решение. Программа останется правильной. Однако она станет ра- ботать медленнее. Дело в том, что теперь вызов может породить два вызова (хотя и одинаковых) вместо одного | и число вызовов быстро растёт с глубиной рекурсии. Программа по-прежнему имеет логариф- мическую глубину рекурсии, но число шагов работы становится линей- ным вместо логарифмического. Этот недостаток можно устранить, написав t:= power(a, n div 2); power:= t*t; или воспользовавшись функцией возведения в квадрат (sqr). 7.1.6. Используя команды write(x) лишь при x = 0 . . . 9, напишите рекурсивную программу печати десятичной записи целого положитель- ного числа 𝑛. Решение. Здесь использование рекурсии облегчает жизнь (пробле- ма была в том, что цифры легче получать с конца, а печатать надо с начала). procedure print (n:integer); {n>0} begin if n<10 then begin write (n); end else begin print (n div 10); write (n mod 10); end; end; 7.1.7. Игра «Ханойские башни» состоит в следующем. Есть три стержня. На первый из них надета пирамидка из 𝑁 колец (большие кольца снизу, меньшие сверху). Требуется переместить кольца на дру- гой стержень. Разрешается перекладывать кольца со стержня на стер- жень, но класть большее кольцо поверх меньшего нельзя. Составьте программу, указывающую требуемые действия. 120 7. Рекурсия Решение. Напишем рекурсивную процедуру перемещения i верхних колец с m-го стержня на n-й (остальные кольца предполагаются боль- шими по размеру и лежат на стержнях без движения). procedure move(i,m,n: integer); var s: integer; begin if i = 1 then begin writeln (’сделать ход ’, m, ’->’, n); end else begin s:=6-m-n; {s - третий стержень: сумма номеров равна 6} move (i-1, m, s); writeln (’сделать ход ’, m, ’->’, n); move (i-1, s, n); end; end; (Сначала переносится пирамидка из i-1 колец на третью палочку. По- сле этого i-е кольцо освобождается, и его можно перенести куда следу- ет. Остаётся положить на него пирамидку.) 7.1.8. Напишите рекурсивную программу суммирования массива a: array [1..n] of integer. [Указание. Рекурсивно определяемая функция должна иметь допол- нительный параметр | число складываемых элементов.] 7.2. Рекурсивная обработка деревьев Двоичным деревом называется картинка вроде такой: k k k k k k A A A A A A Нижняя вершина называется корнем. Из каждой вершины могут ид- ти две линии: влево вверх и вправо вверх. Вершины, куда они ведут, 7.2. Рекурсивная обработка деревьев 121 называются левым и правым сыновьями исходной вершины. Вершина может иметь двух сыновей, а может иметь только одного сына (левого или правого). Она может и вовсе не иметь сыновей, и в этом случае называется листом. Пусть 𝑥 | какая-то вершина двоичного дерева. Она сама вместе с сыновьями, внуками, правнуками и т. д. образует поддерево с корнем в 𝑥 | поддерево потомков 𝑥. В следующих задачах мы предполагаем, что вершины дерева прону- мерованы целыми положительными числами, причём номера всех вер- шин различны. Мы считаем, что номер корня хранится в переменной root. Мы считаем, что имеются два массива l,r: array [1..N] of integer и левый и правый сын вершины с номером i имеют соответственно номера l[i] и r[i]. Если вершина с номером i не имеет левого (или правого) сына, то l[i] (соответственно r[i]) равно 0. (По традиции при записи программ мы используем вместо нуля константу nil, рав- ную нулю.) Здесь N | достаточно большое натуральное число (номера всех вер- шин не превосходят N). Отметим, что номер вершины никак не связан с её положением в дереве и что не все числа от 1 до N обязаны быть номерами вершин (и, следовательно, часть данных в массивах l и r | это мусор). 7.2.1. Пусть N = 7, root = 3, массивы l и r таковы: i 1 2 3 4 5 6 7 l[i] 0 0 1 0 6 0 7 r[i] 0 0 5 3 2 0 7 Нарисуйте соответствующее дерево. Ответ. 3 1 5 6 2 A A A A A A 122 7. Рекурсия 7.2.2. Напишите программу подсчёта числа вершин в дереве. Решение. Рассмотрим функцию n(x), равную числу вершин в подде- реве с корнем в вершине номер x. Считаем, что n(nil) = 0 (полагая со- ответствующее поддерево пустым), и не заботимся о значениях nil(s) для чисел s, не являющихся номерами вершин. Рекурсивная программа для n такова: function n(x:integer):integer; begin if x = nil then begin n:= 0; end else begin n:= n(l[x]) + n(r[x]) + 1; end; end; (Число вершин в поддереве над вершиной x равно сумме чисел вер- шин над её сыновьями плюс она сама.) Глубина рекурсии конечна, так как с каждым шагом высота соответствующего поддерева уменьша- ется. 7.2.3. Напишите программу подсчёта числа листьев в дереве. Ответ. function n (x:integer):integer; begin if x = nil then begin n:= 0; end else if (l[x]=nil) and (r[x]=nil) then begin {лист} n:= 1; end else begin n:= n(l[x]) + n(r[x]); end; end; 7.2.4. Напишите программу подсчёта высоты дерева (корень имеет высоту 0, его сыновья | высоту 1, внуки | 2 и т. п.; высота дерева | это максимум высот его вершин). [Указание. Рекурсивно определяется функция f(x) = высота под- дерева с корнем в x.] 7.2.5. Напишите программу, которая по заданному n считает число всех вершин высоты n (в заданном дереве). 7.3. Порождение комбинаторных объектов, перебор 123 Вместо подсчёта количества вершин того или иного рода можно просить напечатать список этих вершин (в том или ином порядке). 7.2.6. Напишите программу, которая печатает (по одному разу) все вершины дерева. Решение. Процедура print subtree(x) печатает все вершины под- дерева с корнем в x по одному разу; главная программа содержит вызов print subtree(root). procedure print_subtree (x:integer); begin if x = nil then begin {ничего не делать} end else begin writeln (x); print_subtree (l[x]); print_subtree (r[x]); end; end; Данная программа печатает сначала корень поддерева, затем подде- рево над левым сыном, а затем над правым. Три строки в else-части могут быть переставлены 6 способами, и каждый из этих способов даёт свой порядок печати вершин. 7.3. Порождение комбинаторных объектов, перебор Рекурсивные программы являются удобным способом порождения комбинаторных объектов заданного вида. Мы решим заново несколько задач соответствующей главы. 7.3.1. Напишите программу, которая печатает по одному разу все последовательности длины n, составленные из чисел 1 . . . k (их количе- ство равно kn). Решение. Программа будет оперировать с массивом a[1] . . . a[n] и числом t. Рекурсивная процедура generate печатает все последо- вательности, начинающиеся на a[1] . . . a[t]; после её окончания t и a[1] . . . a[t] имеют то же значение, что и в начале: procedure generate; var i,j : integer; 124 7. Рекурсия begin if t = n then begin for i:=1 to n do begin write(a[i]); end; writeln; end else begin {t < n} for j:=1 to k do begin t:=t+1; a[t]:=j; generate; t:=t-1; end; end; end; Основная программа теперь состоит из двух операторов: t:=0; generate; Замечание. Команды t:=t+1 и t:=t-1 для экономии можно вынести из цикла for. 7.3.2. Напишите программу, которая печатала бы все перестановки чисел 1 . . . n по одному разу. Решение. Программа оперирует с массивом a[1] . . . a[n], в котором хранится перестановка чисел 1 . . . n. Рекурсивная процедура generate в такой ситуации печатает все перестановки, которые на первых t по- зициях совпадают с перестановкой a; по выходе из неё переменные t и a имеют те же значения, что и до входа. Основная программа такова: for i:=1 to n do begin a[i]:=i; end; t:=0; generate; Вот описание процедуры: procedure generate; var i,j : integer; begin if t = n then begin for i:=1 to n do begin write(a[i]); end; writeln; 7.3. Порождение комбинаторных объектов, перебор 125 end else begin {t < n} for j:=t+1 to n do begin поменять местами a[t+1] и a[j] t:=t+1; generate; t:=t-1; поменять местами a[t+1] и a[j] end; end; end; 7.3.3. Напечатайте все последовательности из n нулей и единиц, со- держащие ровно k единиц (по одному разу каждую). 7.3.4. Напечатайте все возрастающие последовательности длины k, элементами которых являются натуральные числа от 1 до n. (Предпо- лагается, что k 6 n, иначе таких последовательностей не существует.) Решение. Программа оперирует с массивом a[1] . . . a[k] и целой пе- ременной t. Предполагая, что a[1] . . . a[t] | возрастающая последо- вательность натуральных чисел из отрезка 1 . . . n, рекурсивно опреде- лённая процедура generate печатает все её возрастающие продолжения длины k. (При этом t и a[1] . . . a[t] в конце такие же, как в начале.) procedure generate; var i: integer; begin if t = k then begin печатать a[1]..a[k] end else begin t:=t+1; for i:=a[t-1]+1 to t-k+n do begin a[t]:=i; generate; end; t:=t-1; end; end; Замечание. Цикл for мог бы иметь верхней границей n (вместо t − k + n). Наш вариант экономит часть работы, учитывая тот факт, что предпоследний ((k-1)-й) член не может превосходить n-1, (k-2)-й член не может превосходить n-2 и т. п. 126 7. Рекурсия Основная программа теперь выглядит так: t:=1; for j:=1 to 1-k+n do begin a[1]:=j; generate; end; Можно было бы добавить к массиву a слева фиктивный элемент a[0] = = 0, положить t = 0 и ограничиться единственным вызовом процедуры generate. 7.3.5. Перечислите все представления положительного целого чи- сла n в виде суммы последовательности невозрастающих целых поло- жительных слагаемых. Решение. Программа оперирует с массивом a[1..n] (максимальное число слагаемых равно n) и с целой переменной t. Предполагая, что a[1] . . . a[t] | невозрастающая последовательность целых чисел, сум- ма которых не превосходит n, процедура generate печатает все пред- ставления требуемого вида, продолжающие эту последовательность. Для экономии вычислений сумма a[1] + . . . + a[t] хранится в специ- альной переменной s. procedure generate; var i: integer; begin if s = n then begin печатать последовательность a[1]..a[t] end else begin for i:=1 to min(a[t], n-s) do begin t:=t+1; a[t]:=i; s:=s+i; generate; s:=s-i; t:=t-1; end; end; end; Основная программа при этом может быть такой: t:=1; for j:=1 to n do begin a[1]:=j 7.4. Другие применения рекурсии 127 s:=j; generate; end; Замечание. Можно немного сэкономить, вынеся операции увеличе- ния и уменьшения t из цикла, а также не возвращая s каждый раз к исходному значению (увеличивая его на 1 и возвращая к исходному значению в конце). Кроме того, добавив фиктивный элемент a[0] = n, можно упростить основную программу: t:=0; s:=0; a[0]:=n; generate; 7.3.6. Напишите рекурсивную программу обхода дерева (используя те же команды и проверки, что и в главе 3 (Обход дерева). Решение. Процедура обработать над обрабатывает все листья над текущей вершиной и заканчивает работу в той же вершине, что и на- чала. Вот её рекурсивное описание: procedure обработать_над; begin if есть_сверху then begin вверх_налево; обработать_над; while есть_справа do begin вправо; обработать_над; end; вниз; end else begin обработать; end; end; 7.4. Другие применения рекурсии Топологическая сортировка. Представим себе 𝑛 чиновников, каж- дый из которых выдаёт справки определённого вида. Мы хотим полу- чить все эти справки, соблюдая установленные ограничения: у каждого чиновника есть список справок, которые нужно собрать перед обраще- нием к нему. Дело безнадёжно, если схема зависимостей имеет цикл (справку 𝐴 нельзя получить без 𝐵, 𝐵 без 𝐶,. . . , 𝑌 без 𝑍 и 𝑍 без 𝐴). 128 7. Рекурсия Предполагая, что такого цикла нет, требуется составить план, указы- вающий один из возможных порядков получения справок. Изображая чиновников точками, а зависимости | стрелками, при- ходим к такой формулировке. Имеется 𝑛 точек, пронумерованных от 1 до 𝑛. Из каждой точки ведёт несколько (возможно, 0) стрелок в другие точки. (Такая картинка называется ориентированным графом.) Циклов нет. Требуется расположить вершины графа (точки) в таком порядке, чтобы конец любой стрелки предшествовал её началу. Эта задача на- зывается топологической сортировкой. 7.4.1. Докажите, что это всегда возможно. Решение. Из условия отсутствия циклов вытекает, что есть верши- на, из которой вообще не выходит стрелок (иначе можно двигаться по стрелкам, пока не зациклимся). Её будем считать первой. Выкидывая эту вершину и все соседние стрелки, мы сводим задачу к графу с мень- шим числом вершин и продолжаем рассуждение по индукции. 7.4.2. Предположим, что ориентированный граф без циклов хранит- ся в такой форме: для каждого i от 1 до n в num[i] хранится число вы- ходящих из i стрелок, в adr[i][1], . . . , adr[i][num[i]] | номера вер- шин, куда эти стрелки ведут. Составьте (рекурсивный) алгоритм, кото- рый производит топологическую сортировку не более чем за 𝐶 · (n + m) действий, где m | число рёбер графа (стрелок). Замечание. Непосредственная реализация приведённого выше дока- зательства существования не даёт требуемой оценки; её приходится немного подправить. Решение. Наша программа будет печатать номера вершин. В мас- сиве printed: array[1..n] of boolean мы будем хранить сведения о том, какие вершины напечатаны (и кор- ректировать их одновременно с печатью вершины). Будем говорить, что напечатанная последовательность вершин корректна, если ника- кая вершина не напечатана дважды и для любого номера i, входящего в эту последовательность, все вершины, в которые ведут стрелки из i, напечатаны, и притом до i. procedure add (i: 1..n); {дано: напечатанное корректно;} {надо: напечатанное корректно и включает вершину i} 7.4. Другие применения рекурсии 129 begin if printed [i] then begin {вершина i уже напечатана} {ничего делать не надо} end else begin {напечатанное корректно} for j:=1 to num[i] do begin add(adr[i][j]); end; {напечатанное корректно, все вершины, в которые из i ведут стрелки, уже напечатаны - так что можно печатать i, не нарушая корректности} if not printed[i] then begin writeln(i); printed [i]:= TRUE; end; end; end; Основная программа: for i:=1 to n do begin printed[i]:= FALSE; end; for i:=1 to n do begin add(i) end; К оценке времени работы мы вскоре вернёмся. 7.4.3. В приведённой программе можно выбросить проверку, заме- нив if not printed[i] then begin writeln(i); printed [i]:= TRUE; end; на writeln(i); printed [i]:= TRUE; |