Ооро. Практикум. Дискретная математика.. Сборник задач и упражнений по дисциплине Дис кретная математика
 Скачать 188.15 Kb.
|
|
Симоненко Евгений А. Д ИСКРЕТНАЯ МАТЕМАТИКА П РАКТИКУМ (20 февраля – 18 апреля 2012) Краснодар 2012 © 2012, Симоненко Евгений А. < easimonenko@mail.ru > Учебное пособие представляет из себя сборник задач и упражнений по дисциплине «Дис- кретная математика», практические и лабораторные занятия по которой автор проводил в Ку- банском государственном технологическом университете студентам-бакалаврам направлений 230100 – «Информатика и вычислительная техника» и 231000 – «Программная инженерия» в 2011/2012 учебном году. В пособии рассматриваются все основные разделы дискретной мате- матики, знание которых необходимо для специалистов указанных направлений, а именно: теория множеств, исчисление конечных сумм, теория рекурсии, теория чисел, комбинатори- ка, теория графов, дискретные оптимизационные задачи. 3 Оглавление Введение..............................................................................................................................................5 Множества и отношения.................................................................................................................7 Комбинаторика: подсчёт.................................................................................................................9 Комбинаторика: генерация............................................................................................................19 Исчисление конечных сумм.............................................................................................................21 Элементы теории чисел.................................................................................................................23 Рекуррентные соотношения..........................................................................................................25 Теория графов: основы....................................................................................................................27 Теория графов: циклы и связность................................................................................................29 Теория графов: оптимизационные задачи...................................................................................31 Теория графов: покрытие и независимость................................................................................33 Библиография...................................................................................................................................35 Введение 5 Введение Практикум по дискретной математике преследует цель закрепления знаний, полученных из лекций, получения новых знаний посредством решения задач и упражнений, а также получе- ние практического навыка решения прикладных задач в том числе и с привлечением компью- тера посредством написания программ. Тема «Множества и отношения» обычно дублируется в курсе математического анализа, поэтому в учебный план по дискретной математике не включена, однако присутствует в этом учебном пособии с целью повторения и закрепления материала по этой теме, и рекомендует- ся для самостоятельного выполнения. Символом звёздочка (*) помечены упражнения повышенной сложности, символом (С) – упражнения для самостоятельного выполнения. При составлении этого пособия были использованы следующие учебники: 1. [Грэхем, Кнут, Паташник] Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основания информатики: Пер. с англ. – 3-е изд. – М.: Мир; БИНОМ. Лаборатория зна- ний, 2009. – 703 с. 2. [Кузьмин: комбинаторика] Кузьмин О.В. Перечислительная комбинаторика: учеб. по- соб. – М.: Дрофа, 2005. – 110 с. 3. [Окулов: ДМ] Окулов С.М. Дискретная математика. Теория и практика решения задач по информатике: учебное пособие. – М.: БИНОМ. Лаборатория знаний, 2008. – 422 с. 4. [Хаггарти] Хаггарти Р. Дискретная математика для программистов. – 2-е изд. – М.: Техносфера, 2005. – 400 с. Более полный список рекомендуемой литературы смотри в разделе «Библиография». Множества и отношения 7 Множества и отношения Упражнение 1 (С) Изобразите с помощью кругов Эйлера понятия подмножества, объединения, пересечения, разности и симметрической разницы двух множеств. Упражнение 2 (С) Пусть дано некоторое множество X и универсум U. Выясните, что представляют из себя сле- дующие множества: X ∪∅ , X ∪U , X ∪ X , X ∪X , X ∩∅ , X ∩U , X ∩ X , X ∩X , X ∖∅ , X ∖ U , X ∖ X ,∅ ∖ X , U , ∅ , X Докажите это. Упражнение 3 (С) Пусть даны два множества X и Y, X ⊆U ,Y ⊆U . Выясните, что представляют из себя следую- щие множества: ( X ∩Y )∪ X , X ∩( X ∪Y ) Докажите это. Упражнение 4 (С) Пусть даны два множества X и Y, такие что X ⊂Y . Выясните, что представляют из себя сле- дующие множества: X ∪Y , X ∩Y , X ∪Y ,Y ∩ X Докажите это. Упражнение 5 (С) Пусть дано множество X ={a , b ,c} . Перечислите элементы множества, состоящего из двух элементных подмножеств множества X. Упражнение 6 (С) Пусть дано множество X ={a , b , c} . Перечислите элементы множества 2 X . Чему равна мощность этого множества? Упражнение 7 (С) Пусть дано множество X ={a , b , c} . Перечислите элементы множества X 2 . Чему равно ∣ X 2 ∣ ? 8 Симоненко Е.А. Дискретная математика. Практикум Упражнение 8 (С) Пусть X – множество всех вертикалей шахматной доски, а Y – множество всех ей горизонта- лей. Выпишите элементы множеств X, Y и X ×Y . Чему равно ∣X ×Y∣ ? Комбинаторика: подсчёт 9 Комбинаторика: подсчёт Во всех упражнениях ответ должен быть обоснован. Упражнения с 1 по 16 на базовые прави- ла комбинаторики, с 17 по 30 на перестановки и размещения, с 31 по 48 на сочетания, с 49 по 76 на комбинации с повторениями и с 77 и до конца на биномиальные коэффициенты и поли- номиальную формулу. Упражнение 1 На факультете информатики на первом курсе учатся 15 студентов, на втором – 20, на третьем – 20, а на четвёртом – 25. Сколько всего на факультете информатики учится студентов? Упражнение 2 На факультете информатики 10 студентов участвуют в олимпиадах по программированию, а 15 занимаются спортом, при этом известно, что 5 занимаются и тем, и другим. Сколько всего студентов занято чем-то ещё кроме посещения занятий, если под «чем-то ещё» подразумева- ется спорт и олимпиадное программирование? Упражнение 3 Города A и B соединяют три дороги, а города B и C – четыре дороги. Сколькими способами можно совершить поездку из A в C через B и вернуться обратно в A также через B? (Не торо- питесь с ответом. Нарисуйте картинку. Попробуйте посчитать количество путей туда и обрат- но по ней. Сравните получающееся значение с Вашим первоначальном ответом.) (См. [Кузь- мин: комбинаторика].) Упражнение 4 (С) В корзине лежат 12 яблок и 10 апельсинов. Серёжа выбирает из неё яблоко или апельсин, по - сле чего Елена берёт и яблоко, и апельсин. В каком случае Елена имеет большую свободу вы- бора: если Серёжа взял яблоко или если он взял апельсин? (См. [Кузьмин: комбинаторика].) Упражнение 5 (С) Из Киева до Чернигова можно добраться пароходом, поездом, автобусом и самолётом; из Чернигова до Новгорода Северского – пароходом и автобусом. Сколькими способами можно осуществить путешествие по маршруту Киев – Чернигов – Новгород Северский? Ответ обос- нуйте. (См. [Кузьмин: комбинаторика].) Упражнение 6 Музыкальный концерт состоит из трёх песен и двух скрипичных пьес. Сколькими способами можно составить программу концерта так, чтобы он начинался и оканчивался исполнением песни, и чтобы скрипичные пьесы не исполнялись одна за другой? Ответ обоснуйте. (См. [Кузьмин: комбинаторика].) 10 Симоненко Е.А. Дискретная математика. Практикум Упражнение 7 (С) Если повернуть лист белой бумаги на 180º, то цифры 0, 1, 8 не изменяются, цифры 6 и 9 пере- ходят в друг друга, а остальные цифры теряют смысл. Сколько существует семизначных чи- сел, величина которых не изменяется при повороте листа бумаги на 180º? Ответ обоснуйте. (См. [Кузьмин: комбинаторика].) Упражнение 8 Сколько сигналов можно поднять на мачте, имея четыре флага различных цветов, если каж- дый сигнал должен состоять не менее чем из двух флагов? Ответ обоснуйте. (См. [Кузьмин: комбинаторика].) Упражнение 9 На одной из боковых сторон треугольника отмечено n различных точек, а на другой – m. Каж- дая из вершин при основании треугольника соединена прямыми с этими точками. Сколько точек пересечения этих прямых образуется внутри треугольника? На сколько частей делят треугольник эти прямые? Ответ обоснуйте. (См. [Кузьмин: комбинаторика].) Упражнение 10 (*) Каждая из трёх вершин треугольника соединена прямыми с n различными точками, располо- женными на противоположной стороне треугольника. На сколько частей делят треугольник эти прямые, если никакие три из них не пересекаются в одной точке? Ответ обоснуйте. (См. [Кузьмин: комбинаторика].) Упражнение 11 На вступительном экзамене по математике были предложены три задачи: одна по алгебре, одна по геометрии и одна по тригонометрии. Из 1000 абитуриентов задачу по алгебре реши- ли 800, по геометрии – 700, по тригонометрии – 600. При этом задачи по алгебре и геометрии решили 600 абитуриентов, по алгебре и тригонометрии – 500, по геометрии и тригонометрии – 400, а 300 абитуриентов решили все задачи. Сколько абитуриентов не решили ни одной за- дачи? Ответ обоснуйте. (См. [Кузьмин: комбинаторика].) Упражнение 12 Сколько из первых ста натуральных чисел не делится ни на одно из чисел 2, 3, 5? Ответ обос- нуйте. (См. [Кузьмин: комбинаторика].) Упражнение 13 (С) В классе 35 учащихся. Из них 20 посещают факультатив по математике, а 11 – по информати- ке, и 10 не посещают ни один из этих факультативов. Сколько учащихся посещают факульта- тивы и по математике, и по информатике? Сколько учащихся посещают факультатив только по математике или только по информатике? Ответ обоснуйте. (См. [Кузьмин: комбинатори- ка].) Комбинаторика: подсчёт 11 Упражнение 14 (*) В библиотеке n книг. Каждый читатель прочитал по крайней мере одну книгу из этой библио- теки. О любых k, 1⩽k ⩽n , книгах из библиотеки можно сказать, сколько читателей прочита- ли все эти книги. Сколько читателей в библиотеке? Ответ обоснуйте. (См. [Кузьмин: комби- наторика].) Упражнение 15 (*) Пусть p 1, p 2, … , p k – все различные простые делители натурального числа n, а φ (n) – число составных натуральных чисел, меньших и взаимно простых с n. Докажите, что φ ( n)=n ( 1− 1 p 1 )( 1− 1 p 2 ) ⋯ ( 1− 1 p k ) (Функция φ (n) называется функцией Эйлера.) (См. [Кузьмин: комбинаторика].) Упражнение 16 (*) Найдите чему равно ∣2 X ∣ , где ∣X ∣=n . (См. [Окулов: ДМ].) Упражнение 17 Сколькими различными способами можно разместить на полке n различных книг? (См. [Кузьмин: комбинаторика].) Упражнение 18 Сколькими способами можно упорядочить множество ℕ n ={ 1, 2,... ,n} так, чтобы каждое чётное число имело чётный номер? (См. [Кузьмин: комбинаторика].) Упражнение 19 На собрании должны выступить пять человек: А, Б, В, Г и Д. Сколькими способами можно расположить их в списке выступающих, если: Б не должен выступать до того, как выступит А; А должен выступит непосредственно перед Б? (См. [Кузьмин: комбинаторика].) Упражнение 20 Сколькими способами можно составить трёхцветный полосатый флаг с заданным направле- нием полос, если имеется материал пяти различных цветов? Если один из цветов уже вы- бран? (См. [Кузьмин: комбинаторика].) Упражнение 21 Укротитель хищных зверей хочет вывести на арену цирка m львов и k тигров, при этом не- льзя, чтобы два тигра шли друг за другом. Сколькими способами он может расположить зве- рей? (См. [Кузьмин: комбинаторика].) 12 Симоненко Е.А. Дискретная математика. Практикум Упражнение 22 Сколько существует перестановок из n элементов, в которых: 1) определённые два элемента не стоят рядом; 2) между определёнными двумя элементами стоит ровно m элементов; 3) определённые три элемента не стоят рядом; 4) никакие два из определённых трёх элементов не стоят рядом? (См. [Кузьмин: комбинаторика].) Упражнение 23 N девушек водят хоровод. Сколькими различными способами они могу образовать круг? (См. [Кузьмин: комбинаторика].) Упражнение 24 Сколько ожерелий можно составить из n различных бусинок? (См. [Кузьмин: комбинаторика].) Упражнение 25 Сколькими способами можно посадить за круглый стол n мужчин и n женщин так, чтобы ни- какие два лица одного пола не сидели рядом? (См. [Кузьмин: комбинаторика].) Упражнение 26 (С) Сколькими способами можно посадить за карусель n мужчин и n женщин так, чтобы никакие два лица одного пола не сидели рядом? (Расположения, переходящие друг в друга при враще- нии карусели, считаются одинаковыми.) (См. [Кузьмин: комбинаторика].) Упражнение 27 (С) Имеется n точек на плоскости, никакие три из которых не лежат на одной прямой. Сколько имеется k-звенных замкнутых ломаных с вершинами в этих точках? (См. [Кузьмин: комбина- торика].) Упражнение 28 (С) Сколькими способами можно посадить рядом троих англичан, троих французов и троих нем- цев так, чтобы никакие три соотечественника не сидели рядом? Два соотечественника? (См. [Кузьмин: комбинаторика].) Упражнение 29 (*) Сколькими способами можно посадить за круглый стол троих англичан, троих французов и троих немцев так, чтобы никакие два соотечественника не сидели рядом? (См. [Кузьмин: комбинаторика].) Упражнение 30 (*) Сколькими способами n человек могут выбрать из k пар перчаток по правой и левой перчатке так, чтобы ни один из них не получил пары? (См. [Кузьмин: комбинаторика].) Комбинаторика: подсчёт 13 Упражнение 31 Студенту необходимо сдать четыре экзамена за восемь дней. Сколькими способами это мож- но сделать, если разрешается сдавать не более одного экзамена в день? (См. [Кузьмин: комби- наторика].) Упражнение 32 Сколькими способами можно обозначить треугольник, помечая его вершины различными прописными латинскими буквами? (См. [Кузьмин: комбинаторика].) Упражнение 33 Во скольких точках пересекаются диагонали выпуклого n-угольника, если никакие три из них не пересекаются в одной точке? (См. [Кузьмин: комбинаторика].) Упражнение 34 Рассмотрим прямоугольную сетку квадратов размерами n⋅m (шахматный город, состоящий из n×m прямоугольных кварталов, разделённых n−1 горизонтальными и m−1 вертикаль- ными улицами). Каково число различных кратчайших на этой сетке путей, ведущих из левого нижнего угла (из точки O(0,0) ) в правый верхний угол (в точку M (m , n) )? (См. [Кузьмин: комбинаторика].) Упражнение 35 В комнате n лампочек. Сколько всего может быть разных способов освещения комнаты, при которых горит ровно k ( k ⩽n ) лампочек? Сколько всего может быть различных способов освещения комнаты? (См. [Кузьмин: комбинаторика].) Упражнение 36 Городской совет состоит из головы и шести старейшин. Сколько различных комиссий из четырёх членов можно сформировать из членов городского совета, если: 1) голова города входит в каждую комиссию? 2) голова города не входит ни в одну из комиссий? (См. [Кузь- мин: комбинаторика].) Упражнение 37 (С) Сколькими способами можно выбрать 12 человек из 17, если данные двое из этих 17 не мо- гут быть выбраны вместе? (См. [Кузьмин: комбинаторика].) Упражнение 38 (С) Сколько имеется четырёхзначных чисел, у которых каждая следующая цифра: 1) больше пре- дыдущей? 2) меньше предыдущей? (См. [Кузьмин: комбинаторика].) 14 Симоненко Е.А. Дискретная математика. Практикум Упражнение 39 (С) У мамы Серёжи есть m одинаковых яблок и n одинаковых груш. Каждый день в течение пяти дней подряд она выдаёт Серёже по одному фрукту. Сколькими способами это может быть сделано? (См. [Кузьмин: комбинаторика].) Упражнение 40 (С) Сколькими различными способами можно разделить 25 одинаковых предметов между четырьмя людьми? (См. [Кузьмин: комбинаторика].) Упражнение 41 (С) В железнодорожном вагоне 10 мест расположены по ходу поезда и 10 мест – против хода. Сколькими способами можно посадить в вагон 8 пассажиров, если два из них отказываются сидеть лицом по ходу поезда, а 3 – против хода? (См. [Кузьмин: комбинаторика].) Упражнение 42 Докажите, что C n k +1 > C n k при k < n−1 2 , C n k +1 < C n k при k > n−1 2 Укажите наибольшее среди C n k , 0⩽k ⩽n . (См. [Кузьмин: комбинаторика].) Упражнение 43 Дано n точек, никакие три из них не лежат на одной прямой. Сколько прямых можно прове- сти, соединяя эти точки попарно? (См. [Кузьмин: комбинаторика].) Упражнение 44 Сколько диагоналей можно провести в выпуклом n-угольнике? (См. [Кузьмин: комбинатори- ка].) Упражнение 45 У Серёжи p белых и q чёрных шаров, p>q . Сколькими способами он может выложить эти шары в ряд так, чтобы никаких два чёрных шара не лежали рядом? (См. [Кузьмин: комбина- торика].) Упражнение 46 На плоскости проведено n прямых так, что никакие две из них не параллельны и никакие три не пересекаются в одной точке. Каково количество точек пересечения этих прямых? Сколько треугольников образуют эти прямые? На сколько частей делят плоскость эти прямые? Сколь- ко среди этих частей ограниченных и сколько неограниченных? (См. [Кузьмин: комбинатори- ка].) Комбинаторика: подсчёт 15 Упражнение 47 (*) На окружности отмечено несколько точек, A – одна из них. Каких (и на сколько) выпуклых многоугольников с вершинами в этих точках больше: содержащих точку A или не содержа- щих её? (См. [Кузьмин: комбинаторика].) Упражнение 48 (*) Найдите число способов размещения k различных предметов в n ящиках, при которых ровно m ящиков остаются пустыми. (См. [Кузьмин: комбинаторика].) Упражнение 49 Сколькими способами можно расселить восемь студентов по трём комнатам: одноместной, трёхместной и четырёхместной? (См. [Кузьмин: комбинаторика].) Упражнение 50 Девушка получила в подарок n бусинок для изготовления ожерелья: из них n 1 белых, n 2 красных и n 3 голубых ( n 1 + n 2 + n 3 = n ). Сколько различных видов ожерелья может получить девушка, если будет менять порядок расположения бусинок? Как будет отличаться ответ, если ожерелье будет замкнутым или незамкнутым? (См. [Кузьмин: комбинаторика].) Упражнение 51 Имеется n одинаковых предметов и столько же различных. Сколькими способами можно вы- брать из них n предметов? Сколькими способами можно упорядочить все 2n вещей? (См. [Кузьмин: комбинаторика].) Упражнение 52 Сколько различных десятизначных чисел можно составить, используя три цифры: 1, 2 и 3, если цифра 3 используется ровно два раза? Сколько из этих чисел делится на 9? (См. [Кузь- мин: комбинаторика].) Упражнение 53 У мамы два яблока, три груши и четыре апельсина. Каждый день в течение девяти дней под- ряд она выдаёт Серёже по одному фрукту. Сколькими способами это можно сделать? (См. [Кузьмин: комбинаторика].) Упражнение 54 Сколькими способами можно разделить m+n+r предметов на три группы так, чтобы в од- ной группе было m предметов, в другой – n и в третьей – r? (См. [Кузьмин: комбинаторика].) Упражнение 55 Есть a шаров чёрного цвета, b – красного, c – белого и d – синего. Сколькими способами можно выстроить эти шары в ряд по k штук. (См. [Кузьмин: комбинаторика].) 16 Симоненко Е.А. Дискретная математика. Практикум Упражнение 56 (С) Сколькими различными способами можно из 30 рабочих сформировать: 1) три бригады по 10 человек в каждой? 2) 10 звеньев по три человека в каждом? (См. [Кузьмин: комбинаторика].) Упражнение 57 (С) Сколькими способами можно разложить девять книг: 1) в четыре бандероли по две книги и в одну бандероль – одну книгу; в три бандероли по три книги? (См. [Кузьмин: комбинаторика].) Упражнение 58 (*) Даны 2⋅n элементов a 1, a 1, a 2, a 2, … , a n , a n , причём a i ≠ a j , i≠ j . Во скольких перестановках из этих 2⋅n элементов никакие два одинаковых не стоят рядом? (См. [Кузьмин: комбинато- рика].) Упражнение 59 Имеется по три экземпляра трёх разных книг. Сколькими различными способами можно расставить на полке три книги? (См. [Кузьмин: комбинаторика].) Упражнение 60 Четверо студентов сдали экзамен. Сколькими способами могли быть поставлены им отметки, если известно, что никто из них не получил неудовлетворительной отметки? (См. [Кузьмин: комбинаторика].) Упражнение 61 (С) В селении проживают 2000 жителей. Доказать, что по крайней мере двое из них имеют оди- наковые инициалы. (См. [Кузьмин: комбинаторика].) Упражнение 62 (С) Сколькими способами можно зажечь n светофоров, из которых k светофоров могут находить- ся в одном из трёх состояний, а остальные n−k – в одном из двух? (См. [Кузьмин: комбинаторика].) Упражнение 63 Сколько k-разрядных натуральных чисел можно записать в p-ичной системе счисления? (См. [Кузьмин: комбинаторика].) Упражнение 64 (С) Из Лондона в Брайтон ведут два шоссе, соединяемых десятью просёлочными дорогами. Сколькими способами можно проехать из Лондона в Брайтон так, чтобы ни разу не пересе- кать пройденный путь? (См. [Кузьмин: комбинаторика].) Комбинаторика: подсчёт 17 Упражнение 65 Сколько целых неотрицательных решений имеет уравнение x 1 + x 2 +…+ x m = n ? (См. [Кузь- мин: комбинаторика].) Упражнение 66 (С) В почтовом отделении продаются открытки десяти сортов. Сколькими способами можно ку- пить в нём: 1) восемь различных открыток; 2) восемь любых открыток; 3) двенадцать откры- ток? (См. [Кузьмин: комбинаторика].) Упражнение 67 (С) Поезду, в котором находится n пассажиров, предстоит сделать m остановок. Сколькими способами могут распределяться пассажиры между этими остановками? (См. [Кузьмин: ком- бинаторика].) Упражнение 68 Сколькими способами можно разложить на k кучек n одинаковых монет так, чтобы в каждой кучке была хотя бы одна монета? (См. [Кузьмин: комбинаторика].) Упражнение 69 В кондитерском магазине продаются четыре сорта пирожных. Сколькими способами можно купить семь пирожных? (См. [Кузьмин: комбинаторика].) Упражнение 70 В домино играют костями (двойными фишками), на каждой половинке из которых изображе- ны точки в количестве от нуля (пустая) до шести. Сколько всего различных костей в полном наборе домино? Сколько можно сделать всего костей домино, если использовать от нуля до n точек? (См. [Кузьмин: комбинаторика].) Упражнение 71 Сколько существует треугольников, длины сторон которых принимают одно из значений – 4, 5, 6, 7? (См. [Кузьмин: комбинаторика].) Упражнение 72 Сколько можно построить различных прямоугольных параллелепипедов, длина каждого ре- бра которых является целым числом от 1 до n? (См. [Кузьмин: комбинаторика].) Упражнение 73 Сколько существует различных натуральных решений уравнения x 1 + x 2 +…+ x m = n ? (См. [Кузьмин: комбинаторика].) 18 Симоненко Е.А. Дискретная математика. Практикум Упражнение 74 Сколькими способами можно представить число n в виде трёх целых положительных слагае- мых, если представления, отличающиеся порядком слагаемых, считать за различные? (См. [Кузьмин: комбинаторика].) Упражнение 75 Сколько различных натуральных решений имеет неравенство x 1 + x 2 +…+ x m ⩽ n ? (См. [Кузь- мин: комбинаторика].) Упражнение 76 Сколькими способами можно составить треугольники, длины сторон которых принимают на- туральные значения большие n и не превосходящие 2⋅n ? Сколько среди них равнобедрен- ных? Сколько среди них равносторонних? (См. [Кузьмин: комбинаторика].) Упражнение 77 Докажите, что для произвольного c>1 и натурального n>1 верно соотношение c n > 1+n⋅(c−1) . (См. [Кузьмин: комбинаторика].) Упражнение 78 Докажите, что для произвольного 0<c<1 и натурального n>1 верно неравенство c n < 1 n⋅(c−1) . (См. [Кузьмин: комбинаторика].) Упражнение 79 Докажите, что если n⋅x мало отлично от нуля, то (1+ x) n ≈ 1+n⋅x . (См. [Кузьмин: комбина- торика].) Комбинаторика: генерация 19 Комбинаторика: генерация Упражнение 1 «Биномиальный коэффициент» Даны натуральные числа n и k, n⩾k . Требуется написать программу, которая вычисляет C n k Напишите различные варианты этой программы: по определению, по сокращённой формуле, по рекуррентной формуле. Выявите ограничения для каждого способа. Упражнение 2 «Генерация всех перестановок» Дано натуральное число n. Требуется написать программу, которая генерирует все переста- новки последовательности натуральных чисел от 1 до n. Реализуйте алгоритм генерации перестановок в лексикографическом порядке. Исчисление конечных сумм 21 Исчисление конечных сумм Упражнение 1 Найдите и докажите формулу для суммы S n = ∑ k =1 n k . Упражнение 2 Найдите и докажите формулу для суммы S n = ∑ k=1 n 2 k Упражнение 3 Найдите и докажите формулу для суммы S n = ∑ k=1 n k 2 Упражнение 4 Найдите и докажите формулу для суммы S n = ∑ k=1 n k 3 Упражнение 5 Найдите формулу для суммы S n = ∑ k=1 n ak 3 + bk 2 + ck+ d . Элементы теории чисел 23 Элементы теории чисел Упражнение 1 Дано натуральное число n. Требуется написать программу, которая находит все делители это- го числа. Упражнение 2 Дано натуральное число n. Требуется написать программу, которая проверяет это число на простоту. Упражнение 3 Дано два натуральных числа n и m, n⩽m . Требуется написать программу, которая находит все простые числа в диапазоне [n,m]. Упражнение 4 Дано натуральное число n. Требуется написать программу, которая находит все простые де- лители этого числа. Рекуррентные соотношения 25 Рекуррентные соотношения Упражнение 1 «Ханойские башни» Напишите программу, которая для заданного натурального n, находит последовательность пе- рекладывания n дисков в задаче о «Ханойских башнях». Теория графов: основы 27 Теория графов: основы … Теория графов: оптимизационные задачи 31 Теория графов: оптимизационные задачи … Теория графов: покрытие и независимость 33 Теория графов: покрытие и независимость … Библиография 35 Библиография 1. [Виленкин: комбинаторика] Виленкин Н.Я., Виленкин А.Н., Виленкин П.А. Комбина- торика. – М.: ФИМА, МЦНМО, 2006. – 400 с. 2. [Грэхем, Кнут, Паташник] Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основания информатики: Пер. с англ. – 3-е изд. – М.: Мир; БИНОМ. Лаборатория зна- ний, 2009. – 703 с. 3. [Кузьмин: комбинаторные методы] Кузьмин О.В. Комбинаторные методы решения ло- гических задач: учеб. пособ. – М.: Дрофа, 2006. – 187 с. 4. [Кузьмин: комбинаторика] Кузьмин О.В. Перечислительная комбинаторика: учеб. по- соб. – М.: Дрофа, 2005. – 110 с. 5. [Мельников] Мельников О.И. Занимательные задачи по теории графов. – 2-е изд. – Минск: ТетраСистемс, 2001. – 144 с. 6. [Новиков] Новиков Ф.А. Дискретная математика для программистов. – 2-е изд. – СПб.: Питер, 2004. – 364 с. 7. [Окулов: ДМ] Окулов С.М. Дискретная математика. Теория и практика решения задач по информатике: учебное пособие. – М.: БИНОМ. Лаборатория знаний, 2008. – 422 с. 8. [Окулов: алгоритмы] Окулов С.М. Программирование в алгоритмах. – 3-е изд. – М.: БИНОМ. Лаборатория знаний, 2007. – 383 с., ил. 9. [Палий] Палий И.А. Дискретная математика. Курс лекций. – М.: Эксмо, 2008. – 352 с. 10. [Седжвик] Седжвик Р. Алгоритмы на C++. – Пер. с англ. – М.: Вильямс, 2011. – 1056 с. 11. [Скиена] Скиена С. Алгоритмы. Руководство по разработке. – 2-е изд.: пер. с англ. – СПб.: БХВ-Петербург, 2011. – 720 с. 12. [Хаггарти] Хаггарти Р. Дискретная математика для программистов. – 2-е изд. – М.: Техносфера, 2005. – 400 с. |