Лабораторна робота №4
(модуль 1)
Тема: Програмування циклів. Оператори повторення з передумовою та постумовою. (2 години)
Мета: Формувати навички і вміння складати циклічні алгоритми, використовуючи оператори повторення з переумовою та постумовою й реалізовувати їх засобами мови програмування Pascal.
Література:
Архангельский А.Я. Язык Pascal и основы программирования в Delphi
Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.– М.: Мир, 1979.– 536 с.
Венц А. Н. Профессия – программист.– Ростов: Изд-во «Феникс», 1999.– 384 с.
Виноградов И.М. Основы теории чисел.– М.: Наука, 1972.– 167 с.
Вирт Н.. Алгоритмы + структуры данных = программы. Москва, Мир, 1985 г. 406 с.
Вирт Н.. Алгоритмы и структуры данных. Москва, Мир, 1989 г. 420 с.
Гусева А.И. Учимся информатике: задачи и методы решения.– М.: «Диалог – МИФИ», 1998.– 320 с.
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ.– М.: МЦНМО, 1999.– 960 с.
Короткі теоретичні відомості.
У більш загальному випадку, коли кількість повторень заздалегідь невідома, а задана деяка умова закінчення (або продовження) циклу, у мові Pascal використовують інші оператори повторення: оператор циклу з передумовою While і оператор циклу з постумовою Repeat.
Оператор циклу з передумовою визначений діаграмою:
Оператор (тіло циклу) виконується доти, доки умова істинна. Якщо при першій перевірці умова виявилась хибною, оператор не виконується ні разу.
Оператор циклу з постумовою визначений діаграмою:
Тіло циклу Repeat виконується доти, доки умова приймає значення False. Дії, що містяться в тілі циклу, будуть виконані принаймні один раз. Таким чином, умова є умовою закінчення циклу.
Цикли While і Repeat називають ще ітераційними циклами, оскільки за їх допомогою легко реалізувати різного роду ітераційні обчислення (обчислення, в яких кожний наступний результат є уточненням попереднього). Умова закінчення циклу – досягнення відхилення результату Yn від Yn-1 деякої допустимої похибки e:|Yn - Yn-1| < e.
Приклад. Знайти найменший натуральний розв’язок нерівності
x3 + ax2 + bx + c > 0
з цілими коефіцієнтами.Очевидний алгоритм пошуку розв’язку складається у послідовному обчисленні значень
Y = x3+ax2+bx+c для x = 1, 2, 3, ... до тих пір, поки Y<= 0.
Program UneqvSolution;Var a, b, c : Integer; X, Y: Integer;Procedure FindRoot (a, b, c : Integer; Var X: Integer);Var Y : integer;Begin X := 1; Y := a + b + c + 1; While Y <= 0 Do Begin X := Succ(X); Y := ((X + a)*X + b)*X + c; End;End;Begin FindRoot (a, b, c, X);End.
Задачі для самостійного розв’язування
Розробити програму, яка вибирає з десяткового запису натурального числа N тільки непарні цифри і записує їх не змінюючи порядка.
Нехай запис натурального числа N у десятковій системі є akak-1...a1a0. Скласти програму, яка знаходить ak-ak-1+...+(-1)ka0 (тобто суму цифр числа зі зміною знаків).
Послідовність Фіббоначчі визначається так:a(0)= 0, a(1) = 1, a(k) = a(k-1) + a(k-2) при k >= 2. Дано n, обчислити a(n).
Розв’яжіть попередню задачу, якщо необхідно, щоб число операцій було пропорціонально log n. (Змінні повинні бути цілочисельними.)
Вказівка. Пару сусідніх чисел Фіббоначчі отримуємо із попередньої множенням на матрицю
|1 1|
|1 0| .
Так що задача зводиться до піднесення матриці до n степеня. Це можна зробити за C*log n дій тим же способом, що і для чисел.
Дано натуральне n, обчислити 1/0!+1/1!+...+1/n!.
Дано натуральне n, обчислити 1/0!+1/1!+...+1/n!, якщо потрібно, щоб кількість операцій була б не більше C*n для деякої константи С.
Скласти програму, яка друкує квадрати всіх натуральних чисел від 0 до заданого натурального n.
Скласти програму, яка друкує квадрати всіх натуральних чисел від 0 до заданого натурального n. Дозволяється використовувати лише додавання і віднімання, причому загальна кількість дій повинна бути порядка n.
Скласти програму, яка друкує всі множники заданого натурального числа n > 0.
Перевірити, чи є заданое натуральне число n > 1 простим.