Тема 1.8. Автоматы

Цель.

Основные понятия.

Ключевые слова.

Автомат, диаграмма состояний

ПРИМЕР.

Алгоритм.

Решение.

Задачи для обязательного решения.

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

Машина Тьюринга

Продвинутые задачки.

Тема 1.9. Дополнительные задачи

Цель.

Умение найти нужный алгоритм для решения практической задачи с сюжетом (легендой).

Основные понятия.

Абстрагирование от сюжета.

Ключевые слова.

ПРИМЕР.

Алгоритм.

Решение.

Задачи для обязательного решения.

1.9.1.1. Про размен денег набором банкнот. В банкомате находятся купюры mразличных достоинств. При выдаче нужной суммы банкомат сначала пытается набрать её более крупными купюрами. Когда эти купюры кончаются или сумма превышена, то он начинает добавлять следующие по величине купюры, и т.д. В первой строке входных данных задаётся натуральное числоn- количество различных достоинств каждой купюры. В следующихnстроках находятся по два натуральных числаK_iиM_i– номинал очередной купюры и количество банкнот с таким номиналом. Номиналы иду в порядке убывания величин. В следующей строке находится число запросов к банкоматуQ. Каждый запрос записан в виде требуемой суммы и находится в отдельной строке. Для каждого запроса нужно напечатать в первой строке количество различных выдаваемых купюр и несколько строк по два числа – номинал купюры и количество таких купюр. Все купюры, выдаваемые по одному запросу должны составлять требуемую сумму. Если данный запрос не удаётся удовлетворить, то печатать -1.

Исходные данные:

5

25 2

10 1

5 2

2 5

1 2

3

10

66

6

Результат:

1

10 1

3

25 2

5 2

2 3

2

2 2

1 2

1.9.1.3. Про кинотеатр и заказ мест. В кинотеатре имеется прямоугольный зрительный зал размера n(рядов) наm(мест в каждом ряду). К кассиру приходятkпокупателей, желающих купить билеты. Каждый покупатель указывает номер желаемого ряда и количество мест подряд, которые он хотел бы купить в этом ряду. Если в указанном ряду нет столько мест, он уходит, не купив билеты. В первой строке задаются числаn,m,k.

Далее следуют kстрок с парой натуральных чиселA_iиB_i– номер ряда и количество мест дляi-го покупателя (1 <=A_i<=nи 1 <=B_i<=m). Для каждого покупателя в отдельной строке печатать «ДА» или «НЕТ» в зависимости от того, купил он билеты или нет.

Исходные данные:

2 2 3

1 2

1 2

2 1

Результаты:

ДА

НЕТ

ДА

1.9.1.4. Про кинотеатр и заказ мест. В кинотеатре имеется прямоугольный зрительный зал размера n(рядов) наm(мест в каждом ряду). К кассиру приходятkпокупателей, желающих купить билеты. Каждый покупатель указывает номер желаемого ряда, в котором он хотел бы купить один билет. Если в указанном ряду нет свободных мест, он согласен на билет в ближайшем ряду. Если есть два ближайших ряда, то клиент покупает в ближнем из них. В первой строке задаются числаn,m,k. Далее следуютkстрок, содержащих одно целое числоA_i – номер ряда, в котором хочет купить билетi-ый покупатель. Для каждого покупателя печатать в отдельной строке номер того ряда, в котором он купил билет.

Исходные данные:

2 2 4

1

1

1

1

Результаты:

1

1

2

2

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

1.9.2.1. Разбить кучу камней заданных весов на 2 части так, чтобы их суммы отличались минимально. В первой строке задаётся число камней n, во второй – n целых чисел – веса камней. В первой строке напечатать два числа – количества камней в первой и второй куче, во второй и третьей строке – веса камней в первой и второй полученной куче.

Исходные данные:

5

1 2 3 4 9

Результат:

4 1

1 2 3 4

9

1.9.2.2. Разбить кучу камней заданных весов на 3 части так, чтобы суммы самой большой и самой маленькой отличались минимально. В первой строке задаётся число камней n, во второй строке – n целых чисел – веса камней. В первой строке напечатать три числа – количества камней в первой, второй и третьей куче, во второй, третьей и четвёртой строках – веса камней в первой, второй и третьей полученных частях.

