Предыдущая глава
1028 Даны натуральные числа m, а1, ...,an.
В последовательности а1, ...,an выбрать подпоследовательность
ai1, аi2, .... аik (0 1≤ i1
При решении этой задачи полезно следующее соображение. Чтобы выбрать подпоследовательность из
последовательности a1 ,..., аn, нужно про каждый член
a1 ... ..., аn решить, принимается он в подпоследовательность или нет.
Может возникнуть следующая ситуация: относительно членов а1, ..., аi, (i < n)
приняты какие-то решения, после этого обнаружилось, что, как бы мы ни распоряжались остальными n-i
членами, нам все равно не удастся получить подпоследовательность, удовлетворяющую поставленному
условию (например, если сумма нескольких положительных чисел больше m, то невозможно добавить к
ним еще несколько положительных чисел так, чтобы сумма стала равна m). В этом случае можно сразу
исключить из рассмотрения все подпоследовательности, первые члены которых выбраны из
a1, ..., аi в соответствии с принятыми решениями.
1029 Получить все расстановки 8 ладей на шахматной доске,
при которых ни одна ладья не угрожает другой.
Здесь полезно соображение, аналогичное приведенному
в предыдущей задаче. Если расставлены ладьи в i первых вертикалях (i < 8) и обнаружилось, что i-я
ладья угрожает ладье в какой-то вертикали с меньшим номером, то можно далее не заниматься теми
расстановками ладей, которые предполагают то же самое расположение в первых вертикалях *).
1030 Дано натуральное число m. Получитьт расстановок 8 ферзей на шахматной доске, при которых ни один из ферзей не угрожает другому. Если т больше, чем общее число таких расстановок, то следует получить все расстановки.
1031 Получить все перестановки элементов 1, .... 6.
1032 Получить все сочетания из 10 элементов 1, ..., 10, по 4 элемента в каждом.
1033 Получить все размещения из 9 элементов 1, ..., 9, по 5 элементов в каждом.
1034 Получить все полные перестановки 10 элементов 1, ..., 10 (перестановка р1 ..., рn элементов 1, ..., n называется полной, если pi ≠i для i=1, ..., n).
1035 Указать маршрут коня, начинающийся на одном заданном поле шахматной доски и оканчивающийся на другом. Никакое поле не должно встречаться в маршруте дважды.
1036 Лабиринт может быть задан матрицей соединений, в которой для каждой пары комнат указано, соединены ли они коридором (см. задачу 626). Даны матрица соединений для лабиринта из п комнат и номера комнат i, j (11≤i1≤n, 11≤j1≤n). Построить путь из комнаты с номером i в комнату с номером j.
1037 Дана матрица соединений некоторой линии (см. задачу 626), содержащей 6 узлов. Выяснить, существует ли замкнутый путь, состоящий из некоторых звеньев линии, который проходит через каждый из 6 узлов ровно один раз. Если такой путь существует, то построить соответствующую ему последовательность номеров узлов. (Для линии, изображенной на рис. 33, последовательность узлов будет, например, 1, 2, 3, 4, 5, 6.)
1038 Имеется n городов. Некоторые из них соединены дорогами известной длины. Вся система дорог задана квадратной матрицей порядка n, элемент аij которой равен некоторому отрицательному числу, если город i не соединен напрямую дорогой с городом j и равен длине дороги в противном случае (i, j=1,...,n).
1039 Найти такую расстановку пяти ферзей на шахматной доске, при которой каждое поле будет находиться под ударом одного из них.
1040 Найти такую расстановку двенадцати коней на шахматной доске, при которой каждое поле будет находиться под ударом одного из них.
1041 Найти такую расстановку восьми слонов на шахматной доске, при которой каждое поле будет находиться под ударом одного из них.
1042 В данной последовательности действительных чисел a1, ..., а20 выбрать возрастающую подпоследовательность наибольшей длины.
1043 Построить все правильные скобочные выражения (см. задачу 1027) длины 10, т.е. те, которые содержат по 5 левых и по 5 правых круглых скобок.
1044 Имеется n предметов, веса которых равны а1, ... ..., аn. Разделить эти предметы на две группы так, чтобы общие веса двух групп были максимально близки.
1045 Получить последовательность а1, ...,an цифр О, 1, 2, в которой нет смежных одинаковых участков (например, последовательность 2, 0, 1, 1, ... не годится, так как рядом расположены два одинаковых члена 1; последовательность 2, 1, 0 1, 2, 1, 0 1, ... не годится, так как рядом расположены два одинаковых участка 2, 1, 0, 1 и т.д.).
1046 "Задача о рюкзаке". Имеется m различных предметов, известны вес каждого предмета и его стоимость. Определить, какие предметы надо положить в рюкзак, чтобы общий вес не превышал заданной границы, а общая стоимость была максимальна. Решить эту задачу для m предметов, веса которых в килограммах равны р1, .... рm, стоимости - С1 ..., сm. Вес рюкзака не должен превышать 50 кг.
| Предыдущая глава |
К началу | Следующая глава |