При розв’язуванні поставлених задач намагатися будувати економічні алгоритмів (зокрема уникати повного перебору тощо).
Лабораторна робота №1-2.
Тема: “Алгоритми та їх властивості”
Питання:
1. Інтуїтивне поняття алгоритму. Приклади алгоритмів.
2. Властивості алгоритмів.
3. Способи подання алгоритмів.
4. Базові структури алгоритмів. Реалізація базових структур в мовах програмування (Pascal, С).
5. Основні типи алгоритмів. Приклади алгоритмів різних типів.
Завдання.
Побудувати алгоритм у вигляді блок-схеми та написати програму на мові Pascal (С) для розв’язання наступних задач:
1. Побудувати алгоритм знаходження дійсних коренів квадратного рівняння 
, де a,b,c – довільні дійсні числа.
2. Задано довжини трьох відрізків a,b,c. Скласти алгоритм, за допомогою якого можна визначити чи існує трикутник із сторонами a,b,c чи ні і якщо трикутник існує, то знайти його площу за допомогою формули Герона.
3. Задано два натуральних числа a,b. Побудувати алгоритм Евкліда для знаходження НСД цих чисел.
4. Скласти алгоритм, за допомогою якого можна знайти кількість натуральних чотирьохзначних чисел, які діляться на 23 і свою останню цифру.
Завдання для самостійного виконання.
1. Підготуватися до самостійної роботи з теми “Поняття алгоритму і його властивості. Базові структури алгоритмів, їх типи і способи подання”.
2. Розглянути теоретичний матеріал наступної теми: “Алгоритмічно розв’язні і нерозв’язні проблеми”.
3. Виконати індивідуальне завдання №1.
4. Подати звіт про виконання лабораторної роботи (див. додаток 1).
|
|
|
Індивідуальні завдання №1.
Побудувати алгоритм у вигляді блок-схем та написати програму мовою Pascal (С) для розв’язування наступних задач:
1. Трикутник задано координатами його вершин A(a1,a2), B(b1,b2), C(c1,c2). На площині вибирається довільна точка X(x1,x2). Скласти алгоритм, за допомогою якого можна визначити де знаходиться точка X відносно трикутника: належить йому, знаходиться всередині нього або за його межами.
2. Назвемо квиток щасливим, якщо в його номері xyztuv (від 000000 до 999999) перші три цифри непарні і різні, а інші – парні. Крім того, 7 і 8 не повинні стояти поруч. Скласти алгоритм для знаходження всіх таких квитків.
3. Скласти алгоритм, який дозволяє приписати до числа 1022 зліва і справа по одній цифрі так, щоб одержане 6-значне число ділилось на 7, 8 і 9.
4. Українську грошову одиницю – 1 гривну можна розміняти монетами по 1, 2, 5, 10, 25 і 50 копійок. Скласти алгоритм, який визначає скількома способами це можна зробити?
5. Скласти алгоритм, за допомогою якого для довільної формули алгебри висловлень від n змінних (1<=n<=4), яка задана таблично, визначається до якого класу формул вона відноситься.
6. Скласти алгоритм, за допомогою якого для довільної бульової функції від n змінних (1<=n<=4), яка задана таблично, будується досконала диз’юнктивна нормальна (ДДНФ).
|
|
|
7. Скласти алгоритм, за допомогою якого для довільної бульової функції від n змінних (1<=n<=4), яка задана таблично, будується досконала кон’юнктивна нормальна форма (ДКНФ).
8. Скласти алгоритм, за допомогою якого для алгебраїчного многочлена n-го степеня (1<=n<=10) з цілими коефіцієнтами визначається чи має він цілі корені, і якщо має, то які.
9. Скласти алгоритм, за допомогою якого для довільного скінченного неорієнтованого графа з n вершинами (1<=n<=20), що задається матрицею суміжності, визначається чи є він ейлеровим. Примітка. Скористатися критерієм ейлерового графа.
10. Скласти алгоритм, за допомогою якого для довільного скінченного неорієнтованого графа з n вершинами (1<=n<=20), що задається матрицею суміжності, визначається чи є він гамільтоновим. Примітка. Скористатися теоремою Дірака.
11. Побудувати алгоритм, який реалізує теорему Лагранжа: довільне натуральне число n можна подати у вигляді: n=x2+y2+z2+t2, де n,x,y,z,t Î NÈ{0}, nÎ[0, 65535].
12. Скласти алгоритм для знаходження 4-значних чисел, які дорівнюють сумі факторіалів своїх цифр.
13. Скласти алгоритм, за допомогою якого можна знайти кількість натуральних чотирьохзначних чисел, які діляться на задане натуральне число m і свою останню цифру.
|
|
|
14. Скласти алгоритм для знаходження наближеного значення квадратного кореня додатного дійсного числа a із заданою точністю 
, використовуючи рекурентну формулу 
, де 
, 
- початкове наближення.
Примітка. При наближеному обчисленні кореня з числа a вважають, що досягнута задана точність, якщо 
, при цьому початкове наближення можна покласти рівним a.
15. Побудувати алгоритм у вигляді блок-схеми та написати програму мовою Pascal для знаходження значення алгебраїчного многочлена n-го степеня за схемою Горнера:
.
16. Скласти алгоритм, за допомогою якого можна знайти кількість розміщень з n елементів по k елементів без повторень 
і кількість комбінацій з n елементів по k елементів 
без повторень, де величини n і m натуральні і виконується умова m<=n.
17. Скласти програму, за допомогою якої можна визначати коефіцієнти для бінома Ньютона виразу 
за допомогою трикутника Паскаля.
18. Скласти програму знаходження n! для заданого натурального числа n за означенням і за формулою Стірлінга, згідно якої 
. Після одержаних двох значень знайти абсолютну похибку обчислень факторіала за формулою Стірлінга.
|
|
|
Примітки.
При розв’язуванні поставлених задач намагатися будувати економічні алгоритмів (зокрема уникати повного перебору тощо).
2. Розв’язок задач оформляється за схемою:
1) назва задачі:
вказується назва задачі, що розв'язується, ім'я програми, система програмування, що використовується.
2) вхідні дані:
описуються вхідні дані, їх тип, вказуються межі, в яких вони можуть змінюватися, значення, які вони можуть приймати і т.д.
3) вихідні дані: описуються вихідні дані, які є результатом розв'язування поставленої задачі.
3. Програма повинна:
- видавати на дисплей умову задачі; запит на введення вхідних даних, яких саме і в якій формі; повідомлення про одержані результати;
- мати захист на введення некоректних вхідних даних.
Контрольні запитання:
1. Яке походження терміну “алгоритм“?
2. Що називають алгоритмом у інтуїтивному розумінні?
3. Назвати основні властивості алгоритмів.
4. Перелічити основні способи задання алгоритмів.
5. Які основні базові конструкції використовуються при побудові алгоритмів і яке їх графічне подання?
6. Які існують типи алгоритмів?
7. Що таке масова проблема?
8. Що таке алгоритмічна проблема?
9. Яка масова проблема називається алгоритмічно нерозв’язною?
10. Навести приклади алгоритмічно нерозв’язних проблем?
11. Які шляхи уточнення поняття алгоритму відомі в математиці?
12. Які основні відкриття і застосування теорії алгоритмів?
Теми рефератів:
1. Історія виникнення поняття алгоритму.
2. Приклади алгоритмічно нерозв’язуваних проблем у математиці.
3. Автобіографія вчених і характеристика їх наукового доробку:
- Алонзо Чьорч;
- Стефан Коул Кліні;
- Алан Тьюрінг;
- Еміль Пост;
- Марков Андрій Андрійович;
- Колмогоров Андрій Миколайович.
Додаток 1.
Дата добавления: 2018-05-12; просмотров: 152; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!