Исходные данные:

5

1 2 3 4 9

Результат:

2 2 1

1 4

2 3

9

1.9.2.3. Обход шахматным конем всех клеток на доске размера nна n по одному разу. В первой строке задаётся размер доски n, во второй строке задаётся два числа – номер строки и столбца – начальная позиция коня. Напечатать квадратную матрицу чисел с номерами ходов коня. Начальная позиция имеет номер 1. Если решения нет, то напечатать «НЕТ».

Исходные данные:

3

Результат:

НЕТ

1.9.2.4. Обход шахматным конем всех клеток на доске размера nна n по одному разу и возврат в начальную клетку. В первой строке задаётся размер доски n, во второй строке задаётся два числа – номер строки и столбца – начальная позиция коня. Напечатать квадратную матрицу чисел с номерами ходов коня. Начальная позиция имеет номер 1. Если решения нет, то напечатать «НЕТ».

Исходные данные:

3

Результат:

НЕТ

1.9.2.5. Попасть шахматным конем из одной заданной клетки в другую (кратчайший путь) на доске размера nна n. В первой строке задаётся размер доски n, во второй строке задаётся два числа – номер строки и столбца – начальная позиция коня, в третьей строке задаётся два числа – номер строки и столбца – конечная позиция коня. Напечатать квадратную матрицу чисел с номерами ходов коня. Начальная позиция имеет номер 1. Если решения нет, то напечатать «НЕТ».

Исходные данные:

3

1 1

1 3

Результат:

1 0 0

0 0 2

0 0 0

1.9.2.6. Расставить nферзей на шахматной доске размераnи напечатать для каждой строки номер позиции, в которой стоит в этой строке ферзь. Значениеnвводится.

4

Результат:

2 4 1 3

1.9.2.7. Два ферзя на доске угрожают друг другу или нет. На шахматной доске размера nданы позиции двух ферзей. Напечатать «ДА», если ферзи угрожают друг другу. Напечатать «НЕТ» в противном случае. В первой строке задаётся размер доски n, во второй строке задаётся два числа – номер строки и столбца первого ферзя, в третьей строке задаётся два числа – номер строки и столбца второго ферзя.

Исходные данные:

3

1 1

1 3

Результат:

НЕТ

1.9.2.8. Из символов 1, 2, 3 построить последовательность длины N, которая не содержит смежные (соседние) одинаковые подпоследовательности. ЗначениеNвводится.

Исходные данные:

3

Результат:

123

1.9.2.9. Дан целочисленный массив из Nэлементов. Построить дерево Фенвика и вычислять суммы на отрезках для заданных диапазонов. В первой строке задаётся размер массиваN, а во второй – сам массив, элементы идут через один пробел. Далее следует число запросовkи сами запросы, каждый в отдельной строке. Каждый запрос содержит пару индексовiиj. На каждый запрос нужно вывести сумму элементов массива от номераiдо номераjвключительно.

Исходные данные:

11

1 2 3 4 5 6 7 8 9 10 11

3

1 11

2 10

7 8

Результат:

66

54

15

1.9.2.10. Медиана на плоскости. На плоскости находятся Nточек (Nчётно). Никакие три точки не лежат на одной прямой. Ваша задача — выбрать две точки так, что прямая линия, проходящая через них, делит множество точек на две части одинакового размера. Первая строка содержит целое числоN(2 ≤N≤ 10 000). Каждая из следующихNстрок содержит пары целых чиселx_i,y_i(−10⁹≤x_i,y_i≤ 10⁹) — координатыi-й точки. Вывестиномера выбранных точек.

Исходные данные:

4

0 0

1 0

0 1

1 1

Результат:

1 4

Продвинутые задачки.

1.9.3.1. Охотники и приведения. Группа из N охотников сражается с N привидениями. Каждый охотник вооружен протонной пушкой, которая стреляя лучом в привидение, испепеляет его. Луч распространяется по прямой линии и исчезает после попадания в привидение. Охотники договорились о следующей стратегии. Каждый из них выберет по привидению, образовав таким образом N пар Охотник-привидение, а затем одновременно каждый из охотников стреляет в свое привидение. Как известно, очень опасно дать протонным лучам пересечься, поэтому охотники разбиваются на пары так, чтобы лучи не пересеклись. Задача заключается в том, чтобы помочь охотникам разбиться на пары, удовлетворяющие указанному ограничению

