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

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

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

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


    Скачать 5.46 Mb.
    НазваниеПо вопросам приобретения обращаться
    Дата06.12.2019
    Размер5.46 Mb.
    Формат файлаpdf
    Имя файлаProgrammirovanie_v_algoritmakh.pdf
    ТипДокументы
    #98984
    страница9 из 26
    1   ...   5   6   7   8   9   10   11   12   ...   26
    128
    3. Перебор и методы его сокращения
    21. «Американские кубики». Даны четыре кубика — на ри- сунке изображены их развертки. Требуется сложить из них башню 1*1*4 так, чтобы на каждой боковой грани встречались все четыре цифры. Определить форматы входных и выходных данных. Написать программу поиска всех вариантов (если они есть) раскладки кубиков, удовлетворяющих условию задачи.
    22. Клетки доски 8*8 раскрашены в два цвета: белый и чер- ный. Необходимо пройти из левого нижнего угла в правый вер- хний так, чтобы цвета клеток перемежались. За один ход раз- решается перемещаться на одну клетку по вертикали или горизонтали.
    Программа должна (если путь существует):
    • находить хотя бы один путь;
    • находить путь минимальной длины.
    Указание. Для решения задачи применим метод «волны» с учетом условия задачи — чередования клеток разного цвета.
    23. Дана матрица N*N
    состоящая из целых чисел.
    За одну операцию разрешается изменить знаки всех чисел про- извольно выбранной строки или столбца на противоположные.
    Требуется сделать суммы чисел во всех строках и столбцах не-
    Программа должна ввести матрицу и вывести в качестве ре- зультата последовательность операций. Количество операций должно быть минимальным.
    Указание. Задача решается перебором вариантов. У нас есть
    2*N элементов, N строк и N столбцов. Необходимо генериро- вать подмножества из множества 2*N элементов,
    k изменяется от 1 до 2*N, и проверять матрицу после измене- ния знаков в строках и столбцах, принадлежащих очередному подмножеству.
    24. Круг разбили на 8 секторов*. Какие-то два соседних сек- тора пусты, а в остальных расположены буквы, Р, О, С, С, И, Я
    в некотором порядке (по одной в секторе).
    Задача предложена для одной из кировских олимпиад по информатике Анто- ном Валерьевичем

    3. Перебор и методы его сокращения
    129
    За один ход разрешается взять любые две подряд идущие буквы и перенести их в пустые сектора, сохранив порядок. При этом сектора, которые занимали перене- сенные буквы до хода, становятся пусты- ми. Номером хода назовем номер первого из секторов в порядке обхода по часовой стрелке содержимое которого пере- носится.
    Состояние круга назовем правильным, если начиная с секто- ра 1 по ЧС можно прочесть слово «РОССИЯ». При этом место- положение пустых секторов может быть произвольным. Состо- яние круга можно закодировать строкой из 8 символов,
    получающихся при чтении круга по ЧС, начиная с сектора 1,
    если пустому сектору поставить в соответствие символ подчер- кивания
    Эту строку из 8 символов будем называть кодом круга.
    По заданному коду найти кратчайшую последовательность ходов, переводящую круг в правильное состояние. Если реше- ний несколько, то необходимо выдать только один вариант.
    Указание. Задача решается перебором вариантов. Из каждо- го состояния круга генерируются все состояния, в которые можно попасть из него. Запоминаем состояния в структуре дан- ных типа очередь. Повторяющиеся состояния в очередь не за- писываются. Процесс перебора заканчивается при достижении состояния, эквивалентного состоянию «РОССИЯ».
    25. Заданы две символьные строки и Б, не содержащие пробелов. Требуется вычислить, сколькими способами можно получить строку В из строки А, вычеркивая некоторые симво- лы. Например, если строки и В имеют соответственно вид Са- маринаИрина и Сара, то искомое число равно 7, для строк
    аааввввссс и авс это число равно 36.
    0
    а
    b
    с
    0
    1
    0
    0
    0
    а
    1
    1
    0
    0
    а
    1
    2
    0
    0
    а
    1
    3
    0
    0
    b
    1
    3
    3
    0
    Ь
    1
    3
    6
    0
    b
    1
    3
    9
    0
    b
    1
    3
    12
    0
    с
    1
    3
    12
    12
    с
    1
    3
    12
    24
    с
    1
    3
    12
    36
    Написать программу, находящую требуемое число способов.
    Указание. Рассмотрим идею решения на примере. Для кле- ток, у которых символы на горизонтали и вертикали не совпа- дают, значение переписывается из соседней по горизонтали

    130 3. Перебор и методы его сокращения клетки. Например, символ 'а' и первый символ '&' по горизон- тали. Способов получения строки 'а' из строки столько же, сколько из строки
    Для случая совпадения символов,
    например по вертикали и второе по горизонтали, количе- ство способов — это сумма способов для строк и
    (без последнего символа во второй строке), а также — 'а' и 'aaab'
    (последние символы строк совпадают).
    26. В вашем распоряжении имеется по четыре экземпляра каждого из чисел: 2, 3, 4, 6, 7, 8, 9, 10. Требуется написать программу такого размещения их в таблице 6x6, чтобы в клет- ках, обозначенных одинаковыми значками, находились равные числа и суммы чисел на каждой горизонтали, вертикали и обе- их диагоналях совпадали.
    +
    #
    +
    11
    @
    @
    $
    11
    $
    #
    +
    11
    #
    +
    @
    @
    I
    11
    #
    Примечание
    Обратите внимание на то, что число 11 уже записано в таблице 4
    раза.
    Указание. Метод решения задачи традиционный — перебор вариантов, но организовать его следует достаточно грамотно.
    Первоначально необходимо выбрать числа для помеченных клеток, а затем дополнять до значения суммы элементов, кото- рая вычисляется очень просто — сложить все числа и разде- лить на шесть (она равна 40).
    27. Возьмем клетчатую доску MxN
    Воткнем в каждую клеточку штырек. В нашем распоряжении есть абсолютно одинаковых колечек, каждое из которых можно нанизывать на штырек, причем на один штырек разре- шается надеть несколько колечек. Подсчитать, сколькими спо- собами можно распределить все эти колечки по штырькам. Два распределения считаются разными, если на каком-то из шты- рьков находится разное количество колечек, и одинаковыми в противном случае. Входные данные: М, N, К. Пример: 2, 2, 2.
    Результат: 10.
    Указание. Заметим, что клеточная доска дана для «устраше- ния». С таким же успехом задачу можно решать на линейке из клеток. Допустим, что найдено решение для L клеток, то есть определено число способов для всех значений колечек от 1

    3. Перебор и методы его сокращения 131
    до К. При L+1 клетке решение получается очевидным спосо- бом — в клетке L+1
    колечек, а в клетках от 1 до
    L — оставшиеся. Традиционная схема, называемая динамиче- ским программированием.
    28. Для известной игры «Heroes of Might and Magic III» ге- нератор случайных карт создает острова, на которых изначаль- но будут расположены герои. Но при случайной генерации кар- ты острова получаются различными по величине. Назовем коэффициентом неспра- ведливости отношение площади наибольше- го острова к площади наименьшего. Необхо- димо подсчитать этот коэффициент. Карта представляет собой прямоугольник NxM, в каждой клетке которого записан 0 (вода) или
    1 (земля). Островом считается множество клеток, содержащих 1, таких, что от любой до любой из них можно пройти по клеткам этого множества, переходя только через их стороны.
    Входные данные. В первой строке входного файла содержат- ся числа N и М (размеры карты, 1
    В следующих
    М строках записано
    N чисел (разделенных пробелами), каж- дое из которых либо 0, либо 1.
    Выходные данные. В выходной файл вывести коэффициент несправедливости с 5 знаками после запятой. Если на карте нет ни одного острова, вывести 0.
    Указание. Упростим задачу. Пусть размеры поля не превы- шают по каждому измерению значения
    Проблем с опера- тивной памятью в этом случае нет, и решение хорошо извест- но — алгоритм волны (выход из лабиринта). Суть: «цепляем»
    первую ненулевую клетку поля и пытаемся распространять
    «волну» по всем ненулевым соседним клеткам (обходом в ши- рину), гася при этом единичные значения в клетках поля и подсчитывая количество таких клеток.
    Изменение размерности, а именно приводит к совершенно другому решению. Сложность задачи возрастает на порядок. Описание карты следует считывать по строкам, ибо нет возможности хранить ее полностью в памяти (количество клеток умножим на 4 — по два байта на координату — это приводит к значению явная нехватка памяти). Что изменится в ре- шении? Пусть данные обработаны из N строк, считываем дан- ные по строке. Каждый остров, сформированный по данным из первых iV строк и активный к этому этапу обработки,

    132 3. Перебор и методы его сокращения
    имеет уникальный идентификатор. Заметим, что если при до- бавлении строки размер острова не увеличился, то из этого сле- дует, что остров не вышел на строку (если это единствен- ный выход острова на данную строку), его площадь следует проверить на значения минимума, максимума и исключить из дальнейшего рассмотрения.
    Как происходит обработка очередной строки? Просматрива- ем ее слева направо. Если встречаем единичный элемент (ост- ров), то возможны следующие ситуации:
    • слева и сверху в предыдущей строке не было единичных элементов — создаем описание нового острова;
    • слева или сверху есть единичный элемент (остров) — описа- ние острова существует, присоединяем элемент к острову;
    • слева и сверху есть единичные элементы, текущий эле- мент «склеивает» ранее созданные ост- рова, объединяем их (пример приведен на рисунке — обработка «темной»
    клетки приводит к склеиванию ранее созданных связных областей).
    После этих действий необходимо прове- рить, все ли острова подтвердили свою ак- тивность. Если есть острова, не подтвердившие свою актив- ность, то следует проверить их площади на минимум и максимум, откорректировать последние и исключить их из да- льнейшей обработки.
    29. «Полигон»*. Существует игра для од- ного игрока, которая начинается с задания
    Полигона с N вершинами. Пример графиче- ского представления Полигона при по- казан на рисунке. Для каждой вершины
    Полигона задается значение — целое число,
    а для каждого ребра — метка операции +
    (сложение) либо * (умножение). Ребра По- лигона пронумерованы от 1 до N.
    Первым ходом в игре удаляется одно из ребер.
    Каждый последующий ход состоит из следующих шагов:
    • выбирается ребро Е и две вершины
    ж
    которые сое- динены ребром
    • ребро Е и вершины и
    заменяются новой вершиной со значением, равным результату выполнения операции, опре- деленной меткой ребра Е, над значениями вершин и
    Задача о Международной олимпиады школьников по информатике
    1999 года.

    3. Перебор и методы его сокращения
    133
    Игра заканчивается, когда больше нет ни одного ребра. Ре- зультат игры — это число, равное значению оставшейся верши- ны.
    Пример игры. Рассмотрим полигон, приведенный в условии задачи. Игрок начал игру с удаления ребра 3. После этого иг- рок выбирает ребро 1, затем — ребро 4 и, наконец, ребро 2. Ре- зультатом игры будет число 0.
    Требуется написать программу, которая по заданному Поли- гону вычисляет максимальное значение оставшейся вершины и выводит список всех ребер, удаление которых на первом ходе игры позволяет получить это значение.
    Входные данные. Файл pol.in описывает Полигон с N верши- нами. Файл содержит две строки. В первой строке записано число N. Вторая строка содержит метки ребер с номерами 1,
    ..., N, между которыми записаны через один пробел значения вершин (первое из них соответствует вершине, смежной ребрам
    1 и 2, следующее — смежной ребрам 2 и 3 и так далее, послед- нее — смежной ребрам N и 1). Метка ребра — это буква t, соот- ветствующая операции +, или буква х, соответствующая опера- ции
    Выходные данные. В первой строке выходного файла pol.out программа должна записать макси- мальное значение оставшейся вершины, которое может быть достигнуто для заданного Полигона.
    Во второй строке должен быть записан список всех ребер, удаление которых на первом ходе по- зволяет получить это значение. Номера ребер должны быть записаны в возрастающем порядке и отделяться друг от друга пробелом.
    Ограничения.
    Для любой последовательности ходов значения вершин находятся в пределах [-32768, 32767].
    Указание. После удаления первого ребра остается выраже- ние, в котором необходимо так расставить скобки, чтобы его значение было максимальным. Например, пусть удалено пер- вое ребро в примере из формулировки задачи. Остается выра- жение -7+4*2*5. Способы расстановки скобок: (-7)+(4*2*5),

    134
    3. Перебор и методы его сокращения
    (-7+4*2)*5. Введем следующий массив
    ray[l..MaxN,l..MaxN] Of
    где константа MaxN равна
    50 (по условию задачи). Элемент
    определяет макси-
    мальное значение выражения
    j, начиная с вершины i
    (ключевой момент). Например, Мах[1,3] — для выражения
    —7+4*2. Очевидно, что Max[i,l] равно значениям вершин для всех i. Явно просматривается традиционная динамическая схе- ма. Единственная сложность — отрицательные числа. При ум- ножении отрицательных чисел может быть получен максимум.
    В силу этого необходимо считать и минимальные значения для каждого выражения. Просчитаем наш пример «вручную» (рас- смотрим только массив
    Выбор максимального значения из последнего столбца таблицы дает ответ задачи — максимум выражения и номера ребер.
    30. «Почтовые отделения»*. Вдоль прямой дороги располо- жены деревни. Дорога представляется целочисленной осью, а расположение каждой деревни задается одним целым чис- лом — координатой на этой оси. Никакие две деревни не имеют одинаковых координат. Расстояние между двумя деревнями вычисляется как модуль разности из координат.
    В некоторых, не обязательно во всех, деревнях будут постро- ены почтовые отделения. Деревня и расположенное в ней поч- товое отделение имеют одинаковые координаты. Почтовые от- деления необходимо расположить в деревнях таким образом,
    чтобы общая сумма расстояний от каждой деревни до ближай- шего к ней почтового отделения была минимальной.
    Задача с Международной олимпиады школьников по информатике
    2000 года.

    3. Перебор и методы его сокращения
    135
    Напишите программу, которая по заданным координатам деревень и количеству почтовых отделений находит такое рас- положение почтовых отделений по деревням, при котором об- щая сумма расстояний от каждой деревни до ее ближайшего почтового отделения будет минимальной.
    Входные данные. В первой строке файла ся два целых числа: первое число — количество деревень V,
    второе число — количество почтовых отделений Р,
    1<Р<30,
    Вторая строка содержит V целых чисел в возрас- тающем порядке, являющихся координатами деревень. Для каждой координаты X выполняется
    Выходные данные. Первая строка файла содержит одно целое число S — общую сумму расстояний от каждой деревни до её ближайшего поч- тового отделения. Вторая строка содер- жит Р целых чисел в возрастающем по- рядке. Эти числа являются искомыми координатами почтовых отделений.
    Если для заданного расположения де- ревень есть несколько решений, то программа должна найти
    Указание. При размещении одного почтового отделения эта задача известна как задача Лео Мозера (1952 год). Ответ V Div
    2+1 (V — нечетное число) и любая из двух средних деревень
    (V — четное). Решение задачи с одним почтовым отделением на взвешенном графе основано на использовании алгоритма Флой- да и поиска вершины с минимальной суммой расстояний до других вершин. При увеличении количества почтовых отделе- ний эти идеи «не проходят». Переборные схемы также не рабо- тают при данных ограничениях. Остается поиск динамической схемы. Рассмотрим пример, приведенный в формулировке за- дачи. Размещаем одно почтовое отделение в деревне с номером
    i. Оценим расстояние до деревень, находящихся левее её.
    1 0
    2 1
    3 3
    4 12 6
    16 26 7
    38 8
    115 9
    291 10 345
    Что это дает? Пока ничего. Попытаемся решить задачу для двух почтовых отделений. Рассмотрим деревни с номерами от 1
    до i. Одно почтовое отделение размещается в деревне с номером
    i. Найдем место второго почтового отделения, дающего минима- льную сумму расстояний. Пример равно 5). Крестиками обо-

    136
    Перебор и методы его сокращения значены деревни с поч- товыми отделениями.
    Справа на рисунке приведены суммы рас- стояний до ближай- ших почтовых отделе-
    1 00 2
    0 3
    1 4
    2 5
    3 6
    7 7
    12 8
    21 9
    37 10
    ний. Из четырех вариантов выбираем второй, дающий минимальную оценку — 3. Просчитаем для всех значений i.
    Массив оценок имеет вид.
    обозначен бессмыслен- ный случай — два почтовых отделения в одной деревне. Продол- жим рассмотрение — три почтовых отделения. На рисунке при- веден случай при
    (в 7 деревнях размещаются 3 почтовых отделения). Первый справа отрезок характеризует вариант, при котором два почтовых отделения расположены в деревнях с 1-й по 6-ю. Он подсчитан (равен 7, третье отделение в седьмой дерев- не, итоговая оценка не изменяется и равна 7), мы почти «нащу- пали» динамическую схему. Второй отрезок — два почтовых от- деления в деревнях с 1-й по 5-ю. Из предыдущего рассмотрения стоимость этого случая равна 3, расстояние от 6 деревни до бли- жайшего почтового отделения 2, итого 5. Окончательные оценки при 3, 4 и 5 отделениях приведены в таблице.
    1 00 00 2
    00 00 00 3
    0
    СО
    00
    .4 1
    0 00 5
    2 1
    0 6
    3 2
    1 7
    5 3
    2 8
    9 5
    3 9
    21 9
    5 10 27 15 9
    Осталось сделать последний шаг. Оценка расстояний в на- шей схеме проводилась до деревень, расположенных слева. К

    3. Перебор и методы его сокращения
    137
    этим оценкам следует прибавить сумму расстояний до дере- вень, находящихся справа. Окончательные оценки:
    Итак, общая сумма расстояний от каждой деревни до её бли- жайшего почтового отделения равна 9. Это минимум в оконча- тельном массиве оценок. Как зафиксировать в этой схеме де- ревни с почтовыми отделениями? Как обычно в алгоритмах типа Флойда, при улучшении оценки, запоминать соответству- ющую ситуацию.
    31. Палиндром* — это симметричная строка, т. е. она одина- ково читается как слева направо, так и справа налево. Вы дол- жны написать программу, которая по заданной строке опреде- ляет минимальное количество символов, которые необходимо вставить в строку для образования палиндрома.
    Например, вставкой двух символов строка может быть преобразована в палиндром («dAb3bAd» или «Adb3bdA»),
    а вставкой менее двух символов палиндром в этом примере по- лучить нельзя.
    Входные данные. Файл palin.in состоит из двух строк. Пер- вая строка содержит одно целое число — длину N входной строки,
    Вторая — строку длины N, которая состоит из прописных (заглавных) букв от до строчных букв от 'а' до 'г' и цифр от '0' до '9'. Прописные и строчные буквы счи- таются различными.
    Выходные данные. Файл palin.out состоит из одной строки.
    Эта строка содержит одно целое число, которое является иско- мым минимальным числом символов.
    Указание. Рассмотрим идею решения задачи.
    Формируем матрицу R[i,j] (i,j=l..N), где R[i,j]
    минимальное количество букв, которые необходи- мо вставить в строку S(i,j) с
    символа по символ строки S для того, чтобы получить из неё
    палиндром. Искомый результат — R[1,N]. Как формируется матрица
    Во-первых, заполняется только одна часть матрицы, выше или ниже главной диагонали, включая её.
    Во-вторых, если то
    В-третьих, ес- ли S[i]<>S[j], то R[i,j]=Min(R[i+l,j],R[i,j-l])+l. Потрениру- емся на примерах.
    R имеет вид:
    Задача с Международной олимпиады школьников по информатике
    2000 года.

    138 3. Перебор и методы его сокращения
    1   ...   5   6   7   8   9   10   11   12   ...   26


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