1.2. Вложенные циклы
Любой цикл, содержащий внутри себя один или несколько других циклов, называется вложенным. Цикл, охватывающий другие циклы, называется внешним, а остальные циклы - внутренними.
Типы циклических алгоритмов внешнего и внутреннего циклов при этом могут быть любыми. Внутренний цикл, от подготовки до завершения, должен находиться внутри внешнего, точнее, быть его телом.
Правила организации, как для внешнего, так и для внутреннего циклов такие же, как и для простого одиночного цикла (см. лабораторную работу № 7). Параметры этих циклов изменяются не одновременно, то есть при одном значении параметра внешнего цикла параметр внутреннего цикла принимает по очереди все свои значения.
Согласно типовой блок-схеме организации ЦВП внутренний цикл во вложенных ЦВП выступает в роли тела цикла для внешнего цикла.
Вложенные циклические процессы наиболее часто встречаются при программировании вычислительных процессов, содержащих многомерные массивы (матрицы), при вычислении таблиц значений функций, зависящих от большого числа аргументов, и во многих других задачах.
В принципе количество подобных вложений может быть любым. При этом согласно типовой блок-схеме организации циклических вычислительных процессов каждый внутренний цикл по отношению к внешнему циклу является телом цикла для внешнего цикла.
Общий вид графической схемы цикла в цикле изображен на рис. 9.2. Здесь внешний цикл – цикл с предусловием, внутренний цикл – цикл с постусловием. Рабочая часть внешнего цикла выделена пунктирной линией. Число выполнений команд рабочей части внутреннего цикла может быть найдено как произведение числа повторений внутреннего цикла на число повторений внешнего цикла.
Рис. 9.2. Схема цикла с постусловием в цикле с предусловием
Кратность вложения циклов может равной, не только двум, но и трем, четырем и т.д.
Рассмотрим программирование вложенных циклических вычислительных процессов на конкретных примерах.
Пример 9.4
Вывести на экран таблицу умножения
В качестве тела цикла может быть использован другой цикл (вложенный).
# include<stdio.h>
#include <conio.h> // подключение библиотеки функций ввода-вывода
#include <iostream.h> // подключение библиотеки потокового ввода-вывода
int main()
{
int i,j;
for(i=1;i<=9;i++)
{ cout <<"\n";
for(j=1;j<=9;j++)
{
cout <<i <<" * " << j << " = " << i*j << endl;
}
}
cout << "Нажмите любую клавишу..." ;
getch();
return 0;
}
Пример 9.5
Протабулировать функцию двух переменных
где 0 ≤ x ≤ 1; hx =0,2; 20 ≤ y ≤40; hy =2.
Для рассматриваемого примера, таблица выбора идентификаторов будет очевидной; N
Таблица идентификаторов примера 9.5
Таблица 9.1
В исходном выражении |
x |
|
у |
f(х,у) |
В программе на С++ |
x |
|
у |
fху |
Блок-схема алгоритма, реализующего циклические вычисления, показана на рис. 9.3.
Рис. 9.3. Блок-схема алгоритма примера 9.5
Программа на C++ может иметь вид:
int main()
{
float x, y, fxy;
for(x=0.1; x<=1.1; i+=0.2);
{
for(y=20; y<=41; i+=2);
fxy = (х*x + y*y)/(x + y);
cout << x << y << fxy << endl;
}
}
Пример 9.6
Составить программу для вычисления выражения
при следующих значениях переменных: х = 8, 12, 16, 20; а = 3, 6, 9, .... 18; b = 200, 300, 400, 500; и с = 0,82.
Программа на языке С++ может иметь вид:
int main()
{
float a, b, c, x, u;
for(x=8; x<=22; x+=4);
{
for(a=3; a<=19; a+=3);
{
for(b=200; b<=550; b+=100);
u = (a + b*b)/(c*pow(fabs(sin(x)), 1.0/3.0) + pow(a,5)*exp(-3*a)*cos(x)*cos(x);
cout << x << a << b << u << endl;
} //Конец цикла по b
}//Конец цикла по a
} //Конец цикла по x
}
При программировании вложенных циклов повторения каждого цикла управляются своим заголовком цикла, для чего в каждом из циклов определяются переменные - параметры и характер их изменения.
Отметим, что за редким исключением, в задачах на вложенные циклические процессы не имеет значения по какому параметру организовывать внутренний и внешний циклы.
При программировании вложенных циклических процессов рекомендуется, как и ранее при программировании одиночных циклов, выражения, не зависящие от параметра цикла, вычислять до входа в цикл по этому параметру. Такой прием позволяет в ряде случаев значительно сократить общее время выполнения программы. Например, в предыдущем примере участок программы, реализующей циклические вычисления, с учетом высказанного замечания следует переписать в виде:
int main()
{
float a, b, c, x, u, y, z, d;
for(x=8; x<=22; x+=4);
{
y = cos(x)*cos(x);
z = c*pow(fabs(sin(x)), 1.0/3.0);
for(a=3; a<=19; a+=3);
{
d = pow(a,5)*exp(-3*a)*y;
for(b=200; b<=550; b+=100);
u = (a + b*b)/z + d;
cout << x << a << b << u << endl;
} //Конец цикла по b
}//Конец цикла по a
} //Конец цикла по x
}
Пример 9.7
Составить программу вычисления значений функции многих переменных А(t, z, w, s), которая задана следующей формулой:
Аргументы меняются в следующих пределах: I *z i. fe 4 с шагом h± » I, 12 6 2 6 18 с шагом hz » 0,25, 0,3 iW6 0,8 с шагом hw = 0,1, 0,5 £ $4 2,5 с шагом hs s 0,5. Программа,реализующая вложенный циклический процесс примера 7.9, может иметь вид:
int main()
{
float a, b, c, x, u, y, z, d;
for(x=8; x<=22; x+=4);
{
y = cos(x)*cos(x);
z = c*pow(fabs(sin(x)), 1.0/3.0);
for(a=3; a<=19; a+=3);
{
d = pow(a,5)*exp(-3*a)*y;
for(b=200; b<=550; b+=100);
u = (a + b*b)/z + d;
cout << x << a << b << u << endl;
} //Конец цикла по b
}//Конец цикла по a
} //Конец цикла по x
}
Пример 9.8
Сложный арифметический цикл
Функция двух переменных F(x, y) или функция с параметром F(А, x) порождает необходимость использования сложного арифметического цикла тогда, когда оба аргумента изменяются. Здесь решается задача полного перебора, то есть нахождения всех возможных значений функции при всех возможных значениях ее аргументов.
При решении таких задач необходимо выделить обе управляющие переменные, описать закон их изменения, и выбрать, какая из них по логике задачи главная или условно главная. Главная переменная будет параметром внешнего цикла, другая переменная будет параметром внутреннего цикла. Для каждого зафиксированного значения главной переменной другая переменная должна пробегать все значения своего диапазона. В сложном арифметическом цикле можно строить таблицу значений функции вида F(x, y) для всех возможных значений x и y. Чтобы значение параметра внешнего цикла не повторялось во многих строках таблицы, его следует выводить однократно во внешнем цикле как заголовок таблицы.
Пусть требуется вычислить объемы нескольких цилиндрических емкостей
где H – высота, а d – диаметр основания цилиндра.
Высота может изменяться в диапазоне H [1;5], ΔH = 1, а диаметр в диапазоне d [0.5; 3.5], Δd = 0.5. Переменные равноправны, поэтому внешним циклом может быть любой. Пусть это высота, тогда для одного фиксированного значения высоты нужно выводить таблицу значений функции F (d).
Текст программы примера 9.8
#include <stdio.h>
#include <conio.h>
#include <math.h>
int main()
{
float d, h; // Диаметр основания и высота емкости
float v; // Объем емкости
float PI = 3.14159; // Число
// Управление внешним циклом, параметр h.
for (h = 1.; h <= 5.; h += 1.)
{
clrscr (); // Очистка экрана перед выводом очередной таблицы.
cout << "Таблица зависимости объема от диаметра основания\n";
cout << "-----------------------------\n";
cout << " Высота = " << h << " Диаметр = " << d << " Обьем = " << V;
cout "\n";
cout "-----------------------------\n";
// Управление внутренним циклом, параметр d.
for (d = 0.5; d <= 3.5; d += 0.5)
{
v = h*PI * pow (0.5*d, 2.);
cout <<"\n" << h << d << v;
}
getch(); // Удержание экрана после вывода очередной таблицы
}
} // End of main
Очистка экрана перед выводом очередной таблицы функцией clrscr () не необходима. В этом варианте на очередном экране мы будем видеть одну таблицу для одного значения высоты. Если убрать эту строку, то таблицы будут выводиться подряд одна за другой. Удержание экрана после вывода очередной таблицы обязательно, так как программа выводит данных больше, чем вмещается на один экран.
Пример 9.9
Сложный (вложенный) цикл, управляемый событием
Требуется найти площадь треугольника, построенного по значениям длин трех заданных отрезков. Известно, что треугольник существует только тогда, когда длина каждой его стороны меньше, чем сумма длин двух других сторон. Если введенные данные не удовлетворяют этому условию, ввод повторяется.
Внутренний цикл проверяет корректность введенных данных (условие существования треугольника), а внешний цикл позволяет в диалоге управлять ее многократным повторением.
Текст программы примера 9.9
#include <stdio.h>
#include <conio.h>
#include <math.h>
int main ()
{
float a, b, c; // Длины сторон треугольника.
float S, pp; // S – площадь, pp – полупериметр.
// Цикл, управляющий процедурой многократных вычислений.
do
{
// Цикл проверки корректности введенных данных.
do
{
cout "Введите длины сторон треугольника\n";
cin >>a >> b >> c; // Тут может появиться ошибка.
}
while (!(a < b + c && b < a + c && c < a + b));
pp = (a + b + c) / 2.;
S = sqrt (pp*(pp – a)*(pp – b)*(pp – c));
cout << "Площадь треугольника равна: " << S;
// Управление внешним циклом.
cout "Если больше нет треугольников, нажмите ESC\n";
} while (getch () != 27);
} // End of main
Пример 9.10
Пример демонстрирует трехкратное вложение циклов.
Определить количество трехзначных, натуральных чисел, сумма цифр которых равна n.
Решение. Пусть l - искомое количество натуральных трехзначных чисел; i -старшая цифра числа; j - средняя цифра; k - младшая цифра. Тогда сумма цифр трехзначного числа есть i+j+k, где i=1, 2, 9; j=0, 1, 2, 9; k=0, 1, 2, 9 (старшая цифра трехзначного числа не может быть нулем). Начальное значение 1=0. Для вычисления всех возможных сумм i+j+k организуем вложенные циклы (кратность вложения равна трем) с предусловием с параметрами i, j, k (соответственно). Например, цикл по k в цикле по j, цикл по j в цикле по i (то есть цикл в цикле и еще раз в цикле). В самом внутреннем цикле значение l будем увеличивать на единицу, если выполнится условие i+j+k=n. Графическая схема изложенного алгоритма приведена на рис. 9.4. Рабочие части циклов выделены пунктирными линиями. Рабочей частью самого внутреннего цикла является ветвление с логическим блоком 9. Это ветвление выполнится 900 раз (10*10*9), что равно произведению числа повторений внутреннего, среднего и внешнего циклов. При этом для каждого из значений i=1, 2, ., 9 j принимает значения 0, 1, 2, ., 9. k принимает значения 0, 1, 2, ., 9 для каждого значения j.
Текст программы примера 9.10
#include <stdio.h>
#include <iostream.h>
int main()
{
int L,i,j,k,n;
L=0;
cout << "\пВведите целое число "; cin >> n;
for(i=1; i<=9; i++)
for(j=0; j<=9; j++)
for(k=0; k<=9; k++)
if (i+j+k==n) {L=L+1; cout<< "\n" <<i <<j <<k;}
cout <<"\nКоличество трехзначных чисел, сумма цифр которого равна "<<n<<" есть "<<L;
cout << "\n Нажмите любую клавишу \n";
fflush(stdin);
getchar();
return(0);
}
Рис. 9.4. Графическая схема алгоритма задачи 9.10