Предположим, что позиция каждого охотника и каждого привидения - это фиксированная точка на плоскости и никакие три точки не лежат на одной прямой.

Составьте программу, которая:

считывает позиции охотников и привидений из входного файла;

разбивает множество введенных позиций на пары Охотник-привидение;

выводит полученную последовательность пар в выходной файл.

В первой строке набора находится число N - количество сражающихся охотников (N<=150), В следующих 2*N строках заданы позиции на плоскости N охотников и N привидений (сначала все охотники, затем - все привидения); каждая позиция занимает отдельную строку и представляет собой пару целых чисел, разделенных пробелами, - координаты позиции на плоскости (абсолютные значения координат не превосходят 32000).

Исходные данные:

4

-100 -200

-100 200

-200 -100

200 -100

100 200

100 -200

200 100

-200 100

Результаты:

4

-100 -200 100 -200

-100 200 100 200

-200 -100 -200 100

200 -100 200 100

1.9.3.2. Лопасти и винты. Винт вертолёта состоит из трёх лопастей. Три лопасти подходят для одного винта, если их длины отличаются не более, чем на 1 см. Каждая лопасть может входить только в один винт, но не все лопасти обязательно попадут в какие-то винты. Если решений несколько, можно вывести любое. В первой строке исходных данных указано число лопастей n (n <=100). Во второй строке перечислены n целых чисел – длины лопастей. Написать программу, которая составит из имеющихся лопастей наибольшее число винтов и напечатает их количество в первой строке результата, а в последующих строках тройки номеров лопастей, составляющих собранные винты.

Исходные данные:

7

3 2 7 4 3 2 1

Результат:

2

1 2 3

2 3 4

1.9.3.3. Решить судоку. В матрице 9 на 9 некоторые числа уже расставлены по правилам судоку, остальные клетки пустые (0). Расставить недостающие числа по правилам судоку: в каждой строке, каждом столбце и в каждом фрагменте 3 на 3 встречаются все цифры от 1 до 9. Если решений нет, то напечатать «НЕТ» или напечатать заполненную матрицу.

Исходные данные:

6 7 0 0 0 0 0 3 1

8 3 5 1 6 0 0 2 9

0 0 4 9 3 5 7 0 0

7 6 0 0 0 3 9 4 2

0 0 2 6 8 0 0 0 7

5 9 0 0 0 0 0 0 6

0 0 6 0 0 1 0 0 0

1 2 0 0 0 0 0 0 5

4 0 0 0 0 0 0 0 3

Результат:

6 7 9 8 4 2 5 3 1

8 3 5 1 6 7 4 2 9

2 1 4 9 3 5 7 6 8

7 6 8 5 1 3 9 4 2

3 4 2 6 8 9 1 5 7

5 9 1 7 2 4 3 8 6

9 8 6 3 5 1 2 7 4

1 2 3 4 7 8 6 9 5

4 5 7 2 9 6 8 1 3

1.9.3.4. ГО выявить все группы одноцветных камней на доске NнаN. В первой строке задаётся размер доскиN. В следующихNстроках поNсимволов записано положение камней в игре ГО. Символ ‘.’ обозначает пустое место, символ ‘*’ обозначает чёрный камень, символ ‘O’ – белый камень. Написать программу, которая найдёт и напечатает все группы чёрных камней. В первой строке вывести количество чёрных групп, а далее сами группы в отдельной строке в следующем формате: сначала будет идти натуральное числоk– размер группы, потом будут перечисленыkпар чисел – позиции камней этой группы (номер строки и номер столбца) – числа от 1 доN. Два камня входят в одну группу, если они являются соседями по вертикали или горизонтали, или имеют других соседей из этой группы.

Исходные данные:

5

.O...

**..O

..O**

..*..

*OOO.

Результат:

4

2 2 1 2 2

2 3 4 3 5

1 4 3

1 5 1

