Окулов.Программирование.в.алгоритмах. По вопросам приобретения обращаться
 Скачать 5.46 Mb.
|
|
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 года. |