11 клас (академ). Приклади програм з використання циклів. - 11 клас (академічний) - Інформатика - Каталог статей - Кабінет інформатики Черкаської СПШ №20
Кабінет 208
Головна | Реєстрація | Вхід
Четвер, 08.12.2016, 07:57
Меню сайту
Форма входу

Категорії розділу
5 клас [11]
6 клас [24]
7 клас [16]
8 клас [15]
9 клас [25]
10 клас (стардарт) [17]
10 клас (академічний) [23]
11 клас (стандарт) [21]
11 клас (академічний) [33]
Головна » Статті » Інформатика » 11 клас (академічний)

11 клас (академ). Приклади програм з використання циклів.
Приклади програм з використання циклів.

Презентація пояснення матеріалу

При розв’язуванні багатьох задач доцільно використовувати ще 2 арифметичні операції: знаходження неповної частки і остачі при діленні цілого числа на натуральне.  Нагадаємо, що для будь-яке ціле число m = nq + r (q – неповна частка, число r – остача). Для знаходження неповної частки в Delphi використовується операція div, а для знаходження остачі – mod. Наприклад,   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  then k := k+1;
// Якщо i – дільник n, то збільшення кількості дільників на 1
  if k = 2 then Label1.Caption := 'просте' else Label1.Caption := 'не просте';
end;


Але при великих n час виконання цієї програми буде значним і його можна суттєво зменшити, якщо врахувати такі властивості натуральних чисел:
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 парне і n<>2, то воно не просте
    else begin
              k := 3;
//інакше, то будемо шукати його дільники, починаючи з числа 3
              while (k <= sqrt(n)) and f do
// Шукати дільники числа будемо серед чисел, які не перевищують арифметичний квадратний корінь з числа n, і поки такий дільник не знайшовся
              if n mod k = 0 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(«число»).

Задача 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;



Домашнє завдання
    §2.9 пит. 1-12 стор. 92
    Впр. 5 (для чисел 125 і 54), 13 стор. 94   
    Підготуватись до пр/роботи №9

Категорія: 11 клас (академічний) | Додав: admin (05.10.2013)
Переглядів: 902
Пошук
Статистика

Онлайн всього: 1
Гостей: 1
Користувачів: 0
Copyright MyCorp © 2016
Безкоштовний хостинг uCoz