1.9.3.5. ГО проверить, что группа одноцветных камней на доске NнаNокружена камнями противника (другого цвета). В первой строке задаётся размер доскиN. В следующихNстроках поNсимволов записано положение камней в игре ГО. Символ ‘.’ обозначает пустое место, символ ‘*’ обозначает чёрный камень, символ ‘O’ – белый камень. В следующей строке заданы координаты одного из камней некоторой группы. Написать программу, которая напечатает «ДА», если группа камней окружена камнями противника. В противном случае напечатать «НЕТ». Два камня входят в одну группу, если они являются соседями по вертикали или горизонтали, или имеют других соседей из этой группы. Группа камней окружена, если все соседние позиции заняты камнями противника.

Исходные данные:

5

*O*..

**..O

..O**

..*..

*OOO.

1 2

Результат:

ДА

1.9.3.6. ГО проверить, что группа одноцветных камней на доске NнаNимеет по крайней мере два глаза, т.е. жизнеспособна. В первой строке задаётся размер доскиN. В следующихNстроках поNсимволов записано положение камней в игре ГО. Символ ‘.’ обозначает пустое место, символ ‘*’ обозначает чёрный камень, символ ‘O’ – белый камень. В следующей строке заданы координаты одного из камней некоторой группы. Написать программу, которая напечатает «ДА», если группа камней имеет два глаза и не может быть окружена и снята с доски. В противном случае напечатать «НЕТ». Два камня входят в одну группу, если они являются соседями по вертикали или горизонтали, или имеют других соседей из этой группы. Группа камней окружена, если все соседние позиции заняты камнями противника.

Исходные данные:

5

*.*..

**ООO

.*O**

.*О..

*OOO.

3 3

Результат:

НЕТ

СПИСОК ЛИТЕРАТУРЫ

Литература по языкам программирования

Бьерн Страуструп. Язык программирования С++. Специальное издание. Бином, Москва, 2001г.

Пышкин, Е.В. Основные концепции и механизмы объектно-ориентированного программирования [Текст] Учебное пособие. BHV, СПб., 2005г.

Дейтел Х. Как программировать на С++. М. БИНОМ, 2001г.

Культин Н. C/C++ в задачах и примерах. BHV, 2003г.

Романов Е.Л. Практикум по программированию на C++. BHV, 2004г.

Климова Л. С++. Решение типовых задач. КУДИЦ-ОБРАЗ, Москва, 2004г.

Прата С. Язык программирования С++. Лекции и упражнения. СПб, ООО ДиаСофтЮП, 2004г.

Шилдт Г. Самоучитель С++. BHV, СПб., 2005г.

Шилдт, Г., С# 4.0: полное руководство [Текст]: Пер. с англ. / Герберт Шилдт. – М., ООО «ИД Вильямс», 2011. - 1056 с.

Сайт со справочной информацией по языкам программирования

http://www.iu.hio.no/~mark/CTutorial/CTutorial.html

http://en.cppreference.com/w/

http://cplusplus.com

Сайты с задачками и соревнованиями

Acm.timus.ru– Уральский Федеральный университет

Codeforces.com- Саратов

Codechef.com- Индия

Icl.kazan.ru/turnir- Казань

Acmp.ru- Красноярск

Литература по алгоритмам

А.Ахо, Д.Хопкрофт, Д.Ульман. Структуры данных и алгоритмы. Диалектика. 2003г.

Долинский М.С. Алгоритмизация и программирование на TurboPascal: от простых до олимпиадных задач. Питер, СПб., 2004г.

Окулов С.М. Программирование в алгоритмах.

Бином. Лаборатория Знаний, Москва, 2004г.

Долинский М.С. Решение сложных и олимпиадных задач по программированию. Учебное пособие. Питер, СПб., 2006г.

Стивен С. Скиена, Мигель А. Ревилла. Олимпиадные задачи по программированию. Рук-во по подготовке к соревнованиям. КУДИЦ-ОБРАЗ, Москва, 2005г.

Потопахин Виталий. TurboPascal. Решение сложных задач.

БХВ-Петербург, СПб., 2006г.

Федор Меньшиков. Олимпиадные задачи по программированию. Питер, СПб, 2006-2007г.

И.Н.Порублев, А.Б.Ставровский. Алгоритмы и программы. Решение олимпиадных задач. «Диалектика», 2007г

Шень А. Программирование. Теоремы и задачи. 2 изд., Изд-во МЦНМО, Москва, 2004г.

Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. 2 изд. »Вильямс», М., 2007 г.

89