Програмиране и алгорими

Скъпи читатели,

Поради постоянното изчерпване на книгата и трудностите с намирането й в мрежата
за разпространение решихме да ви направим малък „подарък“, като публикуваме книгата
безплатно в електронен вид (лицензът за рапространение се намира на страница 2).

С пожелание за много успехи, 10 февруари 2013
Панайот и Преслав

За контакти с нас (авторите):
 Уеб сайт на книгата: http://www.programirane.org
 Facebook група: http://www.facebook.com/groups/168112146541301

Глава 1 - Компютърна информатика, алгоритми и програмиране 2 от 740

©Автори: Преслав Наков и Панайот Добриков, 2012.

Всички запазени марки, използвани в тази книга, са собственост на техните притежатели.
Всички права запазени. Никоя част от съдържанието на тази книга не може да бъде
репродуцирана или предавана под каквато и да е форма или по какъвто и да е повод без
писменото съгласие на авторите.
Авторите на книгата „Програмиране = ++Алгоритми;“ Преслав Наков и Панайот Добриков ви
предоставят заедно с настоящия pdf файл еднократен, безсрочен, персонален, нетрансферуем
лиценз за ползване на книгата за лични и некомерсиални цели. В допълнение настоящият лиценз
дава право на преподаватели в български училища и университети да използват същата в процеса
на обучение, например като учебник или за подготовка на учебни материали. Настоящият лиценз
не позволява книгата да се разпространява допълнително под каквато и да е форма, както и да се
променя съдържанието на този pdf файл.

Съдържание

СЪДЪРЖАНИЕ ............................................................................................................................. 3
ПРЕДГОВОР ОТ НАУЧНИЯ РЕДАКТОР .......................................................................... 13
ПРЕДГОВОР КЪМ ТРЕТОТ О ИЗДАНИЕ........................................................................... 15
ГЛАВА 0 КОМПЮТЪРНА ИНФОРМАТИ КА, АЛГОРИТМИ, ПРОГР АМИРАНЕ 17
0.1. ПЕРСПЕКТИВНИ НАПРАВЛЕ НИЯ В КОМПЮТЪРНАТА И НФОРМАТИКА .................................... 18
0.1.1. Връзка компютър-потребител ................................................................................... 18
0.1.2. Компютърни комуникации и сигурност .................................................................... 19
0.1.3. Новаторски компютърни архитектури ................................................................... 20
0.1.4. Моделиране на сложни феномени ............................................................................... 20
0.1.5. Изкуствен интелект ...................................................................................................... 21
0.1.6. Нетрадиционни методи за изчисление ...................................................................... 21
0.1.7. Фундаментална компютърна информатика ........................................................... 22
0.2. ПОНЯТИЕТО ЛЕЙМЪР................................................................................................................ 23
0.3. РАЗВИТИЕ НА АЛГОРИТМИ ТЕ ................................................................................................... 24
0.3.1. Произход на думата “алгоритъм”............................................................................. 24
0.3.2. Алгоритмите през вековете......................................................................................... 25
0.3.3. Анализ на алгоритмите ................................................................................................. 25
0.3.4. Изчислимост .................................................................................................................... 26
0.4. ПРОГРАМИРАНЕ = ++АЛГОРИТМИ........................................................................................... 26
0.4.1. За кого е предназначена книгата ................................................................................ 26
0.4.2. Кратко представяне на съдържанието ................................................................... 27
0.4.3. Защо Cи? .......................................................................................................................... 28
0.4.4. Конвенция на изходните текстове ............................................................................. 29
0.5. “СЛЕДГОВОР” ........................................................................................................................... 29
Посвещение ................................................................................................................................. 29
0.5.1. Благодарности ................................................................................................................ 29
0.5.2. Търсене на грешки........................................................................................................... 30
0.5.3. Коментари и въпроси .................................................................................................... 30
ГЛАВА 1 ВЪВЕДЕНИЕ В АЛГОРИТМИТЕ ...................................................................... 33
1.1. ОСНОВНИ МАТЕМАТИЧЕСКИ ПОНЯТИЯ И АЛГОРИТМИ........................................................... 33
1.1.1. Основни математически понятия .............................................................................. 33
- Множества ...........................................................................................................................33
- Числа....................................................................................................................................35
- Целочислено деление и остатък. Брой цифри на естествено число ...................................37
- Сума и произведение...........................................................................................................38
- Степен, логаритъм, n-ти корен ............................................................................................39
- Факториел. Рекурентни функции ........................................................................................40
- Матрици ...............................................................................................................................41
1.1.2. Намиране броя на цифрите на произведение ........................................................... 43
1.1.3. Прости числа................................................................................................................... 44
- Проверка дали дадено число е просто................................................................................45
- Решето на Ератостен. Търсене на прости числа в интервал...............................................47
- Разлагане на число на прости делители ..............................................................................50
- Намиране на броя на нулите, на които завършва произведение ........................................51

Съдържание 4

1.1.4. Мерсенови и съвършени числа...................................................................................... 52
- Мерсенови числа .................................................................................................................52
- Съвършени числа. “Големи” числа.....................................................................................54
1.1.5. Биномни коефициенти, триъгълник на Паскал. Факторизация ........................... 56
1.1.6. Бройни системи и преобразуване ................................................................................ 59
- Преминаване от десетична в p-ична бройна система .........................................................61
- Преминаване от p-ична в десетична бройна система. Формула на Хорнер .......................63
1.1.7. Римски цифри .................................................................................................................. 65
- Представяне на десетично число с римски цифри .............................................................65
- Преобразуване на римско число в десетично ....................................................................66
1.2. РЕКУРСИЯ И ИТЕРАЦИЯ ............................................................................................................ 67
1.2.1. Факториел ....................................................................................................................... 68
1.2.2. Редица на Фибоначи ...................................................................................................... 69
1.2.3. Най-голям общ делител. Алгоритъм на Евклид........................................................ 74
1.2.4. Най-малко общо кратно ............................................................................................... 76
1.2.5. Връщане от рекурсията и използване на променливите ....................................... 77
1.3. ОСНОВНИ КОМБИНАТОРНИ АЛГОРИТМИ ................................................................................ 80
1.3.1. Пермутации ..................................................................................................................... 80
- Генериране...........................................................................................................................81
- Кодиране и декодиране .......................................................................................................84
- Пермутации с повторение ...................................................................................................86
1.3.2. Вариации .......................................................................................................................... 86
- Видове, генериране .............................................................................................................86
- Сума нула.............................................................................................................................88
1.3.3. Комбинации ..................................................................................................................... 90
1.3.4. Разбиване на числа ......................................................................................................... 92
- Генериране на всички разбивания на число като сума от дадени числа ...........................92
- Генериране на всички разбивания на число като произведение от числа .........................93
- Генериране на всички разбивания на число като сума от дадени числа ...........................94
1.3.5. Разбиване на множества ............................................................................................. 96
- Числа на Бел и Стирлинг .....................................................................................................96
1.4. ОЦЕНКА И СЛОЖНОСТ НА АЛГОРИТМИ ................................................................................... 97
1.4.1. Размер на входните данни ............................................................................................ 99
1.4.2. Асимптотична нотация ............................................................................................... 99
1.4.3. O(F): Свойства и примери..........................................................................................100
1.4.4. (F): Свойства и примери .........................................................................................102
1.4.5. (F): Свойства и примери .........................................................................................103
1.4.6. Асимптотични функции и реални числа ..................................................................105
1.4.7. Нарастване на основните функции ..........................................................................106
1.4.8. Определяне на сложност на алгоритъм ..................................................................107
- Елементарна операция .................................................................................