Контрольная работа по дискретной математике:
Вопрос 1:
Согласно опросу 250-ти телезрителей, 95 из них нравится смотреть новости, 125 предпочитают смотреть спорт, 125 – смотрят комедии, 25 – новости и комедии, 45 – комедии и спорт, 5 – любят все три вида программ. Ответье на вопросы:
1) Сколько телезрителей смотрят новости, но не смотрят спорт?
2) Сколько телезрителей смотрят не только спорт?
3) Сколько телезрителей не любят смотреть ни новости ни спорт?
Решение:
25 телезрителей любят смотреть новости и комедии, 45 – комедии и спорт, 5 – любят все три вида программ. Значит, 20 (25-5) телезрителей любят смотреть комедии и новости, но не смотрят спорт. 40 (45-5) телезрителей любят смотреть комедии и спорт, но не смотрят новости.
Только комедии любят смотреть 60 (125-20-5-40) телезрителей.
Посчитаем скольтко телезрителей любят смотреть новости и сопрт, но не смотрят комедии. Для этого распишем всех телезрителе: 70 (смотрят новости, но не смотрят комедии, в том числе смотрят спорт)+20 (смотрят новости и комедии но не смотрят спорт)+5 (смотрят все три вида программ)+40 (смотрят спорт и комедии, но не смотрят новости)+80 (смотрят спорт, в том числе смотрят новости)+60 (смотрят комедии)=275. В данном случае мы два раза учли терезрителей, который смотрят новости и спорт, но не смотрят комедии. Всего 250 телезрителей. Тогда 25 телезрителей смотрят новости и спорт, но не смотрят комедии.
45 (95-20-5-25) смотрят только новости. 55(125-25-5-40) смотрят только спорт.
Составим диаграмму:
Вопрос 2:
Если в урне имеются 20 красных, 20 зеленых и 20 синих шаров, то сколькими различными способами можно выбрать 10 шаров?
Решение:
Всего 20+20+20=60 шаров.
Можно методом перебора найти количество способов выбора из 60 шаров 10 шаров. Считаем, что шары одного цвета одинаковые.
Можно выбрать одним способом 10 красных шаров, одним способом 10 зеленых шаров, одним способом 10 синих шаров.
Если 1 шар красный, то возможны следующие варианты: 9 зеленых + 0 синих,8 зеленых + 1 синий, 7 зеленых + 2 синих, 6 зеленых + 3 синих, 5 зеленых + 4 синих, 4 зеленых + 5 синих, 3 зеленых + 6 синих, 2 зеленых + 7 синих, 1 зеленых + 8 синих, 9 синих.
Если 2 шара красных, то возможны следующие варианты: 8 зеленых + 0 синих, 7 зеленых + 1 синий, 6 зеленых + 2 синих, 5 зеленых + 3 синих, 4 зеленых + 4 синих, 3 зеленых + 5 синих, 2 зеленых + 6 синих, 1 зеленый + 7 синих, 8 синих.
Если 3 шара красных, то возможны следующие варианты: 7 зеленых + 0 синих, 6 зеленых + 1 синий, 5 зеленых + 2 синих, 4 зеленых + 3 синих, 3 зеленых + 4 синих, 2 зеленых + 5 синих, 1 зеленый + 6 синих, 7 синих.
Если 4 шара красных, то возможны следующие варианты: 6 зеленых + 0 синих, 5 зеленых + 1 синий, 4 зеленых + 2 синих, 3 зеленых + 3 синих, 2 зеленых + 4 синих, 1 зеленый + 5 синих, 6 синих.
Если 5 шаров красных, то возможны следующие варианты: 5 зеленых + 0 синих, 4 зеленых + 1 синий, 3 зеленых + 2 синих, 2 зеленых + 3 синих, 1 зеленый + 4 синих, 5 синих.
Если 6 шаров красных, то возможны следующие варианты: 4 зеленых + 0 синих, 3 зеленых + 1 синий, 2 зеленых + 2 синих, 1 зеленый + 3 синих, 4 синих.
Если 7 шаров красных, то возможны следующие варианты: 3 зеленых + 0 синих, 2 зеленых + 1 синий, 1 зеленый + 2 синих, 3 синих.
Если 8 шаров красных, то возможны следующие варианты: 2 зеленых + 0 синих, 1 зеленый + 1 синий, 2 синих.
Если 9 шаров красных, то возможны следующие варианты: 1 зеленый + 0 синих, 1 синий.
Тогда всего 57 возможных различных способов выбора шаров.
Вопрос 3:
Нарисовать граф и построить матрицу смежности для него если множество вершин состоит из V = {a, b, c, d, e, f}: а множество ребер состоит из E = {(a, b), (a, e), (b, f), (d, c), (c, c), (f, d), (d, f)}. Также нарисовать матрицу смежности для неориентированного графа заданного тем же набором вершин и ребер.
Решение:
Нарисуем ориентированный граф:
a
f
e
d
c
b
Построим матрицу смежности для ориентированного графа:
010000002 010001000001000000 001000100
Нарисуем неориентированный граф:
a
f
e
d
c
b
Построим матрицу смежности для неориентированного графа:
010100002 010001100001100010 002000200
Вопрос 4:
Используйте алгоритм Дейкстры для нахождения в приведенных ниже графах кратчайшего расстояния между вершинами v0 и v.
Решение:
Алгоритм:
Каждой вершине из V сопоставим метку — минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.
Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые.
Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, в которые ведут рёбра из u, назовем соседями этой вершины. Для каждого соседа вершины u, кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг алгоритма.
Обозначим вершину v0 как начальную, у остальных вершин поставим метку 0.
Пометим вершину v1 меткой 1, v3 меткой 2, v2 меткой 6. И зачеркнем вершину v0.
Далее проведем процедуру для вершины v1. У вершины v2 поставим метку 5=1+4, т.к. 5<6. У вершины v4 поставим метку 3=1+2. И вычеркнем вершину v1.
Проведем процедуру для вершины v3. У вершины v4 оставим метку 3, т.к. 3<7=5+2. И вычеркнем вершину v3.
Проведем процедуру для вершины v4. Поставим метку в вершины v равную 7=3+4. И зачеркнем вершину v4.
Проведем процедуру для оставшейся вершины v2. У вершины v оставим метку 7, т.к. 7<5+3=8.
Расстояния от вершины v0 до вершины v1 равно 1, до v2 равно 5, до v3 равно 2, до v4 равно 3, до v равно 7.