8 клас. Інформатика. Дистанційне навчання.: Рекурсивні алгоритми

Класифікація алгоритмів

в компетентнісних завданнях

з теми «Алгоритми та програмування»

Під час розв’язування компетентнісних задачах з інформатики створюються, реалізуються, тестуються найчастіше використовуються:

· алгоритми форматування(редагування) об’єктів за даними параметрами;

· алгоритми переміщення(розміщення) об’єктів за даними параметрами;

· алгоритми видалення(приховування) об’єктів за даними параметрами;

· алгоритми перевірки властивостей об’єктів за даними параметрами;

· алгоритми зміни або заміни властивостей об’єктів за даними параметрами;

· обчислювальні алгоритми: алгоритми-калькулятори;

· алгоритми пошуку об’єктів за даними параметрами;.

· алгоритми фільтрування змінних величин у лінійному масиві;

· алгоритми (створення)генерування об’єктів: алгоритми-генератори;

· алгоритми перестановки та впорядкування числових та символьних величин.

В ході розв’язування компетентнісних задач з інформатики на початкових етапах розв’язування проводиться аналіз властивостей об’єктів та даних умови для того, щоб використати уміння та навички під час реалізації різних видів алгоритмів, а саме створюються:

1.Нелінійні алгоритми:

1.1. Алгоритми розгалуження :

1.1.1. Алгоритми з повним розгалуженням;

1.1.2. Алгоритми з певним розгалуження;

1.2. Алгоритми з узагальненим вибором:

1.2.1. Алгоритми з повним узагальненим вибором;

1.2.2. Алгоритми з неповним узагальненим вибором;

1.3 . Циклічні алгоритми:

1.3.1 Циклічні алгоритми з лічильником з кроком +1;

1.3.2 Циклічні алгоритми з лічильником з кроком -1;

1.3.3 Циклічні алгоритми з лічильником з кроком +m;

1.3.4 Циклічні алгоритми з лічильником з кроком –m;

1.4. Циклічні алгоритми з передумовою:

1.4.1. Циклічні алгоритми з простою передумовою;

1.4.2. Циклічні алгоритми з складеною передумовою;

1.5. Циклічні алгоритми з післяумовою:

1.5.1. Циклічні алгоритми з простою післяумовою;

1.5.2. Циклічні алгоритми з складеною післяумовою.

1.6. Вкладені циклічні алгоритми:

1.6.1. Цикл лічильником має цикл з післяумовою;

1.6.2. Цикл лічильником має цикл з передумовою;

1.6.3. Цикл лічильником має цикл з лічильником;

1.6.4. Цикл передумовою має цикл з лічильником;

1.6.5. Цикл передумовою має цикл з передумовою;

1.6.6. Цикл передумовою має цикл з лічильником;

1.6.7. Цикл ісляумовою має цикл з лічильником;

1.6.8. Цикл післяумовою має цикл з передумовою;

1.6.9. Цикл післяумовою має цикл з післяумовою.

1.7. Рекурсивні алгоритми:

1.7.1. Алгоритм з рекурсивною процедурою;

1.7.2. Алгоритм з рекурсивною функцією;

1.8. Ітераційні алгоритми без рекурсії:

1.7.1. Алгоритм з процедурною ітерацією без рекурсії;

1.7.2. Алгоритм з ітераційною функцією без рекурсії;

Завдання для самостійного опрацювання.

Приклад 1. Рекурсивний алгоритм факторіалу невід’ємного числа.

Побудуємо математичну модель рекурсивного алгоритму факторіалу невід’ємного числа.

Означення. Факторіалом цілого невід'ємного числа m називається добуток всіх натуральних чисел від 1 до m і позначається m!.

Приклади: 3!=1*2*3=6; 4!=1*2*3*4=24; 6!= 1*2*3*4*5*6=720.

Якщо створити функцію: q(m) = m!, то мають місце рекурентні співвідношення:

k! = k*q(k – 1) (*)

q(0) = 1 (**)

Перша рівність описує крок рекурсії - метод обчислення q(k) через q(k - 1). Друга рівність вказує, коли при обчисленні функції слід зупинитися. Якщо його не використовувати, то функція буде працювати нескінченно довго.

Наприклад, значення q(7) можна обчислити таким чином:

7! = 7 * q(6) = …= 7 * 6 * 5 * q(4) = 7 * 6 * 5 * 4 * q(3) =

