Рекуррентные соотношения

232. Подсчитать количество последовательностей длины N, состоящих из 0 и 1, в которых никакие две единицы не стоят рядом.

233. Посылка бандероли стоит 18 рублей, а на почте имеются марки по 4, 6 и 10 рублей. Сколькими разными способами можно наклеить на бандероль марки, на нужную сумму?

234. Имеется возможность передавать 4 разных сигнала А, Б, В, Г, причем их передача занимает соответственно Т1, Т2 Т3, Т4 (целые) единиц времени. Сколько различных сообщений может быть передано за время Т (тоже целое)?

235. Абитуриент сдает в вуз 4 экзамена по 5-балльной системе и хочет набрать не менее 17 баллов. Сколькими способами он может это сделать.

236. Сколькими способами можно разбить натуральное число М на К простых слагаемых, где способы разбиения, отличающиеся порядком слагаемых, считаются разными? Например при М=10 и К=2 ответом будет 3, так как 10=3+7=5+5=7+3.

237. В лототроне имеются бочонки с номерами от 1 до К. Последовательно вынимают по одному бочонку, записывают его номер и считают сумму записанных чисел. Сколькими способами может получиться сумма М?

238. В лототроне имеются бочонки с номерами от 1 до К. Последовательно вынимают по одному бочонку, записывают его номер и считают сумму записанных чисел, после записывания номера бочонок возвращается обратно в лототрон. Сколькими способами может получиться сумма М?

239. На единственной улице в деревне стоят К домов с известными координатами. Требуется соединить их телефонными проводами минимальной суммарной длины так, чтобы житель каждого дома мог пообщаться хотя бы с одним жителем другого дома.

240. В пригородном автобусе кондуктор следил за тем, чтобы все покупали билеты и отмечал, сколько билетов (k_i,j) куплено с i–й остановки до j–й. По известной матрице k_i,j нужно найти промежуток времени, когда в автобусе было максимальное количество пассажиров и чему оно равно.

241. Прямоугольная таблица размерами МхК произвольно заполнена цифрами от 0 до 9. Найти путь из левого нижнего угла в правый верхний с максимальной суммой цифр в клетках пути (разрешается на каждом шаге переходить вверх или вправо).

242. В романе N глав, причем р-я глава состоит из Ар страниц. Роман нужно разбить на К томов, причем главы должны идти по порядку и главы нельзя разбивать в разные тома. Какова может быть минимальная толщина самого толстого тома при этом?

243. Для последовательности с f(1)=5 и f(2)=13, удовлетворяющей рекуррентному соотношению f(к+2)=5f(к+1)-6f(к), выписать формулу общего члена.

244. Для последовательности с f(0)=6 и f(1)=24, удовлетворяющей рекуррентному соотношению f(к+2)=6f(к+1)-9f(к), выписать формулу общего члена.

245. Для последовательности с f(0)=4, f(1)=-7 и f(2)=15, удовлетворяющей рекуррентному соотношению f(к+3)=-6f(к+2)-11f(k+1)-6f(к), выписать формулу общего члена.

246. Найдите общее решение рекуррентных соотношений:

a) а_n+2-7a_n+1+12a_n=0;

b) а_n+2+3a_n+1-10a_n=0;

c) а_n+2+9a_n=0;

d) а_n+2+4a_n+1+4a_n=0.

247. Найдите решение рекуррентного соотношения:

a) а_n+2-5a_n+1+6a_n=0, а₁=1, а₂=-7;

b) а_n+2-4a_n+1+4a_n=0, а₁=2, а₂=4.

Введение в теорию графов

Среди дисциплин и методов дискретной математики теория графов и особенно алгоритмы на графах находят наиболее широкое применение в программировании. Дело в том, что теория графов дает очень удобный язык для описания программных моделей. Особенно важно наличие наглядной графической интерпретации понятия графа. Картинки позволяют сразу «усмотреть» суть дела на интуитивном уровне, дополняя и украшая утомительные рациональные текстовые доказательства и сложные формулы.

Начало теории графов относят к 1736 г., когда Л. Эйлер решил задачу о Кениксбергских мостах. Около 100 лет это был единственный результат теории графов. В задаче о Кениксбергских мостах (см. рис. 1) необходимо было определить можно ли, начав с некоторой точки, совершить прогулку и вернуться в исходную точку, пройдя по каждому мосту ровно один раз.

В 1930 году К. Куратовским была решена задача о трех домах и трех колодцах, сформулированная следующим образом: «Имеются три дома и три колодца. Жители домов поссорились и решили проложить дороги к своим колодцам так, чтобы они не пересекались. Возможно ли это?»

Почти 100 лет не была доказана теорема о раскраске карты: «Любую карту на плоскости можно раскрасить четырьмя красками так, чтобы никакие две соседние области не были закрашены одним цветом.»

Родившись при решении головоломок и занимательных игр, теория графов стала в настоящее время простым, доступным и мощным средством решения вопросов, относящихся к широкому кругу проблем. В виде графов можно интерпретировать схемы дорог и электрические цепи, географические карты и молекулы химических соединений, связи между людьми и группами людей. То есть виде графа можно изобразить любую структуру, на которой задано некоторое отношение между её объектами.

На рисунках 2 и 3 изображены участок электрической цепи и часть карты дорог. Ясно, что оба эти рисунка могут быть представлены одной и той же диаграммой из точек и линий, изображенной на рисунке 4

Основные определения

Определение. Определим граф как совокупность двух множеств непустого множества V (множество вершин) и множества E неупорядоченных и упорядоченных пар вершин из V.

Определение. Неупорядоченная пара вершин называется ребром, а упорядоченная пара - дугой.

Определение. Граф, содержащий только ребра, называется неориентированным; граф, содержащий только дуги, - ориентированным, или орграфом, содержащий и ребра и дуги – смешанным.

Каждый граф можно представить на плоскости множеством точек, соответствующих вершинам, которые соединены линиями, соответствующими ребрам. В трехмерном пространстве любой граф можно представить, таким образом, что линии (ребра) не будут пересекаться. Вершины графа на рисунке выделяют обычно кружочками или квадратиками, так как не всегда точки пересечения ребер являются вершинами графа.

На рисунке 5 изображен неориентированный граф G1, с пятью вершинами и восьмью ребрами.

На рисунках 6 и 7 изображены ориентированный и смешанный графы, соответственно.

Дата добавления: 2014-12-29