Задачи для самостоятельного решения. 1.9.2.1. Разбить кучу камней заданных весов на 2 части так, чтобы их суммы отличались минимально
1.9.2.1. Разбить кучу камней заданных весов на 2 части так, чтобы их суммы отличались минимально. В первой строке задаётся число камней n, во второй – n целых чисел – веса камней. В первой строке напечатать два числа – количества камней в первой и второй куче, во второй и третьей строке – веса камней в первой и второй полученной куче.
Исходные данные:
1 2 3 4 9
Результат:
4 1
1 2 3 4
1.9.2.2. Разбить кучу камней заданных весов на 3 части так, чтобы суммы самой большой и самой маленькой отличались минимально. В первой строке задаётся число камней n, во второй строке – n целых чисел – веса камней. В первой строке напечатать три числа – количества камней в первой, второй и третьей куче, во второй, третьей и четвёртой строках – веса камней в первой, второй и третьей полученных частях.
Исходные данные:
1 2 3 4 9
Результат:
2 2 1
1 4
2 3
1.9.2.3. Обход шахматным конем всех клеток на доске размера n на n по одному разу. В первой строке задаётся размер доски n, во второй строке задаётся два числа – номер строки и столбца – начальная позиция коня. Напечатать квадратную матрицу чисел с номерами ходов коня. Начальная позиция имеет номер 1. Если решения нет, то напечатать «НЕТ».
Исходные данные:
Результат:
НЕТ
1.9.2.4. Обход шахматным конем всех клеток на доске размера n на n по одному разу и возврат в начальную клетку. В первой строке задаётся размер доски n, во второй строке задаётся два числа – номер строки и столбца – начальная позиция коня. Напечатать квадратную матрицу чисел с номерами ходов коня. Начальная позиция имеет номер 1. Если решения нет, то напечатать «НЕТ».
Исходные данные:
Результат:
НЕТ
1.9.2.5. Попасть шахматным конем из одной заданной клетки в другую (кратчайший путь) на доске размера n на n. В первой строке задаётся размер доски n, во второй строке задаётся два числа – номер строки и столбца – начальная позиция коня, в третьей строке задаётся два числа – номер строки и столбца – конечная позиция коня. Напечатать квадратную матрицу чисел с номерами ходов коня. Начальная позиция имеет номер 1. Если решения нет, то напечатать «НЕТ».
Исходные данные:
1 1
1 3
Результат:
1 0 0
0 0 2
0 0 0
1.9.2.6. Расставить n ферзей на шахматной доске размера n и напечатать для каждой строки номер позиции, в которой стоит в этой строке ферзь. Значение n вводится.
Результат:
2 4 1 3
1.9.2.7. Два ферзя на доске угрожают друг другу или нет. На шахматной доске размера n даны позиции двух ферзей. Напечатать «ДА», если ферзи угрожают друг другу. Напечатать «НЕТ» в противном случае. В первой строке задаётся размер доски n, во второй строке задаётся два числа – номер строки и столбца первого ферзя, в третьей строке задаётся два числа – номер строки и столбца второго ферзя.
Исходные данные:
1 1
1 3
Результат:
НЕТ
1.9.2.8. Из символов 1, 2, 3 построить последовательность длины N, которая не содержит смежные (соседние) одинаковые подпоследовательности. Значение N вводится.
Исходные данные:
Результат:
1.9.2.9. Дан целочисленный массив из N элементов. Построить дерево Фенвика и вычислять суммы на отрезках для заданных диапазонов. В первой строке задаётся размер массива N, а во второй – сам массив, элементы идут через один пробел. Далее следует число запросов k и сами запросы, каждый в отдельной строке. Каждый запрос содержит пару индексов i и j. На каждый запрос нужно вывести сумму элементов массива от номера i до номера j включительно.
Исходные данные:
1 2 3 4 5 6 7 8 9 10 11
1 11
2 10
7 8
Результат:
1.9.2.10. Медиана на плоскости. На плоскости находятся N точек (N чётно). Никакие три точки не лежат на одной прямой. Ваша задача — выбрать две точки так, что прямая линия, проходящая через них, делит множество точек на две части одинакового размера. Первая строка содержит целое число N (2 ≤ N ≤ 10 000). Каждая из следующих N строк содержит пары целых чисел xi, yi (−109 ≤ xi, yi ≤ 109) — координаты i-й точки. Вывести номера выбранных точек.
Исходные данные:
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).
Исходные данные:
-100 -200
-100 200
-200 -100
200 -100
100 200
100 -200
200 100
-200 100
Результаты:
-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 целых чисел – длины лопастей. Написать программу, которая составит из имеющихся лопастей наибольшее число винтов и напечатает их количество в первой строке результата, а в последующих строках тройки номеров лопастей, составляющих собранные винты.
Исходные данные:
3 2 7 4 3 2 1
Результат:
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. Два камня входят в одну группу, если они являются соседями по вертикали или горизонтали, или имеют других соседей из этой группы.
Исходные данные:
.O...
**..O
..O**
..*..
*OOO.
Результат:
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’ – белый камень. В следующей строке заданы координаты одного из камней некоторой группы. Написать программу, которая напечатает «ДА», если группа камней окружена камнями противника. В противном случае напечатать «НЕТ». Два камня входят в одну группу, если они являются соседями по вертикали или горизонтали, или имеют других соседей из этой группы. Группа камней окружена, если все соседние позиции заняты камнями противника.
Исходные данные:
*O*..
**..O
..O**
..*..
*OOO.
1 2
Результат:
ДА
1.9.3.6. ГО проверить, что группа одноцветных камней на доске N на N имеет по крайней мере два глаза, т.е. жизнеспособна. В первой строке задаётся размер доски N. В следующих N строках по N символов записано положение камней в игре ГО. Символ ‘.’ обозначает пустое место, символ ‘*’ обозначает чёрный камень, символ ‘O’ – белый камень. В следующей строке заданы координаты одного из камней некоторой группы. Написать программу, которая напечатает «ДА», если группа камней имеет два глаза и не может быть окружена и снята с доски. В противном случае напечатать «НЕТ». Два камня входят в одну группу, если они являются соседями по вертикали или горизонтали, или имеют других соседей из этой группы. Группа камней окружена, если все соседние позиции заняты камнями противника.
Исходные данные:
*.*..
**ООO
.*O**
.*О..
*OOO.
3 3
Результат:
НЕТ
СПИСОК ЛИТЕРАТУРЫ
Литература по языкам программирования
Бьерн Страуструп. Язык программирования С++. Специальное издание. Бином, Москва, 2001г.
Пышкин, Е.В. Основные концепции и механизмы объектно-ориентированного программирования [Текст] Учебное пособие. BHV, СПб., 2005г.
Дейтел Х. Как программировать на С++. М. БИНОМ, 2001г.
Культин Н. C/C++ в задачах и примерах. BHV, 2003г.
Романов Е.Л. Практикум по программированию на C++. BHV, 2004г.
Климова Л. С++. Решение типовых задач. КУДИЦ-ОБРАЗ, Москва, 2004г.
Прата С. Язык программирования С++. Лекции и упражнения. СПб, ООО ДиаСофтЮП, 2004г.
Шилдт Г. Самоучитель С++. BHV, СПб., 2005г.
Шилдт, Г., С# 4.0: полное руководство [Текст]: Пер. с англ. / Герберт Шилдт. – М., ООО «ИД Вильямс», 2011. - 1056 с.