Главная страница
Навигация по странице:

  • В качестве примера действий в блоке общих отсечений можно взять следующую логику. Подсчитать для каждого значения i множество партий, представляемых жителями, номера ко

  • Перебор и методы его сокращения 119

  • Of Boolean; way

  • По вопросам приобретения обращаться


    Скачать 5.46 Mb.
    НазваниеПо вопросам приобретения обращаться
    Дата06.12.2019
    Размер5.46 Mb.
    Формат файлаpdf
    Имя файлаProgrammirovanie_v_algoritmakh.pdf
    ТипДокументы
    #98984
    страница8 из 26
    1   ...   4   5   6   7   8   9   10   11   ...   26
    Один из вариантов решения.
    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Во строке находятся времена прихода посетителей разделенные пробелами для всех i=l,2,...,iV).
    В третьей строке находятся величины благосостояния посети- телей
    ...
    разделенные пробелами для всех
    В четвертой строке находятся значения степени полноты посетителей разделенные пробелами для всех
    Все исходные данные — целые числа.
    Выходные данные. Выводится одно число, являющееся мак- симальным значением суммарного благосостояния посетите- лей. В случае, если нельзя добиться прихода в ресторан ни од- ного посетителя, выходной файл должен содержать значение 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. Возможно ли разложить открытки по конвертам и если да, то привести все варианты раскладки.

    1   ...   4   5   6   7   8   9   10   11   ...   26


    написать администратору сайта