Окулов.Программирование.в.алгоритмах. По вопросам приобретения обращаться
 Скачать 5.46 Mb.
|
|
Один из вариантов решения. Procedure {*k- номер элемента массива A; Res - множество партий, которые представлены в текущем решении; Rt - множество партий, которые следует решением; - минимальное количество членов в парламенте; - число членов парламента в текущем Rbest - минимальный Rwork - текущий первый вызов - Solved, [], [1..N]) .*} Var i:Nint; Begin блок общих отсечений If Rt=[] Then Begin If Then Begin End; End Else Begin i:=k; While i<=N Do Begin 1 блок отсечений i жителя, информация которому записана на месте i в массиве А, в *} Solve из *} (i) ; End; End; End; В качестве примера действий в блоке общих отсечений можно взять следующую логику. Подсчитать для каждого значения i множество партий, представляемых жителями, номера ко- торых записаны в элементах массива с i t (массив Of Sset). Тогда, если Res — текущее решение, a Rt — множество партий, требующих представления, то при Res+C[i] не может быть получено и эту ветку перебора следует «отсечь». 116 3. Перебор и методы его сокращения Пример отсечений i — если при включении элемента с номером i в решение значение величины не изменяется, то это включение жителя, по которому записана на месте i в массиве А, бессмысленно. 2. Какое наименьшее число ферзей можно расставить на до- ске так, чтобы они держали под боем все ее свободные поля? Модификация задачи. Найти расстановку ферзей, которая од- новременно решает задачу для досок 9*9, 10*10 и 11*11. Указание. Задачу можно решать как обычным перебором, так и, представив доску как граф, путем поиска минимального доминирующего множества вершин. 3. Расставить на доске N ферзей так, чтобы наи- большее число ее полей оказалось вне боя ферзей. 4. Расставить на доске как можно больше ферзей так, чтобы при снятии любого из них появлялось ровно одно неатакован- ное поле. 5. Задача о коне Аттилы («Трава не растет там, где ступил мой конь!»). На шахматной доске стоят белый конь и черный король. Некоторые поля доски считаются «горящими». Конь должен дойти до неприятельского короля, повергнуть его и вер- нуться на исходное место. При этом ему запрещено становиться как на горящие поля, так и на поля, которые уже пройдены. 6. Магараджа — это фигура, которая объединяет в себе ходы коня и ферзя. Для доски 10*10 найти способ расстановки 10 мирных (не бьющих друг друга) магараджей. 7. Пронумеровать позиции в матрице (таблице) размером 5*5 следующим образом. Если номер i соответствует позиции с координатами вычисляемыми по одному из следующих правил: (z,w)=(x±3,y); Требуется: • написать программу, которая последовательно нумерует позиции матрицы 5*5 при заданных координатах пози- ции, в которой поставлен номер 1 (результаты должны быть представлены в виде заполненной матрицы); • вычислить число всех возможных расстановок номеров для всех начальных позиций, расположенных в правом верхнем треугольнике матрицы, включая ее главную диа- гональ.* Третья международная олимпиада по информатике, 1991 год. 3. Перебор и методы его сокращения 117 Написать программу, которая определяет: • количество комнат в замке; • площадь наибольшей комнаты; • какую стену в замке следует удалить, чтобы получить комнату наибольшей площади. Замок условно разделен на M*N клеток iV>50). Каж- дая такая клетка может иметь от 0 до 4 стен. План замка содержится во входном файле в виде последова- тельности чисел, по одному числу, характеризующему каждую клетку. В начале файла расположено число клеток в направлении с севера на юг и число клеток в направлении с запада на восток. В последующих строках каждая клетка описывается числом р Это число являет- ся суммой следующих чисел: 1 (если клетка имеет западную стену), 2 (се- верную), 4 (восточную)-, 8 (южную). Внутренняя стена считает- ся принадлежащей обеим клеткам. Например, южная стена в клетке (1,1) также является северной стеной в клетке (2,1). Замок содержит по крайней мере две комнаты. В выходном файле должны быть три строки. В первой стро- ке содержится число комнат, во второй — площадь наиболь- шей комнаты (измеряется количеством клеток). Третья строка содержит три числа, определяющих удаляемую стену: номер строки, номер столбца клетки, содержащей удаляемую стену, и положение этой стены в клетке — север, W — запад, S — юг, Е — восток). 9. Автозаправка. Вдоль кольцевой дороги расположено М городов, в каждом из которых есть автозаправочная станция. Известна стоимость Z[i] заправки в городе с номером i и стои- Шестая международная олимпиада по информатике, 1994 год. 118 Перебор и методы его сокращения C[i] проезда по дороге, соединяющей и горо- да, С[М] — стоимость проезда между первым и городами. Для жителей каждого города определить город, в который им необходимо съездить, чтобы заправиться самым дешевым обра- зом, и направление — «по часовой стрелке» или «против часо- вой стрелки», города пронумерованы по часовой стрелке. Указание. Переборный вариант решения задачи сводится к проверке всех 2*М вариантов для жителей каждого города, итого — проверок. Введем два дополнительных масси- ва On, Ag: Of Record wh, pr:Integer;End;. означает, где следует заправляться (wh) и стоимость заправки жителям города, если движение разрешено только по часовой стрелке. В этом случае жители города i имеют две аль- тернативы: либо заправляться у себя в городе, либо ехать по часовой стрелке. Во втором случае жителям города i надо за- правляться там же, где и жителям города или в первом, ес- ли Итак, Откуда изве- стно значение Необходимо найти город с минимальной стоимостью заправки — После этого можно последовательно вычислять значения ..., Аналогичные действия необходимо вы- полнить при формировании массива Ag[i], после этого для жи- телей каждого города i следует выбрать лучший из On[i].pr и Ag[i].pr вариант заправки. 10. В Of Byte), заполненном 0 и 1, найти квадратный блок максимального размера, состоящий 0. Указание. Пусть N=5, и массив А заполнен следующим образом (см. верхнюю таблицу). Определим массив В Of Byte) следующим образом. Элементы первой строки и пер- вого столбца инвертируются относитель- но соответствующих элементов массива А. И далее, при и j=2..M если и если Для нашего примера В представлен в нижней таблице. Ответ за- дачи — 3. Как изменится решение, если потре- бовать нахождение прямоугольного блока максимального разме- ра? Решает ли следующий фрагмент программного кода задачу? Перебор и методы его сокращения 119 Procedure Solve; Var j, к, Integer; Begin *} For To N Do For M Do If A[i, j]=0 Then j]:=B[i, j-l]+l Else B[i, массиве А исходные данные, в В - результаты *} For N Do For j :=1 M Do Begin For k:=i 1 Do Begin nx:=Min(nx, B[k, If nx* >sqa Then ; End; End; End; 11. Задача о паркете*. Комнату размером N*M единиц тре- буется покрыть одинаковыми плитками паркета размером 2*1 единиц без пропусков и наложений iV<8, M, N — це- лые). Пол можно покрыть паркетом различными способами. Например, для iV=3 все возможные способы укладки приведены на рисунке. Требуется определить количество всех возможных способов укладки паркета для конкретных значений Резу- льтат задачи — таблица, содержащая 20 строк и 8 столбцов. Элементом таблицы является число, являющееся решением задачи для соответствующих N и М. На месте ненайденных ре- зультатов должен стоять символ <<*». Указание. Пусть i — длина комнаты j — ширина комнаты «Разрежем» комнату на части. Разрез прово- дится по вертикали. Плитки, встречающиеся на пути разреза, обходим справа, т. е. при движении сверху вниз на каждом Задача Сергея Геннадьевича с Всероссийской олимпиады школьников по информатике 1994 год. 120 3. Перебор и методы его сокращения шаге либо обходим справа выступаю- щую клетку, либо нет. При других укладках паркета могут получиться другие сечения. Все варианты сечений легко пронумеровываются, ибо это не что иное, как двоичное число: обход справа плитки соответствует 1, отсут- ствие обхода — 0. На рисунке сечение выделено «жирной» линией, ему соот- ветствует двоичное число 00100011 (35). Количество различ- ных сечений 2' (пронумеруем их от 0 до где i — длина комнаты. Не будем пока учитывать то, что некоторые из сечений не могут быть получены. Обозначим парой комнату с фикси- рованной длиной i, правый край которой не ровный, а пред- ставляет собой сечение с номером k. B[k,j] — количество вари- антов укладки паркета в такой комнате. Задача в такой постановке сводится к нахождению — количества укла- док паркета в комнате размером с ровным правым краем. Считаем, что при любом i, ибо комната нулевой ширины, нулевого сечения и любой длины укладывается пар- кетом, при этом не используется ни одной плитки. Кроме этого считаем для всех сечений с номерами так как ненулевые сечения при нулевой ширине нельзя реализовать. Попытаемся найти для фиксированного i. Предполо- жим, что нам известны значения B[l,j—1] для всех сечений с номерами 1). Сечение считаем совместимым с сечени- ем k, если путем добавления целого числа плиток паркета из первого можно получить второе. Тогда сум- мирование ведется по всем сечениям совместимым с сечением Налицо динамическая схема решения задачи. Схема её реа- лизации имеет вид: Var B:Array[0..255,0..20] .8,1..20] of таблица.*} Procedure Solve; Var Begin For i:=l To 8 Do Begin значению длины комнаты. *} ; { *Вычисляем 2 в степени i минус 1. *} FillChar (В) ,0) ; В[0,0] 3. Перебор и методы его сокращения 121 For j:=l 20 Do Begin {*Цикл по значению ширины комнаты. *} For max Do {*Сечение с номером к. *} For max Do с номером 1.*} If Then +B[1 ,j-l] ; сечений "зарыта" в функции Can (k,l,i). *} End; End; End; При решении вопроса о совместимости сечений следует раз- личать понятия совместимость сечений в целом и совмести- мость в отдельном разряде. При анализе последнего входными данными являются значения разрядов сечений и информация о предыстории процесса (до текущего разряда) — целое или неце- лое количество плиток уложено. Выходными данными — при- знак — целое, нецелое количество плиток, требуемых для пере- вода сечения в сечение или решение о том, что анализ продолжать не следует — сечения несовместимы. Оставим эту часть работы и доведение схемы решения до работающего вари- анта на самостоятельное выполнение. Еще несколько замечаний. Во-первых, если произведение N на М нечетно (размеры комнаты), то количество укладок пар- кетом такой комнаты равно 0. Во-вторых, при и четном ответ равен 1. В-третьих, результирующая таблица на относительно главной диагонали. В-четвертых, для комнат размером достаточно просто выводится следующая рекур- рентная формула: A[2,t]=A[2,t-l]+A[2,t-2] (ряд Фибоначчи). Эти замечания реализуются этапе предварительной обработ- ки и приводят к незначительной модификации логики проце- дуры Solve. Еще одно замечание касается точности результата. Для больших значений N и М необходимо организовать вычис- ления с использованием «длинной» арифметики ибо результат равен 3547073578562247994. «Канадские авиалинии»*. Вы победили в соревновании, организованном канадскими авиалиниями. Приз — бесплатное путешествие по Канаде. Путешествие начинается с самого за- падного города, в который летают самолеты, проходит с запада на восток, пока не достигнет самого восточного города, в кото- Задача с Пятой Международной олимпиады школьников по информатике 1993 года. 122 3. Перебор и методы его сокращения рый летают самолеты. Затем путешествие продолжается обрат- но с востока на запад, пока не достигнет начального города. Ни один из городов нельзя посещать более одного раза за исключе- нием начального города, который надо посетить ровно дважды (в начале и в конце путешествия). Вам также нельзя пользова- ться авиалиниями других компаний или другими способами передвижения. Задача состоит в следующем: дан список горо- дов и список прямых рейсов между парами городов; найти мар- шрут, включающий максимальное количество городов и удов- летворяющий вышеназванным условиям. Указание. Пусть нам необходимо попасть из самого западно- го города в самый восточный, посетив при этом максимальное количество городов. Связи между городами будем записывать с помощью массива West: Пусть мы каким-то образом ре- шили задачу для всех городов, ко- торые находятся западнее города с номером i, т. е. для городов с номе- рами Что значит решили? У нас есть маршруты для каждого из этих городов, и нам известно, через сколько городов они проходят. Обозначим через множество городов, находящих- ся западнее i и связанных с городом i авиалиниями. Для этих городов задача решена, т. е. известны значения — количество городов в наилучшем маршруте, заканчивающемся в городе с номером у. Итак: Остается открытым вопрос, а где же маршрут? Ибо значение d дает только количество городов, через которые он проходит. А для этого необходимо запомнить не только значение d[i], но и номер города дающего это значение. Возможно использова- ние следующей структуры данных: Of Record d, l:Byte; End;. В данной схеме мы видим не что иное, как ме- тод динамического программирования в действии. Как обоб- щить этот набросок решения для первоначальной формулиров- ки задачи? Для удобства перенумеруем города в обратном порядке — с востока на запад. Изменим массив А 3. Перебор и методы его сокращения 123 1 Of Record Под элементом A[i,j].d (путь из города i в город j) понимается максимальное число городов в маршруте, состоящем из двух частей: от i до 1 (на восток) и от 1 до (на запад). По условию задачи нам необ- ходимо найти наилучший по числу городов путь из города в N-&. Считаем, что A[l,l].d=l Через обозна- чим множество городов, из которых можно попасть в город i. Верны следующие соотношения: A[i,j] . (A[k,j] , при koj если .d=max , при i>l и keQi. 13. Решить предыдущую задачу методом полного перебора вариантов. Указание. Определим структуры данных, а именно: Of Boolean; way, Of Byte; Первый массив необходим для хранения признака — посещал- ся или нет город — города с номером i нет в мар- шруте). Во втором и третьем массивах запоминаются по прин- ципу стека текущий и наилучший маршруты соответственно. Для работы со стеками необходимы указатели — переменные и Логика перебора поясняется на нижеприведенном рисунке. Ищем путь из города с номером Фрагмент основной части логики. Begin Solve (1) ; End. И процедура поиска решения. Procedure Var j Begin 124 3. Перебор и методы его сокращения If i=N Then *} If And Not pp Then Begin {*Вернулись в первый город. *} If Then Begin Запоминаем решение.*} ; End; перебор. *} End; направлению определяем просматриваемых городов. *} If Then Begin pn:=i+l; pv:=n; End Else Begin End; For To pv Do If West And Then Begin { *B город с номером j летают самолеты из города i, и город j еще не посещался. *} {*Включаем город j в маршрут. *} Solve (j) ; (yk); {*Исключаем город j из *} If j=N Then =True ; {*Если исключается самый восточный город (N) , то меняем направление *} End; End; 14. Ресторан. В ресторане собираются N посетителей. Посе- титель с номером i подходит во время Т. и имеет благосостоя- ние Входная дверь ресторана имеет состояний открыто- сти. Состояние открытости двери может изменяться на одну единицу за одну единицу времени, т. е. она или открывается на единицу, или закрывается, или остается в том же состоянии. В начальный момент времени дверь закрыта (состояние 0). Посе- титель с номером i входит в ресторан только в том случае, если дверь открыта специально для него, то есть когда состояние от- крытости двери совпадает с его степенью полноты Если в момент прихода посетителя состояние двери не совпадает с его степенью полноты, то посетитель уходит и больше не возвраща- ется. Ресторан работает в течение времени Т. Цель состоит в том, чтобы, правильно открывая и закрывая дверь, добиться того, чтобы за время работы ресторана в нем собрались посетители с максимальным суммарным благососто- янием. Перебор и методы его совращения 125 Входные данные. В первой строке находятся значения N, К и Т, разделенные пробелами (l В третьей строке находятся величины благосостояния посети- телей ... разделенные пробелами для всех В четвертой строке находятся значения степени полноты посетителей разделенные пробелами для всех Все исходные данные — целые числа. Выходные данные. Выводится одно число, являющееся мак- симальным значением суммарного благосостояния посетите- лей. В случае, если нельзя добиться прихода в ресторан ни од- ного посетителя, выходной файл должен содержать значение 0. Классическая задача на метод динамического программиро- вания. Состояния откры- тости двери можно пред- ставить «треугольной решеткой », изображен- ной на рисунке. Каждая вершина определяет сте- пень открытости q в мо- мент времени t. Некото- рым вершинам решетки приписаны веса, равные величине благосостояния посетителя, приходяще- го в момент времени t и имеющего степень полноты, равную Что осталось сделать? Найти путь по решетке, проходящий через вершины, сумма ве- сов которых имеет максимальное значение. Следует отметить, что нет необходимости хранить оценки всех вершин. Нам необ- ходимо подсчитать оценки для момента времени t. Это возмож- но, если известны их значения для момента времени 15. Имеется клеточное поле размером N*M. Из каждой клетки можно перемещаться в одну из соседних, если она есть (вверх, вправо, вниз, влево). Коммивояжер стартует из ка- кой-то клетки. Может ли он обойти все клетки и вернуться в исходную клетку? 16. Даны два массива A[1..N] и B[1..N]. Матрица расстояний между городами формируется по правилу: или при ioj. Решить задачу коммивояжера для этих случаев. 126 Перебор и методы его сокращения 17. Черепашка находится в городе, все кварталы которого имеют прямоугольную форму, и ей необходимо попасть с край- него северо-западного перекрестка на крайний юго-восточный. Пример. На некоторых улицах проводится ремонт, и по ним запреще- но движение (например, между перекрестками 3 и 7, 5 и 6, и 11), длина, а значит и стоимость проезда по остальным ули- цам задается. Кроме того, для каждого перекрестка определена стоимость поворота. Так, если Черепашка пришла на 7-й пере- кресток и поворачивает к то она платит штраф, а если идет в направлении 8-го, то платить ей не приходится. Найти для Черепашки маршрут минимальной стоимости. Исходные данные: • N — количество перекрестков, определяется через два числа m и N=l*m • длина улиц (стоимость проезда) и стоимость поворота на перекрестках — целые числа. Указание. Определим для каждого перекрестка два числа: стоимость перемещения на юг и стоимость перемещения на вос- ток. Начнем их вычисление с крайнего юго-восточного пере- крестка. Логика вычислений имеет вид: A[i ,j Min (A[i A[i , j +1 ]/ При этом i изменяется от Z-1 до 1, а от до 1. Пример (max — обозначено отсутствие движения в этом направлении). Итак, стоимость минимального маршрута равна 40. Дальней- шее решение во многом зависит от удачности выбора структур данных. Если определить: Const Type Cross=Record Right, Down, Turn End; Var .Nmax,l. Of Cross, то программная реализация будет достаточно компактна. 3. Перебор и методы его сокращения 127 18. Задано прямоугольное клеточное поле N*M и число k. Построить k различных непрерывных разрезов этого поля на два клеточных поля равной площади. Разрез должен проходить по границам клеток. Пример разреза. Указание. Задача логически разбивается на следующие части: • построение разреза между двумя точками на границе клеточного поля; • подсчет площадей; • вывод результата. Наиболее интересной является первая часть. Перенумеруем точки на границе поля по часовой стрелке. После этой опера- ции появляется возможность перебирать по две точки и стро- ить между этими точками разрез. Организация перебора оче- видна. Номер первой точки изменяется от 1 до L, где L — количество точек на границе, номер второй от значения до L. Для построения разреза используется классический волно- вой алгоритм (задача о лабиринте). Дальнейшее решение зави- сит от выбора структур данных. Целесообразно хранить коор- динаты точек линии разреза. В этом случае площадь — это сумма площадей прямоугольников. 19. Имеется механизм, состоящий из N расположенных в одной плоскости и свободно надетых на зафиксированные оси пронумерованных шестеренок, зубья которых соприкасаются друг с другом. Информация о механизме ограничивается тем, что для каждой шестеренки перечислены все те, с которыми она находится в непосредственном зацеплении. Напишите про- грамму, определяющую, есть ли такая шестеренка, поворачи- вая которую мы приведем в движение весь механизм. 20. Дано N конвертов с размерами и N прямоугольных открыток с размерами i=l, ..., N. Возможно ли разложить открытки по конвертам и если да, то привести все варианты раскладки. |