QalOGUGtk0
.pdfВариант № 11.
1. Разработать и отладить программу, методом динамического программи-
рования решающую задачу о порядке перемножения цепочки матриц. Ис-
ходный массив размерностей перемножаемых матриц ввести из входного файла. Вывести матрицу стоимостей S и матрицу тех k, при которых достигается минимум, на экран.
2.На входе: два множества А и В, элементами которых являются цифры: {0, 1, …, 9}.
1)Сформировать дополнения D = !A и F = !B к каждому из этих множеств;
2)сгенерировать и пронумеровать все (n+2)-элементные перестановки с повторениями из элементов множества D (где n – мощность множества D);
3)для каждой комбинации подсчитать произведение всех чётных цифр;
4)результат вывести в выходной текстовый файл.
3.Изменить исходный способ хранения сильно ветвящегося дерева на заданный. Представление дерева на входе (из входного файла): имя вершины; ссылки на всех её сыновей. Представление дерева на выходе: имя вершины; ссылки на левого сына, правого брата, отца.
4.Неориентированный граф представлен матрицей инцидентности. Прочитав матрицу инцидентности из входного текстового файла, найти
вершину (или вершины) с максимальной степенью.
Вариант № 12.
1. Разработать и отладить программу, по заданным n и m генерирующую все размещения с повторениями. Каждая комбинация должна состоять из элементов множества {1, 2, ..., n} и содержать m элементов. Для каждой
m
комбинации подсчитать сумму S вида: ( 1)i (xi / xi 1) .
i 2
Пронумеровав все комбинации, вывести их и соответствующие им суммы S в выходной текстовый файл.
2.На входе: два множества А и В, элементами которых являются цифры: {0, 1, …, 9}.
1)Сформировать объединение первого из них с дополнением ко второму D = A U !B;
2)сгенерировать и пронумеровать все трёхэлементные сочетания с повторениями из элементов множества D;
3)для каждой комбинации подсчитать квадрат суммы входящих в неё цифр;
4)результат вывести в выходной текстовый файл.
3.Изменить исходный способ хранения ориентированного псевдографа на заданный. Представление псевдографа на входе (из входного
131
файла): матрица смежности. Представление псевдографа на выходе: список рёбер.
4. Неориентированный граф задан списком рёбер. Прочитав список рёбер из входного текстового файла, найти все мосты данного графа.
Указание. Для каждого ребра поочерёдно проделать следующее: удалив это ребро, получить новый граф. Для этого графа, использую процедуру обхода в глубину, подсчитать количество компонент связности.
Вариант № 13.
1. Разработать и отладить программу, по данным весам и стоимостям с по-
мощью метода ветвей и границ решающую задачу об оптимальной вы-
борке (о рюкзаке) для n 11 объектов. Считать исходные данные веса и цены с экрана. Вывести оптимальную выборку в выходной текстовый файл.
2.На входе: два множества А и В, элементами которых являются цифры: {0, 1, …, 9}.
1)Сформировать пересечение D этих множеств;
2)сгенерировать и пронумеровать все перестановки из элементов множества D;
3)для каждой перестановки подсчитать сумму цифр, НЕ делящихся на три без остатка;
4)результат вывести в выходной текстовый файл.
3.Изменить исходный способ хранения сильно ветвящегося дерева на заданный. Представление дерева на входе (из входного файла): имя вершины; ссылки на левого сына, правого и левого брата. Представление дерева на выходе: имя вершины; ссылка на отца.
4.Неориентированный граф, содержащий от n = 3 до n = 8 вершин, представлен матрицей инцидентности. Прочитав матрицу инцидентности из входного текстового файла, найти все треугольники (простые циклы, содержащие 3 ребра) этого графа.
Указание. Сформировать все трёхэлементные подмножества множества вершин {1, 2, ..., n}. Для каждого подмножества проверить наличие соответствующих рёбер.
Вариант № 14.
1. Разработать и отладить программу, по заданным n и m генерирующую все сочетания. Каждая комбинация должна состоять из элементов множества {1, 2, ..., n} и содержать m элементов (m n). Для каждой комбинации
m
подсчитать сумму S вида: ( 1)i (xi xm i 1) .
i 1
132
Пронумеровав все комбинации, вывести их и соответствующие им суммы S в выходной текстовый файл.
2. На входе: два множества А и В, элементами которых являются символы; символ x.
1)Проверить, принадлежит ли x множеству А. Если “да”, то перенести его в множество В;
2)сгенерировать и пронумеровать все двухэлементные размещения с повторениями из элементов изменённого множества А;
3)результат вывести в выходной текстовый файл.
3.Изменить исходный способ хранения ориентированного псевдографа на заданный. Представление псевдографа на входе (из входного файла): матрица инцидентности. Представление псевдографа на выходе: матрица смежности.
4.Неориентированный граф задан списками смежности. Прочитав списки смежности из входного текстового файла, найти любую цепь, соединяющую две данные вершины.
Указание. Использовать процедуру обхода графа в глубину.
Вариант № 15.
1. Разработать и отладить программу, по данному значению n 5 генерирующую те подмножества множества {1, 2, ..., n}, которые содержат от двух до четырех элементов. Для каждой комбинации подсчитать сумму S
m 1
вида: (xi / xi 1) .
i 0
Пронумеровав все комбинации, вывести их и соответствующие им суммы S в выходной текстовый файл.
2. На входе: два множества А и В, элементами которых являются цифры: {0, 1, …, 9}.
1) Сформировать разность дополнений к этим множествам: D = (!А) \ (!В); 2) сгенерировать и пронумеровать все перестановки из элементов множества D;
3) для каждой перестановки подсчитать произведение нечётных цифр;
4) результат вывести в выходной текстовый файл.
3. Изменить исходный способ хранения сильно ветвящегося дерева на заданный. Представление дерева на входе (из входного файла): имя вершины; ссылки на левого сына, правого и левого брата. Представление дерева на выходе: имя вершины; ссылки на всех ее сыновей.
4. Неориентированный граф представлен матрицей инцидентности. Прочитав матрицу инцидентности из входного текстового файла, составить списки смежности для графа, являющегося дополнением к данному графу.
133
Вариант № 16.
1. Разработать и отладить программу, по заданным n и m генерирующую все композиции (z1, z2, …, zn) натурального числа m. Слагаемые композиции должны отвечать условию: zi > 0. Для каждой композиции подсчитать про-
n 1
изведение П вида: (zi 1 zi 1) .
i 2
Пронумеровав все комбинации, вывести их и соответствующие им произведения П в выходной текстовый файл.
2.На входе: два множества А и В, элементами которых являются символы.
1)Сформировать декартово произведение D = A×B этих множеств;
2)сгенерировать и пронумеровать все двухэлементные размещения из элементов множества D;
3)результат вывести в выходной текстовый файл.
3.Изменить исходный способ хранения ориентированного псевдографа на заданный. Представление псевдографа на входе (из входного файла): список рёбер. Представление псевдографа на выходе: матрица инцидентности.
4.Неориентированный граф задан списками смежности. Прочитав списки смежности из входного текстового файла, найти любое остовное дерево (остовный лес) данного графа.
Указание. Использовать процедуру обхода графа в глубину.
Вариант № 17.
1. Разработать и отладить программу, по заданным n и m генерирующую все перестановки с повторениями. Каждая комбинация должна состоять из элементов множества {1, 2, ..., n} и содержать m элементов (m n). Для каждой комбинации подсчитать произведение П её элементов.
Пронумеровав все комбинации, вывести их и соответствующие им произведения П в выходной текстовый файл.
2.На входе: два множества А и В, элементами которых являются цифры: {0, 1, …, 9}.
1)Сформировать объединение дополнений: D = !A U !B;
2)сгенерировать и пронумеровать все перестановки из элементов множества D;
3)для каждой перестановки подсчитать произведение суммы всех чётных цифр и суммы всех нечётных цифр;
4)результат вывести в выходной текстовый файл.
3.Изменить исходный способ хранения сильно ветвящегося дерева на заданный. Представление дерева на входе (из входного файла): имя
134
вершины; ссылки на левого брата и на отца. Представление дерева на выходе: имя вершины; ссылки на самого левого сына и правого брата.
4. Неориентированный граф задан списками смежности. Прочитав списки смежности из входного текстового файла, подсчитать количество рёбер данного графа. Проверить, является ли граф полным.
Вариант № 18.
1. Разработать и отладить программу, по заданным n и m генерирующую все размещения. Каждая комбинация должна состоять из элементов множества {1, 2, ..., n} и содержать m элементов (m n). Для каждой комбинации подсчитать сумму S ее нечётных элементов.
Пронумеровав все комбинации, вывести их и соответствующие им суммы S в выходной текстовый файл.
2.На входе: два множества А и В, элементами которых являются цифры: {0, 1, …, 9}.
1)Сформировать объединение первого из них с дополнением ко второму D = A U !B;
2)сгенерировать и пронумеровать все двухэлементные сочетания из элементов множества D;
3)для каждого сочетания подсчитать произведение суммы всех чётных цифр и суммы всех нечётных цифр;
4)результат вывести в выходной текстовый файл.
3.Изменить исходный способ хранения ориентированного псевдографа на заданный. Представление псевдографа на входе (из входного файла): списки смежности. Представление псевдографа на выходе: список рёбер.
4.Неориентированный граф представлен матрицей инцидентности. Прочитав матрицу инцидентности из входного текстового файла, найти все вершины графа, у которых степени равны.
Вариант № 19.
1. Разработать и отладить программу, по заданным n и m генерирующую все сочетания с повторениями. Каждая комбинация должна состоять из элементов множества {1, 2, ..., n} и содержать m элементов. Для каждой комбинации подсчитать сумму S ее неповторяющихся элементов.
Пронумеровав все комбинации, вывести их и соответствующие им суммы S в выходной текстовый файл.
2. На входе: два множества А и В, элементами которых являются цифры: {0, 1, …, 9}.
1) Сформировать пересечение D этих множеств;
135
2)сгенерировать и пронумеровать все (n+2)-элементные перестановки с повторениями из элементов множества D (где n – мощность множества D);
3)для каждой комбинации подсчитать сумму цифр, НЕ делящихся на три без остатка;
4)результат вывести в выходной текстовый файл.
3. Изменить исходный способ хранения сильно ветвящегося дерева на заданный. Представление дерева на входе (из входного файла): имя вершины; ссылка на отца. Представление дерева на выходе: имя вершины; ссылки на самого левого сына и правого брата.
4. Неориентированный граф задан списком рёбер. Прочитав список рёбер из входного текстового файла, найти степени вершин в графе, который является дополнением к данному графу.
Вариант № 20.
1.Разработать и отладить программу, генерирующую все разбиения натурального числа n. Для каждой комбинации подсчитать произведение П ее нечётных элементов.
Пронумеровав все комбинации, вывести их и соответствующие им произведения П в выходной текстовый файл.
2.На входе: два множества А и В, элементами которых являются символы; символы x и y.
1) Проверить, принадлежит ли x множеству А. Если “да”, то перенести его во множество В; 2) сгенерировать и пронумеровать все двухэлементные размещения из
элементов изменённого множества А; 3) результат вывести в выходной текстовый файл.
3.Изменить исходный способ хранения ориентированного псевдографа на заданный. Представление псевдографа на входе (из входного файла): матрица инцидентности. Представление псевдографа на выходе: списки смежности.
4.Неориентированный граф задан матрицей инцидентности. Прочитав матрицу инцидентности из входного текстового файла, найти все точ-
ки сочленения данного графа.
Указание. Для каждой вершины поочерёдно проделать следующее: удалив эту вершину вместе со всеми инцидентными ей рёбрами, получить новый граф. Для этого графа, использую процедуру обхода в глубину, подсчитать количество компонент связности.
Вариант № 21.
1. Разработать и отладить программу, по заданным n и m генерирующую все композиции (z1, z2, …, zn) натурального числа m. Слагаемые композиции
136
должны отвечать условию: zi 0. Для каждой композиции подсчитать про-
изведение П вида: n ( 1)i zi .
i 1
Пронумеровав все комбинации, вывести их и соответствующие им произведения П в выходной текстовый файл.
2.На входе: два множества А и В, элементами которых являются цифры: {0, 1, …, 9}.
1)Сформировать разность дополнений к этим множествам: D = (!А) \ (!В);
2)сгенерировать и пронумеровать все (n+2)-элементные перестановки с повторениями из элементов множества D (где n – мощность множества D);
3)для каждой перестановки подсчитать сумму нечётных цифр;
4)результат вывести в выходной текстовый файл.
3.Изменить исходный способ хранения сильно ветвящегося дерева на заданный. Представление дерева на входе (из входного файла): имя вершины; ссылки на самого левого сына и правого брата. Представление дерева на выходе: имя вершины; ссылка на отца.
4.Неориентированный граф, содержащий от n = 3 до n = 8 вершин, представлен списками смежности. Прочитав списки смежности из входного текстового файла, найти все треугольники (простые циклы, содержащие 3 ребра) этого графа.
Указание. Сформировать все трёхэлементные подмножества множества вершин {1, 2, ..., n}. Для каждого подмножества проверить наличие соответствующих рёбер.
Вариант № 22.
1. Разработать и отладить программу, по заданным n и m генерирующую все размещения с повторениями. Каждая комбинация должна состоять из элементов множества {1, 2, ..., n} и содержать m элементов. Для каждой
комбинации подсчитать произведение П вида: m ( 1)i (xi xi 1) . Пронуме-
i 2
ровав все комбинации, вывести их и соответствующие им произведения П
ввыходной текстовый файл.
2.На входе: два множества А и В, элементами которых являются символы.
1) Сформировать декартово произведение D = A×B этих множеств;
2) сгенерировать и пронумеровать все (n+2)-элементные сочетания с повторениями из элементов множества D (где n – мощность множества D);
3) результат вывести в выходной текстовый файл.
3.Изменить исходный способ хранения ориентированного псевдографа на заданный. Представление псевдографа на входе (из входного
137
файла): списки смежности. Представление псевдографа на выходе: матрица смежности.
4. Неориентированный граф задан матрицей смежности. Прочитав матрицу смежности из входного текстового файла, найти все мосты данного графа.
Указание. Для каждого ребра поочерёдно проделать следующее: удалив это ребро, получить новый граф. Для этого графа, использую процедуру обхода в глубину, подсчитать количество компонент связности.
Вариант № 23.
1. Разработать и отладить программу, по заданным n и m генерирующую все сочетания. Каждая комбинация должна состоять из элементов множества {1, 2, ..., n} и содержать m элементов (m n). Для каждой комбинации
подсчитать произведение П вида: m ( 1)i (xm i 1 xi ) .
i 1
Пронумеровав все комбинации, вывести их и соответствующие им произведения П в выходной текстовый файл.
2.На входе: два множества А и В, элементами которых являются цифры: {0, 1, …, 9}.
1)Сформировать объединение дополнений: D = !A U !B;
2)сгенерировать и пронумеровать все (n+2)-элементные перестановки с повторениями из элементов множества D (где n – мощность множества D);
3)для каждой перестановки подсчитать сумму всех нечётных цифр;
4)результат вывести в выходной текстовый файл.
3.Изменить исходный способ хранения сильно ветвящегося дерева на заданный. Представление дерева на входе (из входного файла): имя вершины; ссылка на отца. Представление дерева на выходе: имя вершины; ссылки на левого сына, правого и левого брата.
4.Неориентированный граф представлен списками смежности. Прочитав списки смежности из входного текстового файла, составить список рёбер для графа, являющегося дополнением к данному графу.
Вариант № 24.
1. Разработать и отладить программу, по данному значению n 6 генерирующую те подмножества множества {1, 2, ..., n}, которые содержат от четырех до пяти элементов. Для каждой комбинации подсчитать произ-
m 1
ведение П вида: (xi ( 1)i xi 1) .
i 0
Пронумеровав все комбинации, вывести их и соответствующие им произведения П в выходной текстовый файл.
138
2. На входе: два множества А и В, элементами которых являются цифры:{0, 1, …, 9}.
1) Сформировать объединение первого из них с дополнением ко второму D = A U !B;
2) сгенерировать и пронумеровать все двухэлементные размещения с повторениями из элементов множества D;
3) для каждой комбинации подсчитать факториал суммы входящих в неё цифр; 4) результат вывести в выходной текстовый файл.
3. Изменить исходный способ хранения ориентированного псевдографа на заданный. Представление псевдографа на входе (из входного файла): список рёбер. Представление псевдографа на выходе: матрица смежности.
4. Неориентированный граф, имеющий 5 или 6 вершин, задан списком рёбер. Прочитав список рёбер из входного текстового файла, определить, является ли данный граф планарным?
Указание. Использовать критерий Понтрягина-Куратовского.
Литература:
1.Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. М.: Издательский дом “Вильямс”, 2001.- 384 с.
2.Вирт Н. Алгоритмы и структуры данных. М.: Мир, 1989. - 360 с.
3.Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. -
М,.: Мир, 1981. 368 с.
4.Дмитриева М.В., Кубенский А.А. Элементы современного программирования: Учебное пособие. Спб.: Изд-во С.-Петербургского университета,
1991. - 272 с.
5.Иванов Б.Н. Дискретная математика. Алгоритмы и программы: Учеб. пособие. - М.: Лаборатория базовых знаний, 2001. - 288 с.
6.Кнут Д. Искусство программирования для ЭВМ. Том 1: Основные алгоритмы. М.: Издательский дом “Вильямс”, 2000. - 720 с.
7.Кнут Д. Искусство программирования для ЭВМ. Том 3: Сортировка и поиск. М.: Издательский дом “Вильямс”, 2000. - 832 с.
8.Липский В. Комбинаторика для программистов. М.: Мир, 1988.
9.Новиков Ф.А. Дискретная математика для программистов. Спб: Питер,
2000. - 304 с.
139
Локоть В.В.
Задачи для подготовки к к государственному экзамену по математике
Текстовые задачи
1. Теплоход проходит от пристани А до пристани В по течению реки за 3 ч, а против течения за 4 ч. За сколько часов проплывёт это расстояние плот?
Решение.. Пусть x |
км/ч – собственная скорость теплохода, |
y км/ч – ско- |
|||
рость течения реки, |
S км – расстояние от пристани А до пристани В. По |
||||
условию |
S 3(x y), S 4(x y), требуется |
найти |
S / y. |
3(x y) |
4(x y), x 7 y, S 3(x y) 24 y S / y 24. Ответ: 24ч.
2. Для перевозки груза было заказано две машины разной грузоподъёмности, которые должны были сделать одинаковое число рейсов, при этом первая машина должна перевезти на 80 т груза больше, чем вторая. В действительности оказалось, что грузоподъёмность этих машин больше, чем предполагалось: у первой машины – на 3 т, а у второй – на 2 т. В результате каждый водитель перевёз свою часть груза, сделав на 4 рейса меньше, чем предполагалось. Какова плановая грузоподъёмность первой машины?
Решение. Пусть x предполагаемая грузоподъёмность первой машины, y
предполагаемая грузоподъёмность |
второй |
машины, |
n предполагаемое |
|||
число |
рейсов. |
По |
условию |
xn (x 3)(n 4) 3n 4x 12 (1), |
||
yn ( y 2)(n 4) 2n 4 y 8 (2), |
xn yn 80 (3). Из (1) |
и (2) следует, что |
||||
3y 2x (4). Из (3) и (4) исключаем y, |
получим 3xn 3yn 240 |
|||||
3xn 2xn 240 xn 240 (5). Из (1) |
и (5) находим x 12. Ответ: 12. |
3. В магазине костюм, состоящий из пиджака и брюк, стоит на 20% дороже, чем такой же костюм на рынке, причём брюки стоят на 30% дороже, чем на рынке, а пиджак – на 15%. Во сколько раз на рынке брюки от этого костюма дешевле пиджака?
Решение. Пусть x стоимость брюк на рынке, y стоимость пиджака на рынке. Тогда x 0, 3x и y 0,15y стоимость соответственно брюк и пиджа-
ка в магазине, |
x y стоимость костюма на рынке, 1, 3x 1,15 y стоимость |
костюма в |
магазине. По условию 1, 3x 1,15 y (x y) 0, 2(x y) |
0,1x 0, 05 y y 2x. Брюки дешевле пиджака в два раза.
140