Пример
2: Напечатать все целые
числа в диапазоне от 5 до 25.
?
for i := 5 to 25 do
writeln(i); |
Как видно, в данном примере
на каждом шаге печатаются разные числа.
Используем эту возможность для чего-то
более полезного.
Пример
3: Табуляция функций.
Под табуляцией функций подразумевается
составление таблицы значений функции
для некоторого диапазона значений аргумента.
Пусть требуется Nзначений функции f(x) в диапазоне
от Xmin до Xmax. Рассматривая переменную-счетчик
как номер аргумента функции, составим
выражение, позволяющее по номеру получить
значение аргумента:
x := Xmin + (Xmax — Xmin)*(i-1)/(N-1).
Убедитесь, что действительно
первое значение аргумента (при i = 1) составляет
x = Xmin, а N-е (i = N) – x = Xmax. Вычисляя на каждом
шаге значение аргумента, можем тут же
вычислить функцию и составить требуемую
таблицу.
?
for i := 1 to N do
begin
x := Xmin+(Xmax-Xmin)*(i-1)/(N-1);
y := f(x);
writeln(x, ' ', y);
end; |
Вместо f(x) в приведенной
программе следует подставить любое выражение,
составленное по правилам языка Паскаль.
.2. Прием накопления
суммы
Данный алгоритмический прием
используется, когда надо просуммировать
большое количество чисел. Для этого переменной,
в которую будет записываться сумма, в
начале присваивается нулевое значение,
затем делается цикл, где на каждом шаге
к этой переменной добавляется очередное
число.
Пример
4: Просуммировать
все целые числа от 1 до 100.
?
s := 0; {Обнуление переменной}
for i:=1 to 100 do
s:=s+i; {Прибавление очередного
элемента суммы} |
Очень важная, фундаментальная
идея, использованная в данном приеме,
состоит в том, что результат выполнения
каждого шага цикла, зависит от значения
переменной, вычисленной на предыдущем
шаге. Таким образом, вместо тривиального
повторения одного и того же, мы на каждом
шаге получаем новый результат. Так в приведенном
примере очередное число добавляется
к значению переменной s, полученному на
предыдущем шаге.
А к чему добавляется очередное
число на самом первом шаге? Чтобы было
к чему добавлять, перед циклом обязательно
должна присутствовать инициализация
(присваивание начального значения) переменной,
в которой накапливается сумма. Чаще всего
требуется присвоить ей начальное значение
0.
Программистский анекдот в тему:
Буратино подарили
три яблока. Два он съел. Сколько яблок
осталось у Буратино? Ответ «одно» неправильный.
Неизвестно, сколько осталось, так как
не сказано, сколько яблок было у него
до того, как ему подарили три новых. Мораль:
не забывайте обнулить переменные.
3.3. Прием накопления
произведения
Аналогично накоплению суммы
можно в отдельной переменной накапливать
произведение. Переменной, в которой производится
накопление, присваивается начальное
значение 1.
Пример
5. Вычисление факториала.
Факториалом целого числа n называется
произведение всех целых чисел от 1 до
n. Обозначается n!. То есть: n! = 1*2*3*…*n
?
readln(n);
p:=1;
for k:=2 to n do
p:=p*k;
writeln(p); |
3.4. Комбинация
обоих приемов
Пример
6: Вычислить значение
выражения 1!+2!+3!+…+n!
Решение «в лоб» состоит в том,
чтобы в теле цикла, осуществляющего суммирование,
производить вычисление факториала:
?
s:=0;
for i:=1 to n do
begin
{Вычисление факториала
от i}
p:=1;
for k:=1 to i do
p:=p*k;
{Добавление вычисленного
факториала к сумме}
s:=s+p;
end; |
Заметим, однако, что при вычислении
факториала на каждом шаге получается
факториал все большего целого числа.
Эти «промежуточные» результаты однократного
вычисления факториала и можно суммировать:
?
s:=0;
p:=1;
for i:=1 to n do
begin
p:=p*i;
s:=s+p;
end; |
.5. Цикл с downto
Если вместо слова to в цикле for поставить downto, то после выполнения
каждого шага цикла переменная-счетчик
будет не увеличиваться, а уменьшаться
на единицу. Так приведенный ниже код:
?
for i:=10 downto 1 do
writeln(i); |
Напечатает числа 10, 9, 8, …
Если начальное значение в цикле
с downto будет меньше
конечного, то тело цикла не выполнится
ни разу.
3.6. Операторы break и
continue
Ходом выполнения цикла можно
управлять с помощью двух операторов break и continue.
break – прерывает выполнение цикла,
управление передается операторам, следующим
за оператором цикла.
continue – прерывает выполнение очередного
шага цикла и возвращает управление в
начало цикла, начиная следующий шаг.
Например:
?
for n:=1 to 10 do
begin
if n mod 2 = 0 then
continue;
if n = 7 then
break;
writeln(n);
end; |
Данная программа будет печатать
только нечетные числа (из-за срабатывания
continue). Цикл прекратит выполняться, когда
n станет равно 7. В итоге будут напечатаны
числа: 1, 3, 5.
Контрольная работа
№3
1. Сколько раз на экран
выведется слово Hello?
for i:=-2 to 7 do
writeln('Hello'); |
2. Какого типа должна
быть переменная i в предыдущем
задании?
3. Что изменится, если убрать
операторные скобки (слова begin и end) ?
for i:=1 to 10 do
begin
writeln(i+1);
end; |
4. Что выведут на экран
приведенные программы
(а) |
s:=1;
for i:=1 to 5 do
if i>2 then
s:=s*i;
writeln(s); |
|
(б) |
s:=0;
a:=3;
for i:=1 to 10 do
s:=a+i;
writeln(s); |
|
(в) |
s:=0;
a:=5;
for i:=1 to 3 do
s:=2*a;
writeln(s); |
|
5. Составьте таблицы изменения
переменных для циклов
(а) |
s:=0;
p:=1;
for i:=1 to 5 do
begin
p:=p*i;
s:=s+p;
end; |
|
(б) |
c:=2;
for i:=1 to 4 do
c:=1/(1-c); |
|
(в) |
s:=0;
p:=1;
for i:=1 to 5 do
begin
p:=-p*2;
s:=s+p;
end; |
|
Задание 3: Цикл for, приемы накопления
суммы и произведения
1. Цикл for
1.1. Напечатайте таблицу
умножения на 5. предпочтительно
печатать 1 x 5 = 5, 2 x 5 = 10, а не просто
5, 10 и т.д.
1.2. Напечатайте в столбик
нечетные числа от 3 до 25.
1.3. Напечатайте свое имя
так, чтобы оно располагалось
в углах окна вывода.
1.4. Выведите на экран
таблицу значений синуса от 0 до
2*Pi. В каждой строке должны
стоять один аргумент и одно
значение. Количество значений аргумента
пусть задает пользователь.
2. Прием накопления суммы
2.1. Напишите программу, которая
вычисляет сумму квадратов чисел
т 1 до N. Число N программа должна
запрашивать у пользователя.
2.2. Напишите программу, перемножающую
целые числа без использования
операции «*». Например, при умножении
целых чисел n*m число m надо сложить
само с собой n раз (m+m+…+m).
2.3. Используя прием накопления
суммы, найдите сумму нечетных
чисел от 1 до N. Число N программа
должна запрашивать у пользователя.
2.4. Выведите на экран
последовательность сумм чисел
от 1 до n. n меняется от 1 до 10. То есть
первые члены последовательности:
1, 3 (1+2), 6 (1+2+3), 10 (1+2+3+4) и т.д.
2.5. Вычислите сумму элементов
последовательности сумм из предыдущего
задания.
2.6. Найдите сумму 100 синусов
от аргументов в диапазоне
от 0 до 2*Pi (из задачи 1.4).
3. Прием накопления произведения
3.1. Факториалом целого
числа n (обозначается n!) называется
произведение всех целых чисел
от 1 до n. Напишите программу вычисления
факториала введенного пользователем
числа.
3.2. Напишите программу
возведения числа в целую степень.
Число и степень запрашивайте
у пользователя.
4. Комбинация обоих приемов
4.1. Используя комбинацию
обоих приемов, напишите программу,
вычисляющую функцию
4.2. Вычислите сумму ряда:
Из мат. анализа известно, что
. Выясните, на сколько 5-й и 10-й член последовательности
таких сумм отличается от
.
4.1. Рекуррентные
соотношения: основные понятия
В основе рассмотренных ранее
алгоритмических приемов накопления суммы
и произведения лежит фундаментальная
идея о том, что результат вычислений на
каждом шаге цикла должен зависеть от
результата вычислений на предыдущем
шаге. Обобщенным математическим выражением
этой идеи являютсярекуррентные соотношения.
Будем говорить, что последовательность
векторов
задана рекуррентным соотношением, если
задан начальный вектор
и функциональная зависимость последующего
вектора от предыдущего
Вектора
можно интерпретировать как наборы значений
переменных. Таким образом, они характеризуютсостояние вычислительного
процесса. Функцию
будем понимать как преобразование значений
переменных на каждом шаге цикла.
Задача: Пусть задано рекуррентное соотношение
, начальное значение
. Найдите
.
Пример
1: Запишите рекуррентные
соотношения для нахождения суммы целых
чисел от 1 до m и факториала m!
Для суммы возьмем начальное
значение
и рекуррентное соотношение
. Требуемая сумма будет найдена на m-м шаге.
Аналогично для факториала:
,
, требуемое значение также будет найдено
на m-м шаге.
Как видно, вычислительные процессы,
соответствующие накоплению суммы и произведения
действительно могут быть заданы рекуррентными
соотношениями.
В приведенных примерах рекуррентные
соотношения явно содержали номер шага n, чего, вообще говоря,
нет в формуле (1). С практической точки
зрения это не важно – в цикле for на каждом шаге
можно использовать значение переменной-счетчика
шагов. Однако, заботясь о математической
строгости, нетрудно свести все к виду
(1), сделав номер шага элементом вектора
состояния вычислительного процесса.
Так для вычисления факториала будем иметь:
при начальных условиях
,
.
Однократное вычисление следующих
значений по предыдущим посредством рекуррентных
соотношений называется итерацией. А
процесс вычислений с помощью рекуррентных
соотношений соответственноитерированием.
4.2. Задачи на
составление рекуррентных соотношений
1) Придумайте рекуррентное
соотношение, задающее следующие
числовые последовательности:
а) 1, 2, 3, 4, …
б) 0, 5, 10, 15, …
в) 1, 1, 1, 1, …
г) 1, -1, 1, -1, …
д) 1, -2, 3, -4, 5, -6, …
е) 2, 4, 8, 16, …
ж) 2, 4, 16, 256, …
з) 0, 1, 2, 3, 0, 1, 2, 3, 0, …
и) 1!, 3!, 5!, 7!, …
2) Придумайте рекуррентные
соотношения для вычисления последовательностей
следующего вида:
а)
б)
в)
3) Придумайте рекуррентное
соотношение, укажите начальное
значение и число шагов, необходимые
для вычисления следующих величин:
а)
б)
в)
г)
д)
е)
ж)
з)
и)
к)
4) Составьте рекуррентные
соотношения для приведенных
ниже величин.
Указание: как видно, данные
формулы основаны на повторении одной
или нескольких операций. Рекуррентное
соотношение должно содержать их однократное
выполнение.
а) Золотое сечение
Если вычисления продолжать до бесконечности,
то результат сойдется к числу называемому
«Золотое сечение» (оно же золотая пропорция,
гармоническое деление и число Фидия).
Данное число было известно еще до нашей
эры (его открытие приписывают Пифагору),
а само название было дано Леонардо да
Винчи. Считается, что объекты, в которых
присутствуют пропорции, равные этому
числу, воспринимаются как красивые.
4.3. Многомерные
рекуррентные соотношения
Размерностью рекуррентного
соотношения называют размерность (количество
компонент) вектора состояния
. Соответственно говорят об одномерных
или многомерных рекуррентных соотношениях.
Программирование вычислений с помощью
одномерного рекуррентного соотношения
заключается в простом помещении его внутрь
цикла. Например, если надо найти 10-й член
последовательности
, при
:
x:=0.5;
for i:=1 to 10 do
x:=2-x*x; |
Если переменных несколько,
возникает небольшая тонкость. Для примера
рассмотрим двумерное соотношение общего
вида:
Если снова поместить эти формулы
внутрь цикла, как показано ниже:
for i:=1 to 10 do
begin
x:=f(x, y);
y:=g(x, y);
end; |
получится, что строчка
запишет в x значение
, которое будет использовано в следующей
строке вместо требуемого
. Таким образом, чтобы корректно итерировать
многомерные рекуррентные соотношения,
надо перед вычислением последующего
члена последовательности запоминать
предыдущее значение. Для двумерного рекуррентного
соотношения (2) корректная программа будет
выглядеть так: