Центральный Дом Знаний - Лекции по структурам и алгоритмам обработки данных (СиАОД) 3

Информационный центр "Центральный Дом Знаний"

      cendomzn@yandex.ru  

Наш опрос

Я учусь (закончил(-а) в
Результаты | Архив опросов
Всего ответов: 2691

Онлайн всего: 1
Гостей: 1
Пользователей: 0


Форма входа

Лекции по структурам и алгоритмам обработки данных (СиАОД) 3

Лекции по структурам и алгоритмам обработки данных (СиАОД)

стр.: 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25

Полный текст лекций можно скачать здесь

Задачи для самостоятельного решения

1. Квадратное озеро (6)

Квадратное озеро с островами задается матрицей размером 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 с.

Примеры

Ввод 1 Ввод 2 Ввод 3
5 5 5
..... @..@. @....
.@@.. ..##. ..#..
..... ..... .#...
..... ..... .....
..... ..... ....@

Вывод 1 Вывод 2 Вывод 3
...@. @..@. Impossible
.@@.. ..##.
....@ .@..@
..... ..@..
..... @....

3. Остров (9)
Прямоугольный остров имеет кратеры. Требуется соединить каналами ровно два кратера с океаном так, чтобы общая длина каналов была минимальной. Кратером называется совокупность квадратов, удовлетворяющая таким условиям:

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

  • никакие два кратера не пересекаются и не касаются друг друга ни по вертикальной, ни по горизонтальной сторонам квадратов (касание кратеров углами допускается);

  • нет кратеров на границе прямоугольника.

Ввод из файла INPUT.TXT. В первой строке находятся числа N и M через пробел, далее идут N строк по M символов (3 ≤ N, M ≤ 50). Символ X обозначает территорию кратера, точка соответствует незанятой территории. Других символов в исходном файле нет.

Вывод в файл OUTPUT.TXT. Вывести N строк по M знаков. Каналы показать символами '*'.

Примеры
Ввод 1 Вывод 1
5 7
....... ......
....... ......
..X.... **X...
....X.. ....X*
....... ......
Ввод 2 Вывод 2
9 13
............. ........*....
............. ........*....
..XXXXX...... ..XXXXX**....
..X..X....... ..X..X..*....
..X.X.X.X.... ..X.X.X.X....
..X..X....... ..X..X.......
..XXXXX...... ..XXXXX......
............. .............
............. .............
Подсказка. Один из способов решения:

  1. поиском в глубину пометить клетки кратеров числовыми метками (разными для разных кратеров);

  2. поиском в ширину (волновой алгоритм) найти два кратчайших пути от разных кратеров до края, определить их общую длину;

  3. от каждой свободной клетки поиском в ширину найти

  • кратчайший путь до границы;

  • кратчайший путь до двух разных кратеров

и сложить их длину;

  1. из двух вариантов в пунктах 2 и 3 выбрать лучший.

4. Найти кольцо (7)

Прямоугольная комната размером 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)

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

  • сначала имеется всего одна сота (рис. 1) – это правильное поле первого уровня;

  • затем вокруг соты появляются соседние (рис. 2) – это правильное поле второго уровня;

  • затем строится еще один «ободок» (рис. 3) – это правильное поле третьего уровня, и т. д.

Пчела Майя возвращается в улей. Она живет в одной из сот правильного поля уровня N (2 N 20). Для того, чтобы добраться до своей соты (если она не расположена с краю поля), Майе нужно переместиться через другие соты, в которых могут жить как друзья (перемещаться можно), так и враги (перемещаться нельзя). Майя очень устала и хочет добраться до своей соты, пройдя через минимальное число других сот. Свой путь она может начинать с любой дружественной соты, находящейся с краю поля (то есть такой соты, которая не окружена со всех сторон соседними сотами).

Ввод. В первой строке записано одно число N – уровень правильного поля. В следующих 2N-1 строках содержатся последовательности из символов ‘V’, ‘D’, ‘M’ (‘V’ – сота врага, ‘D’ – сота друга, ‘M’ – сота Майи).

Вывод. В единственной строке выводится минимальное число сот, через которые придется пройти Майе, чтобы попасть в свою соту (своя сота тоже считается), или ноль, если Майе не удастся попасть в свою соту.

