QalOGUGtk0

Вариант № 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 ч. За сколько часов проплывёт это расстояние плот?

4(x y), x 7 y, S 3(x y) 24 y S / y 24. Ответ: 24ч.

2. Для перевозки груза было заказано две машины разной грузоподъёмности, которые должны были сделать одинаковое число рейсов, при этом первая машина должна перевезти на 80 т груза больше, чем вторая. В действительности оказалось, что грузоподъёмность этих машин больше, чем предполагалось: у первой машины – на 3 т, а у второй – на 2 т. В результате каждый водитель перевёз свою часть груза, сделав на 4 рейса меньше, чем предполагалось. Какова плановая грузоподъёмность первой машины?

Решение. Пусть x предполагаемая грузоподъёмность первой машины, y

3. В магазине костюм, состоящий из пиджака и брюк, стоит на 20% дороже, чем такой же костюм на рынке, причём брюки стоят на 30% дороже, чем на рынке, а пиджак – на 15%. Во сколько раз на рынке брюки от этого костюма дешевле пиджака?

Решение. Пусть x стоимость брюк на рынке, y стоимость пиджака на рынке. Тогда x 0, 3x и y 0,15y стоимость соответственно брюк и пиджа-

0,1x 0, 05 y y 2x. Брюки дешевле пиджака в два раза.

140