Информационный центр "Центральный Дом Знаний"
Онлайн всего: 1 Гостей: 1 Пользователей: 0
|
Лекции по структурам и алгоритмам обработки данных (СиАОД) 3Задачи для самостоятельного решения
Квадратное озеро с островами задается матрицей размером N N (1 N 300). Каждый элемент матрицы содержит либо символ '@' (собака), обозначающий территорию, которая включает часть острова, либо символ '.' (точка), обозначающий участок свободной воды. В левом верхнем углу озера находится квадратный плот размером M M (1 M < N) клеток. За один шаг плот может сдвигаться на одну клетку по горизонтали или вертикали. Плот и остров не могут иметь общих клеток. Требуется определить минимальное число шагов, необходимых для того, чтобы плот достиг правого нижнего угла озера. Ввод из файла INPUT.TXT. В первой строке содержатся числа N и M, разделенные пробелами. В следующих N строках находится матрица, представляющая озеро, по N подряд идущих символов в строке. Подматрица размером M M, находящаяся в левом верхнем углу, не содержит островов, то есть начальное положение плота всегда допустимо. Вывод: файл OUTPUT.TXT должен содержать единственное число — количество необходимых шагов. Если правого нижнего угла достичь невозможно, то в файл выводится No. Пример Ввод 1 Ввод 2 Ввод 3 7 2 7 3 7 3 ....... ....... ....... ...@... .....@@ .....@@ ....... ......@ ......@ ..@.... .@..... .@....@ ....... .@..... .@..... ....... ....... ....... ....@.. ..@@... ..@@... Вывод 1 Вывод 2 Вывод 3 10 8 No 2. Путь коня (6) Дана шахматная доска, состоящая из N N клеток, несколько из них вырезано. Провести ходом коня через невырезанные клетки путь минимальной длины из одной заданной клетки в другую. Ввод из файла INPUT.TXT. В первой строке задано число N. В следующих N строках содержится по N символов. Символом # обозначена вырезанная клетка, точкой - невырезанная клетка, @ - заданные клетки (таких символов два). Вывод в файл OUTPUT.TXT. Если путь построить невозможно, вывести "Impossible", в противном случае вывести такую же карту, как и на входе, но пометить все промежуточные положения коня символом @. Ограничения: 2 ≤ N ≤ 300, время 1 с. Примеры
Ввод из файла INPUT.TXT. В первой строке находятся числа N и M через пробел, далее идут N строк по M символов (3 ≤ N, M ≤ 50). Символ X обозначает территорию кратера, точка соответствует незанятой территории. Других символов в исходном файле нет. Вывод в файл OUTPUT.TXT. Вывести N строк по M знаков. Каналы показать символами '*'.
Прямоугольная комната размером M N метров с мебелью покрыта квадратными паркетными плитами со стороной один метр. В углу комнаты стоит тяжелый сейф, занимая всю площадь плиты. Под сейф закатилось кольцо с бриллиантом, поэтому решено полностью освободить плиту под сейфом. Для этого нужно переместить сейф на одну из соседних плит путем кантования - поворота в плоскости пола на 90° вокруг одного из своих углов. Соседними считаются плиты, имеющие общую сторону. Некоторые плиты комнаты заняты стульями. Каждый стул может быть переставлен на свободную соседнюю с ним плиту. В комнате может быть и другая мебель. Она также занимает определенные плиты, но в отличие от стульев не может перемещаться. При повороте сейфа никакая его точка не должна пересекать внутреннюю часть такой плиты, на которой стоит стул или другая мебель. Матрица M N определяет начальное положение мебели. Каждый элемент матрицы описывает одну паркетную плиту. Сейф находится в левом верхнем углу. Плите с сейфом соответствует символ '#', свободной плите паркета - символ '.' (точка), плите со стулом - символ '@', плите с другой мебелью - символ '*'. Поворот сейфа выполняется за одну минуту, а перестановка стула - за одну секунду. Найти минимальное время в секундах, за которое сейф может быть перемещен. Ввод из файла INPUT.TXT. В первой строке содержатся числа M и N (2 M, N 300), разделенные пробелами. В следующих M строках находится матрица, описывающая комнату, по N подряд идущих символов в строке. Вывод в файл OUTPUT.TXT. Вывести наименьшее число секунд, необходимых для освобождения плиты под сейфом. Если плиту освободить невозможно, вывести No. Ограничения. Максимальное время работы на одном тесте: 2 секунды. Максимальный объем используемой памяти: 64 мегабайта.
Ввод 1 Ввод 2 Ввод 3 4 4 4 3 4 2 #... #.* #. .... .@. .@ @.@. @** @* ...@ @.@ @@ Вывод 1 Вывод 2 Вывод 3 60 61 No 5. Пчела Майа (6) Пчелы живут в ульях, где есть соты. Соты представляют собой поле правильных шестиугольников, соприкасающихся друг с другом. Правильное поле строится следующим образом:
Пчела Майя возвращается в улей. Она живет в одной из сот правильного поля уровня N (2 N 20). Для того, чтобы добраться до своей соты (если она не расположена с краю поля), Майе нужно переместиться через другие соты, в которых могут жить как друзья (перемещаться можно), так и враги (перемещаться нельзя). Майя очень устала и хочет добраться до своей соты, пройдя через минимальное число других сот. Свой путь она может начинать с любой дружественной соты, находящейся с краю поля (то есть такой соты, которая не окружена со всех сторон соседними сотами).
Ввод. В первой строке записано одно число N – уровень правильного поля. В следующих 2N-1 строках содержатся последовательности из символов ‘V’, ‘D’, ‘M’ (‘V’ – сота врага, ‘D’ – сота друга, ‘M’ – сота Майи). Вывод. В единственной строке выводится минимальное число сот, через которые придется пройти Майе, чтобы попасть в свою соту (своя сота тоже считается), или ноль, если Майе не удастся попасть в свою соту. Примеры Ввод 1 Ввод 2 Ввод 3
2 6 0 5. Целочисленная арифметика
Напомним некоторые термины. Натуральными числами называют целые положительные числа. Натуральное число называется простым, если делится без остатка только на 1 и само на себя. Иначе число называется составным. Число 2 является единственным четным простым числом. Начнем с распространенной задачи. Требуется определить, является ли заданное натуральное число N простым. Можно последовательно перебирать вероятные делители 2, 3, …, N-1. Если N не делится ни на одно из этих чисел, то оно простое. Как уменьшить объем вычислений? Во-первых, достаточно проверять делимость на числа от 2 до K = [ √N ], где квадратными скобками обозначена целая часть числа. Действительно, если один из делителей больше K, то второй должен быть меньше K. Во-вторых, нет необходимости проверять четные числа, большие 2: они составные. А для нечетных чисел достаточно исследовать только нечетные делители. Описанный подход реализуется следующей функцией:
Несколько усложним задачу. Пусть сейчас требуется вывести все простые числа от M до N, где M ≤ N ≤ 106, а время счета не должно превышать 2 сек. Описанный выше подход не укладывается в это ограничение. Будем для каждого числа проверять делимость не на все числа до корня из этого числа, а только на простые числа. Их может быть не более 1000, поэтому легко найти их заранее и поместить в массив. Два натуральных числа называют взаимно простыми, если они не имеют общих делителей, больших 1. Взаимную простоту двух чисел X и Y легко проверить путем нахождения их наибольшего общего делителя НОД(X, Y). Если он оказывается равным 1, то числа взаимно просты. Максимальное сокращение дроби X / Y возможно на величину НОД(X, Y). Приведем без доказательства свойства наибольшего общего делителя:
На этих свойствах основан алгоритм Евклида нахождения НОД(X, Y). Например, НОД(12, 9) = НОД(3, 9) = НОД(9, 3) = НОД(6, 3) = НОД(3, 3) = 3. При большом X и малом Y последнее свойство будет использоваться много раз. Более современная версия алгоритма Евклида основана на том, что при Y ≠ 0 и X ≥ Y выполняется свойство НОД(X, Y) = НОД(Y, X mod Y). Приведем фрагмент программы вычисления НОД(X, Y). While Y>0 do Begin Z:=X mod Y; X:=Y; Y:=Z; End; {ответ в X} Более эффективный алгоритм поиска НОД, не требующий трудоемкой операции деления по модулю, приведен в [3]. В ряде приложений используется наименьшее общее кратное двух чисел НОК(X, Y), связанное с НОД(X, Y) простым соотношением: НОК(X, Y) = (X×Y) / НОД(X, Y). Греческому математику Эратосфену, жившему до нашей эры, принадлежит алгоритм нахождения простых чисел в заданном диапазоне. Из всех чисел последовательно удаляются те, которые делятся на 2, на 3 и т. д. В итоге остаются только простые числа. Такой способ называют методом «решета» [4]. Рассмотрим для примера следующую задачу. Окраска чисел. Профессор Психовецкий решил покрасить все числа от 1 до N (1 ≤ N ≤109) так, чтобы каждые два числа A и B имели разный цвет, если A делится на B. Каким минимальным количеством цветов можно обойтись? Ввод. В единственной строке файла INPUT.TXT задано число N (1 ≤ N ≤10000). Вывод. В единственную строку OUTPUT.TXT вывести минимальное количество цветов. Примеры Ввод 1 Ввод 2 Ввод 3 3 5 12 Вывод 1 Вывод 2 Вывод 3 2 3 4 Можно решать задачу перебором, рассматривая по возрастанию возможные делители чисел до N включительно. Такой способ реализуется следующим образом.
Метод имеет квадратичную трудоемкость, поэтому непригоден при больших значениях N. Опишем другой подход. В соответствии с методом Эратосфена более рационально перекрашивать последовательно все числа, имеющие общий делитель. Для этого достаточно переписать цикл окраски в следующем виде.
|
Loading
|