Окулов.Программирование.в.алгоритмах. По вопросам приобретения обращаться
 Скачать 5.46 Mb.
|
|
0 0 1 1 1 1 1 0 0 1 1 1 1 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 ТГ 1 |7 1 | 7 8 9 10 15 16 17 18 Матрица будет разделена на квадраты, как показано на ри- сунке справа, где квадраты, выделенные серым, те, которые со- держат только черные точки. Преобразование выполняется следующим образом. Корень дерева представляет все изображение. Каждая вершина дерева описывает некий квадрат. Она может иметь 4 исходящих ребра к другим вершинам, представляющим квадраты, на которые делится исходный квадрат. Вершины без исходящих ребер со- ответствуют квадратам, состоящим из точек одного цвета. На- пример, приведенному выше изображению с его разбивкой на Одна из самых красивых задач, с которой пришлось работать автору. Избранные задачи по программированию 297 квадраты соответствует дерево, изображенное ниже. Серые вер- шины обозначают квадраты, содержащие 2 цвета, а белые и черные — квадраты, состоящие из точек одного цвета (такого же, как цвет квадрата). В дереве вершины пронумерованы в соответствии с нумера- цией квадратов на рисунке. Квадраты обходятся слева-направо и сверху-вниз, начиная с верхнего левого угла (верхний левый, верхний правый, нижний левый, нижний правый). Каждая черная вершина дерева кодируется следующим образом: подни- маемся от вершины по ребрам к корню, записывая при этом по- дряд цифры от 1 до 4 в соответствии с тем, где находится теку- щий квадрат по отношению к вышестоящему (верхний левый — 1, верхний правый — 2 , нижний левый — 3, нижний правый — 4 ). Получившееся число записано по основанию 5, запишем его по основанию 10. Например, вершина с номером 4 имеет путь Н-Л, В-П. Полу- чается число (по основанию 5) или (по основанию 10). Вершина с номером 12 имеет путь Н-Л, Н-П, или и со- ответственно. Вершина с номером 15 имеет путь В-Л, Н-Л, Н-П, или После этого дерево кодируется строкой чи- сел: 9 14 17 22 23 44 63 69 88 94 113. Требуется написать программу перевода изображения в строку чисел и обратного преобразования — строки чисел в изображение. Входные данные. Файл содержит описание одного или неско- льких изображений. Все изображения — это квадратные рисун- ки, сторона квадрата которых имеет значение длины, являюще- еся степенью двойки. Входной файл начинается с целого числа п, где \п\ — длина стороны квадрата (\п\ < 64). Если число п боль- ше 0, то затем следует \п\ строк по \п\ знаков в строке, заполнен- ных 0 и 1. При этом 1 соответствует черному цвету. Если п ме- ньше 0, то затем следует описание изображения в виде строки из десятичных чисел, оканчивающейся - 1 . Полностью черному квадрату соответствует кодировка из одного 0. Белый квадрат имеет пустую кодировку (ничего не вводится). Признаком конца входного файла является значение п, равное 0. Выходные данные. каждого изображения из входного файла выводится его номер. В том случае, когда изображение задается с помощью 0 и 1, в выходной файл записывается его представление в виде строки из десятичных Числа в строке сортируются в порядке возрастания. Для изображений, содержащих больше 12 черных областей, после каждых 12 чи- сел вывод начинается с новой строки. Количество черных 298 6. Избранные олимпиадиые задачи по программированию стей выводится после строки из десятичных чисел. В том слу- чае, когда изображение задается строкой из десятичных чисел, в выходной файл записывается его представление в виде квад- рата, в котором символ соответствует 0, а символ '*' — 1. Пример входного и выходного файлов приведен в таблице. Входной файл 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 -8 9 14 17 22 23 44 63 69 88 94 113-1 2 0 0 0 0 -4 0-1 Выходной файл Изображение 1 9 14 17 22 23 44 63 69 88 94 Общее число черных областей Изображение 2 * * * * * * * * * * * * * * * * * * * Изображение 3 Общее число черных областей 0 Изображение 4 * * * * * * * * * * * * * * Указание. Очередной раз используем технологию «сверху вниз» в наших рассуждениях. Основная программа не требует пояснений. Begin размерность изображения. *} While Do Begin If N>0 Then SolveA Else процедура преобразует изображение в виде матрицы в строку деся- тичных чисел, вторая процедура выполняет обратное пре- *} End; End. 6. Избранные задачи по программированию 299 Дальнейшее уточнение требует осознания того, каким обра- зом в нашей задаче описывается очередной квадрат. Итак, это координаты левого верхнего угла квадрата, длина его стороны и тот путь по изображению, который предшествовал попада- нию в этот квадрат. Формирование пути по изображению сле- дует из формулировки задачи — строка из цифр от 1 до 4. На- зовем функцию обработки квадрата RecA, ее заголовок — Function Way.String ):Boolean. Значение функции True говорит о том, что квадрат черный. Другим оче- видным соображением является введение массива для хране- ния результата — десятичных чисел, описывающих изображе- ние. Пусть это будет массив (Cp:Array[l..MaxCn] Of где — константа, равная 64*64), а счетчиком числа записей в Ср является значение переменной Cnt. Мы со- всем забыли сказать о том, что исходное изображение записано в массиве A (A:Array[l..MaxN,l..MaxN] Of Boolean, где MaxN — константа, равная 64). Значение элемента массива равное True, соответствует черной клетке с координата- ми а при False — белой. Итак, SolveA. Procedure SolveA; Var Begin описание изображения из входного формируем А. *} If RecA(l,l,N, ' ') Then Begin Cp[Cnt] :=0; End;{*Если все изображение состоит из одного черного' цвета, то записываем в первый элемент массива Ср ноль и заканчиваем обработку этого теста, во всех остальных случаях массив Ср сформирован рекурсивной функцией RecA. *} массив Ср.*} { результат в выходной файл OutPut. *} End; Функция RecA имеет вид. Function Var c:Boolean; Begin If d=l Then c:=A[i,j] до квадрата единичной длины, значение функции определяется цветом *} 300 6. Избранные задачи по программированию Else Begin к:= d Div 2; And RecA(i,j+k,k, And RecA(i+k,j,d, And функции на данном уровне рекурсии определяется значениями функции на квадратах меньшего размера. *} If с Then Dec (Cnt, 4) ; { *Если все составляющие квадраты черные, то и данный квадрат черный. *} End; If с Then Begin черный, преобразуем путь (строка, описывающая число в пятеричной системе счисления) в десятичное число и записываем *} строку символов, описывающую число в пятеричной системе счисления, в число в десятичной системе счисления>; End; End; На этой ветке логики осталось уточнить функцию преобра- зования пути по квадрату в десятичное число. Процедуры Sort и PrintA (мы вызываем их из процедуры SolveA) «прозрачны» для человека, прочитавшего книгу до этого места. Описание ло- гики получения матрицы, описывающей изображение, из стро- ки десятичных чисел чуть сложнее. Вся суть в аналогичной процедуре RecB. Квадрат описывается координатами верхнего левого угла и длиной стороны, безусловно, что они являются параметрами процедуры. Кроме того, у нас есть путь, представ- ленный пятеричным числом. Вопрос. Как из очередной цифры этого числа сделать переадресацию по квадрату, т. е. перейти к одному из четырех квадратов меньшего размера? Ответив на него, можно про- граммировать как процедуру RecB, так и всю логику SolveB. Поясним ситуа- цию рисунком. Пусть координаты лево- го верхнего угла квадрата задаются значениями переменных i и j, а длина стороны нового квадрата — значение Цифры в кружках — это значения пе- ременной k, получаемой из очередной © i+rj © © i+rj+r © 6. Избранные задачи по программированию 301 цифры пятеричного числа с помощью операции Mod 5—1. Итак, в зависимости от значения переменной k с помощью операций i+r*(k Div 2) и Mod 2) мы переходим к левым верхним углам любого из четырех квадратов меньшего разме- ра. Для убедительности проиллюстрируем этот фрагмент суждений примером. Номер вызова процедуры 1 2 3 i 1 1 3 j 1 5 5 d 8 4 2 Way 3 0 к 1 2 - 4 2 - Дальнейшую работу по уточнению логики оставим заинтере- сованному читателю. 21. На числовой прямой отметили несколько отрезков, каж- дый из которых обозначили одной из букв латинского алфави- та (различные отрезки — различными буквами). Используя эти значения как операнды, а также операции объединения (+), пе- ресечения разности (-) множеств и круглые скобки, было составлено теоретико-множественное выражение. Множество точек, являющееся результатом вычисления со- ставленного выражения, разбивается на некоторое количество связных частей, каждая из которых является либо отдельной точкой, либо промежутком, т. е. отрезком, интервалом или по- луинтервалом. Если потребовать, чтобы число частей в разбие- нии было минимальным (никакие две части нельзя объединить в большую), то такое представление окажется единственным. Написать программу, представляющую результирующее множество точек в указанном виде. Входные данные. В первой строке входного файла (input.txt) содержится натуральное число N — количество отрезков на прямой. В каждой из следующих N строк находится описание одного из отрезков: буква, приписанная этому отрезку, и коор- динаты его левого и правого концов. Все координаты — целые числа из диапазона [0, 10 9 ], строчные и прописные буквы счи- таются различными. В следующей строке содержится выраже- ние длиной не более 250 символов. Выражение не содержит пробелов и лишних скобок. Выходные данные. В выходной файл записыва- ется разбиение результирующего множества на связные части. Порядок вывода частей должен соответствовать порядку их следования на числовой прямой, если передвигаться по ней слева направо. Точка представляется указанием ее ной координаты в фигурных скобках, числовые промежутки 302 Избранные задачи по программированию представляются согласно стандартным пра- вилам: квадратная скобка означает, что соот- ветствующая концевая точка принадлежит промежутку; круглая — не принадлежит. А 0 30 а 10 15 Пример. input.txt 3 b 15 20 (A-(a+b))+(a*b) output.txt [0;10) {15} (20;30] Целочисленные координаты левого и правого концов промежутка должны быть разделены точкой с запятой, каждую из частей разбие- ния следует записать в отдельную строку вы- ходного файла. Указание. Заданные отрезки определяют множество точек на прямой, назовем их гра- ничными. Так, для примера из условия задачи это [0, 10, 15, 15, 20, 30] (после сортировки). В результате выполнения теорети- ко-множественного выражения интервал между двумя соседними граничными точками, например (0, 10), или принадлежит, или не принадлежит результирующему множеству (не может часть интервала (0, 10) принадлежать результату, а другая нет). Для проверки принадлежности интервала достаточно проверить, а принадлежит ли его средняя точка результату. Множество гра- ничных точек преобразуется и имеет вид: [0, 5, 10, 12.5, 15, 15, 15, 17.5, 20, 25, 30]. Количество точек для N интервалов' — Что дальше? Берем каждую точку и проверяем, анализи- руя выражение. Операция объединения (А+В) заменяется на (А Or В), — на (A And Not В) и (А*В) — на (A And В). Запись выражения в форме Бэкуса-Наура имеет вид: <выражение>=<слагаемое>{<операция><слагаемое>} <слагаемое>=(<выражение>)|<идентификатор> .Z Определим «узловые» моменты решения задачи. Из струк- туры данных (они даны не все) приведем следующие. Const количество 26 символов алфавита.*} Var Of множество граничных точек. *} *} переменная, определяет номер символа в выражении при его *} Мы должны просматривать все множество граничных точек, их N*4— 1, а в массиве ОпХ только часть из них, средние точки интервалов не присутствуют. Не будем дописывать их в ОпХ, а попытаемся просто вычислять по номеру с помощью следую- щей функции. 6. Избранные олимпиадные задачи по программированию 303 Function Begin If к Mod 2=0 Then Get: Div [k Div 2+1])/2 Else Div ; End; к 1 2 3 4 5 6 7 8 9 10 11 0 10 (10*1.0+15)/2=12.5 15 (15*1.0+15)/2=15 15 20 (20*1.0+30)/2=25 30 Atln(Get(k)) True True False False True True True False False True True Результат вызова функции Get на множестве граничных то- чек из нашего примера представлен во 2-м столбце таблицы. Функция дает истину или ложь в зависимости от того, принадлежит или нет точка прямой результирующему множе- ству. Ее вид: Function -.Boolean; Begin обрабатываемого символа в *} очередной раз тяжесть на следующую функцию будем пока ее рассматривать) - вычисления это позволит нам до конца выяснить отношения с процедурой *} . End; Итак, основная логика обработки заключена в процедуре Procedure Var i Begin i : =1 ; 304 Избранные задачи по программированию While (i<=N*4-l) And (Not (Get (i))) Do Inc(i); граничные точки до'тех пор, пока не дойдем до точки, принадлежащей результирующему множеству. *} While i<=N*4-l Do Begin a:=i; (*Левая граница интервала из результирующего *} While (i<=N*4-l) And (Get (i)) {*Пропускаем точки, принадлежащие результирующему множеству. *} граница *} SayRes Процедура не *} Inc(i) ; While And (Not (Get (i))) ( *Снова пропускаем граничные точки до тех пока не дойдем до точки, принадлежащей результирующему *} End; End; Закончим рассмотрение. Осталось уточнить процедуру Say- Res — вывода найденного интервала и вычисления выражения при конкретном значении х, а также основную логику и ввод данных. 22. Дана последовательность, состоящая из нулей и единиц. Требуется найти N битовых подпоследовательностей длиной от до включительно, которые встреча- ются в исходной последовательности наиболее часто. Входные данные. Файл input.txt содержит данные в следую- щем формате. В первой строке — число А, во второй — В, в тре- тьей — число iV, в четвертой — последовательность символов 0 и 1, заканчивающуюся символом 2. Примечание Размер входного файла не превышает 2-х мегабайт. Выходные данные. В файл output.txt записываются не более строк, каждая из которых содержит одну из наибольших частот вхождения и соответствующие ей подпоследовательно- сти. Строки располагаются в порядке убывания частот вхожде- ния и имеют следующий вид: частота подпоследовательности подпоследовательность ... подпоследовательность, где частота — это количество вхождений указанных далее подпос- ледовательностей. Подпоследовательности в каждой строке дол- 6. Избранные задачи по программированию 305 жны располагаться в порядке убыва- ния длины. При равной длине — в порядке убывания их числового зна- чения. Если в последовательности встречается менее N различных час- тот, выходной файл будет содержать меньше N строк. Указание. Входной файл очень бо- льшой. Следует провести обработку за один его просмотр. Количество раз- личных подпоследовательностей не так велико, как кажется. Их 8191 и это путь к реальному решению задачи. Введем массив (D) для хранения час- тоты встречаемости каждой подпосле- довательности. Обрабатывая разряд за разрядом исходной последовательно- сти, будем добавлять по единице к со- ответствующему элементу D. Ниже в таблице приводятся результаты обработки первых 10 разрядов из примера, приведенного в условии задачи (единственное отличие — А считается равным 1). В первом столбце указана длина подпосле- довательности, во втором — номер элемента массива D, в тре- тьем — соответствующая подпоследовательность, далее номер об- рабатываемого разряда и в последнем столбце — результат обработки. Пример. input.txt 2 4 10 010100100100010001111 0110000101 001100111100001001001 1110010000 0002 output.txt 23 00 15 10 01 12 100 11 001 000 11 10 010 8 0100 7 1001 0010 6 0000 111 5 1000 110 011 4 1100 ООН 0001 L 1 2 3 N 0 1 2 3 4 5 6 7 8 9 10 11 12 13 0 1 00 01 10 11 000 001 010 011 100 101 110 111 1 1 2 1 1 3 2 1 1 4 2 2 1 5 3 2 2 6 4 1 1 7 3 3 1 8 5 3 3 9 6 2 2 10 4 4 2 D 39 26 23 15 15 11 11 11 10 5 12 3 5 6 |