= 7 *6* 5 * 4 * 3 * q(2) = 7 * 6 * 5 * 4 * 3 * 2 * q(1) =

= 7 * 6 * 5 * 4 * 3 * 2 * 1 * 1 = 7*720 = 5040

Очевидно, що при обчисленні q(k) слід зробити k рекурсивних викликів.

Завдання 1. Самостійно реалізувати та протестувати цей рекурсивний алгоритм мовою програмування.

Приклад 2. Рекурсивний алгоритм піднесення до степеня числа.

Побудуємо математичну модель рекурсивного алгоритму піднесення до степеня числа.

Найпростішим та досить важливими для інформатики є числа, які є степенями 2. Отже, розглянемо на прикладі таких чисел рекурсивний алгоритм піднесення числа до степеня, який пізніше спробуємо реалізувати ітераційним методом.

Означення. Добуток р*р*р*……*р*р декількох однакових дійсних множників р називають степенем дійсного числа р, і записють степінь числа р^m.

Приклад. 4³=4*4*4=64; 0,3⁶=0,3*0,3*0,3*0,3*0,3*0,3=0,000729

Для того щоб можливо було написати рекурсивну функцію необхідно виділити основні рекурентні співвідношення. Ми знаємо, що 4⁰= 1 та 4¹ = 4. Кожна наступна степінь 4 утворюється за принципом множення на 4 числа, що утворилося раніше. Отже, справедливими будуть такі формули:

R(0) = 1,

R(1) = 4,

R(k) = 4 * R(k - 1).

Завдання 3. Самостійно реалізувати та протестувати цей рекурсивний алгоритм мовою програмування.

Прийоми і технології мислення програміста

Кліпове мислення ( Шаблон:псих. звичка сприймати інформацію за допомогою коротких, яскравих посилів, що втілені у форматі постеру, відеокліпу. Суть «кліпового мислення» полягає в здатності людини швидко переключатися між різними за смислом фрагментами інформації та швидко її обробляти)

Практичне мислення(застосування раціонального вибору умінь і знань для відповідальних дій)

Теоретичне мислення(систематизація, узагальнення, абстрагування об’єктів)

Абстрактне мислення(уміння відобразити головні ідеї та сутнісні властивості в системі)

Асоціативне мислення(дослідження можливостей об’єктів в середовищі і створення ситуації успіху)

Критичне мислення(подолання сумнів до інформації, аналіз, інтеграція, синтез)

Логічне мислення(послідовність ланцюгів дедукції та індукції)

Креативне мислення(уміння знайти власну нішу інтересів, помічати "невидимі" зв'язки і степені свободи в системі об'єктів і їх перенесення по аналогії та застосування у своїй творчості)

Нестандартне мислення(генерування відкритих закритих, тонких, провокативне запитання до невідомого об’єкта);

Дивергентне мислення(спрощення до адекватного сприйняття корисності)

Когнітивне мислення(пошук правильної, адекватної відповіді)

Системне мислення(використання системних зв’язків та ієрархій)

Емоційне мислення(уміння змінювати емоції в різних випадках)

Штучне мислення(уміння програмувати алгоритми для складних дій)

Інтуїтивне мислення(розрізнення та об’єднання об’єктів)

Саногенне мислення(мислення в стані переляків, стресів, страхів)

Дискурсивне мислення(психологічна зміна догматів та правил)

Образне мислення(поєднання типажів в одну систему)

Проблемні відкриті запитання.

1.Який із видів мислення найкраще навчає вчитись самостійно?

2.Яке мислення є більш ефективним критичне чи креативне?

3.Чи всіх можна навчити критично мислити?

Приклад 3. Рекурсивний алгоритм суми цифр цілого невід’ємного числа.

Побудуємо математичну модель рекурсивного алгоритму суми цифр цілого невід’ємного числа.

Означення. Сумою цифр s(m)=m₁+m₂+m₃+…+ m_k

цілого невід'ємного числа m= m₁m₂m₃…+m_k

називається сума усіх розрядів цілого невід'ємного числа і позначається s(m)

Приклади: s(123)=1+2+3=6; s(1234)=1+2+3+4=10;

s(123456) = 1+2+3+4+5+6=21.

Суму чисел натурального числа k можна знайти за допомогою функції s(k), визначеної в такий спосіб:

s(0) = 0 (*)

s(k) =k mod 10 + s(k div 10) (**)

Умова продовження рекурсії: сума цифр числа дорівнює останній цифрі плюс сума цифр числа без останньої цифри (числа, поділеної без остачі на 10).

