Задачник по информатике

Оглавление 3

Введение 5

1 Задачи для систем счисления 6

1.1 Двоичная система счисления 6

1.2 Подсчет числа дней между датами. 6

2 Вычисление специальных чисел 7

3 Числовые треугольники 10

4 Сложные виды рекурсии 14

5 Вычисление констант 16

5.1 Методы и алгоритмы вычисления числа π 16

5.2 Алгоритмы и методы вычисления числа e 18

5.3 Вычисление постоянной Гельфонда 19

5.4 Алгоритмы вычисления золотого сечения 20

5.5 Методы и алгоритмы вычисления функций 20

6 Поиск 21

6.1 Поиск в массивах. 21

6.1.1 Поиск в одномерных массивах 21

6.1.2 Поиск в двухмерных массивах 25

6.2 Поиск в треугольных матрицах 27

7 Шахматные задачи 28

8 Обработка строк символов. 29

9 Транслятор. 30

10 Полиндром 30

11 Комбинаторная генерация 31

11.1 Генерация перестановок 32

11.2 Генерация разбиений числа n 33

11.3 Генерация разбиений множеств 34

11.4 Множества, заданные факториальными числами (2n)!! , (2n-1)!! 34

11.5 Генерация комбинаторных объектов описываемы биномиальными коэффициентами 36

11.6 Генерация множеств, заданных треугольными числами 38

11.7 Тетраэдрические (или треугольные пирамидальные) числа 39

11.8 Тритриангулярные числа 40

11.9 Множества, описываемые центральными биномиальными коэффициентами 40

11.10 Множества, описываемые биномиальными коэффициентами Сn+12n+1 41

11.11 Генерация комбинаторных объектов на основе чисел Фибоначчи 41

11.12 Задание на генерацию множеств Каталана 42

11.13 Генерация множеств, заданных числами Моцкина 53

11.14 Множества, заданные числами Шредера 56

11.15. Генерация комбинаторных объектов на основе чисел Риордана 58

11.16. Генерация множеств, заданных числами Фина 59

11.15 Генерация множеств, заданных сопряженными числами Фина 62

11.16 Генерация множеств, описываемых числами Белла 63

11.17 Генерация множеств, описываемых числами Фубини 64

11.18 Генерация множеств, описываемые формулой Фусса-Каталана 65

11.19 Генерация множеств, описываемых треугольником Каталана 1 67

11.20 Генерация множеств, заданных треугольником Каталана 2 69

11.21 Генерация множеств, заданных треугольником Моцкина 71

11.22 Генерация множеств, описываемых треугольниками Шредера 73

11.23 Генерация множеств, описываемых числами Нараяна 75

11.24 Генерация множеств, заданных треугольником Риордана 76

11.25 Генерация множеств, заданных треугольником Фибоначчи. 78

11.26 Генерация множеств, заданных треугольником Фина 79

11.27 Пирамида Нараяны 79

11.28 Пирамида Эйлера первого рода 80

11.29 Множества, описываемые числами Стирлинга второго рода. 81

11.30 Множества, описываемые числами Стирлинга первого рода 82

11.31 Множества, описываемые треугольником Эйлера первого рода 82

11.32 Множества, описываемые треугольником Эйлера второго рода 83

11.33 Множества, описываемые тангенциальным числами 83

11.34 Множества, описываемые треугольником Эйлера-Бернулли 85

12 Пример реализации алгоритмов комбинаторной генерации для множеств, описываемых числами Каталана. 86

Заключение 91

Литература 92

Приложение 1 94