232. Несвязные области. На плоскость Z0 Г произвольным образом размещают JV произвольных прямоугольников со сторонами, параллельными осям координат. Взаимное расположение прямоугольников допускает их пересечение. Требуется составить алгоритм-программу определения количества несвязных областей, на которые прямоугольники разбивают плоскость XOY. Входные и выходные данные. В первой строке входного файла содержится число N. В каждой из следующих Л'строк располагаются координаты одного прямоугольника: (а,-, Ь,) - координаты левого верхнего угла; (г,-, d,) - координаты правого нижнего угла. Выходной файл должен содержать единственное число, равное количеству

несвязных областей.

Пример файла исходных данных: б

Выходной файл для данного примера:

233. Площадь участка. Требуется составить алгоритм-программу определения площади участка, ограниченного замкнутой ломаной, составленной из отрезков единичной длины, параллельных

осям координат. Исходные данные - координаты концов отрезков - задаются в текстовом файле. Найденную площадь сохранить в файле результатов. Отметим, что отрезки, составляющие границу участка, во входном файле могут следовать в произвольном порядке.

Пример файла исходных данных:

24 - количество отрезков

1 1 1 2

3 0 3 1

40 41 41 42

50 51 51 52 52 53

Пример файла результатов:

11 - площадь участка

234. Совмещение ломаных. Две ломаные построены по ребрам сеточной области с целочисленными координатами. Требуется составить алгоритм-программу проверки совпадения двух ломаных, составленных из отрезков, с точностью до параллельного переноса и поворота на 90°, 180°, 270°. Исходные данные - число отрезков ломаных и значения координат их концов - определяются в текстовом файле. Выходной файл результатов должен содержать признак если ломаные совпадают, и 0 - в противном случае.

Пример файла исходных данных:

4 - количество отрезков первой ломаной

00 10 30 20 10 20 30 31 2 - количество отрезков второй ломаной 11 14 04 14

Пример файла результатов:

1 - ломаные совпадают.

235. Деление на равные половины. Текстовый файл содержит последовательность целых чисел - веса элементов: ах, а2,..., ап. Составить алгоритм-программу деления этих предметов на две группы так, чтобы общие веса двух групп были максимально близкими друг к другу. Результаты расчетов сохранить в текстовом файле. Исходные данные представлены в текстовом файле со следующей структурой. Первая строка: п - количество чисел. Следующие строки содержат веса элементов

Пример файла исходных данных:

6 3 14 5.

Пример файла выходных данных:

б 3 1 - первая группа 4 5 - вторая группа.

236. Простой круг. Натуральные числа 1, я (я - чётное число) располагают по кругу как на диаграмме. Первое число по кру-

гу всегда должно быть Все остальные числа располагаются таким образом, чтобы сумма двух соседних чисел по кругу была простым числом, начиная с 1. Составить алго-определения всех указанных расстановок. Исходное число я задается в текстовом файле. Результаты расчетов сохранить в текстовом файле.

237. Почтальон. Дана последовательность из Л^улиц (по названиям) . Каждая улица соединяет два перекрестка. Первая и последняя буквы названия улицы определяют два перекрестка для этой улицы. Длина названия улицы определяет стоимость проезда по ней. Все названия улиц состоят из строчных символов алфавита. Например, название улицы computer показывает, что улица находится между перекрестками с и -г . адлина ее 8. Нет улиц, которые имеют одинаковые первые и последние символы. Есть не более одной улицы, напрямую соединяющей два любых перекрестка. Всегда есть путь между любыми двумя перекрестками. Число улиц с данным перекрестком называется степенью этого перекрестка. Есть не более двух перекрестков нечетной степени. Все остальные перекрестки - четной степени. Составить алго-определения минимальной стоимости проезда по всем улицам, по крайней мере, один раз. Путешествие должно начаться и закончиться на одном и том же перекрестке. Стоимость проезда по улице равна ее длине.

Пример входного файла

one two three

Пример выходного файла

238. Пересечение с отрезками. Имеются /Уотрезков, концы которых задаются двумя парами точек на плоскости: (xl[/], yl[i]) и (x2[i], у2[/]). Требуется составить алгоритм-программу определе-

