§4. Покрокове виконання алгоритму
Для того, щоб переконатися, що алгоритм працює правильно, необхідно виконати його покроково, за конкретних значень даних. Це можна виконати або «вручну», або за допомогою комп’ютера.
Розглянемо форму «ручного» виконання алгоритму. За такою формою контролю людина формально виконує команди алгоритму і результати заносить у таблицю, складену спеціальним чином. Покажемо на конкретному прикладі покрокове виконання алгоритму для визначення, чи є задане натуральне число простим.
Відомо, що натуральне число є простим, якщо в нього немає інших дільників, крім одиниці і самого числа. Якщо ж у числі є інші дільники, то його називають складеним. Одиниця не є ні простим, ні складеним числом.
Алгоритм визначення виду числа може мати вигляд:
АЛГ Просте число (ціл n , ціл p )
АРГ n
РЕЗ р
ПОЧ цілий і
р:=0
якщо n=1
то р:=1
інакше якщо n>2
то і:=2
поки
пц
якщо n=int (n/i)*i
то р=2
інакше і:=і+1
все
кц
все
все
якщо р=1
то ДРУКУВАТИ (“ Число дорівнює одиниці “)
інакше якщо р=0
то ДРУКУВАТИ (“ Число просте “, n)
інакше
ДРУКУВАТИ (“ Число складене “, n)
все
все
КІН
Пояснення до алгоритму
Найменше просте число – це двійка. Спочатку передбачається, що задане число – просте, тому р=0. Потім здійснюється низка перевірок, в результаті яких р може набути значення 1 (якщо це число 1) або 2 (якщо це число складене). Перевірку дільників числа достатньо робити до кореня квадратного з цього числа. Результат видається в комірці р у вигляді:
Потім аналізується вміст комірки р і залежно від її вмісту видається результат. Звичайно цей алгоритм записують у вигляді алгоритму-функції і використовують як допоміжний.
Алгоритм мовою Паскаль має вигляд:
Program Simple;
var n: longint; i: word;
begin
write (‘ Введіть натуральне число >‘);
readln (n);
if n=1
then writeln (‘ Число дорівнює 1 ‘);
else if n=2
then writeln (‘Число_’, n ‘_просте’)
else begin
i:=3;
while (i<=sqrt(n)) and (n mod i< >0)
do i:=i+2;
if n mod i=0
then writeln (‘Число_’, n, ‘_складене‘);
else writeln (‘Число_’, n, ‘_просте’);
end;
end.
У запропонованому варіанті враховано, що єдине парне просте число – це 2. Якщо введено саме це число, про це видається відповідне повідомлення. Решта простих чисел – непарні, а тому перевіряється подільність тільки на непарні числа (початкове значення і=3, а крок зміни 2). До того ж, умова у циклі while написана з урахуванням того, що всі непарні значення і перебираються, доки задане число n не поділиться на і та і не перевищить квадратного кореня з n.
Після виходу з циклу залишається з’ясувати, за якою умовою він припинив роботу. Якщо за першою (число поділилося націло) число складене, в протилежному випадку – просте.
Результати покрокового виконання алгоритму при n=25 подано в таблиці (розглядаємо розв’язування мовою НАМ).
Для закріплення попереднього матеріалу наводимо блок-схему алгоритму «Просте число»
(схема 9).
Висновок
Покрокове виконання алгоритму виконують, щоб переконатися в правильності його роботи. Звичайно це виконують для складних ділянок алгоритму. На перших кроках у програмуванні це рекомендується робити «вручну», а з набуттям досвіду роботи – за допомогою комп’ютера.
Контрольні запитання
1.З якою метою виконується покрокове виконання алгоритму?
2.Який вигляд має таблиця, у яку вміщують результати покрокового виконання алгоритму?
Вправа
Складіть алгоритм, для визначення того, чи є задумане число N досконалим. Натуральне число називають досконалим, якщо воно дорівнює сумі всіх своїх дільників, крім самого числа.
Наприклад, число 6=1+2+3 є досконалим.
Виконайте покрокове виконання алгоритму при N=28.