Вложенные циклы
Пример 1. Даны
натуральные числа n
и k.
Составить программу вычисления выражения 1k+2k+...+nk.
Ввод:1 строка - число N
2 строка - число k
Вывод:
Сумма - S
Для вычисления указанной суммы целесообразно использовать
1) Внешний цикл For с управляющей переменной i, изменяющейся от 1 до n.
2) Внутренний цикл For с управляющей переменной j, изменяющейся от 1 до k, в котором будем вычислять p=i в степени k и сумму всех элементов.
Program z1 ;
Var n, k, i, j: Integer;
p,s:int64;
Begin
ReadLn (n,k) ;
s:=0 ;
For i:=1 To n Do
Begin
p:=1;
For j:=1 To k Do
p:=p*i;
s:=s+p;
End;
WriteLn(s);
End.
Экспериментальный раздел работы
1) Выполните команду Debug/Watch. Появится окно Watches.
2) Используя клавиши Ctrl+F7 (инициируется открытие окна Add Watch), введите переменные программы (i ,P,s).
3) Выполните программу в пошаговом режиме (последовательное нажатие на F8), отслеживая изменение значений переменных в окне Watches. При выполнении ReadLn (n,k) введите, например, значения 4 и 2 для того, чтобы количество повторений цикла было небольшим.
2. Измените программу так, чтобы вычислялась
сумма 11+22+ + ...+nn .
Указание. Требуется изменить
параметры у внутреннего оператора For (For j:=1 То i Do p:=p*i;) и убрать переменную k.
Тесты Посмотреть решение
Задание 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 и проверить, являются ли они делителями. program z11; var n,i:integer; BEGIN readln(n); for i:=1 to n do if n mod i = 0 then write(i, ' '); END. На этом примере ясна общая структура решения задач на перебор вариантов. Для организации перебора используется цикл, каждый шаг выполнения которого соответствует рассмотрению одного из вариантов. Внутри цикла стоит проверка, подходит ли данный вариант под условие задачи. Решая задачи методом перебора, всегда следует подумать, а нельзя ли каким-то образом сократить количество перебираемых вариантов. В данном случае заметим, что любое число делится само на себя и на 1. Поэтому эти варианты можно исключить из перебора. Более того, наибольшим делителем, отличным от самого числа N может быть только N/2, а все числа, большие N/2 заведомо делителями не являются. Учет этих особенностей приводит к более эффективной программе: program z11; var n,i:integer; BEGIN readln(n); write(1, ' ', n,' '); for i:=2 to n div 2 do if n mod i = 0 then write(i, ' '); END. Продолжая размышления о сокращении перебора, заметим, что если i является делителем, то частное от деления на i — тоже делитель. Таким образом, выводя делители парами, можно ограничится перебором до корня из n: program z11; var n,i,m:integer; BEGIN readln(n); m:=trunc(sqrt(n)); write(1, ' ', n,' '); for i:=2 to m do if n mod i = 0 then write(i, ' ',n div i,' '); END. Задание 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. Тесты Посмотреть решение Экспериментальный раздел работы1. Сколько раз будет проверяться условие? (11*21*201=46431 раз)2. Можно ли сократить количество проверок? (Если известно количество коров и быков, тогда количество телят можно найти с.о. 100-(b+k)). Program z2; Var b, k, t: Integer; Begin For b:=0 To 10 Do For k:=0 To 20 Do begin t:=100-(b+k); If (20*b+10*k+t=200) and (b+k+t=100) Then WriteLn (' b= ' ,b,' k= ',k,' t= ' ,t); end; End. 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. program z3; Var a,b,c, d:Integer; Begin For c:=0 To 7 Do Begin a:=c+2; d:=9-c; For b:=0 To 9 Do If (b<>c) And (b<>a) And (b<>d) Then writeln(a,b,c,d) ; End; End.
1. Что будет выведено на экране монитора после выполнения следующего фрагмента программы: |
3. Выведите на экран числа в следующем виде:
7 6 5 4 3 2
6 5 4 3 2
5 4 3 2
4 3 2
3 2
2
|
4. Разобрать решение задачи:
Составить программу-генератор пифагоровых троек. Пифагоровой тройкой называют такие целые числа a, b и c, которые удовлетворяют условию a2+b2=c2. Известно, что существует прямоугольный треугольник с такими длинами сторон. Найдем все пифагоровы тройки для c < 5.
Тройное вложение циклов позволит перебрать все возможные комбинации значений трех чисел a, b и c и вывести те из них, которые удовлетворяют заданному равенству.
MaxC:=25; MaxAB:=trunc(sqrt(MaxC));
for a:=1 to MaxAB do
for b:=1 to MaxAB do
for c:=1 to MaxC do
if a*a+b*b = c*c then
begin
write(a, ' ', b, ' ', c); writeln;
end;
Как всегда при решении задачи методом перебора, следует задуматься, можем ли мы сократить число перебираемых вариантов. Оказывается, можно ограничиться только перебором a и b, а cвычислять по теореме Пифагора. Вычисленное таким образом c может оказаться нецелым, поэтому условие задачи для него проверять все равно необходимо.
MaxC:=25;
MaxAB:=trunc(sqrt(MaxC));
for a:=1 to MaxAB do
begin
for b:=1 to MaxAB do
begin
c:=round(sqrt(a*a+b*b));
if a*a+b*b = c*c then
begin
write(a, ' ', b, ' ', c); writeln;
end;
end;
end;
5. Исходное данное — натуральное число S, выражающее площадь. Написать программу для нахождения всех таких прямоугольников, площадь которых равна S и стороны выражены натуральными числами.