имя такой прямой линии, которая пересекает как можно большее количество заданных отрезков. Исходные данные определяются в текстовом файле, имеющем следующую структуру. Первая строка: N - количество отрезков. Вторая и следующие строки: xl[i], yl[i] nx2[ij, y2[i] - пары точек на плоскости (концы отрезков). Результаты расчетов сохранить в выходном текстовом файле t имеющем следующую структуру данных. Строки файла - номера отрезков в возрастающем порядке, которые пересекает найденная прямая. Если найденная прямая линия проходит через концы отрезков, то это учитывать как пересечение. 239. Простые суммы. Даны числа от 1 до л, К и < 5000. Требуется составить разбиения данных чисел на ми-

нимальное количество групп, в каждой из которых сумма является простым числом. Например, при п = 8 такими группами могут быть: {1,4, 5, 6, 7}, {2, 3, 8}. Примечание: число 1 не считается простым. Файл исходных данных содержит число я. Выходной файл должен содержать п чисел (номера которые показывают в

какую группу входит соответствующее по порядку число. Для нумерации групп должны использоваться идущие подряд натуральные числа, начиная с единицы.

Пример файла исходных данных:

Пример файла выходных данных:

12211112.

240. Движение плота. Квадратное озеро, покрытое многочисленными островами, задается матрицей размером ; N. Каждый элемент матрицы - либо символ - решетка, обозначающий остров, либо символ - минус, обозначающий участок воды. В верхнем левом углу озера находится квадратный плот размером Мх Л/клеток. За один шаг плот может перемещаться на одну клетку по горизонтали или вертикали. Составить для определения минимального числа шагов, за которое плот жет достигнуть правого нижнего угла озера. Входной файл исходных данных содержит числа Ми N. В следующих Строках располагается матрица, представляющая озеро. Выходной файл должен содержать единственное число - количество необходимых шагов. Если правого нижнего угла достичь невозможно, то выходной файл должен содержать число -1 (минус один).

Выходной файл для данного примера:

241. Пират в подземелье. В поисках драгоценных камней пират проваливается в подземелье. План подземелья - матрица NX M комнат с драгоценными камнями. Камни из одной комнаты имеют одинаковую стоимость. Пирату в каждой комнате разрешается взять с собой лишь один камень и следовать в любую другую соседнюю с ним комнату. Каждую из комнат пират может посещать неоднократно. Требуется составить алгоритм-программу определения маршрута посещения пиратом К комнат лабиринта таким образом, чтобы он набрал камней на максимально возможную сумму. Входные и выходные данные. В первой строке входного файла содержатся числа N, Мп К. В следующих Л^строкахраспо-лагается матрица N М лабиринта. Каждый элемент матрицы представляется стоимостью камня соответствующей комнаты. Маршрут начинается с левой верхней угловой комнаты лабиринта. Выходной файл должен содержать единственное число, равное общей стоимости взятых с собой камней.

Пример файла исходных данных:

3 4 7 1111 112 1 112 3

Выходной файл для данного примера:

242. Оставить условие задачи №241 и предписать пирату, чтобы он за К шагов еще и вернулся в начальную комнату лабиринта.

Пример файла исходных данных:

8 2

- #-#-##-

- ##

243. Задана Д.Андре. Составить алгоритм-программу поиска всех способов заполнения числами 1,2,.... п массива из п ячеек

так, чтобы во всех строках и столбцах они располагались в возрастающем порядке (слева-направо и сверху-вниз). Исходное число п задается в текстовом файле. Результаты заполнения сохранить в файле результатов.

244. Сумма чисел. Дано натуральное число т. Вставить между некоторыми цифрами: 1, 2, 3, 4, 5, 6, 7, 8, 9, записанными именно в таком порядке, знаки +, - так, чтобы значением получившегося выражения было число т. Например, если т = 122, то подойдет следующая расстановка знаков: 12 + 34- 5 -6+ 78 + 9. Требуется составить определения всех расстановок знаков +, отвечающих условию задачи. Исходное число т задается во входном текстовом файле. Выходной текстовый файл должен содержать найденные расстановки знаков. Если требуемая расстановка знаков невозможна, то выходной файл должен содержать число 1.

245. Обслуживание авиалиний. Имеется некоторый город М, который связан маршрутами с городами Ах.Аг,...,Ап. Пусть, согласно расписанию, маршрут в интервале времени [a bj] Другими словами, , - это тот момент, начиная с которого самолет связан с маршрутом a - тот момент, когда эта связь прекращается. Таким образом, задано п временных интервалов [aj,bi],i = 1,2,..., п. Требуется составить алгоритм-программу определения минимального числа самолетов, достаточного

для обслуживания всех рейсов.

246. Симпатичный прием. Генерал желает устроить юбилей с максимальным числом гостей из своих знакомых. Стремясь сделать юбилейный вечер приятным, он должен организовать все так, чтобы на этом вечере присутствовали люди, симпатизирующие друг другу. Оказалось, что у генерала п знакомых. Каждый из них получил соответствующий номер от 1 до п. Исходные данные задачи - это список пар симпатизирующих гостей генерала. Составить алгоритм-программу определения по исходным данным максимально возможного числа гостей на юбилейном вечере и сохранить его в выходном файле результатов.

247. Таблицаинверсий. Составить алгоритм-программу определения таблицы инверсий did2...dn перестановки {аь а2,..., 0 ), где dj - число элементов, большиху и расположенных левее j (см.п. 1.13). Исходные данные - число п и произвольная перестановка чисел 1, 2, ..., п - определяются в текстовом файле. Выходной файл результатов должен содержать найденную таблицу инверсий.

Пример файла исходных данных:

5 - число п

5 3 4 2 1 - перестановка

Пример файла результатов:

4 3 110 - таблица инверсий.

1. Множество D всех сочетаний С* разобьем на два непересекающихся подмножества D = D\ и D2, где D\ n D2 = 0. Множество включает все сочетания с произвольным фиксированным элементом, Z>j = С*:/. Множество D2 включает все сочетания без выделенного фиксированного элемента, Z)2 =С^у. Следовательно, С* =Ск~1 +Ск.

Я 11-1 11-1

2. Используйте бином Ньютона (1+л) УС*Х*.

3. Применить индукцию по п. 7. 2 .

л

8. Воспользуйтесь тождеством (а + А) = ]ГС*а 2> ~ .