Умова закінчення рекурсії: Якщо число дорівнює 0, то сума його цифр дорівнює 0.

Наприклад, сума цифр числа 576 буде обчислюватися так:

s(576) = 6 + s(57) = 6 + 7 +s (5) = 6 + 7 + 5 + s(0) = 6 + 7 + 5 + 0 = 18.

Завдання 3. Самостійно реалізувати та протестувати цей рекурсивний алгоритм мовою програмування.

Приклад 4. Відбір в розвідку [ACM, 1999]. Із n солдатів, вишикуваних в шеренгу, потрібно відібрати кількох в розвідку. Для здійснення цього виконується наступна операція: якщо солдат в шерензі більше ніж 3, то видаляються всі солдати, які стоять на парних позиціях, або всі солдати, які стоять на непарних позиціях. Ця процедура повторюється до тих пір, поки в шерензі залишиться 3 або менше солдатів. Їх і відсилають в розвідку. Обчислити кількість способів, якими таким чином можуть бути сформовані групи розвідників рівно з трьох осіб.

Вхідні дані. Кількість солдатів в шерензі n (0 <k ≤ 10⁵).

Вихідні дані. Кількість способів, якими можна відібрати солдат в розвідку описаним вище способом.

Приклад вхідних та вихідних даних:

Введення Виведення

10 2

4 0

Математична модель рекурсивного алгоритму відбору розвідників.

Нехай функція r(m) кількість способів, якими можна сформувати групи розвідників з m осіб в шерензі. Оскільки нас цікавлять тільки групи по три розвідника, то r(1) = 0, r(2) = 0, r(3) = 1. Тобто з трьох осіб можна сформувати тільки одну групу, з одного або двох - жодної.

Якщо m – парне число, то застосовуючи дану процедуру видалення солдат в шерензі, ми отримаємо або 0,5m солдатів, що стоять на парних позиціях, або 0,5m солдатів, що стоять на непарних позиціях. Тобто r(m) = 2 · r(0,5m) при парному m.

Якщо n непарне, то після видалення залишиться або 0,5m солдатів стояли на парних позиціях, або 0,5m + 1 солдат, які стояли на непарних позиціях. Загальна кількість способів при непарному m рівне

r(m) = r(m/2) + r(m/2 + 1).

Таким чином, отримана рекурентна формула для обчислення значення r(n):

r(m) = 2 · r(m / 2), якщо m - парне =2k;

r (m) = r (m / 2) + r(m/ 2 + 1), якщо m - непарне =2k-1;

r (1) = 0, r(2) = 0, r (3) = 1.

https://scratch.mit.edu/projects/editor/?tip_bar=home - Scratch он-лайн

https://studio.code.org/courses - студія Code.org

Історія розвитку мов програмування

Всю історію комп'ютерної індустрії і комп'ютерних наук з певної точки зору можна уявити як історію розвитку мов програмування. Змінюються часи, ускладняється завдання, те, що раніше вимагало людино-років, нині ентузіасти роблять на коліні за кілька тижнів; накопичена величезна маса типових рішень, типових бібліотек та типових програмістів. А створення, розвиток і зміна мов програмування йде повним ходом.

Об'єкт дослідження теми - це мови програмування, які в різний час і в різних умовах пропонувалися і пропонуються як альтернатива звичному і загальноприйнятому; їх доля, властивості і шанси.

Зараз я запропоную Вам коротку історію мов програмування:

1801 - Йосип Марія Жаккард за допомогою перфокарт вишиває «hello world» на тканини. Хабровчане тих часів незадоволені відсутністю хвостовій рекурсії, багатопоточності і заголовних букв.

1842 - Ада Лавлейс пише першу програму. Її успіхам перешкоджає маленька проблемка - комп'ютера для виконання цієї програми ще не винайшли. Через півтора століття архітектори корпоративних додатків переймуть техніку Ади з написання неісполняемих програм і назвуть цей метод UML.

1936 - Алан Тьюринг винаходить все мови, які теоретично можуть існувати, але не встигає запатентувати їх.

1936 - Алонзо Черч теж винаходить можливі мови для програмування, але тільки найкращі. Його лямбда-числення непопулярне, тому що не схоже на Сі. Критиків не бентежить, що мова Сі ще не винайшли.

1940-і - Різні «комп'ютери» «програмують», паяяючи дроти і замикаючи контакти.

