Вложенные циклы
Для решения задачи достаточно часто требуется использовать две и более циклические конструкции, одна из которых помещается в тело цикла другой. Такие конструкции называют вложенными циклами. Внутренний и внешний циклы могут быть любыми из трех рассмотренных ранее видов. Правила организации внешнего и внутреннего циклов такие же, как и соответствующих простых операторов. Однако при использовании вложенных циклов необходимо соблюдать следующее условие: внутренний цикл должен полностью укладываться в циклическую часть внешнего цикла.Пример 1. Даны натуральные числа n и m. Составить программу вычисления выражения 1ⁿ+2ⁿ+...+mⁿ
Входные данные:
1 строка: число n
2 строка: число m
Выходные данные:
единственное число: сумма s
Для вычисления указанной суммы целесообразно использовать:
1) Внешний цикл for с управляющей переменной i, изменяющейся от 1 до m. В цикле будем вычислять сумму степеней.
2) Внутренний цикл for с управляющей переменной j, изменяющейся от 1 до n, в котором будем вычислять p, равное i в степени n.
#include <iostream>
using namespace std;
int main ()
{
int n, m;
long long p, s = 0
cin >> n;
cin >> m;
for (int i = 1; i <= m; i++)
{
p = 1;
for (int j = 1; j <= n; j++)
p = p * i;
s = s + p;
}
cout << s;
return 0;
}
Экспериментальный раздел работы
1. Измените программу так, чтобы вычислялась сумма 1¹+2²+ + ...+nⁿ .Задание 1. Сложим все цифры какого-либо числа. Получим новое число, равное сумме всех цифр исходного числа. Продолжим этот процесс до тех пор, пока не получим однозначное число (цифру), называемое цифровым корнем данного числа. Например, цифровой корень числа 34697 равен 2 (3+4 + 6+9+7=29; 2+9=11; 1+1=2). Составить программу нахождения цифрового корня натурального числа.
Тесты Посмотреть решение
Задание 2. "Рисование" символами. Выведите на экран числа в следующем виде:
1
2 2
3 3 3
4 4 4 4
5 5 5 5 5
и т.д.
Посмотреть решение
Вложенные циклы. Перебор
Имеется целый класс задач, решение которых сводится к перебору различных вариантов, среди которых выбирается такой, который удовлетворяет условию задачи.Пример 2. Поиск делителей целого числа N.
Целое число K является делителем N, если остаток от деления N на K равен 0. Чтобы найти все делители достаточно перебрать все числа от 1 до N и проверить, являются ли они делителями.
#include <iostream>
using namespace std;
int main()
{
short n;
cin >> n;
for (int i = 1; i <= n; i++)
if ( n % i == 0)
cout << i << " ";
return 0;
}
На этом примере ясна общая структура решения задач на перебор вариантов. Для организации перебора используется цикл, каждый шаг выполнения которого соответствует рассмотрению одного из вариантов. Внутри цикла стоит проверка, подходит ли данный вариант под условие задачи.
Решая задачи методом перебора, всегда следует подумать, а нельзя ли каким-то образом сократить количество перебираемых вариантов. В данном случае заметим, что любое число делится само на себя и на 1. Поэтому эти варианты можно исключить из перебора. Более того, наибольшим делителем, отличным от самого числа N может быть только N/2, а все числа, большие N/2 заведомо делителями не являются. Учет этих особенностей приводит к более эффективной программе:
#include <iostream>
using namespace std;
int main()
{
short n;
cin >> n;
cout << 1 << " " << n << " ";
for (int i = 2; i <= n / 2; i++)
if ( n % i == 0)
cout << i << " ";
return 0;
}
Продолжая размышления о сокращении перебора, заметим, что если i является делителем, то частное от деления на i — тоже делитель. Таким образом, выводя делители парами, можно ограничится перебором до корня из n:
#include <iostream>
#include <math.h>
using namespace std;
int main()
{
short n;
cin >> n;
cout << 1 << " " << n << " ";
for (int i = 2; i <= sqrt (n); i++)
if ( n % i == 0)
{
cout << i << " " ;
if ( i != n / i)
cout << n / i << " ";
}
return 0;
}
Задание 3. Старинная задача. Сколько можно купить быков, коров и телят, если плата за быка 10 рублей, за корову — 5 рублей, за теленка — полтинник (0.5 рубля), если на 100 рублей надо купить 100 голов скота.
Обозначим через b — количество быков; k — количество коров; t — количество телят. После этого можно записать два уравнения: 10b+5k+0.5t=100 и b+k+t=100. Преобразуем их: 20b+10k+t=200 и b+k+t=100.
На 100 рублей можно купить:
не более 10 быков, т. е. 0 < b < 10,
не более 20 коров, т. е. 0 < k < 20,
не более 200 телят, т. е. 0 < t < 200.
#include <iostream>
using namespace std;
int main()
{
short b, k, t;
for (b = 0; b <= 10; b++)
for (k = 0; k <= 20; k++)
for (t = 0; t <= 200; t++)
if (20*b + 10*k + t == 200 && b + k + t == 100)
cout << "b = " << b << " k = " << k << " t = " << t;
return 0;
}
Экспериментальный раздел работы
1. Сколько раз будет проверяться условие? (11*21*201=46431 раз)2. Можно ли сократить количество проверок? (Если известно количество коров и быков, тогда количество телят можно найти с.о. 100-(b+k)).
#include <iostream>
using namespace std;
int main()
{
short b, k, t;
for (b = 0; b <= 10; b++)
for (k = 0; k <= 20; k++)
{
t = 100 - (b + k);
if (20*b + 10*k + t == 200)
cout << "b = " << b << " k = " << k << " t = " << t;
}
return 0;
}
3. Сколько раз будет выполняться проверка условия в этом случае? (11*21=231 раз)
Пример 5. Написать программу, которая находит все четырехзначные числа abсd (а, b, с, d — цифры числа, причем между ними нет совпадений, т. е. числа, например, типа 1221 нас не устраивают, т. е. любые две цифры числа различны), для которых выполняется условие: ab-cd = a+b+c+d. Другими словами, разность чисел, составленных из старших цифр числа и из младших, равна сумме цифр числа.
Например, рассмотрим число 5236: 52-36=5+2+3+6; 16=16.
Один из способов решения— перебор всех четырехзначных чисел и проверка выполнения условия. Попробуем сократить перебор, для этого преобразуем условие.
10*a+b-(10*c+d) = a+b+c+d
10*a+b-10*c-d = a+b+c+d;
9a-11c-2d = 0
9a-9c-2c-2d = 0
9(a-c )= 2(c+d)
(a-c)/(c+d) = 2/9, тогда a-c=2 и c+d = 9, следовательно, а = с+2, d = 9-c и 0 ≤ с ≤ 7.
#include <iostream>
using namespace std;
int main()
{
short a, b, c, d;
for (c = 0; c <= 7; c++)
{
a = 2 + c;
d = 9 - c;
for (b = 0; b <= 9; b++)
if (b != c && b != d && b != a)
cout << a * 1000 + b * 100 + c * 10 + d << "\n";
}
return 0;
}
Задания для самостоятельной работы
1. Выведите на экран числа в следующем виде:7 6 5 4 3 2
6 5 4 3 2
5 4 3 2
4 3 2
3 2
2
2. Разобрать решение задачи:
Составить программу-генератор пифагоровых троек. Пифагоровой тройкой называют такие целые числа a, b и c, которые удовлетворяют условию a2+b2=c2. Известно, что существует прямоугольный треугольник с такими длинами сторон. Найдем все пифагоровы тройки для c < 5.
Тройное вложение циклов позволит перебрать все возможные комбинации значений трех чисел a, b и c и вывести те из них, которые удовлетворяют заданному равенству.
MaxC = 25;
for (a = 1; a <= sqrt(MaxC); a++)
for (b = 1; b <= sqrt(MaxC); b++)
for (c = 1; c <= MaxC; c++)
if (a*a + b*b == c*c)
cout << a << " " << b << " " << c << "\n";
Запишите программу для этого случая. Как всегда при решении задачи методом перебора, следует задуматься, можем ли мы сократить число перебираемых вариантов. Оказывается, можно ограничиться только перебором a и b, а c вычислять по теореме Пифагора. Вычисленное таким образом c может оказаться нецелым, поэтому условие задачи для него проверять все равно необходимо.
3. Исходное данное — натуральное число S, выражающее площадь. Написать программу для нахождения всех таких прямоугольников, площадь которых равна S и стороны выражены натуральными числами.