Р. Воспользуйтесь тождеством (1 + jc)m(l +jc) = (1 + x)m+. 10. Воспользуйтесь тождеством (1 + (1 + 1)) = 3 .

11-13. Воспользуйтесь тождеством + х) =]у'

14. Указание. Воспользуйтесь полиномиальным разложением формулы (1 + 1 + ... + 1) = к .

15. 21. 16. С2+2. 17. 2л2 х 2л2. 18. 2л2х (2л2 - 2л). 19. 2 т. 20.Л53,С4231 21. З6. 22.63. 23. С2 - двустороннихсловарей, А2- односторонних словарей, л - словарей при переводе по циклу. 24. Ат. 25. Д5,7,3) = -$fy = С[5СщС] . 26. С™+т. 27. Сгп.

28. Ат +А^ + Ап - учитывается порядок имен. 29. Д2,2,2,1,1).

31. = 32.

33. где деление на число п обозначает совпадение соседей

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

34. Cf0(Cf0 -1)(Cf0 -2) =A3r6. 35. С£,С£,С£.

36. C,f((C62C2C2)/3!) = 15СЯ6. 37. Слб((С2С2С|)/3!) = 15СП6.

38. ((2л)!/(2!) )/л! - неупорядоченное разбиение множества.

39. См. решение задач 7 и 8. 40. 9!-С^7!3!+С325!3!3!3!-С333!3!3!3!. 42. (С^ХС/з )3 + (С|(С!23 )2ХС/з )2. 43.3 44. З17. 45. т .

4Wl %+/я-Г ч/ (п-т)+т-\ Sl-l1 и(л-*)+т-2 с(л->~>;. )+OT-Jt-l1