1957 - Джон Бакус і IBM винаходять Фортран. З приводу IBM і Фортрана не жартують. Компілятор Фортрана видає помилку, якщо на програміста немає краватки.

1958 - Джон Маккарті і Пол Грем придумують ЛИСП. Популярності ЛИСП заважає виснаження світових запасів круглих дужок, на щастя, запаси фігурних і кутових дужок практично невичерпні. Проте, ЛИСП (в ??наш час відомий як Лісп, іноді Arc) - загальновизнаний стандарт в області «фундаментальних концепцій інформаційних технологій, таких як рекурсія і поблажливість»

1964 - Джон Кемні і Томас Курц пишуть БЕЙСІК, неструктурований мову для людей, які не розуміються на програмуванні.

1970 - Гай Стіл і Джеральд Зюсман створюють Схему. В результаті їхніх зусиль з'являється "Всемогутня Лямбда", а потім «Всемогутня Лямбда, Універсальна Мультиварка» ..

1970 - Ніклас Вірт створює процедурний мову Паскаль. Багато хто незадоволений відмінним від Сі синтаксисом оператора присвоювання. Критиків не бентежить, що мова Сі ще не винайшли.

1972 - Денніс Річі винаходить пістолет, що стріляє в обидві сторони одночасно. Незадоволений числом смертей і каліцтв, принесених цим пристроєм, він створює мову Сі і Юнекс.

1972 - Ален Колмера винаходить логічна мова Пролог. Завдання-максимум вченого - наділити комп'ютер інтелектом дворічної дитини. Він блискуче справляється із завданням, написавши програму, що відповідає «Ні!» На будь-який запит.

1973 - Робін Мілнер пише МЛ, мова на основі теорії типів M & M. МЛ породжує СМЛ, що володіє формально описаної семантикою. У число мов сімейства МЛ входять OCaml, F # і Visual Basic.

1980 - Алан Кей пише Smalltalk і придумує термін «об'єктно-орієнтований». На прохання пояснити він відповідає «Програми в ООП - просто об'єкти». На питання, з чого складаються об'єкти, він відповідає «з об'єктів» і пояснює «все складається з об'єктів, в тому числі і об'єкти. І стоїть на чотирьох слонах. »

1983 - Бйорн Страуструп бере мову Сі, ліпить поверх нього все, що приходить на розум, і називає це С ++. Щоб програми скомпілювати за розумний час, їх доводиться відправляти в майбутнє штучного інтелекту Скайнет. Навіщо це потрібно Скайнет, неясно.

1986 - Бред Кокс і Том Лав придумують Objective-C. За їх словами, він «поєднує безпеку З з неймовірною швидкістю Smalltalk».

1987 - Ларрі Волл засинає на клавіатурі. Прокинувшись, він сприймає рядок на моніторі за програму на мові, який Господь предначертал написати своєму пророку Ларрі. Так з'являється Перл.

1990 - Комісія у складі Саймона Пейтон-Джонса, Пола Худака, Філіпа Водлера, Ештона Катчера і Товариства із захисту прав тварин проектує Хаскелл - чисто функціональна мова з ледачими обчисленнями.

1991 - Голландський програміст Гвідо ван Россум відправляється в Аргентину. Перенісши загадкову операцію, він повертається з шрамом на черепі, пише Пітон, натовпи шанувальників проголошують його Довічним Диктатором, і він заявляє, що «є тільки один спосіб».

1995 - Брендан Ейк збирає помилки всіх відомих мов, додає кілька нових і об'єднує всі в Livescript. Через деякий час мова перейменовують в Javascript, щоб скористатися популярністю мови Java. Через деякий час мова перейменовують в ECMAscript.

Рік випуску 1996 - Джеймс Гослінг придумує Яву. Ява - досить багатослівний статично типізований об'єктно-орієнтована мова на основі класів, із збіркою сміття, одиночної диспетчеризацией викликів, одиночним наслідуванням реалізації і множинним спадкуванням інтерфейсів. Sun голосно проголошує Java самим інноваційним мовою.

2001 - Андерс Хейлсберг придумує C1. C1 - досить багатослівний статично типізований об'єктно-орієнтована мова на основі класів, із збіркою сміття, одиночної диспетчеризацией викликів, одиночним наслідуванням реалізації і множинним спадкуванням інтерфейсів. Microsoft голосно проголошує C1 самим інноваційним мовою.

Самостійна пошуково-дослідна робота
для збагачення словникового запасу юного програміста;