Примеры

Ввод 1 Ввод 2 Ввод 3

2 3 2

VV VVV VV

VMV VDDV VMV

VD VMVDV VV
VVDV
VVD
Вывод 1 Вывод 2 Вывод 3

2 6 0

5. Целочисленная арифметика


Напомним некоторые термины. Натуральными числами называют целые положительные числа. Натуральное число называется простым, если делится без остатка только на 1 и само на себя. Иначе число называется составным. Число 2 является единственным четным простым числом.

Начнем с распространенной задачи. Требуется определить, является ли заданное натуральное число N простым.

Можно последовательно перебирать вероятные делители 2, 3, …, N-1. Если N не делится ни на одно из этих чисел, то оно простое. Как уменьшить объем вычислений?

Во-первых, достаточно проверять делимость на числа от 2 до K = [ √N ], где квадратными скобками обозначена целая часть числа. Действительно, если один из делителей больше K, то второй должен быть меньше K.

Во-вторых, нет необходимости проверять четные числа, большие 2: они составные. А для нечетных чисел достаточно исследовать только нечетные делители.

Описанный подход реализуется следующей функцией:


Function Isprime(N: longint): boolean;

{Возвращает true для простого N, false для составное}

Var

i,k: integer;

Flag: boolean;

Begin

k:=Trunc(Sqrt(N));

Flag:=true; {признак простого числа}
if (not Odd(N)) and (N<>2) then Flag:=false

else

begin

i:=3;

While i<=k do

if (N mod i)=0 then

begin

Flag:=false;

Break; {N-составное}

end

else i:=i+2;

end;

Isprime:=Flag;

End;


Несколько усложним задачу. Пусть сейчас требуется вывести все простые числа от M до N, где M ≤ N ≤ 106, а время счета не должно превышать 2 сек. Описанный выше подход не укладывается в это ограничение.

Будем для каждого числа проверять делимость не на все числа до корня из этого числа, а только на простые числа. Их может быть не более 1000, поэтому легко найти их заранее и поместить в массив.

Два натуральных числа называют взаимно простыми, если они не имеют общих делителей, больших 1. Взаимную простоту двух чисел X и Y легко проверить путем нахождения их наибольшего общего делителя НОД(X, Y). Если он оказывается равным 1, то числа взаимно просты.

Максимальное сокращение дроби X / Y возможно на величину НОД(X, Y).

Приведем без доказательства свойства наибольшего общего делителя:

  1. НОД(X, Y) = X, если Y = 0;

  2. НОД(X, Y) = X, если X = Y;

  3. НОД(X, Y) = НОД(Y, X);

  4. НОД(X, Y) = НОД(X - Y, 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 включительно. Такой способ реализуется следующим образом.


Program Paint;

Const Max=1000000;

Var

M,N,i,j: longint;

Color: array [1..Max] of byte; {номера цветов}

Fin,Fout: text;

begin

Assign(Fin,'input.txt');

Reset(Fin);

ReadLn(Fin,N);

Close(Fin);

For i:=1 to N do Color[i]:=1; {инициализация}
M:=1; {число цветов и максимальный номер цвета}
For i:=2 to N do {i-число для окраски}
For j:=1 to i div 2 do {j-предполагаемый делитель}

if (i mod j = 0) and (Color[i]=Color[j]) then

begin

Color[i]:=Color[i]+1;

if Color[i]>M then M:=M+1;

end;

Assign(Fout,'output.txt');

Rewrite(Fout);

WriteLn(Fout,M);

Close(Fout);
End.


Метод имеет квадратичную трудоемкость, поэтому непригоден при больших значениях N. Опишем другой подход. В соответствии с методом Эратосфена более рационально перекрашивать последовательно все числа, имеющие общий делитель. Для этого достаточно переписать цикл окраски в следующем виде.


For i:=1 to N div 2 do {i-первый сомножитель}
For j:=2 to N div i do {j-второй сомножитель}

begin

if Color[i*j]=Color[i] then Color[k]:=Color[i]+1;

if Color[k]>M then M:=Color[k];

end;