Построить подграф являющийся остовным деревом

2015-12-07

809

Обсуждений (0)

0.00 из 5.00 0 оценок

Министерство образования и науки Российской Федерации

ФГБОУ ВПО «Алтайский государственный технический университет им. И.И.Ползунова»

Контрольная работа

По дисциплине «Дискретная математика»

Вариант 1

Выполнил

студент гр. 7-ИВТ(с)-31

А.В. Погорельских

Проверил

доцент

Н.В. Ломских

Барнаул 2014

Комбинационный автомат

Придумать и словесно описать комбинационный автомат не менее чем на три входа.

Придумать сложное логическое высказывание не удалось, однако было найдена логическая функция с тремя переменными:

1). Построить для него таблицу истинности.

A	B	C	A	B	(A)∧B	(B)∧A	((A)∧B)∨((B)∧A)	C	A∨(C)	(A∨(C))∨B	(A∧B∨B∧A)∧(A∨C∨B)

2). Получить логическую функцию в базисе «И-ИЛИ-НЕ»

3). Изобразить комбинационную схему

Комбинаторика

Задача 1

Сколькими способами из 28 костей домино можно выбрать две кости так, чтобы их можно было приложить друг к другу (то есть чтобы какое-то число очков встречалось на обеих костях)?

Решение:

Сначала выберем одну кость. Это можно сделать 28 способами. При этом в 7 случаях выбранная кость окажется «дублем», то есть костью вида 00, 11, 22, 33, 44, 55, 66, а в 21 случае - костью с различными числами очков (например, 05, 13 и т. д.). В первом случае вторую кость можно выбрать 6 способами (например, если на первом шагу выбрана кость 11, то на втором шагу можно взять одну из костей 01, 12, 13, 14, 15, 16). Во втором же случае вторую кость можно выбирать 12 способами (для кости 35 подойдут кости 03, 13, 23, 33, 34, 36, 05, 15, 25, 45, 55, 56). По правилу произведения в первом случае получаем 7×6=42 выбора, а во втором 21×12 = 252 выбора. Значит, по правилу суммы получаем 42+252 = 294 способов выбора пары.

В проведенном рассуждении учитывался и порядок, в котором выбирались кости. Поэтому каждая пара костей появлялась дважды (например, первый раз 01 и 16, а второй раз 16 и 01). Если не учитывать порядок выбора костей, то получим вдвое меньше способов выбора, то есть 147 способов.

Ответ: 147 способов.

Задача 2

Сколькими способами натуральное число n можно представить в виде суммы

а) k натуральных слагаемых;

б) k неотрицательных целых слагаемых (представления, отличающиеся порядком слагаемых, считаются различными)?

Решение:

Представим n в виде суммы n единиц: n = 1 + 1 + … + 1.

Ответ:

а) ;

б) .

Задача 3

Пара кроликов приносит раз в месяц приплод из двух крольчат (самки и самца), причемноворожденные крольчата через два месяца после рождения уже приносят приплод.Сколько кроликов появится через год, если в начале года была одна пара кроликов?

Решение:

По условию задачи через месяц будет две пары кроликов, и получится 3 пары. А еще через месяц приплод дадут и исходная пара кроликов, и пара кроликов, появившаяся два месяца тому назад. Поэтому всего будет 5 пар кроликов.

Обозначим через F(n) количество пар кроликов по истечении года. Заметим, что через (n+1) месяцев будут эти F(n) пар и еще столько новорожденные пар кроликов, сколько было в конце месяца (n-1), т.е. еще F(n-1) пар кроликов.

Из этого следует соотношение F(n+1)=F(n)+F(n-1). По условию, F(0)=1 и F(1)=2, то последовательно находим F(2)=3, F(3)=5, F(4)=8 и т.д.

Ответ: F(12)=377.

Комбинаторика 2

Задача 1

Из города А в город В ведут 5 дорог, и из города В в город С – три дороги. Сколько путей, проходящих через В, ведут из А в С?

Решение

Рассмотрим рисунок:

Рисунок 1 – схема дорог между городами А, В, С.

Ответ: Из рисунка следует что из города А в город С через В проходит 15 маршрутов.

Задача 2

На ферме есть 20 овец и 24 свиньи. Сколькими способами можно выбрать одну овцу и одну свинью? Если такой выбор уже сделан, сколькими способами можно сделать его еще раз?

Ответ: 20 * 24 = 480

Если выбор сделан, остается на 1 овцу и 1 свинью меньше, следовательно 19 * 23 = 437

Задача 3

Сколькими способами можно выбрать из полной колоды карт по одной карте каждой масти? То же самое при условии, что среди вынутых карт нет ни одной пары одинаковых, то есть двух королей, двух десяток и т.п.

Решение: Так как от 2 до туза одной масти это 13 карт (т.е. выбрать можно одну из 13 разных карт.), следующая карта выбирается уже из двенадцати(чтобы не повторялась), и т.д. Из этого следует:

Ответ: 13 *12 *11*10 =17160

Задача 4

У одного человека есть 7 книг по математике, а у другого - 9 книг. Сколькими способами можно обменять 2 книги одного на 2 книги другого?

Решение

Первые две книги для обмена ( с первой стороны) можно выбрать способами - это количество сочетаний (без повторений) из 7 по 2. Вторые две книги для обмена (со второй стороны) можно выбрать Всего способов по правилу умножения получается 21*36 = 756 способов.

Ответ: 756 способов.

Задача 5

В некотором государстве не было двух жителей с одинаковым набором зубов (либо у них разное число зубов, либо зубов нет в разных местах). Оцените наибольшую численность населения этого государства, если максимальное число зубов у человека – 32.

Решение.

Закодируем каждого жителя набором из 32 нулей и единиц. Единица соответствует наличию зуба в данном месте, нуль – его отсутствию. Выпишем несколько комбинаций: 11111…11, 1010…11, 00000…00, …Элементы повторяются, состав меняется, порядок существенен. Это - размещения с повторениями из 2 по 32.

Ответ: 4294967296 человек.

Задача 6

У мамы было 2 яблока, 3 груши, и 4 апельсина. Каждый день она давала ребенку по одному фрукту. Сколькими способами она может это сделать?

Ответ: Р(2,3,4) = !9/!2*!3*!4 = 1260 способов

Задача 7

В почтовом отделении продаются открытки 10 сортов. Сколькими способами можно купить в нём 12 открыток? 8 открыток? Сколькими способами можно купить 8 различных открыток?

Ответ:

1). Всего 10 по 12. С₁₀¹²=С¹²_10+12-1=С₂₁¹²= 21! = 293930
2). Всего 10 по 8. С₁₀⁸=С⁸_10+8-1=С₁₇⁸=24310
3). Всего 10 по 8. С₁₀⁸=45