У тілі циклу може перебувати будь-який оператор, у тому числі й інший оператор циклу. Така конструкція називається кратними або вкладеними циклами. Число вкладень циклів не обмежене. Якщо цикл містить тільки один вкладений цикл, то він називається подвійним циклом.
Цикл, який містить вкладений цикл, називається зовнішнім, вкладений цикл називається внутрішнім. Керуюча змінна внутрішнього циклу завжди міняється швидше, чим змінна зовнішнього. Це означає, що для кожного значення змінної зовнішнього циклу перебираються всі значення змінної внутрішнього. У випадку вкладення декількох циклів це правило також діє: швидше всього міняється змінна самого внутрішнього циклу.
Пояснимо сказане на прикладі. У конструкції, описаної нижче:
for i:=1 to 5 do begin {початок зовнішнього циклу}
j:=-5;
while j<=5+1e-6 do begin {початок внутрішнього циклу}
{ . . . }
j:=j+0.5;
end; {кінець внутрішнього циклу}
end; {кінець зовнішнього циклу}
при i=1 змінна j послідовно прийме значення -5, -4.5, …, 5, потім процес повториться при i=2, 3, 4 і 5. Таким чином, за час виконання кожного кроку зовнішнього циклу for внутрішній цикл while виконається 21 раз.
Подвійний цикл особливо широко розповсюджений у програмуванні, тому що ідеально підходить для обробки табличної інформації, роботи з матрицями, завдань сортування і т.д. Розглянемо кілька типових завдань, пов'язаних з подвійними циклами.
Пр. Для функції двох змінні f(x,y) = sin 2x + cos 4y побудувати таблицю її значень при значеннях аргументів x і y, що міняються від 0 до 2 із кроком 0.25.
Розв'язок завдання можливо, як мінімум, у трьох варіантах:
| лінійна таблиця, y міняється швидше, чим x:
x1 y1 f(x1,y1)
x1 y2 f(x1,y2)
. . .
x1 ym f(x1,ym)
x2 y1 f(x2,y1)
x2 y2 f(x2,y2)
. . .
x2 ym f(x2,ym)
. . .
| лінійна таблиця, x міняється швидше, чим y:
x1 y1 f(x1,y1)
x2 y1 f(x2,y1)
. . .
xn y1 f(xn,y1)
x1 y2 f(x1,y2)
x2 y2 f(x2,y2)
. . .
xn y2 f(xn,y2)
. . .
| плоска таблиця, x і y відкладені по відповідних до осей координат:
x1 x2 ... xn
y1 f(x1,y1) f(x2,y1) ... f(xn,y1)
y2 f(x1,y2) f(x2,y2) ... f(xn,y2)
. . .
ym f(x1,ym) f(x2,ym) ... f(xn,ym)
|
Варіанти 1 і 2 відрізняються лише порядком проходження зовнішнього й внутрішнього циклів. Розглянемо можливий розв'язок для варіанта 1:
var x,y,f:real;
begin
writeln ('x':8,'y':8,'f':8); {Заголовок таблиці}
x:=0;
while x<=2 do begin
y:=0;
while y<=2 do begin
f:=sin(2*x)+cos(4*y); {Обчислення значення функції}
writeln (x:8:2,y:8:2,f:8:2); {Печатка рядка таблиці}
y:=y+0.25;
end;
x:=x+0.25;
end;
end.
Як видне із прикладу, при розв'язку завдання дотримані всі правила алгоритму табулювання з першої частини курсу: на кожному кроці подвійного циклу виконується обчислення значення функції, потім печатка рядка таблиці й перехід до наступного значення аргументу. Зверніть увагу, що внутрішній цикл повністю втримується в зовнішньому, а ініціалізація змінної внутрішнього циклу відбувається на кожному кроці зовнішнього. Спробуйте переписати цю програму для реалізації другого варіанта розрахунків.
Варіант 3 зручний "природнім" виставою таблиці значень функції двох змінні, однак, перешкодити його реалізації може обмежена ширина вікна консолі (80 символів). Нижче приводиться один з можливих варіантів такої програми:
var x,y,f:real;
begin
writeln;
write (' ':6); {залишаємо місце ліворуч для друку значень y}
x:=0;
while x<=2 do begin { для друку рядка значень x потрібен був}
write (x:6:2); {окремий цикл}
x:=x+0.25;
end;
y:=0;
while y<=2 do begin
writeln; { для чергового y переводимо рядок на екрані}
write (y:6:2); {і друкуємо його значення}
x:=0; {далі - реалізація внутрішнього}
while x<=2 do begin {циклу по x і вивід рядка таблиці}
f:=sin(2*x)+cos(4*y);
write (f:6:2);
x:=x+0.25;
end;
y:=y+0.25;
end;
end.
Як видне з лістингу, код трохи ускладнився за рахунок додаткового циклу формування рядка значень x, для того, щоб рядок таблиці містився на рядку екрана, довелося також зменшити ширину поля виведення з 8 до 6 символів. Однак, виграш безсумнівний – тепер уся таблиця помістилася на одному текстовому екрані. Обмеження на ширину екрана не мало б значення, наприклад, при виведення таблиці значень у текстовий файл замість екрана.
Не обов'язково границі зовнішнього й внутрішнього циклів чітко фіксовані. На практиці поширені завдання, коли границя внутрішнього циклу переменна й залежить від поточного значення керуючої змінної зовнішнього циклу.
Пр. Надрукувати на першому рядку виведення один символ зірочки, на другий – два, на рядку номер N – N символів. Значення N уводиться із клавіатури, 1<N<25.
У загальному виді умова можна сформулювати так: у рядку номер i друкується i зірочок, при цьому i міняється від 1 до N включно. Зрозуміло, для перебору значень i ми використовуємо цикл for. Однак, для друку чергового рядка зірочок нам буде потрібно вкладений цикл. Позначивши його лічильник як j, одержимо закон зміни j від 1 до i включно:
var i,j,n:integer;
begin
repeat {Уведення N з контролем помилок}
write ('N=');
{$I-}read (n);{$I-}
if (Ioresult<>0) or (n<2) or (n>24) then begin
writeln ('Помилка! N повинне бути числом від 2 до 24');
continue;
end;
break;
until false;
{Подвійний цикл, у якім вкладений цикл має змінну границю}
for i:=1 to n do begin
writeln;
for j:=1 to i do
write ('*');
end;
end.
Досить поширене завдання сортування, при розв'язку якої потрібно впорядкувати по зростанню або по убуванню елементи даних. Розглянемо типове завдання сортування одномірного масиву, розв'язувану за допомогою подвійного циклу зі змінною границею вкладеного циклу:
Пр. Задані N елементів масиву A, упорядкувати їх по зростанню значень.
Отже, нам потрібно одержати порядок елементів у масиві, при якім виконується співвідношення A1≤A2≤…≤AN. Досягтися цього можна, зробивши перестановки значень елементів, алгоритм перестановки нам відомий ще із глави 4. Представимо, що в циклі ми порівнюємо перший елемент A1 з усіма іншими Ai, i=2,3,…,N, при необхідності (якщо A1>Ai) переставляючи A1 і Ai. Таким чином, після виконання цього циклу на першім місці в масиві гарантовано виявиться його найменший елемент. Для пошуку наступного по величині елемента алгоритм можна повторити, порівнюючи елемент A2 з іншими й при необхідності виконуючи перестановку. Таким чином, приходимо до подвійного циклу наступного виду:
i=1,2,….,N-1 { до N-1 - тому що в елемента AN немає наступного}
j=i+1,i+2,…,N {будемо для Ai перебирати всі наступні елементи}
{у тілі подвійного циклу порівнюємо Ai і Aj,
при необхідності переставляємо їх значення}
Реалізуємо цей алгоритм у вигляді наступної програми:
const nmax=100; {максимальна розмірність масиву}
var a:array [1..nmax] of real;
i,j,n:integer;
b:real; {буферна змінна для обміну}
begin
repeat {цикл уведення значення N з перевірками}
writeln ('Уведіть N від 2 до ',nmax,':');
{$I-}read (n);{$I+}
if (Ioresult<>0) or (n<2) or (n>nmax) then
writeln ('Помилка! Повторите введення');
until (n>1) and (n<=nmax);
{Цикл уведення й друку вихідного масиву}
Randomize; {Елементи масиву виберемо випадковими}
Writeln ('Вихідний масив:');
for i:=1 to n do begin
a[i]:= Random(100);
write (a[i]:4:0);
end;
{Подвійний цикл сортування}
for i:=1 to n-1 do
for j:=i+1 to n do
if a[i]>a[j] then begin
b:=a[i]; a[i]:=a[j]; a[j]:=b;
end;
{Цикл виведення зміненого масиву}
Writeln;
Writeln ('Відсортований масив:');
for i:=1 to n do write (a[i]:4:0);
Reset (input); Readln;
end.
Сортування масиву по убуванню відрізняється лише знаком в операторі порівняння Ai і Aj.
Існують і значно могутніші алгоритми сортування, однак, їхнє застосування має сенс для дійсно більших обсягів даних.
Пр. Знайти, скільки раз кожний елемент зустрічається в масиві.
Перше, що спадає на думку при розв'язку цього розповсюдженого завдання – крім масиву даних увести "масив частот", елементи якого будуть зберігати інформацію про зустрічальність тих або інших значень. Однак, розв'язати проблему можна й без настільки марнотратних витрат оперативної пам'яті (адже розмірність масиву частот буде дорівнює розмірності вихідного масиву!). Кожний елемент масиву ai, крім останнього, ми будемо порівнювати з наступними за ним елементами aj, уважаючи скільки раз виконалася рівність ai=aj. Для того, щоб виключити повторну обробку елементів, що вже зустрічалися, враховані значення нам доведеться заміняти нулями. Оскільки значення нуль саме може зустрітися в масиві, додатковий цикл перед обробкою підрахує кількість нульових елементів.
Константа Size носить те ж призначення, що nmax у попередньому завданні, а константа Diap задає діапазон значень, які можуть ухвалювати елементи масиву. Елементи масиву слід зробити целочисленными, адже завдання порівняння дійсних чисел у загальному випадку некоректна (див. розділ 7.2).
program m_chast;
const Size=10;
Diap=10;
var a:array [1..Size] of integer;
i,n,k,j:integer;
begin
writeln;
repeat
write('Уведіть розмірність 1 масиву ( від 2 до ',Size,'):');
read (n);
until (n>1) and (n<=Size);
Randomize;
a[1]:=Random(Diap);
write ('A= ',a[1],' ');
for i:=2 to n do begin
a[i]:=Random(Diap);
write (a[i],' ');
end;
writeln;
k:=0;
for i:=1 to n do if a[i]=0 then Inc(k);
if k>0 then writeln ('0: ',k);
for i:=1 to n-1 do if a[i]<>0 then begin
k:=1;
for j:=i+1 to n do if a[i]=a[j] then begin
a[j]:=0;
Inc(k);
end;
writeln (a[i],': ',k);
end;
end.
Подібний же принцип порівняння "кожний з кожним" використовується при розв'язку великої кількості завдань.
Пр. Координати десяти крапок на площині задано двома масивами Xi, Yi, i=1,2,…,10. Знайти дві крапки, відстань між якими мінімально.
Дійсно, нам доведеться шукати відстань від першої крапки до всіх інших, від другий – тільки до крапок з номерами 2,3,…,10, тому що відстань до першої вже відомо і т.д. Спробуйте написати програму самостійно, застосувавши подвійний цикл із попереднього прикладу.
У завершення теми розглянемо завдання, де число вкладень циклів більше двох:
Пр. Номера автобусних квитків складаються з 6 цифр. "Щасливими" називають квитки, у номерах яких сума трьох перших цифр дорівнює сумі трьох останні. Визначити загальна кількість "щасливих" квитків.
Кожна із шести цифр може мінятися від 0 до 9 включно. Створивши кратні цикли по шести змінним, скористаємося відомим нам алгоритмом організації лічильника:
var i,j,k,l,m,n:integer;
kol:longint; {типу integer може бути недостатньо!}
begin
kol:=0;
for i:=0 to 9 do
for j:=0 to 9 do
for k:=0 to 9 do
for l:=0 to 9 do
for m:=0 to 9 do
for n:=0 to 9 do
if i+j+k = l+m+n then inc(kol);
writeln ('Кількість щасливих квитків=',kol);
end.