51. 54, Л\. 52. 53. CC32i, С\-С\Х-С\С\ГС\С\Х

55. Р(3,2,ЗЛ)- 56. CCf 57. (1 + + а2)...(1 +а„),

1-р 1 1-ру2 1- а

- . 59. п {п/р] - столько чисел среди 12V!

1-Л 1-Л 1-А и не кратных р. Всего произведений С*, тогда число произведений, кратных/?, равно С,; -Ct\nip) 60. л! - - т + .(объединить т элементов в один элемент).

61. 2 (С2)2 =ni(fl~l)% способов поставить две ладьи так, чтобы

они не угрожали друг другу. - способов по-

ставить две ладьи так, чтобы они угрожали друг другу. Для ответа на вопрос задачи осталось сравнить указанные числа. 63. q20+С20 =90. 66.18. 68.31. 71. с£2 С* 1.

72. 205223000, см. п. 1.13. 73. 27354186, см. п. 1.13. 75. Указание: воспользуйтесь тем, что перестановка двух соседних меток N и Мне оказывает влияния на произведение 2 ~т. 76.Щп2 . 77. (kn)\f{(k\) n\). 78. (30)!/((1О!)33!), (30)!/((3!)1010!).

79. (С}С2/2\)(С1£С[1). 80. (С20С2С2С42С22)/5!= 10!/((2!)5 5!). 81. 9!/((1!)1(2!)41!4!). 82. 9!/((3!)33!). 83. Р(2,2,2,2,2,2,1,1,1,1). 84. С^С^. 85. 48 -С^З8 + С228 -С4318 - воспользоваться формулой включений и исключений для свойств: - пустой этаж, /=1,4. 87. Л|,4,- 88.(9°+91) + 92 +934-...+91

89. 90. C,(Jj(M -1, где -1 обозначает число 0.

91. Ч+1.92. С^/.. 93. Схема посева сортов пшеницы должна соответствовать латинскому квадрату т х т.

к

94. 95. 96. £(-1)С\ (£-/) .

k-r . k-r

97- r+Pk-f-T =ckr£(-nrk-r<r-r~i}m

A=0 A=0 m

99. Х(-1)*С*(т-А)!-т!2;4г-* п! f -

*=0 A=0

100. X(-i) C;+iC;-(m-r-/:)!=>js=-1. *=0 л=о

102. Введем обозначения. Рк - свойство, что к-я пара враждую-шихрыцарей сидит ряд ом, к =1,2,..., л. ДО) - размещение рыцарей, которые не обладают ни одним из указанных свойств, т.е. требуемые размещения по условию задачи. ДО) = W(0) - W{1)+ + W{2) - ... + {-\)nW{n), где Щк) - количество размещений рыцарей, когда к и более враждующих пар сидят вместе. Объединим каждую из к указанных пар в один объект. Тогда имеем 2л - к объектов, которые можно расположить (2л - Л)! способами. В каждой из к заданных пар врагов можно поменять местами 2к способами. Выбор к враждующих пар можно сделать С? способами. Следова-

п

тельно, искомое число равно ДО) = У(-1) С 2 (2 л-к)1

103. 542. 104. 734. 106. 20%, 60%, 70%. 107. 2, 6, 3. 109-110. Решение подобного уравнения рассмотрено в п.1.1.

11L § f H*% 111 С -2 Действительно> выбирая из л-2 три различных предмета способами, можно однозначно отобразить их в разбиения, требуемые по условию. Если выбраны предметы с номерами < к2 < А 3, то в исходном ряду их номера будут кх<к2 + 1<к3 + 2.

ИЗ. ±(-1У g Ц§. 114. .2.2] (2л)! = (12) (2л)!.

115. 2 , 116. п +1. 117. Количество прямоугольников размера

i xj равно (л - + 1) х -j + 1). Каждый прямоугольник учитывается в сумме столько раз, какова его площадь. Тогда сумма рав-

ЪЪ, ,w i\ ibt . ivl (и(л + 1)( +2)У на 1 n 2> : n -i - I

/=!/=! u=i ) v ч J