Вопросы:
·
Принцип работы цикла с параметром.
·
Программирование цикла с параметром.
· Функция
генерации множества значений из указанного диапазона.
Рассмотрим
пример.
Допустим, нам необходимо вычислить произведение всех элементов некоторой
числовой последовательности А. В этом случае нужно сначала присвоить переменной
для хранения произведения p
значение один, после чего необходимо перебрать все элементы последовательности
А, умножая на них значение переменной p.
После выполнения этих действий переменная p
будет
содержать произведение всех элементов числовой последовательности. Обратим
внимание на то, что при описании этого цикла мы не использовали никаких
условий.
Для
решения такой задачи удобно использовать цикл с параметром. В общем случае его
блок-схема выглядит так.
В
верхнем блоке записывается имя параметра, например, i,
а также указывается множество значений, которые он будет принимать.
Часто в качестве множества указывается некоторый диапазон
от начального до конечного значения, например, от 1
до 10,
с некоторым шагом приращения параметра, например, с шагом, равным 3.
В описанном нами цикле параметр i
будет принимать значения: 1, 4, 7 и 10. То есть все значения из
заданного множества.
Рассмотрим,
как такой цикл записывается на языке Python. Вначале записывается служебное
слово for,
после которого следует имя параметра, а после него записывается
служебное слово in и
описывается множество значений параметра. После множества
записывается двоеточие, а со следующей строки с отступом начинают записываться
инструкции, составляющие тело цикла. Буквально на русский язык заголовок этого
цикла можно перевести как «Для параметра, принимающего множество значений».
Важно, что в теле цикла с параметром нельзя изменять значение параметра внутри
тела цикла. Если это сделать, то цикл будет работать неправильно.
Множество
значений параметра можно описать по-разному. Так, например, можно в круглых
скобках через запятую перечислить все значения. Также в качестве множеств можно
использовать списки, которые мы изучим позже, и диапазоны значений с
определённым шагом.
Решим
простую задачу с использованием цикла с параметром. Написать программу для
вывода на экран кубов четырёх целых чисел, введённых пользователем. Для решения
задачи нам нужно будет перебирать числа, введённые пользователем, возводить их
в куб и выводить полученные значения на экран.
Начнём
написание программы для решения задачи. Вначале с помощью инструкции print
выведем на экран сообщение о том, что это программа, возводящая в куб четыре
числа, и запрос на ввод этих чисел. Дальше считаем числа с клавиатуры в
переменные a, b,
c и d.
Так как в условии задачи не сказано, что числа целые, то при считывании их
значения мы будем преобразовывать в вещественный тип float.
После того, как мы считали значения чисел, с помощь инструкции print
выведем
на экран текстовое сообщение «Кубы введённых чисел», заканчивающееся
двоеточием. Для перебора четырёх чисел используем цикл для параметра i,
принимающего множество значений, которое состоит из переменных a,
b, c
и d. Внутри заданного цикла
запишем единственную инструкцию print,
которая выводит на экран значение параметра i,
возведённого в куб.
print (‘Программа,
возводящая в куб 4 числа. Введите 4 числа.’)
a,
b, c, d = float (input
()),float (input
()),float (input
()),float (input
())
print (‘Кубы
введённых чисел:’)
for i in (a, b, c, d):
print (i ** 3)
Сохраним
написанный модуль и запустим его на выполнение. Введём числа 1, 2, 3 и 4.
Программа действительно вывела на экран значения кубов введённых чисел: 1, 8, 27
и 64. Программа работает правильно. Задача решена.
Если
роль множества играет некоторый диапазон значений с заданным шагом, то его можно
сгенерировать с помощью встроенной функции range,
что в переводе на русский язык означает «диапазон». Эта функция принимает на
вход от 1 до 3 целочисленных значений. Если задать функции один целочисленный
аргумент — a, то она сгенерирует
значения в диапазоне от нуля до этого a,
не включая последнее, с шагом приращения, равным единице. Если a
≤ 0, то функция не сгенерирует ни одного значения. Если
функции задать два аргумента – a
и b, то она сгенерирует
множество значений в диапазоне от a
до b, не включая последнее, с
шагом, равным 1. Если b
≤ a, то функция
сгенерирует пустое множество. Если задать функции range
три аргумента – a, b
и c, то она сгенерирует
множество значений в диапазоне от a
до b, не включая последнее, с
шагом c. При этом, если знак
разности a и a
не совпадает со знаком c,
то функция сгенерирует пустое множество.
Рассмотрим
ещё одну задачу. Написать программу, которая вычисляет значение факториала
целого положительного числа n!.
Факториалом натурального числа n! называется
произведение всех целых чисел в диапазоне от 1 до n
включительно. Очевидно, что для решения этой задачи необходимо перебрать все
целые числа от 1 до n
и перемножить их.
Начнём
написание программы для решения задачи. Вначале выведем на экран сообщение о
том, что это программа, вычисляющая значение n!,
и запрос на ввод n. Теперь считаем
значение n с клавиатуры. По условию
задачи это целое число, поэтому при считывании будем преобразовывать его в
целочисленный тип int.
Теперь объявим переменную f
для расчёта n!.
Так как дальше в ней будет рассчитываться значение произведения, присвоим ей
единицу. Теперь запишем цикл для вычисления факториала числа. Это будет цикл
для параметра i, который будет
принимать значения в диапазоне от 1 до n,
включая концы с шагом, равным 1. Для генерации множества значений из этого
диапазона запишем функцию range
с параметрами 1 и n
+ 1,
так как функция генерирует множество значений, не включая конец заданного
диапазона. Так как шаг равен 1, то его указывать не требуется. Тело цикла будет
содержать единственную инструкцию присваивания переменной f
её собственного значения, умноженного на значение параметра i.
После цикла с помощью инструкции print
выведем на экран поясняющее сообщение о том, что факториал числа n
равен значению переменной f.
print
(‘Программа, вычисляющая значение n!. Введите
n.’)
n =
int (input
())
f =
1
for i in range (1, n + 1):
f = f * i
print (‘n! =’, f)
Сохраним
написанный модуль и запустим его на выполнение. Зададим n
= 3.
Действительно 3! = 6. Снова запустим программу и зададим n
= 5.
Действительно 5! = 120. Программа работает правильно. Задача решена.
Рассмотрим
задачу посложнее. Написать программу, вычисляющую сумму всех нечётных чисел на
промежутке от a до b,
где a >
b. Для решения задачи мы
можем перебрать все целые числа на заданном промежутке, определяя их чётность,
при этом нечётные числа мы должны учитывать при вычислении суммы.
Напишем
программу для решения задачи. Вначале с помощью инструкции print
выведем на экран сообщение о том, что это программа, вычисляющая сумму нечётных
чисел на промежутке от a
до b, и запрос на ввод a
и b. В условии задачи не
сказано, что a и b
— целые числа, поэтому при считывании будем преобразовывать их в вещественный
тип float. Теперь объявим
переменную для хранения суммы нечётных чисел – s.
Так как мы не учли ещё ни одного числа, присвоим ей значение 0. Теперь мы
должны написать цикл для перебора целых чисел на указанном промежутке.
Множество значений в заданном диапазоне мы генерируем с помощью функции range,
но она принимает на вход целочисленные аргументы, а у нас числа a
и b вещественные,
поэтому мы должны привести их к целым значениям. Для этого нужно использовать
функцию int. Но так как она
отбрасывает дробную часть числа, то при переводе числа А мы должны проверить,
равна ли его дробная часть нулю. Дробную часть числа можно выделить, вычислив
разность его самого и его целой части. Если это условие выполняется, то мы
присвоим переменной a
значение её целой части. В противном случае, мы можем сократить промежуток,
перейдя от a к следующему целому
числу, поэтому мы присвоим переменной a
значение её целой части, увеличенное на единицу. Для преобразования переменной b
нам достаточно взять её целую часть. Так и поступим. Теперь запишем цикл для
перебора целых чисел. Это будет цикл для параметра i,
изменяющегося в диапазоне от a
до b + 1,
так как последнее значение не входит в диапазон. В цикле запишем ветвление,
определяющее чётность значения i.
Если остаток от деления i
на 2 равен 1, то мы увеличим значение переменной s
на i. Таким образом, по
окончании работы цикла переменная s
будет содержать значение суммы нечётных чисел на указанном промежутке. С
помощью инструкции print
выведем на экран сообщение о том, что сумма нечётных чисел на заданном
промежутке равна значению переменной s.
print
(‘Программа, вычисляющая сумму нечётных чисел на
промежутке [a; b]. Введите a и
b.’)
a,
b = float (input
()),float (input
())
s =
0
if a — int (a) == 0:
a = int (a)
else:
a = int (a) + 1
b =
int (b)
for i in range (a, b + 1):
if a % 2 == 1:
s = s + i
print
(‘Сумма нечётных чисел на заданном промежутке:’,
s)
Сохраним
написанный модуль и запустим его на выполнение. Зададим промежуток от 1.2 до 7.
На этом промежутке нечётные числа: 3, 5 и 7. Их сумма действительно равна 15.
Программа работает правильно. Задача решена.
Однако
эту же задачу можно решить проще, перебирая в цикле не все числа, а лишь
нечётные. Для этого мы должны найти первое нечётное число на промежутке. Для
этого перед циклом проверим чётность a
с помощью ветвления. Если остаток от деления a
на 2 равен 0, то оно является чётным, а нечётным является следующее целое
число, поэтому мы увеличим a
на 1. Теперь, чтобы в цикле перебирать лишь нечётные числа, так как a
– нечётное число, достаточно перебирать значения от a
до b + 1
с шагом 2, чтобы пропускать чётные числа. Теперь в цикле нам не нужно проверять
чётность числа. Нам достаточно просто на каждом шаге увеличивать значение s
на i. Таким образом, вместо
проверки на каждом шаге цикла мы делаем всего одну проверку до начала цикла.
print
(‘Программа, вычисляющая сумму нечётных чисел на
промежутке [a; b]. Введите a и
b.’)
a,
b = float (input
()),float (input
())
s =
0
if a — int (a) == 0:
a = int (a)
else:
a = int (a) + 1
b =
int (b)
if a % 2 == 0:
a = a + 1
for i in range (a, b + 1, 2):
s = s + i
print (‘Сумма
нечётных чисел на заданном промежутке:’, s)
Проверим,
верно ли работает модуль. Сохраним и запустим его на выполнение. Зададим
промежуток от 4 до 10. На этом промежутке нечётные числа: 5, 7 и 9. Их сумма
действительно равна 21. Программа работает правильно.
Мы
узнали:
· В
цикле с параметром параметр принимает все значения из заданного
множества и для каждого значения выполняется тело цикла.
· Роль
множества значений могут выполнять значения, перечисленные в скобках, списки и
диапазон значений с заданным шагом.
· Функция
range генерирует множество
значений в заданном диапазоне с указанным шагом.Она принимает на вход от 1 до 3
целочисленных параметров.
Циклы с параметрами
Цель: дать понятие о циклах с параметром, блок-схемах, изображающих такие циклы. Учить на частных примерах составлять блок-схемы и программы с циклами; дать понятие о различиях между циклами с предусловием, постусловием и циклом с параметром; учить в одной программе использовать разные циклы, если программа содержит несколько циклов; вводить и выполнять программы, используя компиляторы BPW или Turbo Pascal.
1. Оператор цикла for … to … do …
Иногда заранее известно, сколько раз должен выполняться цикл. Для задач такого типа в языке Паскаль имеются операторы циклов с параметрами.
Формат записи таких операторов следующий:
for <пар.цикла> := <нач.знач> to <кон.знач.> do <оператор>.
Здесь for, to, do — зарезервированные слова (для, до, выполнить);
<пар. цикла> — параметр цикла — переменная типа integer (точнее, любого порядкового типа);
<нач. знач.> — начальное значение — число или выражение того же типа;
<кон. знач.> — конечное значение — число или выражение того же типа;
<оператор> — произвольный оператор Паскаля.
Если операторов несколько, тогда, как и в операторе while … do …, используются операторные скобки: begin … end.
Например, возможны такие записи оператора цикла:
for i := a to b do s1;
for j := a to b do begin s1; s2; …, sn end; или
for k := p to m do
begin
s1;
s2;
…
sn
end;
Здесь s1, s2, s3, … sn — операторы цикла.
При выполнении оператора for вначале вычисляется выражение <нач .знач.> и осуществляется присваивание его значения переменной цикла
<пар .цикла> := <нач. знач.>.
После этого циклически повторяются:
1) проверка условия <пар .цикла> <кон. знач.>; если условие не выполнено, оператор for завершает работу;
2) выполнение оператора <оператор> или операторов s1; s2; s3; … sn;
3) переменная цикла <пар. цикла> увеличивается на единицу.
Надо сразу заметить, что задать шаг цикла, отличный от 1 в этом операторе, нельзя.
Графическое изображение циклов for будет таким (см. рис. 33):
Рис. 33
Здесь: i — переменная цикла; n — ее начальное значение; k — ее конечное значение. Тело цикла составляет оператор или несколько операторов: s1; s2; … sn;, которые нарисованы в прямоугольнике.
Для иллюстрации работы оператора for рассмотрим пример уже ставший традиционным при изучении работы этого оператора.
Пример 1. Составить программу вычисления факториала числа n, т. е. n!.
Вспомним из математики, что факториал числа n равен произведению чисел от 1 до n.
Например:
Замечание. В математике принято: 0! = 1.
Блок-схема
Рис. 34
Программа
Program Problem1; { Вычисление факториала числа n! }
uses WinCrt;
var
n, f, i : longint;
begin
write(«Введите натуральное число «); readln(n);
f := 1;
if n <> 0 then for i := 1 to n do f := f*i;
writeln(«Факториал числа «, n, » равен «, f)
end.
Переменная n — для вводимого пользователем числа, факториал которого надо найти; f — переменная, в которой будет «накапливаться» значение факториала числа n; i — переменная цикла.
Устанавливается первоначальное значение переменной f := 1.
Далее начинается цикл. Переменной i присваивается начальное значение 1; оно сравнивается с конечным — n (1 <= n), если условие истинно, тогда выполняется оператор (в этой программе он один): f := f*i, 1*1=1; значение переменной цикла увеличивается на 1, т. е. станет равным: i := i + 1, 1 + 1 = 2 и цикл повторяется.
Когда значение i станет равным n, тогда цикл выполнится последний раз, потому что следующее значение i будет n + 1, что больше конечного значения n, условие i <= n — ложно, цикл не выполняется.
2. Оператор цикла for…downto…do…
Существует другая форма оператора цикла for:
for <пар .цик.> := <нач. зн.> downto <кон. зн.> do <оператор>.
Замена зарезервированного слова to на downto означает, что шаг параметра цикла равен (-1).
Изменение значения параметра идет от большего значения к меньшему, т. е.
<нач. знач.> <кон. знач.>.
Программу вычисления факториала числа можно составить, используя этот оператор цикла.
Программа
Program Problem1a;
uses WinCrt;
var
n, i, f : longint;
begin
write(«Введите натуральное число «); readln(n);
f := 1;
if n <> 0 then for i := n downto 1 do f := f*i;
writeln(«Факториал числа «, n, » равен «, f)
end.
Задание 1
1. Выполните программу примера 1 на компьютерах.
2. Измените и дополните ее так, чтобы она вычисляла следующую сумму:
Разберем другие, на мой взгляд, более интересные примеры с использованием циклов for … to … do …, а также вложенных друг в друга циклов (циклов в циклах), совмещение циклов с параметром с другими циклами.
Пример 2. Квадрат любого натурального числа n равен сумме n первых нечетных чисел:
12 = 1
22 = 1 + 3
32 = 1 + 3 + 5
42 = 1 + 3 + 5 + 7
52 = 1 + 3 + 5 + 7 + 9
. . . . . . . . . . . . . . . . . . .
Основываясь на этом свойстве, составить программу, позволяющую напечатать квадраты натуральных чисел от 1 до n.
Ясно, что цикл в программе надо организовать от 1 до n, в котором выполнять всего три оператора: находить сумму нечетных чисел (а их как раз столько, сколько раз будет выполняться цикл); выдавать полученную сумму на экран; «получать» следующее нечетное число.
Блок-схема
Рис. 35
Программа
Program Problem2;
uses WinCrt;
var
i, n, s, k: integer;
begin
writeln(«Введите натуральное число, до которого надо»);
write(«выводить квадраты чисел «); readln(n);
writeln(«Квадраты чисел следующие:»);
s := 0; k := 1;
for i := 1 to n do
begin
s := s + k;
writeln(«Квадрат числа «, i, » равен «, s);
k := k + 2
end
end.
Задание 2
1. Измените программу так, чтобы она выдавала на экран не таблицу квадратов чисел от 1 до n, а квадрат только одного числа n, введенного пользователем.
2. Измените и дополните программу так, чтобы она выдавала значение квадрата числа и те нечетные числа, сумме которых он равен.
3. Продолжая тему возведения натуральных чисел в степень, без операций умножения, рассмотрим еще два интересных примера. В первом из них нам придется совмещать, «вкладывать» друг в друга два цикла for, а во втором, циклы for и repeat.
Пример 3. Куб любого натурального числа n равен сумме n нечетных чисел, следующих по порядку за числами, сумма которых составляла куб предыдущего числа n — 1:
13 = 1
23 = 3 + 5
33 = 7 + 9 + 11
43 = 13 + 15 + 17 + 19
. . . . . . . . . . . . . . . . . . . . . .
Основываясь на этом свойстве, создайте программу, позволяющую напечатать таблицу кубов натуральных чисел.
Вот здесь уже нужны два цикла. Один — внешний, по количеству нечетных чисел, которое равно возводимому в куб числу, например, для 43 этот цикл должен выполняться 4 раза. В этом же цикле надо будет после подсчета суммы выводить ее значение на экран вместе с числом, которое возводится в куб.
Второй — внутренний, который будет суммировать нечетные числа и «вырабатывать» нужные нечетные числа для суммирования.
Блок-схема
Рис. 36
Программа
Program Problem3; { Кубы натуральных чисел от 1 до n }
uses WinCrt;
var
i, j, n, s, k : longint;
begin
writeln(«Введите натуральное число, до которого надо»);
write(«выводить кубы чисел «); readln(n);
writeln(«Кубы чисел следующие:»);
k := 1;
for i := 1 to n do
begin
s := 0;
for j := 1 to i do
begin
s := s + k;
k := k + 2
end;
writeln(«Куб числа «, i, » равен «, s)
end
end.
Разберем работу этой программы
Переменные i и j нужны в качестве переменных первого — внешнего и второго — внутреннего циклов. Переменная k для нечетных чисел, а s для суммы чисел. Тип этих переменных установлен целый, но longint, так как могут быть достаточно большие целые числа, большие 32767.
Программа начинается с запроса для пользователя с помощью операторов writeln и write о вводе натурального числа, до которого надо выдавать таблицу кубов чисел. Затем с помощью оператора readln это значение вводится в память компьютера и присваивается переменной n.
Выводится надпись «Кубы чисел следующие«. Она дана перед началом циклов по понятным причинам. В циклах ее дать нельзя, — она будет повторяться несколько раз. По окончании циклов тоже, тогда она будет написана внизу, после вывода самих чисел. Переменной k присваивается первое нечетное значение 1.
Начинается внешний цикл по количеству чисел, от 1 до n. В цикле несколько операторов, поэтому «открываются» операторные скобки: — begin …
Перед началом внутреннего цикла обнуляется переменная s — сумма. Причем такое обнуление будет происходить каждый раз, когда повторяется внешний цикл, перед началом выполнения внутреннего цикла.
Внутренний цикл выполняется от 1 до i. Почему? В цикле вычисляется сумма и увеличивается нечетное k на 2, т. е. «вырабатывается» следующее нечетное число.
Заметьте! Переменной k не присваивается перед началом каждого внутреннего цикла 1. Почему?
Следующим оператором writeln внутри внешнего цикла выдается информация на экран. Почему он размещен во внешнем цикле?
Пример 4. Из математики известно, что всякая натуральная степень числа n есть сумма n последовательных нечетных натуральных чисел. Составьте программу, которая для любой степени натурального числа n находила бы последовательность нечетных чисел, сумме которых равна эта степень.
Например, для 53 она выдавала бы последовательность чисел: 21, 23, 25, 27, 29.
План составления программы
1. Определим цель составления программы: надо показать, что действительно любую натуральную степень натурального числа можно представить в виде суммы последовательных нечетных чисел.
А если это так, тогда нам совершенно необходимо знать значение степени числа n с показателем k.
Это можно сделать с помощью простого цикла:
s := 1;
for i := 1 to k do s := s*n;
Значение степени будут накапливаться в переменной s, для этого ей устанавливается первоначальное значение 1.
В цикле, значение переменной s последовательно, k раз умножается на основание степени n. После выполнения цикла переменная s получит значение степени числа n с показателем k.
2. Вся острота вопроса состоит в том, что неизвестно первое нечетное число, от которого надо начинать суммирование последовательных нечетных чисел.
Для этого надо пробовать складывать нечетные числа вначале от 1 и далее (известно их количество — n);
1 + 3 + 5 + 7 + 9 …,
а затем проверять полученный результат, сравнивая со значением степени s. Если равенство выполняется, тогда закончить цикл и вывести на экран полученные нечетные числа, если равенство не выполняется, тогда надо начинать суммирование со следующего нечетного числа — 3: 3 + 5 + 7 + 9 … и т.д.
Этот процесс легче организовать с помощью цикла repeat. Переменной j, которая будет задавать начальные нечетные числа надо установить перед началом цикла первоначальное значение 1.
Общий вид такого цикла:
j := 1;
repeat
. . . . . .
j := j + 2
until …= s;
3. Осталось продумать, как подсчитывать суммы последовательных нечетных чисел. Мы уже сталкивались с этим вопросом и знаем, что для этого надо создать цикл от 1 до n, в котором в одну из переменных, скажем m, накапливать эту сумму, а вторая переменная должна «вырабатывать» следующее нечетное число.
Этот цикл можно записать так:
p := j; m := 0;
for i := 1 to n do
begin
m := m + p;
p := p + 2
end;
Обратите внимание! Переменная p, каждый цикл repeat, (внешний по отношению к данному), будет получать новое начальное значение нечетного числа, а переменная m — для суммы должна обнуляться перед каждым новым суммированием для другой последовательности нечетных чисел.
4. Наконец, когда последовательность нечетных чисел найдена, ее надо вывести на экран. Для этого надо устроить еще один цикл от 1 до n, в котором выдавать значения этих нечетных чисел. За первое нечетное число из последовательности надо взять значение j, но так как оно уже увеличилось на 2, то из j следует вычесть 2. Этот цикл будет:
j := j — 2;
for i := 1 to n do
begin
write(j, » «);
j := j + 2
end
Блок-схема
Рис. 37
Программа
Program Problem4;
uses WinCrt;
var
n, i, k, j, m, s, p : longint;
begin
write(«Введите натуральное число — основание степени «); readln(n);
write(«Введите натуральное число — показатель степени «); readln(k);
s := 1; j := 1;
for i := 1 to k do s := s*n;
repeat
p := j;
m := 0;
for i := 1 to n do
begin
m := m + p;
p := p + 2
end;
j := j + 2
until m=s;
write(«Степень с основанием «, n);
writeln(» и показателем «, k, » т. е. «, s);
writeln(«равна сумме следующих нечетных чисел»);
j := j — 2;
for i:=1 to n do
begin
write(j, » «);
j := j + 2
end
end.
Чтобы лучше понять ее работу, возьмите степень 25 и проверьте как будут последовательно выполняться операторы программы.
Задание 3
1. Выполните эту программу на компьютерах.
2. Составьте блок-схему и программу, которая выясняет, может ли произведение
а) трех; б) четырех последовательных натуральных чисел равняться некоторой степени некоторого натурального числа (квадрату, кубу, и т. д.)?
4. Разные задачи
Пример 5. Напечатать все четырехзначные числа, в десятичной записи которых нет двух одинаковых цифр.
Замечание. Перед началом составление блок-схемы этой задачи следует знать, как изображаются циклы в циклах, для циклов с параметрами. Общая конструкция двух вложенных циклов с параметрами будет такой:
Рис. 38
Сразу возникает мысль составить программу по следующей схеме:
организовать цикл по числу тысяч, t от 1 до 9, а затем внутренние циклы: по числу сотен, s от 0 до 9; по числу десятков, d от 0 до 9; по числу единиц, e от 0 до 9; проверка условия: если цифры различны, тогда составленное из них четырехзначное число выдавать на экран.
Блок-схема
Рис. 39
Программа
Program Problem5; { 1 — й способ }
uses WinCrt;
var
t, s, d, e : integer;
begin
writeln(«Все четырехзначные числа из разных цифр»);
for t := 1 to 9 do
for s := 0 to 9 do
for d := 0 to 9 do
for e := 0 to 9 do
if (t <> s) and (t <> d) and (t <> e) and (s <> d) and
(s <> e) and (d <> e)
then write(t*1000 + s*100 + d*10 + e, » «)
end.
Понятно, что эта программа выполнена нерационально. В ней все циклы выполняются полностью.
Программу можно усовершенствовать таким путем. Когда выполняется цикл сотен, тогда следующий цикл десятков надо начинать выполнять, если цифра сотен s не равна цифре тысяч t, в противном случае, иначе, цикл сотен надо продолжить, т. е. взять следующую цифру сотен.
Для цифры десятков, также установить условие, что следующий цикл единиц будет выполняться, если цифра десятков d не равна цифре сотен и тысяч, в противном случае, иначе, надо переходить к следующей цифре десятков.
И тогда, «внутри» цикла единиц достаточно записать условие, если цифры единиц e не равны цифре десятков d, сотен s и тысяч t, тогда четырехзначное число является искомым и оно выводится на экран.
Блок-схема
Рис. 40
Программа
Program Problem5a; { 2 — й способ }
uses WinCrt;
var
t, s, d, e : integer;
begin
writeln(«Все четырехзначные числа из разных цифр»);
for t := 1 to 9 do
for s := 0 to 9 do if s <> t then
for d := 0 to 9 do if (d <> s) and (d <> t) then
for e := 0 to 9 do
if (e <> d) and (e <> s) and (e <> t)
then write((((t*10 + s)*10 + d)*10) + e, » «)
end.
Задание 4
1. Дополните и измените эту программу так, чтобы она выдавала на экран не только различные четырехзначные числа, но и их количество.
2. При умножении четырехзначного числа, состоящего из разных цифр, на 9 получилось в произведении число, которое отличалось от множимого только тем, что между цифрами тысяч и сотен оказался нуль. Найти множимое. Составить блок-схему и программу.
Пример 6. Тройки натуральных чисел a, b, c, удовлетворяющих равенству: — называются Пифагоровыми числами.
Например, 3, 4 и 5 являются Пифагоровыми числами, поскольку
Составить программу для нахождения и печати всех Пифагоровых чисел, не превышающих 20.
Математика этого вопроса проста. Для чисел a, b и c возможные значения — это натуральные числа от 1 до 20.
Первоначальное значение a — единица, a = 1. Будем просматривать всевозможные значения b от 1 до 20, а также значения c от 1 до 20 и проверять выполнение равенства a a + b b = c c. Как только равенство будет выполняться, тогда выводить на экран значения a, b и c.
Далее надо брать значение a = 2 и проверять значения b уже от 2 до 20. Почему не от 1, а от 2? Да потому, что набор двух чисел из 1 и 2 уже был рассмотрен при значениях a = 1 и b = 2, чтобы не повторять значения a и b, т.е. избежать появления двух одинаковых пар чисел, значения b следует начинать просматривать или до значения a или от a до 20.
В связи с этим, возможны несколько способов организации циклов для переменных a и b.
1-й способ:
for a := 1 to 20 do
for b := a to 20 do
2-й способ:
for a := 20 downto 1 do
for b := 1 to a do
3-й способ:
for a := 1 to 20 do
for b := 1 to a do
Нетрудно видеть, что при каждом из этих способов не будут повторяться пары чисел. Проверьте это самостоятельно.
Для значений c мы обязаны проверять все натуральные числа от 1 до 20 для каждой пары чисел a и b. Поэтому цикл для c должен быть таким: for c := 1 to 20 do
Блок-схема
Рис. 41
Программа
Program Problem6;
uses WinCrt;
var
a, b, c : integer;
begin
writeln(«Тройки Пифагоровых чисел из промежутка [1; 20]»);
for a := 1 to 20 do
for b := 1 to a do
for c := 1 to 20 do
if a*a + b*b = c*c then writeln(a, » «, b, » «, c)
end.
Задание 5
1. Составьте блок-схему и программу, которая находит все решения уравнения где n — заданное число, из промежутка [2; 100].
2. Найти все натуральные x из промежутка [1; 1000], для которых выражение является квадратом натурального числа.
Пример 7. Сколькими способами заданное натуральное число n можно представить в виде суммы двух кубов натуральных чисел:
Перестановка слагаемых нового способа не дает. Операцией возведения в степень 1/3 пользоваться нельзя.
Сразу возникает следующая простая идея составления программы.
Организовать два цикла, один — внешний цикл с переменной i от 1 до n, а второй — внутренний цикл по j, также от 1 до n.
Сущность работы программы будет заключаться в следующем:
первое значение i равно 1, оно умножается трижды само на себя (этим заменяется возведение в 3-ю степень);
затем «перебираются» все значения j от 1 до n, каждое из которых также умножается трижды на себя и складывается со значением i i i, т. е. i в кубе;
далее, эта сумма проверяется, равна ли она значению n, если равенство выполняется, тогда счетчик, заведомо определенный в программе увеличивается на 1, а значения i и j можно вывести на экран;
цикл по i продолжается, i принимает второе значение — 2 и снова начинает выполняться внутренний цикл по j от 1 до n и так далее.
Если мы составим программу по этому плану, то она будет иметь два существенных недостатка:
1) проделывается много бесполезной работы — оба цикла организованы от 1 до n и среди них много лишних (достаточно брать значения от 1 до корня кубического из n);
2) программа будет выдавать значения, которые получаются при перестановки слагаемых, например: 2 2 2 + 3 3 3 = 35 и 3 3 3 + 2 2 2 = 35, что является недопустимым по условию задачи. Как устранить эти недостатки?
Первый недостаток устраним, если предварительно выясним, сколько значений для каждого из чисел надо рассматривать, чтобы выполнялось неравенство
Для этого можно организовать цикл с предусловием, цикл «пока«, в который включить счетчик — k, который бы подсчитывал, сколько раз такой цикл будет выполняться.
Это можно сделать так:
k := 0; i := 1;
while i*i*i + 1 <= n do
begin
k := k + 1;
i := i + 1
end;
Теперь можно значительно уменьшить число циклов для «испытуемых» чисел и организовать их от 1 до k, ибо при значениях i больше k, даже при самом маленьком значении j (j := 2) неравенство i i i + 1 <=n не выполняется.
Чтобы устранить второй недостаток, т. е., чтобы не выдавать варианты с перестановкой слагаемых можно поступить так:
внешний цикл по i первого числа устроить от k до 1, а внутренний цикл для второго числа по j делать от 1 до i. Получится такая часть программы:
p := 0;
for i := k downto 1 do
for j := 1 to i do
if i*i*i + j*j*j = n
then
begin
p := p + 1;
writeln(i, «*», i, «*», i, «+», j, «*», j, «*», j, «=», n)
end;
Внимательно разберитесь с этой частью программы и подумайте, почему в этом случае мы избегаем повторения вариантов и исключаем случаи перестановки слагаемых?
Осталось красиво закончить программу. Ведь очень часто будут встречаться случаи, когда число вообще нельзя представить в виде суммы кубов двух чисел. Надо учесть и это обстоятельство.
Для этого, после выполнения всех циклов введем условный оператор, в котором, в зависимости от значений счетчика p будут выдаться соответствующие сообщения.
Если p = 0, тогда выдать сообщение, что число нельзя представить в виде суммы кубов двух чисел, а иначе, выдать сообщение о количестве способов.
Эта часть программы может быть выполнена так:
if p = 0
then
begin
write(«Число «, n, » нельзя представить в виде «);
writeln(«суммы кубов двух чисел»)
end
else writeln(«Число способов равно «, p)
Блок-схема
Рис. 42
Программа
Program Problem7;
uses WinCrt;
var
i, j, n, k, p : longint;
begin
write(«Введите натуральное число «); readln(n);
k := 0; i := 1;
while i*i*i + 1 <= n do
begin
k := k + 1; i := i + 1
end;
p := 0;
for i := k downto 1 do
for j := 1 to i do
if i*i*i + j*j*j=n
then
begin
p := p + 1;
writeln(i, «*», i, «*», i, «+», j, «*», j, «*», j, «=», n)
end;
if p = 0
then
begin
write(«Число «, n, » нельзя представить в виде «);
writeln(«суммы кубов двух чисел»)
end
else writeln(«Число способов равно «, p)
end.
Еще одно решение этой задачи
Program Problem7b;
uses WinCrt;
label 1, 2;
var
i, j, m, k, n : longint;
begin
write(«Введите натуральное число «); readln(n);
m := 0; i := 1; j := 1;
while j*j*j + 1 < n do j := j + 1;
repeat
k := i*i*i + j*j*j;
if k = n then m := m + 1;
if k <= n then i := i + 1;
if k >= n then j := j — 1;
until i > j;
if m = 0 then goto 1;
write(«Число «,n,» можно представить в виде суммы»);
writeln(» кубов двух чисел «,m,» способами»); goto 2;
1: write(«Это число не представимо в виде»);
writeln(» суммы кубов двух чисел»);
2: end.
Задание 6
Дано натуральное n. Можно ли n представить в виде суммы трех квадратов натуральных чисел? Если можно, то указать все тройки x, y, z таких натуральных чисел, что Перестановка слагаемых нового способа не дает. Составить блок-схему и программу.
5. Преобразование типов
Пример 8. Двузначное десятичное число в сумме с числом, записанным теми же цифрами, но в обратном порядке, дает полный квадрат. Найти все такие числа.
Пусть искомое двузначное число = a 10 + b, тогда число, записанное теми же цифрами, но в обратном порядке будет = b 10 + a, например, 12 и 21, 13 и 31 и т. п.
Сумма этих чисел должна давать полный квадрат, т.е. точный квадрат целых чисел. Как это проверить?
Проверку можно было бы выполнить так: извлечь квадратный корень из полученной суммы; затем округлить результат до целого числа, а потом умножить полученный результат на себя, если снова получится сумма этих чисел, то значит она является точным или полным квадратом.
Например, 12 + 21=33, извлекаем квадратный корень из 33, он равен 5.74…; округляем, будет 6; умножаем 6 само на себя и получаем 36.
Мы не получили исходного результата, значит сумма 33 не является точным квадратом.
Еще один пример, чтобы вам была понятна идея решения. Пусть двузначное число 29, тогда число, записанное теми же цифрами, но в обратном порядке — 92, в сумме они дают 121. Извлекаем квадратный корень из 121 и получаем 11. Умножив 11 само на себя, снова получим 121. Делаем вывод, что получен точный квадрат, а значит двузначное число 29 является искомым.
Чтобы составить программу по этому принципу, придется извлекать квадратный корень из суммы, что можно сделать с помощью стандартной функции sqrt(x). Результат функции sqrt(x) является вещественным числом, его надо округлить или отбросить дробную часть, а нам неизвестно, как это сделать.
Но, даже более существенным, является то, что если квадратный корень в множестве целых чисел извлекается нацело, как для 121 (он равен 11), то на множестве вещественных чисел мы не получим строго число 11, а результат будет очень близок к 11 и после умножения на себя всё равно не получится 121, т.е. возникает необходимость преобразовать вещественное значение в целое.
Итак перед нами две задачи: 1) выяснить как округлять числа и; 2) установить, как преобразовывать вещественный тип в целый.
Для этого в Паскале есть стандартные функции round(x) и trunc(x)
Стандартные функции round и trunc предназначены для замены значений вещественного типа значениями целого типа.
Функция round(x) округляет вещественное число x до целого — ее значение есть ближайшее целое число:
round(4.2) = 4, round(4.7) = 5, round(4.5)=5,
round(-4.2) = -4, round(-4.7) = -5, round(-4.5) = -5.
Функция trunc(x) отбрасывает (без округления) дробную часть вещественного числа x:
trunc(1.2) = 1, trunc(5.8) = 5, trunc(-1.2) = -1,
trunc(-5.8) = -5, trunc(-6.7) = -6, trunc(8,9) = 8
Функции округления связаны так:
trunc(x + 0.5) = round(x), если x 0,
trunc(x — 0.5) = round(x), если x < 0.
Итак, в программе можно воспользоваться одной из этих функций. Какой? Подумайте сами и попробуйте применить в программе вначале функцию trunc, а потом замените ее на round и сравните полученные результаты.
Блок-схема
Рис. 43
Программа
Program Problem8;
uses WinCrt;
var
d, e, k : integer;
begin
writeln(«Искомые двузначные числа»);
for d := 1 to 9 do
for e := 1 to 9 do
begin
k := round(sqrt(d*10 + e + e*10 + d));
if k*k = d*10 + e + e*10 + d
then write(d*10 + e, » «)
end
end.
Задание 7
Найти целые числа из заданного промежутка [m; n], которые являются точными квадратами и остаются таковыми после приписывания к ним справа единицы (в десятичной системе записи). Составить блок-схему и программу.
Упражнения
- Составьте программу, которая находит 4 последовательных натуральных числа, произведение которых равно 1680.
- Показать, что четырехзначное число, у которого цифры тысяч и десятков одинаковы и цифры сотен и единиц тоже одинаковы, не может быть точным квадратом.
- Произведение шести последовательных натуральных чисел может быть равно произведению трех последовательных натуральных чисел. Например, 1 2 3 4 5 6 = 8 9 10 = 720. Есть ли еще такие числа?
- Доказать, что произведение четырех последовательных целых чисел в сумме с единицей дает полный квадрат.
- Найдите 11 последовательных натуральных чисел, сумма квадратов которых есть квадрат целого числа.
- Существуют ли такие целые числа, которые уменьшаются в 57 раз при зачеркивании их первой (слева) цифры?
- Найти четырехзначное число, зная, что оно является квадратом натурального числа и что цифры его распадаются на две пары, состоящие из одинаковых цифр.
- Найдите все семизначные числа, которые делятся на 15 и записываются только цифрами 0 и 1.
- Шестизначное число начинается с цифры 1. Если эту цифру переставить в конец числа, то новое число будет в три раза больше первоначального. Найдите число.
- Сколько точных квадратов можно составить из цифр 3, 4, 5, 6?
- Даны 20 различных натуральных чисел, не больших 50. Найдите два из них, разность которых равна 4, 5 или 9.
- Во сколько раз увеличится двузначное число, если справа к нему приписать такое же двузначное число?
- Определить наибольшее значение отношения трехзначного числа к числу, равному сумме цифр этого числа.
- Найти трёхзначное число, кратное 45, если разность между этим числом и числом, записанным теми же цифрами, но в обратном порядке равна 297.
- Найти четырёхзначное число , кратное 11, при условии: b + c = a и есть полный квадрат.
- Найти трёхзначное число, равное сумме цифры десятков, квадрата цифры сотен и куба цифры единиц.
- Найти два числа, произведение которых есть трёхзначное число, являющееся кубом некоторого числа, а частное является квадратом этого числа.
- Разность между числом и произведением его цифр равна сумме цифр этого числа. Найти это число.
- Найти все значения числа m, для которых сумма 1! + 2! + ,,, + m! является полным квадратом.
- Найти положительное четырёхзначное число, кратное 7 и представляющее собою сумму куба и квадрата некоторого числа.
- Некоторое число при делении на 7 дает в остатке 3; его квадрат при делении на 72 дает остаток 44; его куб при делении на 73 даёт остаток 111. Найти это число.
- При каком натуральном значении a число a2 + a + 1589 будет точным квадратом?
- Найти совершенное число вида 16p.
- Найти два числа, если сумма их квадратов равна 468, а сумма их общего наибольшего делителя и наименьшего кратного равна 42.
Автор: Тишин Владимир Иванович
|
Первое тысячелетие путь к познанию
Средние века, с начала IV и до XV вв. включительно, были периодом значительного упадка в развитии естественнонаучных знаний на европейском континенте. Причинами тому были гибель к началу этого периода вместе с разрушением государства Византии первого в Европе греко-римского центра культуры и науки. Завоеватели — северные «варвары» с одной стороны, и арабские племена с Аравийского … |
Откуда прилетают и как падают на Землю метеориты
Орбиты метеоритов. Все как-то привыкли к тому, что астероиды кружатся вокруг Солнца на огромных расстояниях. Они в 2—3 раза дальше от Солнца, чем наша Земля. Лишь немногие астероиды приближаются к Земле, но происходит это не из-за малых размеров орбит, а из-за большого их эксцентриситета. Афелии орбит таких астероидов всегда остаются за орбитой Марса. Метеориты, … |
|
Расчет массы вещества в растворе по его массовой доле
Задание: Сколько граммов сахара и воды необходимо взять для получения 200 г 5 % раствора? № п/п 1. 2. 3. … |
To have has got
В разговорной речи для выражения значения ‘иметь, обладать’ в настоящем времени употребляется оборот ‘to have/ has got’: HAVE (хэв), HAS (хэз), GOT (гот). I/ you/ we/ they/ you HAVE(got). Можно делать сокращения : |
Конструирование алгоритмов
Последовательное построение алгоритма
Существуют различные методы конструирования
(разработки, построения) алгоритмов. Мы познакомимся с одним из них — методом последовательного построения (уточнения) алгоритма. Иначе он называется методом разработки «сверху вниз», нисходящим
методом или методом пошаговой детализации.
Процесс последовательного построения алгоритма
выглядит следующим образом.
На первом шаге мы считаем, что перед нами
совершенный исполнитель, который «всё знает и всё умеет». Поэтому достаточно определить исходные данные и результаты алгоритма, а сам алгоритм представить в виде единого предписания — постановки
задачи (рис. 2.4).
Рис. 2.4.
Линейный алгоритм, являющийся результатом первого этапа детализации задачи
Если исполнитель не обучен исполнять заданное
предписание, то необходимо представить это предписание в виде совокупности более простых предписаний (команд).
Для этого:
• задачу разбивают на несколько частей, каждая из
которых проще всей задачи;
• решение каждой части задачи формулируют в
отдельной команде, которая также может выходить за рамки системы команд исполнителя;
• при наличии в алгоритме предписаний, выходящих за
пределы возможностей исполнителя, такие предписания вновь представляются в виде совокупности ещё более простых предписаний.
Процесс продолжается до тех пор, пока все
предписания не будут понятны исполнителю.
Объединяя полученные предписания в единую
совокупность выполняемых в определённой последовательности команд, получаем требуемый алгоритм решения исходной задачи.
Разработка алгоритма методом последовательного
уточнения для исполнителя Робот
Вы уже знакомы с исполнителем Робот. Он действует на
клетчатом поле, между клетками которого могут быть стены.
Система команд исполнителя
Робот:
В одном условии можно использовать несколько команд,
применяя логические операции И, ИЛИ, НЕ.
Известно, что Робот находится где-то в
горизонтальном коридоре. Ни одна из клеток коридора не закрашена.
Составим алгоритм, под управлением которого Робот
закрасит все клетки этого коридора и вернётся в исходное положение.
Представим план действий Робота следующими
укрупнёнными шагами (модулями):
Детализируем каждый из пяти модулей.
1. Чтобы закрасить все клетки коридора, находящиеся
левее Робота, прикажем Роботу шагнуть влево и выполнить цикл — ПОКА:
влево
нц пока сверху стена и снизу стена закрасить; влево
кц
Под управлением этого алгоритма Робот закрасит все
клетки коридора, находящиеся левее от него, и окажется в клетке левее коридора.
2. Командой вправо вернём Робота в коридор. Наша
задача — вернуть Робота в исходную клетку. Эта клетка — первая незакрашенная клетка, находящаяся правее Робота. Поэтому пока занимаемая Роботом клетка оказывается закрашенной, будем перемещать
его вправо.
вправо
нц пока клетка закрашена вправо
кц
Под управлением этого алгоритма Робот окажется в
исходной клетке.
3. Выполнив команду вправо, Робот пройдёт исходную
клетку и займёт клетку правее исходной. Теперь можно закрашивать клетки коридора, расположенные правее исходной.
вправо
нц пока сверху стена и снизу стена закрасить; вправо
кц
4. Так как, выполнив предыдущий алгоритм, Робот
оказался правее коридора, командой влево вернём его в коридор. Возвращение в исходную клетку обеспечивается алгоритмом:
влево
нц пока клетка закрашена влево
кц
5. По команде закрасить Робот закрашивает исходную
клетку. Полностью программа управления Роботом выглядит так:
Вспомогательные алгоритмы
При построении новых алгоритмов нередко возникают
ситуации, когда в разных местах алгоритма необходимо выполнение одной и той же последовательности шагов обработки данных. Для такой последовательности шагов создают отдельный алгоритм, называемый
вспомогательным. В качестве вспомогательных могут использоваться алгоритмы, ранее разработанные для решения других задач.
Вспомогательный алгоритм — алгоритм, целиком
используемый в составе другого алгоритма.
Пример 1. В среде КуМир составим алгоритм для исполнителя Робот, под
управлением которого он нарисует узор:
Начальное положение Робота отмечено звёздочкой. В
алгоритме использован вспомогательный алгоритм фигура.
При представлении алгоритмов с помощью блок-схем для
обозначения команды вызова вспомогательного алгоритма используется блок «предопределённый процесс» (рис. 2.5), внутри которого записывается название (имя) вспомогательного алгоритма, после
которого в скобках перечисляются параметры — входные данные и результаты.
Рис. 2.5. Блок «предопределённый
процесс»
Вспомогательный алгоритм делает структуру алгоритма
более понятной.
Пример 2. Вспомним алгоритм вычисления степени с натуральным показателем
у = аn. Соответствующая блок-схема:
Степень с целым показателем у = ах, где х
— целое число, а ≠ 0 вычисляется так:
В приведённой записи дважды фигурирует вычисление
степени с натуральным показателем. Поэтому в алгоритм вычисления степени с целым показателем можно включить вызов вспомогательного алгоритма вычисления степени с натуральным показателем.
Соответствующая блок-схема:
Алгоритм, представленный на блок-схеме, является
основным по отношению к вызываемому в нём вспомогательному алгоритму.
Параметрами используемого вспомогательного алгоритма
являются величины а, n, у. Это формальные параметры, они используются при описании алгоритма. При конкретном обращении к вспомогательному алгоритму формальные параметры заменяются фактическими
параметрами, т. е. именно теми величинами, для которых будет исполнен вспомогательный алгоритм. Типы, количество и порядок следования формальных и фактических параметров должны совпадать.
Команда вызова вспомогательного алгоритма
исполняется следующим образом (рис. 2.6):
1) формальные входные данные вспомогательного алгоритма заменяются
значениями фактических входных данных, указанных в команде вызова вспомогательного алгоритма;
2) для заданных входных данных исполняются команды вспомогательного
алгоритма;
3) полученные результаты присваиваются переменным с именами
фактических результатов;
4) осуществляется переход к следующей команде основного
алгоритма.
Рис. 2.6. Схема выполнения команды вызова
вспомогательного алгоритма
Алгоритм, в котором прямо или косвенно содержится
ссылка на него же как на вспомогательный алгоритм, называют рекурсивным.
Рассмотрим несколько примеров рекурсивных
алгоритмов.
Пример 3. Алгоритм вычисления степени с натуральным показателем п для
любого вещественного числа а можно представить в виде рекурсивного:
Число а в степени n (n-я степень числа а) есть не
что иное, как произведение аn-1 • а; в свою очередь, аn-1 = аn-2 • а и т. д.
Пример 4. Рекурсивный алгоритм положен в основу эффективного решения
головоломки «Ханойская башня».
Интерактивная игра «Ханойские башни» (195747)
поможет вам вспомнить условие и алгоритм решения головоломки (http://sc.edu.ru/).
Пример 5. Рассмотрим алгоритм построения геометрической фигуры, которая
называется снежинкой Коха. Шаг процедуры построения состоит в замене средней трети каждого из имеющихся отрезков двумя новыми такой же длины, как показано на рисунке:
С каждым шагом фигура становится всё причудливее.
Граница снежинки Коха — положение кривой после выполнения бесконечного числа шагов.
Попробуйте подсчитать, сколько рёбер в границе
снежинки Коха после четвёртого шага; после пятого шага.
Добавил:
Вуз:
Предмет:
Файл:
Учебное пособие 1803.pdf
Скачиваний:
8
Добавлен:
30.04.2022
Размер:
2.24 Mб
Скачать
Алгоритм:
1. Вводим любое число X и точность .
2. Вычислим значения N, S, U в начальный момент времени (т. е. их состояние до цикла). Номер слагаемого = 0, сумма = 0 (т.е. ее накопление начинается с нуля, т.к. добавляя слагаемые к этому начальному нулю, мы не испортим конечный результат), нулевое слагаемое =1 (из заданной в условии формулы суммы).
3. Точка входа в цикл с предшествующим условием. Проверяем условие продолжение цикла «текущее слагаемое больше заданной точности» (цикл будет выполняться, пока это условие – истина).
4. Если условие пункта 3 – истина (выход «да» на схеме), то выполняем тело цикла, состоящее из трех действий. Текущее слагаемое добавляем к текущей сумме.
5. Вычисляем следующее слагаемое U, используем вычисленный заранее рекуррентный множитель +1.
6. Изменяем номер слагаемого на единицу.
7.Все циклически повторяется, начиная с пункта 3 этого алгоритма.
8.Когда результатом вычисления условия пункта 3 станет – ложь цикл останавливается (выход «нет» на схеме). Выводим вычисленную сумму.
9.Конец алгоритма.
2.9. Цикл с параметром
Цикл с заданным числом повторений (с параметром) целесообразно использовать в тех случаях, где количество повторений тела цикла известно из условия задачи. Алгоритм решения задачи будет короче.
В общем виде схема такого алгоритма представлена на рис. 64.
ПЦ=НЗ,КЗ
ТЦ
Рис. 64. Блок-схема цикла с заданным числом повторений
Здесь:
ПЦ – переменная цикла (параметр цикла, счетчик повторения цикла); НЗ – начальное значение переменной цикла;
47
КЗ – конечное значение переменной цикла; ТЦ – тело цикла.
Алгоритм выполнения цикла:
1.При первичном входе (т.е. сверху) в блок модификации (изменения) переменной цикла, переменной цикла (ПЦ) присваивается начальное значение (НЗ).
2.В блоке модификации переменной цикла проверяется условие, текущее значение переменной цикла меньше или равно конечному значению (КЗ) переменной цикла.
3.Если условие пункта 2 истина, то выполняется тело цикла.
4.Возвращаемся в блок модификации переменной цикла (стрелочка возвращается в блок модификации слева, при этом переменная цикла модифицируется, т.е. изменяет свое значение на единицу).
5.Все циклически повторяется с пункта 2 этого алгоритма.
6.Цикл завершается, когда переменная цикла станет больше, чем конечное значение (выход справа из блока модификации).
|
Пример 16. Вычислить: |
1 . |
||
|
Сначала применим уже имеющиеся |
|||
|
знания, т.е. применим для |
|||
|
2 |
|||
|
=1 |
|
вычисления этой конечной суммы один из циклов с условие (предшествующим |
|
|
= ∑ |
или последующим). Это не является оптимальным выбором цикла для данной задачи, т.к. потребует вычислять начальное значение номера слагаемого I=1, проверять условиеI ≤ Nокончания цикла (т.е. не превысил ли этот номер конечного значения N ( )), и увеличивать номер слагаемого I=I+1, что удлинит алгоритм. Блок схема этого алгоритма представлена на рис 65.
Обозначения:
N – количество слагаемых в сумме; I – номер слагаемого;
S – текущая сумма.
Но, поскольку количество повторений цикла известно из условия задачи, целесообразнее применить цикл с параметром при составлении алгоритма решения этой задачи.
Блок-схема с использованием этого типа цикла для решения задачи 16 приведена на рис. 66.
48
|
Начало |
||||||||
|
Ввод N |
||||||||
|
I=1 |
||||||||
|
S=0 |
||||||||
|
нет |
||||||||
|
да |
||||||||
|
= + 2 |
Конец |
|||||||
|
I = I |
+ 1 |
|||||||
Рис. 65. Блок-схема алгоритма решения задания примера 16 с применением цикла с предшествующим условием
Алгоритм (применяем цикл с параметром): 1. Вводим количество слагаемых в сумме – N.
2. Описываем начальное состояние, т.е. обнуляется сумма.
3. Далее цикл с параметром. Параметром цикла (т.е. счетчиком повторений цикла в данном случае является номер слагаемого I, т.к. цикл надо повторить столько раз, сколько слагаемых мы будем добавлять в сумму). В блоке модификации переменной цикла указываем имя переменной цикла (I), ее начальное (1) и конечное (N) значение. При первичном входе в блок
|
модификации (сверху) переменной цикла I присвоится значение 1, |
и пока |
||
|
выполняется условие «текущее значение переменной |
≤ |
», |
будет |
|
выполняться тело цикла, состоящее из одного действия. |
4.Тело цикла. Вычисляем текущую сумму, т.е. добавляем к ней текущее слагаемое. И все повторяется (стрелочка вверх). При возврате в блок модификации переменная цикла модифицируется на 1, и опять проверяется условие пункта 3.
5.Цикл завершается, когда параметр цикла станет больше N (выход из блока модификации справа). Выводится вычисленный результат.
6.Конец алгоритма.
49
|
Начало |
|
|
Ввод N |
|
|
S=0 |
|
|
I=1,N |
|
|
= + 2 |
Конец |
Рис. 66. Блок-схема алгоритма решения задания примера 16
сприменением цикла с параметром
2.10.Циклы с переадресацией
Особенность этих циклов в том, что они работают с массивами переменных.
Массив – упорядоченное множество однородных величин, например коэффициенты полинома, или коэффициенты при неизвестных в системе
|
уравнений. |
11 + 12 |
= 1 |
|||||
|
Рассмотрим систему уравнений: |
= 2 |
||||||
|
Здесь A матрица |
21 + 22 |
||||||
|
= 21 |
22 |
||||||
|
коэффициентов при неизвестных |
|||||||
|
и B вектор свободных членов |
11 |
1 . |
|||||
|
12 . |
|||||||
|
переменной |
. |
= 2 |
|||||
|
A – |
, |
массива |
– количество индексов стоящих у |
||||
|
Количество измерений |
двумерный массив, т.е. чтобы указать место его элемента нужно задать два индекса, в какой строке и в каком столбце находится элемент.
В – одномерный массив. Для указания места его элемента нужно одно число – порядковый номер элемента.
Рассмотрим полином:
50
|
10 |
0 |
+ 1 |
−1 + + −1 + 0 |
||||||||
|
, |
−1 |
||||||||||
|
= |
= |
||||||||||
|
−1. |
.1 |
||||||||||
|
A и B – |
0 |
||||||||||
|
полинома). |
различные массивы, хотя элементы их одинаковы (коэффициенты |
||||||||||
|
Пример 17. Вычислить сумму: |
|||||||||||
|
Т.е. вычислить: |
= . |
||||||||||
|
+ |
=1 |
||||||||||
|
X, Y – одномерные |
+ + |
||||||||||
|
Обозначения: |
1 |
1 |
2 |
2 |
+1 |
+1 |
. |
||||
массивы;
N – количество слагаемых в сумме, и размерность массивов X и Y;
S– искомая сумма;
i – номер элемента в массиве.
Блок-схема алгоритма решения задачи приведена на рис. 67.
Начало
Ввод N
i=1,N
S=0
i=1,N
Рис. 67. Блок-схема алгоритма решения задания примера 17
51
Массивы вводятся и выводятся поэлементно, а поскольку количество элементов массива известно, то целесообразно использовать для этих целей цикл с параметром.
Алгоритм решения задачи:
1. Введем размерность массивов X и Y (т.е. количество элементов в массивах).
2. Цикл с параметром, который выполнится N раз (пока счетчик
|
повторения цикла (он же номер элемента в массиве) i, будет изменяться в |
|||
|
диапазоне от 1 до N). |
|||
|
4. |
, |
||
|
3. Тело цикла содержит одно действие ввод элементов массива X и Y с |
|||
|
номером i (т.е. |
). |
||
|
Описываем начальный момент времени – обнуляем сумму. |
5.Далее – цикл с параметром, в котором будет накапливаться сумма. Для всех значений параметра цикла i (номер слагаемого суммы), изменяющегося в диапазоне от 1 до N , будет выполняться тело цикла.
6.Тело цикла состоит из одного действия – вычисления суммы. При каждом новом проходе цикла к текущей сумме будет добавлять новое слагаемое – произведение элементов массива X и Y с номером i.
7.После окончания цикла (параметр i стал больше чем N), выводим вычисленную сумму S.
8.Конец алгоритма.
Пример 18. Вычислить количество положительных и отрицательных элементов в массиве А из N элементов.
Обозначения:
N – размерность массива;
i – номер элемента в массиве; A – одномерный массив;
KP – количество положительных элементов в массиве;
KO – количество отрицательных элементов в массиве. Блок-схема алгоритма решения задания приведена на рис. 68. Алгоритм решения задачи:
1. Введем размерность массива A (т.е. количество элементов в массиве). 2. Далее – цикл с параметром, который выполнится N раз (пока счетчик
повторения цикла (он же номер элемента в массиве) i, будет изменяться в диапазоне от 1 до N , будет выполняться тело цикла.
3. Тело цикла содержит одно действие, ввод элемента массива А с номером i (т.е. ).
4. Описываем начальный момент времени – обнуляем количество положительных и отрицательных элементов массива.
5. Далее – цикл с параметром, в котором будем обрабатывать каждый элемент массива А и выяснять положительный он или отрицательный и в зависимости от этого изменять счетчики положительных или отрицательных
52
элементов массива KP и KO. Для всех значений параметра цикла i (номер слагаемого суммы), изменяющегося в диапазоне от 1 до N , будет выполняться тело цикла.
6. Тело цикла содержит разветвляющуюся структуру. Разветвление начинается – проверяется условие «элемент массива A с номером i ( ) положительный?».
7. Если условие в пункте 6 будет истинным, то счетчик положительных элементов массива KP увеличим на единицу.
8. Если условие в пункте 6 – ложь, то проверим еще одно условие – «элемент массива A с номером i ( ) отрицательный?».
9. Если условие в пункте 8 будет истинным, то счетчик отрицательных элементов массива KO увеличим на единицу.
10. Если условие в пункте 8 – ложь. То никаких действий производить не требуется. Ветвление закончилось. Т.е. все альтернативные пути решения пришли в одну точку.
11. Алгоритм продолжается – номер элемента массива (переменная цикла) изменяется (увеличивается) на единицу – (стрелка вверх к блоку модификации переменной цикла) и, если, этот номер не превысил N, то все циклически повторяется, начиная с пункта 6 этого алгоритма.
12. Когда i станет больше N – цикл заканчивается – выход справа из блока модификации. Выводим вычисленный результат – KP, KO.
13. Конец алгоритма.
Начало
|
Ввод |
|||||||||||||||||
|
Ввод |
|||||||||||||||||
|
i=1,N |
|||||||||||||||||
|
КP=0, |
KO=0 |
||||||||||||||||
|
i=1,N |
Вывод |
||||||||||||||||
|
нет |
да |
KP, KO |
|||||||||||||||
|
= + 1 |
Конец |
||||||||||||||||
|
нет |
|||||||||||||||||
|
да |
|||||||||||||||||
Рис. 68. Блок-схема алгоритма решения задания примера 18
53
Пример 19. Найти максимальный из положительных элементов одномерного массива.
Обозначения: А – массив;
N – количество элементов в массиве; i – номер элемента в массиве;
MAX – максимальный из положительных элементов массива. Блок схема алгоритма решения этого задания приведена на рис. 69. Алгоритм решения:
1.Вводим размерность массива.
2.Цикл с параметром (на схеме блок модификации), который выполнится N раз. Тело этого цикла содержит одно действие. Организуется цикл
3.Тело цикла, описанного в пункте 2 – вводится элемент массива . Цикл завершится, когда параметр i станет больше N (выход справа из блока
модификации).
4. Описываем начальный момент времени. Начальному максимуму присваиваем первый элемент массива A. В этот момент это предположительный максимум и он может быть равен любому элементу массива A. Но, поскольку, минимальное число N, которое может ввести
|
пользователь – это 1, то элемент в массиве с таким номером будет всегда, какое |
||||||
|
введенного массива. Можно было |
= 1 |
|||||
|
бы число N не было введено пользователем. Значит наше предположение на |
||||||
|
этом этапе алгоритма о том, что |
будет справедливо для любого |
|||||
|
введенного |
= |
на этом этапе задать начальный максимум |
||||
|
равным и |
( |
). Это тоже будет справедливо для любого |
||||
|
массива. |
5.Цикл с параметром предназначенный для обработки введенного массива (на схеме блок модификации). Он выполнится N раз (столько элементов в массиве) и параметр i (счетчик этих элементов) изменяется от 1 до N. Тело этого цикла содержит разветвляющуюся структуру.
6.Тело цикла, описанного в пункте 5. Начинается разветвляющаяся структура проверкой логического выражения «элемент массива A с номером i положительный?».
7.Если логическое выражение в пункте 6 – истина, то проверим еще одно логическое выражение «элемент массива A с номером i больше чем текущий максимум?» (т.к. нам нужно искать максимальный элемент среди положительных элементов введенного массива).
8.Если условие в пункте 7 будет истинным, то изменим ткущий максимум, присвоив ему значение элемента массива A, удовлетворяющего условию пункта 7 (т.к. найден элемент в массиве больший текущего максимума).
54
9. Если логическое выражение пункта 7 в результате вычисления даст значение – ложь (т.е. элемент массива окажется не большим текущего максимума), то никаких действий производить не нужно.
10. Если логическое выражение в пункте 6 в результате вычисления даст значение – ложь (т.е. элемент массива окажется не положительным), то никаких действий производить не нужно. Разветвление закончилось. Все ветви, образовавшиеся в процессе ветвления, пришли в одну точку.
11. Цикл, описанный в пункте 5-10. заканчивается, когда параметр i станет больше чем N. Т.е. будут обработаны все N элементов массива. (>на0схеме выход справа из блока модификации). Теперь проверим условие . Это необходимо сделать т.к. не исключена возможность, что введенный массив вообще не содержит положительных элементов. И тогда предположительный максимум, заданный нами в начальный момент времени не является положительным число, и он не изменится в ходе выполнения алгоритма.
12. Если условие в пункте 11 – истина, то реальный максимум найден, и мы его выводим.
Начало
Ввод N
Вводi=1 N=
|
i=1 N |
||
|
> 0 |
= |
|
|
нет |
> 0 |
да |
Нет положительных элементов в массиве
Конец
Рис. 69. Блок-схема алгоритма решения задания примера 19
55
Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]
- #
- #
- #
- #
- #
- #
- #
- #
- #
- #
- #