Розглянемо кілька цікавих і корисних для подальшого вивчення теми задач, в алгоритмах розв’язування яких використовуються цикли.
При розв’язуванні багатьох задач доцільно використовувати ще 2 арифметичні операції: знаходження неповної частки і остачі при діленні цілого числа на натуральне. Нагадаємо, що для будь-якого цілого числа m і натурального числа n існує єдина пара цілих чисел q і r (0 ≤ r < n), таких що m = nq + r. Число q називається неповною часткою, а число r – остачею. Для знаходження неповної частки в Delphi використовується операція div(англ. divide – поділити), а для знаходження остачі – mod(англ. modulo – остача від ділення). Наприклад,
23 div 5 = 4, 23 mod 5 = 3,
28 div 4 = 7, 28 mod 4 = 0,
2 div 3 = 0, 2 mod 3 = 2.
Задача 3. Дано натуральне числоn, більше 1. З’ясувати, чи є це число простим.
Нагадаємо, що простим називається натуральне число, яке має рівно 2 дільники. Тому можна перебрати всі натуральні числа від 1 до даного числа і підрахувати кількість дільників даного числа. Якщо ця кількість дорівнює 2, то це число просте, якщо більше – не просте. Відповідний фрагмент програми виглядатиме так:
var i, k, n: Integer;
Begin
n := StrToInt(Edit1.Text);
k := 0;// Кількість дільників числаn
for i := 1 to n do
if n mod i = 0 //Перевірка, чи є число i дільником числа n
then k := k+1;//Збільшення на 1 кількості дільників числа n, якщо число i є його дільником
if k = 2
then Label1.Caption := 'просте'
else Label1.Caption := 'не просте';
end;
Функція StrToInt(англ. stringto integer– рядок в ціле) використовується для переведення текстового представлення цілого числа в саме ціле число.
Але час виконання програми для розв’язування цієї задачі можна суттєво зменшити, якщо врахувати такі властивості натуральних чисел:
1. Будь-яке натуральне число, більше 1, завжди має 2 дільники (одиницю і саме це число). Тому простим буде таке натуральне число, яке не матиме інших дільників.
2. Серед натуральних чисел тільки одне парне число є простим (2), всі інші прості числа – непарні.
3. Якщо не враховувати саме число, у натурального числа немає дільників, які перевищують арифметичний квадратний корінь з цього числа.
Якщо при складання програми використати вказані властивості, то відповідний фрагмент програми може бути таким:
var i, k, n: Integer; f: Boolean;
Begin
n := StrToInt(Edit1.Text);
f := true;// Будемо поки що вважати число nпростим, адже дільників у нього поки що не знайшлося
if (n mod 2 = 0) and (n <> 2)
then f := false// Якщо число n парне і не дорівнює 2, то воно не просте
Else
Begin
k := 3;// Якщо число непарне, то будемо шукати його дільники, починаючи з числа 3
while (k <= sqrt(n)) and f do // Шукати дільники числа будемо серед чисел, які не перевищують арифметичний квадратний корінь з числа n, і поки такий дільник не знайшовся
if n mod k = 0// перевірка, чи є число k дільником числа n
then f := false
else k := k + 2;// Якщо k не є дільником n, то наступний можливий дільник – наступне непарне число
end;
If f
then Label1.Caption := 'просте'
else Label1.Caption := 'не просте';
end;
У наведеному фрагменті програми використана логічна змінна f. Її значення визначатиме, чи є число n простим чи ні: true – просте, false– не просте. Тип логічної змінної в Delphi позначається Boolean, на честь Джорджа Буля. Для обчислення арифметичного квадратного кореня використана стандартна функція sqrt (англ. square root– квадратний корінь).
Задача 4. Знайти найбільший спільний дільник (НСД) двох даних натуральних чисел aіb (a > b).
У курсі математики 6 класу ви навчилися знаходити НСД чисел, розкладаючи їх на прості множники. Можна скласти програму, в якій реалізується цей метод знаходження НСД.
Але більш простою виявляється програма, яка реалізує інший метод знаходження НСД, що базується на такому математичному твердженні: якщо a > b, то НСД (a, b) = НСД (b, r), де r – остача від ділення a на b. Ідея цього методу полягає в тому, що послідовно замінюються числа, для яких потрібно знайти НСД: більше з них замінюється на менше, а менше – на остачу від ділення більшого числа на менше. Закінчується цей процес замінювання тоді, коли остача від ділення стає рівною нулю. Тоді НСД дорівнює останній відмінній від 0 остачі від ділення.
Наприклад,
НСД(80, 12) = НСД(12, 8) = НСД(8, 4) = НСД(4,0) = 4,
НСД(125, 54) = НСД(54, 17) = НСД(17, 3) = НСД(3,2) = НСД(2,1) = НСД(1, 0) = 1.
Цей метод знаходження НСД називається алгоритмом Евкліда. Перевірте цей метод знаходження НСД для різних пар натуральних чисел.
Нижче наведений фрагмент програми, в якому знаходиться НСД двох чисел за алгоритмом Евкліда.
var a, b, r: Integer;
Begin
a := StrToInt(Edit1.Text);
b := StrToInt(Edit2.Text);
r := a mod b;
while r <> 0 do
Begin
a := b;
b := r;
r := a mod b;
end;
Label1.Caption := IntToStr (b);
end;
Звертаємо вашу увагу, що наведений фрагмент програми працює правильно і в тих випадках, коли
a ≤ b. Спробуйте самостійно з’ясувати, чому.
