Как составить блок схему для цикла с параметром

Циклы с параметрами

Цель: дать понятие о циклах с параметром, блок-схемах, изображающих такие циклы. Учить на частных примерах составлять блок-схемы и программы с циклами; дать понятие о различиях между циклами с предусловием, постусловием и циклом с параметром; учить в одной программе использовать разные циклы, если программа содержит несколько циклов; вводить и выполнять программы, используя компиляторы 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) переменная цикла <пар. цикла> увеличивается на единицу.

Графическое изображение циклов 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 <оператор>.

Изменение значения параметра идет от большего значения к меньшему, т. е.
<нач. знач.>  <кон. знач.>.
Программу вычисления факториала числа можно составить, используя этот оператор цикла.
Программа

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, в котором выполнять всего три оператора: находить сумму нечетных чисел (а их как раз столько, сколько раз будет выполняться цикл); выдавать полученную сумму на экран; «получать» следующее нечетное число.

Блок-схема

Рис. 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, введенного пользователем.

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 находила бы последовательность нечетных чисел, сумме которых равна эта степень.

План составления программы

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. Выполните эту программу на компьютерах.

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. Дополните и измените эту программу так, чтобы она выдавала на экран не только различные четырехзначные числа, но и их количество.

Пример 6. Тройки натуральных чисел a, b, c, удовлетворяющих равенству:  — называются Пифагоровыми числами.
Например, 3, 4 и 5 являются Пифагоровыми числами, поскольку  

Математика этого вопроса проста. Для чисел 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].

Пример 7. Сколькими способами заданное натуральное число n можно представить в виде суммы двух кубов натуральных чисел:

Сразу возникает следующая простая идея составления программы.

Организовать два цикла, один — внешний цикл с переменной 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

Предыдущий раздел:

Следующий раздел:

3.1. Цикл for

Современные компьютеры выполняют миллиарды операций в секунду. Однако к счастью, программистам не приходится писать программы из миллиардов строк кода. Чтобы с помощью короткой программы указать на необходимость выполнения большого количества операций используется оператор цикла, суть которого в многократном повторении одного и того же набора инструкций. На рис. 1 работа циклов показана с помощью блок-схем.

В варианте (а) если «условие» истинно выполняются «операторы». После этого снова проверяется «условие» и, если оно по прежнему истинно, то снова выполняются операторы и так далее, пока условие не станет ложным. Вариант (б) подобен варианту (а), отличие только в том, что сначала выполняются «операторы», а только затем делается проверка условия, на основе которой мы решаем, нужно ли повторять их выполнение.

Рис. 1. Блок-схемы циклов.

В языке Паскаль существует несколько вариантов организации циклов. Рассмотрим один из них – так называемый цикл с параметром или цикл for. Чтобы записать его нам потребуется переменная целого типа, например:

  var
    i: integer;

Схема его записи выглядит следующим образом:

  for i := <начальное значение> to <конечное значение> do
  begin
    <операторы>
  end;

Здесь i – так называемая переменная-счетчик (разумеется, ее не обязательно называть именно i, это может быть любая переменная целого типа). Начальное и конечное значение это любые выражения, имеющее значение целого типа. Когда оператор цикла начинает работу переменная счетчик принимает начальное значение, затем выполняются <операторы>, после этого счетчик увеличивается на единицу, и снова выполняются операторы. Процесс повторяется, пока счетчик не окажется больше конечного значения. Например, если начальное значение 2, а конечное 3, то <операторы> будут выполнены 2 раза. Область между словами begin и end, где располагаются повторяющие в цикле операторы, называется телом цикла.

На рис. 2 показана блок-схема работы этого цикла.

Рис. 2. Схема работы цикла с параметром (for).

Пример 1: Напечатать слово Hello на экране 100 раз.

Один раз слово Hello можно напечатать с помощью процедуры

  writeln('Hello');

Чтобы напечатать его 100 раз, надо эту инструкцию поместить внутрь оператора цикла, который выполнится нужное количество раз. А именно:

  for n := 1 to 100 do
  begin
    writeln('Hello');
  end;

Переменной счетчику n будет присвоено начальное значение 1. Затем Hello будет напечатано 1-й раз. Счетчик увеличится на 1 и Hello напечатается 2-й раз и т.д.

Перечислим в одном месте все правила, касающиеся работы цикла с параметром:

1) Переменная-счетчик должна быть обязательно целого типа (например, integer).

2) Начальное и конечное значения задаются выражениями, значение которых также имеет целый тип.

Нельзя, например, записать цикл

  for x := 0 to 2*Pi do …

Но можно, например:

  for k := 2*round(n*1000) to trunc(2*pi)+1 do …

3) Если конечное значение меньше начального цикл не выполнится ни разу.

4) После окончания работы переменная-счетчик «портится». Глядя на блок-схему можно предположить, что после окончания работы цикла она на единицу больше конечного значения. На практике это не так и она может иметь любое значение. Отсюда правило: если переменная используется, как счетчик шагов в цикле не следует обращаться к ней после того, как цикл завершил свою работу.

5) Если в теле цикла содержится всего один оператор, то слова begin и end, ограничивающие тело цикла можно опустить. Такая ситуация у нас была в примере 1. Там можно было написать:

  for n := 1 to 100 do
    writeln('Hello');

6) Важное стилистическое правило: хотя это и не запрещено, не следует в теле цикла использовать какие-либо операторы, меняющие значения переменной-счетчика. В частности нельзя ей ничего присваивать. Нарушение этого правила ведет к увеличению вероятности сделать трудно обнаруживаемую ошибку. Соблюдение – никак не ограничивает ваши возможности.

7) Тело цикла может содержать любые операторы. Следовательно, туда можно поместить другой оператор цикла. Переменные-счетчики в этом случае у циклов должны быть разные. Если их сделать одинаковыми это нарушит предыдущее правило – внутренний цикл изменит значение переменной-счетчика внешнего.

Еще одно стилистическое правило: все операторы тела цикла должны быть дополнительно сдвинуты на 2-3 пробела вправо (см. запись программы в примере 1 и последующих примеров ниже по тексту).
Итак, одни и те же действия мы можем выполнять сколько угодно раз, но что полезного это дает? Печатать 100 раз Hello не очень важное приложение. Чтобы сделать что-то полезное, надо чтобы действия на каждом шаге цикла чем-то различались. Первый способ добиться этого состоит в использовании переменной счетчика, которая на каждом шаге принимает различные значения.

Пример 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) в приведенной программе следует подставить любое выражение, составленное по правилам языка Паскаль.

Следующий раздел:

Предыдущий раздел:

Добавить комментарий

Этот вид оператора цикла также называют
циклом со счетчиком. В нем важную
роль играет переменная-параметр,
которая на каждом шаге цикла автоматически
изменяет свое значение ровно на единицу —
поэтому ее и называют счетчиком.

Инструкцию for
можно реализовать двумя способами:

Вариант 1 (с увеличением счетчика):

for
Счетчик := НачальноеЗначение to
КонечноеЗначение
do

begin

{
Инструкции }

end;

Ключевые слова for,
do
обозначают «для», «выполняй»
соответственно. Строка, содержащая
for…do,
называется заголовком цикла,
оператор, стоящий после do
образует его тело. Очень
часто тело цикла — составной оператор.
Если тело цикла представлено одиночным
оператором, то begin
и end
не пишутся.

На блок-схеме алгоритма цикл с параметром
удобно обозначать следующим образом
(рис. 9). Такое обозначение, правда, не
совсем соответствует ГОСТу.

Рис. 9 Условное обозначение на схемах
алгоритмов цикла с параметром

Инструкции между begin
и end
выполняются столько раз, сколько
определяет выражение
[(КонечноеЗначение — НачальноеЗначение)
+ 1].

Это соответствует всем значениям
счетчика от начального до конечного
включительно.

Например, выполнение цикла —
фрагмента программы:

for
i:=10 to 14 do write(i: 3);

выведет на экран последовательность
цифр в виде:

10
11 12 13 14

Вариант 2 (с уменьшением счетчика):

for
Счетчик := НачальноеЗначеиие
downto КонечноеЗначение
do

begin

{
Инструкции }

end;

Инструкции между begin
и end
выполняются столько раз, сколько
определяет выражение
[(НачальноеЗначение — КонечноеЗначение)
+ 1].

Например, выполнение цикла —
фрагмента программы:

for
i:=14 downto 10 do write(i: 3);

выведет на экран последовательность
цифр в виде:

14
13 12 11 10

Оператор
(инструкция) for
используется для организации
циклов с фиксированным, заранее
известным или определяемым во время
выполнения программы числом повторений.
Переменная-счетчик должна быть порядкового
типа: чаще — целочисленная, реже —
символьного, логического
или перечисляемого типов.

Параметр
цикла for
может изменяться (увеличиваться
или уменьшаться) каждый раз при выполнении
тела цикла только на единицу. Если
нужен другой шаг изменения параметра,
предпочтительнее циклы repeat
и while.

Например, рассмотрим фрагмент программы,
в котором предпринята попытка «обмануть»
оператор for
и получить изменение параметра
i
на 2 на каждом шаге цикла (единица
прибавляется автоматически и еще одна
единица прибавляется в теле цикла).

for
i:= 1 to 10 do

begin

write(i:4);
i := i + 1;

end;

В данном случае на экране будут выведены
числа
1 3 5 7 9.

Однако настоятельно не рекомендуем
пользоваться таким приемом. Стоит только
немного видоизменить заголовок цикла
предыдущего примера и взять в качестве
конечного значения 9, а не 10: for
i
:= 1 to
9 do,
как ваша программа не сможет нормально
выйти из цикла — «зациклится»,
так как в момент проверки условия выхода
из цикла i
никогда не будет равно 9 (сначала 8, а
потом сразу 10).

4Пример

Составить блок-схему алгоритма и
программу для вычисления и вывода на
экран таблицы значений функции

,
где аргумент Х изменяется от начального
значения (например, 1) до конечного
(например, 2) с заданным шагом (например,
0,05). Параметры А и В задаются оператором
ввода.

Здесь переменная xmin используется для
обозначения начального значения
аргумента Х, xmax — для обозначения конечного
значения аргумента Х, dx — для обозначения
шага, А и В — для обозначения параметров,
необходимых для вычислений, X и Y — для
обозначения текущего значения аргумента
и текущего значения функции. Эта задача
может быть решена тремя способами.

Вариант 1: Цикла с постусловием
(REPEAT-UNTIL) (Рис. 10)

Рис.10.
Блок-схема для цикла с постусловием .

Текст
программы

program
prim_1;

{программа
вычислений и вывода на экран таблицы
значений функции с использованием
оператора REPEAT-UNTIL}

var
a,b:real;

xmin,xmax,dx:real;

x,y:real;

begin

write(‘A=’);readln(a);

write(‘B=’);readln(b);

write(‘начальное
значение=’);readln(xmin);

write(‘конечное
значение=’);readln(xmax);

write(‘шаг=’);readln(dx);

writeln(‘|___|___|’);

writeln(‘|
X | Y |’);

writeln(‘|___|___|’);

x:=xmin;

repeat

y:=A*sin(B*x)/x;

writeln(‘|’,x:6:2,’|’,y:7:2,’|’);

x:=x+dx;

until
x > xmax+dx/2;

writeln(‘|___|___|’);

end.

Вариант 2: Цикла с предусловием (WHILE-DO)
(Рис.11)

Текст
программы

program
prim_2;

{программа
вычислений и вывода на экран таблицы
значений функции с использованием
оператора WHILE-DO}

var
a,b:real;

xmin,xmax,dx:real;

x,y:real;

begin

write(‘A=’);readln(a);

write(‘B=’);readln(b);

write(‘начальное
значение=’);readln(xmin);

write(‘конечное
значение=’);readln(xmax);

write(‘шаг=’);readln(dx);

writeln(‘|___|___|’);

writeln(‘|
X | Y |’);

writeln(‘|___|___|’);

x:=xmin;

while
x < xmax+dx/2 do

begin

y:=A*sin(B*x)/x;

writeln(‘|’,x:6:2,’|’,y:7:2,’|’);

x:=x+dx;

end;

writeln(‘|___|___|’);

end.

Рис.11
Блок-схема для цикла с предусловием.

Вариант 3: Цикла с параметром (FOR-DO)
(Рис.12)

Рис.12.
Блок-схема для цикла с параметром.

program
prim_4;

{программа
вычислений и вывода на экран таблицы
значений функции с использованием
оператора FOR-DO}

var
a,b:real;

xmin,xmax,dx:real;

x,y:real;

i,n:integer;

begin

write(‘A=’);readln(a);

write(‘B=’);readln(b);

write(‘начальное
значение=’);readln(xmin);

write(‘конечное
значение=’);readln(xmax);

write(‘шаг=’);readln(dx);

writeln(‘|___|___|’);

writeln(‘|
X | Y |’);

writeln(‘|___|___|’);

n:=trunc((xmax-xmin)/dx)+1;

x:=xmin;

for
i:=1 to
n do

begin

y:=A*sin(B*x)/x;

writeln(‘|’,x:6:2,’|’,y:7:2,’|’);

x:=x+dx;

end;

writeln(‘|___|___|’);

end.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

2.3 Циклические алгоритмы. Обработка последовательностей и одномерных массивов

Циклом называется фрагмент алгоритма или программы, который может повторяться несколько раз (в том числе и нуль раз). Каждая циклическая конструкция начинается заголовком цикла и заканчивается конечным оператором. Между ними располагаются операторы, называемые «телом цикла». Количество повторений выполнения команд (операторов), составляющих тело цикла, определяется условием окончания цикла. Условием окончания может быть достижение некоторого значения специальной переменной, называемой параметром цикла (переменной цикла), или выполнение (прекращение выполнения) некоторого условия.

Для организации циклов с параметром в языках программирования используется составной оператор FOR («для»), а в циклах с условием чаще всего используется составной оператор WHILE («пока»).

В случае цикла с параметром количество повторений («оборотов») цикла известно заранее и задаётся специальным выражением в заголовке цикла, а в случае цикла с условием при каждом следующем повторении требуется проверять условие прекращения цикла.

Если при написании операторов в теле цикла допущена ошибка, условие прекращения цикла может не выполниться никогда и цикл окажется бесконечным («программа зациклится»).

Пример блок-схемы цикла с параметром (переменной) показан на рис. 2.9, а пример блок-схемы цикла с условием окончания — на рис. 2.10. Для обозначения заголовка цикла с параметром используется специальный графический элемент — блок модификации, в котором указывается правило изменения параметра цикла.

Для работы с одномерными массивами целесообразно использовать циклы с параметром, поскольку до начала цикла может быть определено количество повторений. В этом случае цикл с параметром требуется для ввода элементов массива, а для выполнения каких-либо действий с этими элементами и вывода результатов также могут потребоваться циклы.

В блок-схеме на рис. 2.10 действия повторяются, пока выполняется некоторое условие. Когда условие перестаёт выполняться, цикл завершается.

Такие циклы целесообразно использовать в ситуации, когда данные вводятся (поступают из какого-то источника), пока не произойдёт некоторое событие. При этом всю обработку чаще всего приходится выполнять «на лету», не создавая массив, поскольку количество элементов заранее неизвестно.

Рассмотрим типичные задачи, решение которых требует вычислений в цикле.

Задача 1. Дан одномерный массив числовых значений, насчитывающий элементов. Найти среднее арифметическое элементов массива.

Постановка задачи:

Дано:

Найти:

Блок-схема алгоритма показана на рис. 2.11.

Текст программы на «псевдоязыке»:

ввод N
S=0
нц для i от 1 до N
	ввод A[i]
	S=S+A[i]
кц
C=S/N
вывод C

Здесь нц и кц обозначают, соответственно, начало и конец цикла, строка с нц является заголовком цикла. Как видно из текста, указываются начальное и конечное значение переменной цикла, которая обязательно должна быть целым числом. В приведённой здесь записи переменная цикла увеличивается на 1 при каждом повторении («шаг переменной цикла» равен 1). Если требуется шаг, не равный 1, это указывается специально.

Тело цикла состоит из двух операторов — ввода очередного числа и прибавления этого числа к текущему значению суммы.

На Python можно написать практически то же самое (с учётом особенностей, связанных с использованием функции range()).

# -*- coding: utf-8 -*-

#

N=input(‘Количество элементов: ‘)

S=0

for i in range(N-1) :

    a=input(‘Введите число: ‘)

    S=S+a

C=S/N

print‘Результат:’,C

Поскольку диапазон чисел, формируемых функцией range(), начинается с 0, то верхней границей должно быть . Так как массив хранить нет необходимости, можно просто вводить числа и добавлять их к текущему значению суммы.

Тело цикла начинается после символа «:», и все операторы тела цикла в Python должны иметь одинаковый отступ от начала строки. Как только отступ исчезает, Python считает, что тело цикла закончилось.

А вот вариант решения этой же задачи на Python с использованием списка и методов списка.

# -*- coding: utf-8 -*-

#

N=input(‘Количество элементов: ‘)

S=0

lst=[]

for i in range(N-1) :

    a=input(‘Введите число: ‘)

    lst.append(a)

C=sum(lst)/N

print‘Результат:’,C

В этом варианте формируется список, а сумма элементов списка вычисляется с помощью встроенной функции. Программа увеличилась на одну строку (создание пустого списка), но зато мы научились формировать список в цикле.

Задача 2. Определить, является ли введённая строка палиндромом («перевёртышем») типа ABBA, kazak и пр.

Постановка задачи: Требуется сравнивать попарно символы с начала и с конца строки (первый и последний, второй и предпоследний и т.д.). Если в каждой такой паре символы одинаковы, строка является палиндромом. Соответственно, каждая проверка пары символов должна получить некоторый признак (flag — «флаг»), который будет равен 1, если символы в паре совпадают и 0, если не совпадают. Окончательный результат обработки строки получится как произведение всех значений «флагов». Если хотя бы один раз «флаг» оказался равен нулю, строка палиндромом не является и произведение всех «флагов» окажется равным 0. Количество пар не превышает половины длины строки (точно равно половине длины для строк с чётным количеством символов и результат целочисленного деления длины строки на 2 для строк с нечётным количеством символов, поскольку «центральный» символ строки с нечётным количеством символов очевидно совпадает сам с собой).

Блок-схема алгоритма показана на рис. 2.12.

Текст программы на «псевдоязыке»:

ввод S
flag=1
L=длина(S)
N=L div 2
нц для i от 1 до N
	если S[i]=S[L-i +1] то
		k=1
	иначе
		k=0
	конец если
	flag=flag *k
кц
если flag=1 то
	вывод 'Палиндром'
иначе
	вывод 'Не палиндром!'
конец если

При проверке каждой пары устанавливается коэффициент , который затем умножается на текущее значение «флага». Окончательный вывод делается по итоговому значению «флага».

Текст программы на Python может быть очень похож на текст на псевдоязыке.

# -*- coding: utf-8 -*-

#

s1=raw_input(‘Исходная строка: ‘)

# Определяем длину строки

L=len(s1)

flag=1

for i in range(L//2):

    if s1[i]==s 1[-i-1]:

        k=1

    else:

        k=0

    flag=flag*k

if flag==1:

    print ‘Палиндром’

else:

    print ‘Не палиндром!’

Для ввода строки использован оператор raw_input(), при этом не требуется записывать строку в кавычках.

Небольшие синтаксические особенности всё-таки есть — условие равенства двух переменных записывается знаком «==», начало каждого составного оператора обозначается символом «:», и, как всегда, необходимо следить за отступами. Кроме того, чтобы отсчитывать символы с конца строки, использованы «отрицательные» индексы элементов строки.

Однако использование особенностей строк в Python, их функций и методов, позволяет решить эту задачу более изящно. Например, так.

# -*- coding: utf-8 -*-

#

s1=raw_input(‘Исходная строка: ‘)

lst=list(s1)

lst.reverse()

s 2=’ ‘.join(lst)

if s1==s2:

    print‘Палиндром’

else:

    print‘Не палиндром!’

Здесь исходная строка преобразуется в список, затем список «переворачивается» и из него с помощью пустой «строки-объединителя» формируется новая строка. Затем строки сравниваются. Цикл оказывается не нужен! Всю работу делает Python.

Если количество повторений операций заранее неизвестно, но известно условие прекращения выполнения операций, используется цикл (составной оператор) WHILE. Покажем его использование на следующем примере.

Задача 3. Последовательно вводятся ненулевые числа. Определить сумму положительных и сумму отрицательных чисел. Закончить ввод чисел при вводе 0.

Задача настолько проста, что дополнительных уточнений в качестве постановки задачи не требуется. Пусть сумма положительных чисел называется SP, а сумма отрицательных чисел — SN.

Блок-схема алгоритма показана на рис. 2.13.

Текст программы на «псевдоязыке»:

SP=0
SN=0
ввод chislo
нц пока chislo <> 0
	если chislo > 0 то
		SP=SP+chislo
	иначе
		SN=SN+chislo
	конец если
ввод chislo
кц
вывод SP
вывод SN

Условие «неравенства» в языках программирования Pascal и BASIC обозначается как «<>«, поэтому здесь сохранено это обозначение.

Следует обратить внимание, что проверяемое число нужно определить до начала цикла, поскольку возможна ситуация, что неопределённое значение окажется равным 0 и программа закончится, не успев начаться. А потом числа вводятся в цикле и каждое вновь поступившее число сравнивается с 0 (после ввода каждого числа следует проверка условия). Порядок операций и проверок в цикле WHILE может оказаться важным для получения верного результата.

Текст программы на Python не имеет каких-то существенных особенностей. Для удобства чтения программа поделена на «блоки» с помощью символа комментария.

# -*- coding: utf-8 -*-

#

SP=0

SN=0

#

chislo=input(‘Следующее число: ‘)

#

while chislo!=0:

    if chislo > 0 :

        SP=SP+chislo

    else:

        SN=SN+chislo

    chislo=input(‘Следующее число: ‘)

#

print‘Сумма положительных:’,SP

print‘Сумма отрицательных:’,SN

2.3.1 Сортировка массива

Задача сортировки, а также задача поиска максимального или минимального элемента в массиве встречается довольно часто. Средствами Python такие задачи решаются очень просто, но тем не менее рассмотрим общую задачу сортировки массива.

Под сортировкой понимается процедура, в результате выполнения которой изменяется исходный порядок следования данных. Причём новый порядок их следования отвечает требованию возрастания или убывания значений элементов одномерного массива. Например, при сортировке по возрастанию из одномерного массива[3 1 0 5 2 7] получается массив[0 1 2 3 5 7]. Возможны и более сложные критерии сортировки. Символьные данные обычно сортируются в алфавитном порядке.

Один из наиболее наглядных методов сортировки — «метод пузырька».

Пусть необходимо упорядочить элементы массива из элементов по возрастанию.

Просматривая элементы массива «слева направо» (от первого элемента к последнему), меняем местами значения каждой пары соседних элементов в случае неравенства , передвигая тем самым наибольшее значение на последнее место. Следующие просмотры начинаем опять с первого элемента массива, последовательно уменьшая на единицу количество просматриваемых элементов. Процесс заканчивается после просмотра.

Метод получил такое название, потому что каждое наибольшее значение как бы всплывает вверх.

Фрагмент блок-схемы алгоритма показан на рис. 2.14.

Действие означает перестановку значений элементов массива.

Текст соответствующего фрагмента программы на «псевдоязыке»:

ввод N, A
нц для m от N-1 до 1 шаг -1
	нц для i от 1 до m
		если A[i] > A[i +1] то
		X=A[i]
		A[i]=A[i +1]
		A[i +1]=X
		конец если
	кц
кц
вывод A

В этом фрагменте для перестановки значений элементов массива используется промежуточная переменная.

Задача поиска максимального элемента в массиве решается следующим образом. Пусть maxA — требуемое значение максимального элемента. Сначала присваиваем переменной maxA значение первого элемента массива, потом сравниваем первый элемент со следующим. Если следующий элемент (второй) больше первого, присваиваем его значение переменной maxA, а если нет — переходим к следующему (третьему элементу) и т. д.

Аналогично решается задача поиска минимального элемента в массиве.

В Python эти алгоритмы уже реализованы в функциях max(), min() и в методе
sort() (метод sort() сортирует список по возрастанию значений элементов).

2.3.2 Задачи для самостоятельного решения

1. Составьте блок-схему поиска максимального элемента в одномерном массиве.
2. Нарисуйте полную блок-схему алгоритма сортировки массива «методом пузырька».
3. Дан одномерный массив числовых значений, насчитывающий элементов. Поменять местами элементы, стоящие на чётных и нечётных местах:
4. Дан одномерный массив числовых значений, насчитывающий элементов. Выполнить перемещение элементов массива по кругу вправо, т. е. .
5. Дан одномерный массив числовых значений, насчитывающий элементов. Поменять местами первую и вторую половины массива.
6. Дан одномерный массив числовых значений, насчитывающий элементов. Поменять местами группу из элементов, начинающихся с позиции с группой из элементов, начинающихся с позиции .
7. Дан одномерный массив числовых значений, насчитывающий элементов. Вставить группу из новых элементов, начиная с позиции .
8. Дан одномерный массив числовых значений, насчитывающий элементов. Сумму элементов массива и количество положительных элементов поставить на первое и второе место.
9. Дан одномерный массив числовых значений, насчитывающий элементов. Исключить из него элементов, начиная с позиции .
10. Дан одномерный массив числовых значений, насчитывающий элементов. Исключить все нулевые элементы.
11. Дан одномерный массив числовых значений, насчитывающий элементов. После каждого отрицательного элемента вставить новый элемент, равный квадрату этого отрицательного элемента.
12. Дан одномерный массив числовых значений, насчитывающий элементов. Определить, образуют ли элементы массива, расположенные перед первым отрицательным элементом, возрастающую последовательность.
13. Дан одномерный массив числовых значений, насчитывающий элементов. Определить, образуют ли элементы массива, расположенные перед первым отрицательным элементом, убывающую последовательность.
14. Дан одномерный массив числовых значений, насчитывающий элементов. Из элементов исходного массива построить два новых. В первый должны входить только элементы с положительными значениями, а во второй — только элементы с отрицательными значениями.
15. Дан одномерный массив числовых значений, насчитывающий элементов. Добавить столько элементов, чтобы элементов с положительными и отрицательными значениями стало бы поровну.
16. Дан одномерный массив числовых значений, насчитывающий элементов. Добавить к элементам массива такой новый элемент, чтобы сумма элементов с положительными значениями стала бы равна модулю суммы элементов с отрицательными значениями.
17. Дан одномерный массив числовых значений, насчитывающий элементов. Дано положительное число . Разделить это число между положительными элементами массива пропорционально значениям этих элементов и добавить полученные доли к соответствующим элементам.
18. Дан одномерный массив числовых значений, насчитывающий элементов. Исключить из массива элементы, принадлежащие промежутку .
19. Дан одномерный массив числовых значений, насчитывающий элементов. Вместо каждого элемента с нулевым значением поставить сумму двух предыдущих элементов массива.
20. Дан одномерный массив числовых значений, насчитывающий элементов. Определить, имеются ли в массиве два подряд идущих нуля.
21. Дан одномерный массив числовых значений, насчитывающий элементов. Подсчитать количество чисел, делящихся на 3 нацело, и среднее арифметическое чисел с чётными значениями. Поставить полученные величины на первое и последнее места в массиве (увеличив массив на 2 элемента).
22. Заданы строк символов, которые вводятся с клавиатуры. Найти количество символов в самой длинной строке. Выровнять строки по самой длинной строке, поставив перед каждой строкой соответствующее количество звёздочек.
23. Заданы строк символов, которые вводятся с клавиатуры. Из заданных строк, каждая из которых представляет одно слово, составить одну длинную строку, разделяя слова пробелами.
24. Заданы строк слов, которые вводятся с клавиатуры. Подсчитать количество гласных букв в каждой из заданных строк.
25. Заданы строк слов, которые вводятся с клавиатуры (в каждой строке – одно слово). Вводится слог (последовательность букв). Подсчитать количество таких слогов в каждой строке.
26. Заданы строк слов, которые вводятся с клавиатуры (в каждой строке – одно слово). Вводится слог (последовательность букв). Удалить данный слог из каждой строки.
27. Заданы строк символов, которые вводятся с клавиатуры. Напечатать все центральные буквы строк нечетной длины.
28. Заданы строк символов, которые вводятся с клавиатуры. Каждая строка содержит слово. Записать каждое слово в разрядку (вставить по пробелу между буквами).
29. Задана строка символов, в которой встречается символ «.«. Поставить после каждого такого символа системное время ПК.
30. Заданы строк, которые вводятся с клавиатуры. Подсчитать количество пробелов в каждой из строк.
31. Заданы строк символов, которые вводятся с клавиатуры. Каждая строка представляет собой последовательность символов, включающих в себя вопросительные знаки. Заменить в каждой строке все имеющиеся вопросительные знаки звёздочками.
32. Последовательно вводятся числа. Определить сумму чисел с нечётными номерами и произведение чисел с чётными номерами (по порядку ввода). Подсчитать количество слагаемых и количество сомножителей. При вводе числа 55555 закончить работу.
33. Определить сумму вводимых положительных чисел. Причём числа с нечётными номерами (по порядку ввода) суммировать с обратным знаком, а числа с чётными номерами перед суммированием возводить в квадрат. Подсчитать количество слагаемых. При вводе первого отрицательного числа закончить работу.
34. Даны число и число . Определить сумму чисел меньше , произведение чисел больше и количество чисел в диапазоне значений и . При вводе числа равного или , закончить работу.
35. Суммировать вводимые числа, среди которых нет нулевых. При вводе нуля обеспечить вывод текущего значения суммы. При вводе числа 99999 закончить работу.
36. Вводятся положительные числа. Определить сумму чисел, делящихся на положительное число нацело. При вводе отрицательного числа закончить работу.
37. Для вводимых чисел определить процент положительных и отрицательных чисел. При вводе числа -65432 закончить работу.

Алгоритмизация и программирование

Алгоритмы, виды алгоритмов, описание алгоритмов. Формальное исполнение алгоритмов

Термин «алгоритм», впервые употребленный в современном значении. Лейбницем (1646–1716), является латинизированной формой имени великого персидского математика Мухаммеда бен Муссы аль-Хорезми (ок. 783 – ок. 850). Его книга «Об индийском счете» в XII в. была переведена на латинский язык и пользовалась широкой популярностью не одно столетие. Имя автора европейцы произносили как Алгоритми (Algorithmi), и со временем так стали называть в Европе всю систему десятичной арифметики.

Научное определение алгоритма дал А. Чёрч в 1930 году. В наше время понятие алгоритма является одним из основополагающих понятий вычислительной математики и информатики.

Алгоритм — это точное и полное описание последовательности действий над заданными объектами, позволяющее получить конечный результат.

Можно сказать, что алгоритм решения какой-либо задачи — это последовательность шагов реализации (или нахождения) этого решения, а процесс построения алгоритма (алгоритмизация) — разложение задачи на элементарные действия или операции.

Область математики, известная как теория алгоритмов, посвящена исследованию свойств, способов записи, области применения различных алгоритмов, а также созданию новых алгоритмов. Теория алгоритмов находит широкое применение в различных областях деятельности человека — в технике, производстве, медицине, образовании и т. д. Появление компьютера позволило решать чрезвычайно сложные, трудоемкие задачи.

Определение алгоритма для применения в области информатики нуждается в некотором уточнении. Во-первых, решение задач в информатике всегда связано с преобразованием информации, а значит, исходными данными и результатом работы алгоритма должна быть информация. Это может быть представлено в виде схемы.

Во-вторых, алгоритмы в информатике предназначены для реализации в виде компьютерных программ или для создания некоторой компьютерной технологии. Для выполнения алгоритма требуется конечный объем оперативной памяти и конечное время.

Основные требования, предъявляемые к алгоритмам:

Дискретность (прерывность): алгоритм должен представлять решение задачи в виде последовательности простых (или ранее определенных) этапов (шагов). Каждый шаг алгоритма формулируется в виде инструкций (команд).

Определенность (детерминированность; лат. determinate — определенность, точность): шаги (операции) алгоритма должны допускать однозначную трактовку и быть понятными для исполнителя алгоритма. Это свойство указывает на то, что любое действие в алгоритме должно быть строго определено и описано для каждого случая.

Массовость: алгоритм должен давать решение не только для конкретного набора значений, а для целого класса задач, который определяется диапазоном возможных исходных данных (область применимости алгоритма). Свойство массовости подразумевает использование переменных в качестве исходных данных алгоритма.

Результативность: алгоритм должен давать конкретный результат, т. е. должны быть рассмотрены все возможные ситуации и для каждой из них получен результат. Под результатом может пониматься и сообщение о том, что задача решения не имеет.

Конечность: количество шагов алгоритма должно быть конечным.

Эффективность: количество шагов и сами шаги алгоритма должны быть такими, чтобы решение могло быть найдено за конечное и, более того, приемлемое время.

Для оценки и сравнения алгоритмов существует много критериев. Чаще всего анализ алгоритма (или, как говорят, анализ сложности алгоритма) состоит в оценке временных затрат на решение задачи в зависимости от объема исходных данных. Используются также термины «временная сложность», «трудоемкость» алгоритма. Фактически эта оценка сводится к подсчету количества основных операций в алгоритме, поскольку каждая из них выполняется за заранее известное конечное время. Кроме временной сложности, должна оцениваться также емкостная сложность, т. е. увеличение затрат памяти в зависимости от размера исходных данных. Оценка сложности дает количественный критерий для сравнения алгоритмов, предназначенных для решения одной и той же задачи. Оптимальным (наилучшим) считается алгоритм, который невозможно значительно улучшить в плане временных и емкостных затрат.

Анализом сложности алгоритмов, исследованием классов задач, решаемых с помощью алгоритмов той или иной сложности, и многими другими теоретическими вопросами занимается специальная область информатики.

Алгоритмы можно представлять как некоторые структуры, состоящие из отдельных базовых элементов.

Логическая структура любого алгоритма может быть представлена комбинацией трех базовых структур:

1. следование — образуется из последовательности действий, следующих одно за другим;
2. ветвление (развилка) — обеспечивает в зависимости от результатов проверки условия (ДА или НЕТ) выбор одного из альтернативных путей алгоритма;
3. цикл — обеспечивает многократное выполнение некоторой совокупности действий, которая называется телом цикла.

Для описания алгоритмов наиболее распространены следующие методы (языки):

Обычный язык. Изложение алгоритма ведется на обычном языке с разделением на последовательные шаги.

Блок-схемы. Графическое изображение алгоритма с помощью специальных значков-блоков.

Формальные алгоритмические языки (языки программирования). При записи алгоритмов используют строго определенный набор символов и составленных из них специальных зарезервированных слов. Имеют строгие правила построения языковых конструкций.

Псевдокод. Синтез алгоритмического и обычного языков. Элементы некоторого базового алгоритмического языка используются для строгой записи базовых структур алгоритма.

Словесный способ (запись на обычном языке) не имеет широкого распространения, т. к. таких описаний есть ряд недостатков:

• строго не формализуемы;
• достаточно многословны;
• могут допускать неоднозначность толкования отдельных предписаний;
• сложные задачи с анализом условий, с повторяющимися действиями трудно представляются в словесной или словесно-формульной форме.

Графический способ представления информации является более наглядным и компактным по сравнению со словесным. При графическом представлении алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий. Такое графическое представление алгоритма называется блок-схемой. Определенному типу действия (ввод/вывод данных, проверка условия, вычисление выражения, начало и конец алгоритма и т. п.) соответствует определенная геометрическая фигура — блочный символ. Блоки соединяются между собой линиями переходов, которые определяют очередность выполнения действий.

Название символа	Графическое изображение	Комментарии
Пуск/Останов (блоки начала и конца алгоритма)		Указание на начало или конец алгоритма
Ввод/Вывод данных (блоки ввода, вывода		Организация ввода/вывода в общем виде
Процесс (операторные блоки)		Выполнение вычислительного действия или последовательности действий (можно объединять в один блок), которые изменяют значение, форму представления или размещение данных
Условие (условный блок)		Выбор направления выполнения алгоритма. Если условие, записанное внутри ромба, выполняется, то управление передается по стрелке «да», в противном случае — по стрелке «нет». Таким образом, реализуется процесс изменения последовательности вычислений в зависимости от выполнения условия
Начало цикла с параметром		Используется для организации циклических конструкций с известным количеством итераций (повторений) и известным шагом изменения параметра цикла. Внутри блока для параметра цикла указываются через запятую его начальное значение, конечное значение и шаг изменения. Цикл, для которого неизвестно количество повторений, записывается с помощью условного и операторных блоков
Предопределенный процесс		Используется для указания обращений к вспомогательным алгоритмам, существующим автономно в виде некоторых самостоятельных модулей, и для обращения к библиотечным подпрограммам
Печать сообщений (документ)		Вывод результатов на печать

При составлении блок-схемы необходимо проверять выполнение следующих условий:

1. из каждого прямоугольника и параллелограмма (кроме конца алгоритма) должна выходить только одна стрелка;
2. в каждый прямоугольник и параллелограмм (кроме начала алгоритма) должна входить хотя бы одна стрелка;
3. в каждый ромб должна входить хотя бы одна стрелка, а выходить из него — две стрелки, помеченные словами «ДА» и «НЕТ».

Псевдокод занимает промежуточное положение между естественным языком и языками программирования. В псевдокоде не приняты строгие синтаксические правила для записи команд, что отличает формальные языки программирования. Однако в псевдокоде есть некоторые конструкции, которые присущи формальным языкам, что облегчает переход от записи алгоритма на псевдокоде к записи алгоритма на языке программирования. Псевдокоды бывают разные. Рассмотрим учебный (школьный) алгоритмический язык АЯ.

Алфавит учебного алгоритмического языка является открытым. В него могут быть введены любые понятные всем символы: русские и латинские буквы, знаки математических операций, знаки отношений, специальные знаки и т. д. Кроме алфавита, в алгоритмической нотации определяются служебные слова, которые являются неделимыми. Служебные слова обычно выделяются жирным шрифтом или подчеркиванием. К служебным словам относятся:

Общий вид записи алгоритма на псевдокоде:

алг — название алгоритма (аргументы и результаты)

дано — условие применимости алгоритма

надо — цель выполнения алгоритма

нач — описание промежуточных величин

последовательность команд (тело алгоритма)

кон

Часть алгоритма от слова алг до слова нач называется заголовком, а часть, заключенная между словами нач и кон, — телом алгоритма (исполняемой частью алгоритма).

В предложении алг после названия алгоритма в круглых скобках указываются характеристики (арг, рез) и тип значения (цел, вещ, сим, лит или лог) всех входных (аргументы) и выходных (результаты) переменных. При описании массивов (таблиц) используется служебное слово таб, дополненное именем массива и граничными парами по каждому индексу элементов массива.

Команды учебного языка:

1. Оператор присваивания, который обозначается «:=» и служит для вычисления выражений, стоящих справа, и присваивания их значений переменным, указанным в левой части. Например, если переменная а имела значение 5, то после выполнения оператора присваивания а := а + 1, значение переменной а изменится на 6.

2. Операторы ввода/вывода:

ввод (список имен переменных)

вывод (список вывода)

Список вывода может содержать комментарии, которые заключаются в кавычки.

3. Оператор ветвления (с использованием команды если…то… иначе…всё; выбор);

4. Операторы цикла (с использованием команд для, пока, до).

Запись алгоритма на псевдокоде:

Здесь в предложениях дано и надо после знака «|» записаны комментарии. Комментарии можно помещать в конце любой строки, они существенно облегчают понимание алгоритма.

При записи алгоритма в словесной форме, в виде блок-схемы или на псевдокоде допускается произвольное изображение команд. Вместе с тем такая запись позволяет понять человеку суть дела и исполнить алгоритм. Однако алгоритм, предназначенный для исполнения на компьютере, должен быть записан на строго формализованном языке. Такой язык называется языком программирования, а запись алгоритма на этом языке — компьютерной программой.

Для решения одной и той же задачи можно предложить несколько алгоритмов. Алгоритмы составляются с ориентацией на определенного исполнителя алгоритма. У каждого исполнителя имеется свой конечный набор команд, которые для него понятны и исполняемы. Этот набор называется системой команд исполнителя. Пользуясь системой команд, исполнитель может выполнить алгоритм формально, не вникая в содержание поставленной задачи. От исполнителя требуется только строгое выполнение последовательности действий, предусмотренной алгоритмом. Таким образом, в общем случае алгоритм претерпевает изменения по стадиям:

• первая стадия — алгоритм должен быть представлен в форме, понятной человеку, который его разрабатывает;
• вторая стадия — алгоритм должен быть представлен в форме, понятной исполнителю алгоритма (вторая стадия может отсутствовать, если исполнять алгоритм будет сам разработчик).

Примеры решения задач

Пример 1. Исполнитель Утроитель может выполнить только две команды, которым присвоены номера:

1 — вычти 1;

3 — умножь на 3.

Первая команда уменьшает число на 1, вторая — увеличивает его втрое.

Написать набор команд (не более пяти) получения из числа 3 числа 16. В ответе указать только номера команд.

Решение.

1 (3 – 1 = 2)

3 (2 * 3 = 6)

3 (6 * 3 = 18)

1 (18 – 1 = 17)

1 (17 – 1 = 16)

Ответ: 13311

Пример 2. Имеется Исполнитель алгоритма, который может передвигаться по числовой оси.

Система команд Исполнителя алгоритма:

1. «Вперед N» (Исполнитель алгоритма делает шаг вперед на N единиц).

2. «Назад M» (Исполнитель алгоритма делает шаг назад на M единиц).

Переменные N и M могут принимать любые целые положительные значения. Известно, что Исполнитель алгоритма выполнил программу из 50 команд, в которой команд «Назад 2» на 12 больше, чем команд «Вперед 3». Других команд в программе не было. Какой одной командой можно заменить эту программу, чтобы Исполнитель алгоритма оказался в той же точке, что и после выполнения программы?

Решение.

1. Найдем, сколько было команд «Вперед», а сколько «Назад». Учитывая, что общее количество команд равно 50 и что команд «Назад» на 12 больше, чем команд «Вперед». Получим уравнение: x + (x + 12) = 50, где x — количество команд «Вперед». Тогда общее количество команд «Вперед»: x = 19, а количество команд «Назад»: 19 + 12 = 31.

2. Будем вести отсчет от начала числовой оси. Выполнив 19 раз команду «Вперед 3», Исполнитель алгоритма оказался бы на отметке числовой оси 57 (19 * 3 = 57). После выполнения 31 раз команды «Назад 2» (31 * 2 = 62) он оказался бы на отметке –5 (57 – 62 = –5).

3. Все эти команды можно заменить одной — «Назад 5».

Ответ: команда«Назад 5».

Пример 3. Черепашка является исполнителем для создания графических объектов на рабочем поле. При движении Черепашка оставляет след в виде линии. Черепашка может исполнять следующие команды:

Для записи повторяющихся действий (цикла) используется команда Повтори. В этой команде два параметра: первый задает количество повторений (итераций), а второй — список команд которые должны повторяться (тело цикла); список заключается в квадратные скобки.

Записать для исполнителя Черепашка алгоритмы:

а) построения квадрата со стороной 100;

б) построения правильного шестиугольника со стороной 50.

в) построения изображения цифры 4, если голова Черепашки смотрит на север.

Ответ: а) Повтори 4 [вп 100 пр 90]; б) Повтори 6 [вп 50 пр 360/6]; в) вп 100; повтори [лв 135 вп 50].

Пример 4. Два игрока играют в следующую игру (это вариант восточной игры). Перед ними лежат три кучки камней, в первой из которых 2, во второй — 3, в третьей — 4 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или удваивает число камней в одной из кучек, или добавляет по два камня в каждую из них. Выигрывает игрок, после хода которого либо в одной из кучек становится не менее 15 камней, либо общее число камней в трех кучках становится не менее 25. Кто выиграет при безошибочной игре обоих игроков — игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ следует обосновать.

Решение. Удобнее всего составить таблицу возможных ходов обоих игроков. Заметим, что в каждом случае возможны всего четыре варианта хода. В таблице курсивом выделены случаи, которые сразу же приносят поражение игроку, делающему этот ход (например, когда камней в какой-либо кучке становится больше или равно 8, другой игрок непременно выигрывает следующим ходом, удваивая количество камней в этой кучке). Из таблицы видно, что при безошибочной игре обоих игроков первый всегда выиграет, если первым ходом сделает 4, 5, 6. У второго игрока в этом случае все ходы проигрышные.

Пример 5. Записано 7 строк, каждая из которых имеет свой номер. В нулевой строке после номера записана цифра 001. Каждая последующая строка содержит два повторения предыдущей строки и добавленной в конец большой буквы латинского алфавита (первая строка — A, вторая строка — B и т. д.). Ниже приведены первые три строкиєтой записи (в скобках указан номер строки):

(0) 001

(1) 001001A

(2) 001001A001001AB

Какой символ находится в последней строке на 250-м месте (считая слева направо)?

Примечание. Первые семь букв латинского алфавита: A, B, C, D, E, F, G.

Решение. Найдем длину каждой строки. Длина каждой следующей строки в два раза больше длины предыдущей плюс один символ, длина строк составит:

(0) 3 символа;

(1) 3*2+1=7;

(2) 7*2+1=15;

(3) 15*2+1=31;

(4) 31*2+1=63;

(5) 63*2+1=127;

(6) 127*2+1=255 символов.

Так как задано 7 строк, а нумерация начинается с нулевой строки, последняя строка имеет номер 6 и содержит 255 символов. Последний символ в строке — F. Предпоследний элемент — E, далее идут символы D, C, B, A, 1 (по правилу формирования строк). Таким образом, 250-й символ — это 1.

Ответ: 1.

Пример 6. Имеется фрагмент алгоритма, записанный на учебном алгоритмическом языке:

n := Длина(а)

k = 2

b := Извлечь(а, k)

нц для i от 7 до n – 1

с := Извлечь(а, i)

b := Склеить(b, с)

кц

Здесь переменные а, b, с — строкового типа; переменные n, i — целые.

В алгоритме используются следующие функции:

Длина(х) — возвращает количество символов в строке х. Имеет тип «целое».

Извлечь(х, i) — возвращает i-й символ слева в строке х. Имеет строковый тип.

Склеить(х, у) — возвращает строку, в которой находятся все символы строки х, а затем все символы строки у. Имеет строковый тип.

Какое значение примет переменная b после выполнения этого фрагмента алгоритма, если переменная а имела значение «ВОСКРЕСЕНЬЕ»?

Решение. Находим общее число символов в строке а, получим, что n = 11.

Выполняя команду b := Извлечь(а, k) при k = 2, получим, что b примет значение «О«.

В цикле последовательно, начиная с 7-го символа строки а и заканчивая предпоследним (n – 1), извлекаем символ из строки а и присоединяем к строке b.

В результате получим слово «ОСЕНЬ» (символы с номерами 2 + 7 + 8 + 9 + 10).

Ответ: «ОСЕНЬ«

Пример 7. Леонардо из Пизы, известный как Фибоначчи, был первым из великих математиков Европы позднего Средневековья. Числовой ряд, который называется его именем, получился в результате решения задачи о кроликах, которую Фибоначчи изложил в своей «Книге Абака», написанной в 1202 году. Он выглядит так:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,…

В этом ряду каждое следующее число, начиная с третьего, равно сумме двух предыдущих. Составить словесный алгоритм и блок-схему проверки принадлежности введенного числа n ряду Фибоначчи.

Решение. Словесный алгоритм:

1. Ввести число n.
2. Установить значение первых трех чисел Фибоначчи: 1, 1, 2 (сумма двух предыдущих чисел).
3. Пока введенное число n больше очередного числа Фибоначчи, взять два последних числа Фибоначчи и получить из них новое число Фибоначчи.
4. Если число Фибоначчи равно введенному n или было введено число n = 1, значит, что было введено число Фибоначчи, в противном случае — введенное число не является числом Фибоначчи.

Приведенный словесный алгоритм в пункте 1, 2 содержит начальные установки, в пункте 3 — цикл с условием, а пункт 4 — это вывод результата работы алгоритма.

Блок-схема алгоритма:

Обозначения:

F — текущее число ряда Фибоначчи;

F1 и F2 — два предыдущих числа ряда Фибоначчи для числа F;

n — число, для которого требуется определить, является ли оно числом из ряда Фибоначчи.

Использование основных алгоритмических конструкций: следование, ветвление, цикл

Логическая структура любого алгоритма может быть представлена комбинацией трех базовых структур: следование, ветвление, цикл.

Базовая структура СЛЕДОВАНИЕ указывает на то, что управление передается последовательно от одного действия к другому.

Учебный алгоритмический язык	Язык блок-схем
действие 1 действие 2 … действие n

Использование исключительно этой структуры возможно лишь для достаточно простых задач, ход решения которых не меняется в зависимости от конкретных исходных данных и состоит в последовательном выполнении определенных операций.

В качестве примера рассмотрим решение простой задачи.

Пример. Найти y(x) = x2 + 3x + 5, используя только операции умножения и сложения.

Решение. На рис. приводятся два алгоритма, реализующие решение поставленной задачи.

Порядок вычисления y(x) в первом случае — обычный, а во втором — (x + 3) x + 5. Обе формулы эквивалентны, но в первом случае для вычисления необходимо 2 умножения, 2 сложения и 3 переменных (x, y, z), а во втором используются 1 умножение, 2 сложения и 2 переменные (x, y).

Приведенный пример показывает, что даже простые задачи могут решаться с помощью различных вариантов алгоритмов.

Обратите внимание, как в блоке следования используется оператор присваивания.

Операция присваивания — важнейшая операция во всех языках программирования. С помощью присваивания переменные получают новые значения: в левой части инструкции ставится идентификатор величины, а в правой части — выражение, значение которого можно определить.

В операторах присваивания используется либо привычный знак равенства, либо сочетание двоеточия и знака равенства «:=». Поскольку знак присваивания — это не знак равенства, возможны записи вида Х := Х + 1 или А := А – В. Нужно учитывать, что оператор присваивания будет выполняться только в том случае, если значения всех переменных правой части уже определены.

Базовая структура ВЕТВЛЕНИЕ (РАЗВИЛКА) используется в случае, когда выполнение программы может измениться в зависимости от результата проверки условия и пойти двумя разными (альтернативными) путями. Другими словами, условие является некоторым высказыванием (предикатом) и может быть истинным или ложным (принимать значение TRUE или FALSE). Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран.

Различают две структуры этого типа — полную и неполную. В случае полной структуры, если условие выполняется (является истинным), вслед за ним выполняется действие 1, иначе — действие 2. В случае неполной структуры, если условие выполняется (является истинным), то вслед за ним выполняется действие 1, иначе ничего не происходит.

Важную роль в операторах ветвления играют содержащиеся в них условия. В простейшем случае условиями служат отношения между величинами. Условия с одним отношением называют простыми условными выражениями, или простыми условиями. В некоторых задачах необходимы более сложные условия, состоящие из нескольких простых, например условие А < X < С, т. е. Х < А и (Х > C) (возможна запись (Х < А) and (Х > C)). Объединение нескольких простых условий в одно образует составное условное выражение, или составное условие. Составные условия образуются с помощью логических операторов not (отрицание), and (логическое И), or (логическое ИЛИ), хоr (исключающее ИЛИ).

Структура ВЕТВЛЕНИЕ существует в четырех основных вариантах:

если — то (неполная структура);

если — то — иначе (полная структура);

выбор (неполный);

выбор — иначе (полный).

Учебный алгоритмический язык	Язык блок-схем
1) если — то
если условие то действие 1 всё
2) если — то — иначе
если условие то действие 1 иначедействие 2 всё
3) выбор
выбор при условие 1: действие 1 при условии 2: действие 2 … при условие N: действие N всё
4) выбор — иначе
выбор при условие 1: действие 1 при условие 2: действие 2 … при условие N: действие N + 1 иначе действия N + 1 всё

В качестве простого примера рассмотрим нахождение модуля числа y(x) = |x|. Решение приведено на рис. для случаев полной (а) и неполной (б) структур ветвления.

Базовая структура ЦИКЛ служит для записи алгоритмов, в которых некоторая часть алгоритма (тело цикла) должна повторяться несколько раз. Количество повторений цикла может определяться разными способами, в зависимости от которых различают три вида циклов.

1. Цикл с предусловием, или цикл «пока». При реализации этого цикла сначала проверяется условие его выполнения. Пока оно выполняется, будут происходить повторения тела цикла. Отсюда и другое его название — цикл «пока». Если условие не выполняется при первой проверке, то тело цикла не будет выполняться вообще. После выхода из цикла управление передается следующей структуре. Для того чтобы избежать зацикливания, т. е. бесконечного цикла, в теле цикла обязательно должны изменяться параметры, записанные в условии.

Учебный алгоритмический язык	Язык блок-схем
нц пока условие тело цикла (последовательность действий) кц

2. Цикл с параметром. Этот вид цикла удобно использовать в тех случаях, когда заранее извесно количество повторений цикла. Вводится понятие счетчика цикла, который по умолчанию считается равным либо 1, либо –1. В некоторых случаях изменение счетчика цикла (приращение) указывают явно. Для организации цикла необходимо задать верхнюю и нижнюю границы изменения счетчика цикла. В зависимости от значения верхней и нижней границы определяется шаг цикла (1 или −1), т. е. значение счетчика цикла.

Учебный алгоритмический язык	Язык блок-схем
нц для i от i1 до i2 тело цикла (последовательность действий) кц

3. Цикл с постусловием, или цикл «до». При реализации этого цикла условие завершение цикла проверяется после тела цикла. В этом случае тело цикла всегда выполняется хотя бы один раз. Цикл будет выполняться до выполнения условия, отсюда и другое название — цикл «до». А пока условие не выполнено, будет повторяться тело цикла (выполнение условия, таким образом, является условием окончания цикла). В этом случае, как и в цикле «пока», необходимо предусмотреть в теле цикла изменение параметров условия цикла.

Учебный алгоритмический язык	Язык блок-схем
нц тело цикла (последовательность действий) до условие кц

Для всех видов цикла предусмотрена возможность досрочного выхода, т. е. прерывание работы цикла.

Помимо трех рассмотренных видов цикла существует и так называемый интерационные циклы. Особенностью итерационного цикла является то, что число повторений операторов тела цикла заранее неизвестно. Для его организации используется цикл типа пока. Выход из итерационного цикла осуществляется в случае выполнения заданного условия. На каждом шаге вычислений происходит последовательное приближение и проверка условия достижения искомого результата. Классический пример — вычисление суммы ряда с заданной точностью.

Алгоритм, в состав которого входит итерационный цикл, называется итерационным алгоритмом. Итерационные алгоритмы используются при реализации итерационных численных методов. В итерационных алгоритмах необходимо обеспечить обязательное условие выхода из цикла (сходимость итерационного процесса). В противном случае произойдет зацикливание алгоритма, т. е. не будет выполняться основное свойство алгоритма — результативность.

Пример. Вычислить сумму знакопеременного ряда $S=x-{x^2}/{2}+{x^3}/{3}-{x^4}/{4}+…$ с заданной точностью $ε$.

Для данной знакочередующейся бесконечной суммы требуемая точность будет достигнута, когда очередное слагаемое станет по абсолютной величине меньше $ε$.

Решение. Запишем блок-схему алгоритма, где будем использовать следующие обозначения:

$S$ — частичная сумма ряда (стартовое значение равно 0);

$ε$ — точность вычисления;

$i$ — номер очередного слагаемого;

$m$ — значение очередного слагаемого;

$p$ — числитель очередного слагаемого.

На псевдокоде алгоритм можно записать следующим образом:

Примечание. Следует отметить, что ряд будет сходящимся только при выполнении условия 0 < х < 1.

Возможны случаи, когда внутри тела цикла необходимо повторить некоторую последовательность операторов, т. е. организовать внутренний цикл. Такая структура получила название цикла в цикле, или вложенного цикла. Глубина вложения циклов (количество вложенных друг в друга циклов) может быть различной.

При использовании такой структуры для экономии времени выполнения необходимо выносить из внутреннего цикла во внешний все действия, результаты которых не зависят от параметра внутреннего цикла.

Пример. Вычислить сумму элементов для заданной матрицы (таблицы из 5 строк и 3 столбцов) А(5,3).

Решение. Алгоритм решения задачи на псевдокоде:

Основная часть блок-схемы нахождения суммы элементов матрицы будет иметь следующий вид:

Здесь порядок выполнения вложенных циклов следующий: счетчик внутреннего цикла изменяется быстрее, т. е. для i = 1(внешний цикл), j пробегает значения 1, 2, 3 (внутренний цикл); далее i = 2, j опять пробегает значения 1, 2, 3 и т. д.

Примеры решения задач

Пример 1. Дан фрагмент блок-схемы некоторого алгоритма.

Определить значение переменной А после выполнения фрагмента алгоритма.

Какие исправления нужно внести, чтобы изменение значения переменной А происходило в обратном порядке?

Как записать исходный алгоритм с помощью двух других видов цикла?

Решение. Если представить пошаговое выполнение алгоритма в виде таблицы, получим:

Таблица обратного хода изменения значения А будет иметь такой вид:

Блок-схема алгоритма примет такой вид:

В алгоритме нужно изменить начальное значение А и операцию деления заменить операцией умножения. Счетчик N в данном случае изменять не нужно.

В приведенной в условии блок-схеме используется цикл с предусловием. Для цикла с параметром блок-схема алгоритма будет иметь такой вид:

Понятно, что цикл должен выполниться пять раз. В заголовке цикла необходимо указать начальное и конечное значение счетчика цикла N (приращение по умолчанию равно 1).

Для цикла с постусловием блок-схема исходного алгоритма имеет такой вид:

В данной схеме условие завершения цикла находится после тела цикла. Цикл, в отличие от цикла с предусловием, выполняется, пока значение условия ложно.

Пример 2. Сколько раз выполнится тело цикла в программе?

Q := 27; P := 36

нц пока (div(Q, 5) = div(P, 7))

Q := Q + 2

P := P + 3

кц

Примечание. Результат функции div(X, Y) — целая часть от деления X на Y.

Решение. Рассмотрим пошаговое выполнение алгоритма, оформив его в виде таблицы.

Ответ: цикл выполнится 4 раза.

Использование переменных. Объявление переменной (тип, имя, значение).
Локальные и глобальные переменные

Величины служат для описания объектов и процессов в материальном мире. Каждая величина имеет некоторые характеристики. В программировании понятие величины несколько отличается от понятия величины в естественных науках — оно является более формальным. Величиной называют объект — переменную, с которым связывается определенное множество значений. Такому объекту присваивается имя — идентификатор. Понятие переменной в программировании сходно с понятием переменной в математике. Например, в алгебраическом равенстве C = F + 2B – 5 значение переменной С зависит от значений переменных F и B, указанных в правой части равенства. Например, при F = 2 и B = 6, С = 9. Такое же равенство можно записать в программе, например на языке программирования Бейсик: C = F + 2*B – 5. В терминах языка программирования C, F и B — это идентификаторы (имена) переменных.

Переменная — это объект программы, имеющий имя и изменяемое значение. Для хранения переменной в памяти компьютера выделено определенное место.

Переменные величины в отличие от постоянных величин (констант) могут со временем менять свое значение. Константой называется величина, которая в ходе выполнения программы не меняет своего значения.

Назначение программы состоит в обработке информации, при этом, конечно, основную роль играют переменные.

Переменная характеризуется:

• идентификатором;
• типом;
• значением.

Каждая переменная имеет свой идентификатор, т. е. свое уникальное имя. Имя переменной показывает, в каком месте памяти компьютера она хранится, значение переменной считывается из указанного ее именем места в памяти. Двух переменных с одним именем в одном программном модуле (блоке) быть не должно. Примерами идентификаторов величин могут быть, например, следующие последовательности символов: a1, SUMMA, X_1, Y_1, My_program.

Во многих языках программирования существуют некоторые ограничения на задания имен переменных. Имена составляются из букв и цифр; первой литерой должна быть буква. Знак подчеркивания «_» считается буквой, его удобно использовать, чтобы улучшить восприятие длинных имен переменных. Разумно давать переменным логически осмысленные имена, в соответствии с их назначением. Нельзя использовать в качестве имен зарезервированные (служебные) слова языка программирования.

Тип переменной — это диапазон (набор) всех значений, которые может принимать данная переменная. Тип переменной определяет, какие операции для нее допустимы. Другими словами, тип переменной — это характеристика, которая для величины определяет:

• необходимый размер памяти;
• диапазон значений, которые может принимать величина;
• возможные операции над величиной (подразумеваются действия относительно использования величин в выражениях);
• формы представления величин (или формат представления величин).

Стандартные типы — это числовые, литерные и логические типы.

Числовой тип, к которому относятся целые и вещественные величины, позволяет оперировать с числами. Целые числа, которые в учебном алгоритмическом языке составляют тип цел, сверху ограничены положительным числом N_max, а снизу — отрицательным числом N_min. Значения N_max и N_min определяются объемом ячеек памяти, в которые записываются целые числа. Обычно для целых чисел выделяется два байта памяти, соответственно границы диапазона равны [N_min = –32768 и N_max = 32767]. Считается, что все операции с величинами типа цел выполняются по обычным правилам арифметики, за одним исключением: возможны две операции деления div и mod.

Операция div обозначает целочисленное деление. При делении с точностью до целых чисел получается два результата — частное и остаток. Знак результата берется по обычным правилам, а полученный остаток игнорируется. Например:

23 div 5 = 4;

2 div 6 = 0;

(–13) div 5 = –2;

(–13) div (–5) = 2.

Операция mod определяет остаток при делении двух целых чисел.

Например:

23 mod 5 = 3;

2 mod 6 = 2;

(–13) mod 5 = –3;

(–13) mod (–5) = 3;

8 mod 2 = 0.

Целые числа чаще всего используются в простых арифметических выражениях и выступают в программах в качестве различных счетчиков и значений индексов.

К другому числовому типу относятся вещественные (вещ) величины. Значения вещественных величин могут изображаться в форме с фиксированной запятой (например, 0,3333; 2,0; –4,567 и т. д.) и с плавающей запятой (например, 7,0*10², 5,173*10^–3 и т. д.).

В отличие от целых чисел, действия с вещественными числами могут быть неточными — это связано с ошибками округлений. Объем памяти, который предоставляется для хранения значений вещественной переменной, — от 4 до 10 байтов (в зависимости от выбранного формата числа). Над числовыми величинами можно выполнять как арифметические операции, так и операции сравнения (>, <, >=, <=, =, ).

Литерный тип, включающий символы и строки, дает возможность работать с текстом. Литерные величины — это произвольные последовательности символов: букв, цифр, знаков препинания, пробела и других специальных знаков (возможными символами могут быть символы таблицы ASCII). Литерные величины обычно заключаются в кавычки: «а», «В», «СТРОКА», «1_2_3». В учебном алгоритмическом языке литерные величины обозначаются как лит. В других языках программирования (например, в Паскале) различают символьный (char) и строковый (string) типы. Величины символьного типа состоят из одного символа и занимают в памяти всего 1 байт. Величины строкового типа представляют собой различные последовательности символов, которые предусмотрены кодовой страницей, установленной в компьютере. Длина строки может составлять от 0 до 255 символов. Над всеми литерными величинами возможны операции сравнения. С помощью отношений типа «a» < «b», «b» < «c», «c» < «d»,… выполняется упорядочение литерных величин (сортировка по возрастанию или убыванию).

Еще одной операцией, характерной для символьных и строковых величин, является операция конкатенации (слияния): «a» + «b» = «ab».

Логический тип позволяет определять логические переменные, которые могут принимать только два значения: истина (true) или ложь (false). Для представления логической величины достаточно одного бита, однако, поскольку место в памяти выделяется по байтам, логической величине отводится минимальная «порция» памяти — один байт. Над логическими величинами можно выполнять все стандартные логические операции.

Значение — это непосредственно то, чему равна переменная в конкретный момент времени. Это может быть число, символ, текст и т. д. Значение переменной в программе можно задать двумя способами: присваиванием и с помощью процедуры ввода.

Оператор присваивания

Во всех языках программирования оператор присваивания является одним из важнейших. С помощью присваивания переменные получают новые значения, например:

Д := 13;

D1 := C;

Х := Х + 1.

В операторах присваивания используется либо обычный знак равенства, либо сочетание двоеточия и знака равенства «:=». Поскольку знак присваивания — это не знак равенства, возможны записи вида Х := Х + 1 или А := А – В. Нужно учитывать, что оператор присваивания будет выполняться только в том случае, если значения всех переменных в правой части уже определены и выполняется соответствие типов для правой и левой части оператора присваивания. Например, С := А > B выполнится только в том случае, если для переменной С определен булевский (логический) тип. Операция присваивания может быть применена к большинству типов величин. Однако для каждого из типов предусмотрен свой набор операций.

Локальные, глобальные и общие переменные

Каждая переменная характеризуется областью действия или областью видимости. По зоне видимости в языках программирования различают локальные и глобальные переменные. Первые доступны только конкретному подалгоритму (вспомогательному алгоритму, подпрограмме, модулю), вторые — всему алгоритму (программе). С распространением модульного и объектного программирования появились еще и общие переменные, доступные для определенных уровней иерархии подпрограмм.

Ограничение зоны видимости придумали как для возможности использовать одинаковые имена переменных, так и для защиты от ошибок, связанных с неправомерным использованием переменных.

Имена локальных и глобальных переменных могут совпадать. При этом действует правило: локальные переменные на время работы подпрограмм, в которых они объявлены, экранируют, т. е. перекрывают глобальные переменные. Например, если в основной программе переменная с именем с определена как логическая, а в подпрограмме идентификатор с используется для задания вещественной переменной, то только на время работы подпрограммы с можно использовать как число — в остальных случаях идентификатор с определяет логическую переменную.

Примеры решения задач

Пример 1. Значения заданных переменных А, В перераспределить таким образом, чтобы А и В поменялись значениями.

Решение. Возможны два варианта решения:

Пример 2. Определить значение переменной A после выполнения фрагмента алгоритма:

Решение. Оформим решение в виде таблицы.

Ответ: А = 128.

Пример 3. Определить значение переменной S:

A := –1; B := 1

нц пока A + B < 10

A := A + 1; B := B + A

кц

S := A * B

Решение. Оформим решение в виде таблицы.

Ответ: S = 21.

Пример 4. Записать последовательность операций присваивания (:=), которая позволит определить номера подъезда и этажа по номеру N квартиры девятиэтажного дома, считая, что на каждом этаже по 4 квартиры, а нумерация квартир начинается с первого подъезда.

Решение.

4 * 9 = 36 {количество квартир в подъезде}

Х := (N – 1) div 36 + 1 {номер подъезда}

N := N – (X – 1) * 36 { N ∊[1, 36] }

Y := (N – 1) div 4 + 1 {номер этажа}

Например, для квартиры с номером 150 получим:

Х = (150 – 1) div 36 + 1 = 4 + 1 = 5;

N = 150 – (5 – 1) * 36 = 6;

Y = (6 – 1) div 4 + 1 = 2.

Ответ: квартира с номером 150 находится в пятом подъезде, на втором этаже.

Работа с массивами (заполнение, считывание, поиск, сортировка, массовые операции и др.)

Величины числового, литерного, логического типов представляются одним значением и относятся к простым типам данных. Характерной особенностью простых типов является атомарность, т. е. они не могут вмещать элементы других типов. Типы данных, которые не удовлетворяют данному условию, называются структурированными, или составными. Например, массивы, записи, строки, множества, файлы. Структурированный тип характеризуется множеством элементов, из которых складываются данные этого типа. Элементы структурированного типа называются компонентами. В свою очередь компонента структурированного типа может принадлежать также к структурированному типу. Из простых данных сложные структуры могут получаться двумя способами:

1. объединением однородных элементов данных;
2. объединением разнородных элементов данных.

В первом случае примером могут служить массивы, а во втором — записи.

Информацию удобно представлять в виде таблиц. Наиболее привычными являются прямоугольные таблицы, т. е. таблицы, состоящие из строк и столбцов. В том числе таблицы, состоящие из единственной строки или единственного столбца, — линейные таблицы, имеющие одно «измерение».

Табличные величины относятся к составным величинам, т. к. включают в себя другие величины. В учебном алгоритмическом языке табличный тип обозначается как таб. Таблицы в программировании принято называть массивами. В математике прототипом массивов являются матрицы и векторы.

Массив

Массив — это упорядоченный набор данных, имеющий одно имя и состоящий из фиксированного числа однотипных элементов.

Каждый элемент массива снабжен индексом. Индекс — это порядковый номер элемента, определяющий его положение в массиве. Таким образом, элементы массива идентифицируются с помощью имени массива и с помощью своих индексов.

Количество элементов массива называется размерностью массива.

Итак, массив характеризуется:

• размерностью;
• базовым типом элементов;
• типом индекса (может быть только порядковым типом);
• множеством значений для индекса.

Массив может быть одномерным (вектор) и многомерным (матрица).

Одномерный массив содержит одно измерение; каждый элемент массива обозначается идентификатором (именем) массива с индексом. Многомерный массив содержит n-е количество измерений; каждый элемент массива обозначается идентификатором массива для n индексов.

Существует несколько способов заполнения массива данными:

1. непосредственное присваивание значений элементам;
2. заполнение массива произвольными элементами, случайными числами;
3. ввод значений элементов с клавиатуры или чтение из файла.

Необходимо заметить, что заполнение массива происходит поэлементно. Для этого используют оператор цикла. Вывод массива также осуществляется поэлементно с помощью оператора цикла.

Примечание. Строковый тип данных напоминает одномерный массив, в котором элементами являются символы. К примеру, строку «МАМА КУПИЛА ХЛЕБ» можно рассматривать как одномерный массив из 16 символов (включая пробелы). Эту строку можно обозначить идентификатором (например, Novost) и пронумеровать все символы, считая их элементами массива: Novost (l)  = «М», … Novost (16) = «Б».

Однако для работы с символьной информацией более гибким инструментом является не одномерный массив, а строка (string). Это связано с тем, что количество символов в строке, в отличие от массива, не фиксировано. Благодаря этому к строке можно без ограничений применять стандартные операции и функции, предназначенные для работы с текстом.

Задачи, связанные с обработкой массивов, как и все задачи вообще, условно можно разделить на два вида:

1. стандартные задачи;
2. задачи, решение которых требует знания вспомогательных алгоритмов, специальных методов и приемов.

Очевидно, что без умения решать задачи первых двух видов невозможно решать нестандартные задачи.

Стандартные задачи обработки массивов

Пример 1. В массиве А каждый элемент равен 0 или 1. Заменить все нули единицами и наоборот.

Решение. Достаточно одного оператора присваивания в теле цикла:

A[i] := 1 – A[i].

Пример 2. В массиве каждый элемент равен 0, 1 или 2. Переставить элементы массива так, чтобы сначала располагались все 0, затем все 1 и, наконец, все 2. Дополнительный массив не использовать.

Решение. Можно не переставлять элементы массива, а подсчитать количество 0, 1, 2 и заново заполнить массив требуемым образом.

Пример 3. Даны два n-элементных массива Х и Y одного типа. Поменять местами все X_i и Y_i, (i = 1…n), не используя промежуточные величины.

Решение. Обмен можно выполнить в цикле для всех i от 1 до n с помощью серии из трех операторов присваивания:

X[i] := X[i] + Y[i]

Y[i] := X[i] – Y[i]

X[i] := X[i] – Y[i].

Пример 4. Записать алгоритм нахождения максимального элемента массива А(n) и его номера.

Решение. На псевдокоде требуемый алгоритм запишется следующим образом:

Примечание. Если таких элементов несколько, будет найден номер последнего.

Пример 5. Найти сумму элементов одномерного массива А(n).

Решение. На псевдокоде алгоритм нахождения суммы запишется следующим образом:

Примечание. Для нахождения суммы положительных элементов массива вместо оператора

S := S + A[i] необходимо записать:

если A[i] > 0

то S := S + A[i]

всё

Пример 6. Записать алгоритм вычисления произведения элементов столбцов заданной вещественной двумерной матрицы A(n, m).

Решение. На псевдокоде алгоритм запишется следующим образом:

Пример 7. Подсчитать количество элементов для заданной целочисленной матрицы A(n, m), равных ее максимальному элементу.

Решение. На псевдокоде алгоритм запишется следующим образом:

Пример 8. Запиcать алгоритм обмена элементами строк с номерами P и Q в заданной вещественной матрице A(n, m).

Решение. На псевдокоде алгоритм запишется следующим образом:

Пример 9. Включить заданное число D в одномерный упорядоченный по возрастанию массив F(n) с сохранением упорядоченности.

Решение. На псевдокоде алгоритм запишется следующим образом:

Пример 10. Сформировать новый массив B из элементов целочисленного массива A(n), для которых выполняется условие D < A_i < C.

Решение. На псевдокоде алгоритм запишется следующим образом:

Пример 11. Найти в заданном целочисленном массиве А(m) хотя бы одну пару элементов, совпадающих по значению.

Решение. На псевдокоде алгоритм запишется следующим образом:

Поиск — одна из важных невычислительных задач. Проведение поиска в упорядоченном и неупорядоченном массивах отличается. В неупорядоченном массиве, если нет никакой дополнительной информации об элементе поиска, его выполняют с помощью последовательного просмотра всего массива. Такой поиск называют линейным. В любом случае существуют два условия окончания поиска:

1. элемент найден;
2. весь массив просмотрен — элемент не найден.

В упорядоченном массиве поиск можно значительно ускорить, применяя метод половинного деления, или бинарный поиск. Его идея заключается в следующем. Пусть фиксированный массив упорядочен по неубыванию (a_i ≤ a_{i + 1}). Случайно выбранный элемент am (обычно берут средний элемент) сравнивают с элементом поиска х. Если он меньше х, то искомый элемент может быть среди элементов a_{m + i}, …, а_n, т. е. в правой половине массива. Если он больше х — то среди элементов левой части массива. Если же он равен х, то поиск успешно заканчивается.

К стандартным задачам относятся задачи сортировки массива. Сортировка массива — это перерасположение элементов массива в заданном порядке. Основная цель сортировки — облегчить последующий поиск. Методы условно разделяют по главной идее алгоритма, а реализуются они целым семейством алгоритмов.

К простым методам сортировки относят:

• сортировку с помощью обмена (метод пузырька);
• сортировку с помощью прямого включения;
• сортировку с помощью выбора.

Сортировка с помощью обмена. При использовании этого метода сортировки соседние элементы массива сравниваются и при необходимости меняются местами до тех пор, пока массив не будет полностью упорядочен. Повторные проходы массива каждый раз сдвигают наименьший (наибольший) элемент оставшейся части массива к левому его концу. Метод широко известен под названием «пузырьковая сортировка», т. к. большие (меньшие) элементы массива, подобно пузырькам, «всплывают» на соответствующую позицию. Основной фрагмент программы содержит два вложенных цикла, причем внутренний цикл удобнее выбрать с убывающим шагом.

Алгоритм сортировки массива A(n) по возрастанию на псевдокоде:

Сортировка с помощью прямого включения (вставки). На каждом шаге этого метода массив разделен на две части: левую, уже отсортированную, и правую, еще не отсортированную. Первый элемент правой части вставляется в левую часть массива так, чтобы левая часть осталась отсортированной. В результате отсортированная часть увеличивается на один элемент, а неотсортированная — на один элемент уменьшается. Таким образом, на каждом шаге алгоритма сортировки вставками приходится выполнять две операции: поиск позиции для вставки элемента и собственно его вставку с последующим сдвигом на одну позицию вправо от элементов отсортированной части. Этот сдвиг «стирает» первый элемент неотсортированной части. Сначала отсортированным подмассивом считаем первый элемент, а остальная часть массива относится к неотсортированной части. Поскольку операции сравнения и перемещения чередуются друг с другом, этот способ сортировки часто называют просеиванием или погружением.

Сортировка с помощью прямого выбора. При сортировке этим методом сначала выбирается наименьший (наибольший) элемент массива и меняется местами с первым. Затем выбирается наименьший (наибольший) среди оставшихся (n – 1) элементов и меняется местами со вторым и т. д. до тех пор, пока не останется один наибольший (наименьший) элемент. Сортировка осуществляется с помощью двух вложенных циклов.

Приведенные алгоритмы сортировки не требуют дополнительной оперативной памяти. Время выполнения алгоритмов сортировки пропорционально количеству операций сравнения и перестановки элементов. Сортировка массива из $n$ элементов методом выбора главного элемента требует выполнения ${n^2}/{2}$ операций сравнения и n операций обмена элементами. Метод сортировки вставками требует ${n^2}/{4}$ операций сравнения и столько же операций обмена, а метод пузырьковой сортировки — ${n^2}/{2}$ операций сравнения и столько же операций обмена. Таким образом, из трех рассмотренных методов сортировки массива методы вставки и выбора приблизительно эквивалентны, а обменная сортировка — медленнее. Кроме того, что в методе вставки исходные элементы могут поступать последовательно, а в методе выбора они должны быть в наличии до начала сортировки.

Примеры решения задач

Пример 1. Одномерный массив, содержащий десять элементов, заполняется по следующему закону: A[1] = 1; A[2] = X; A[i] = 2 * X * A[i – 1] – A[i – 2], где i = 3, 4, …, 10. Каким будет значение A[5] при X = 1?

Решение. Представим значения первых пяти элементов массива А, полученные по заданному закону при Х = 1:

A[1] = 1; A[2] = Х = 1;

A[3] = 2 * Х * A[2] – A[1] = 2 * 1 * 1 – 1 = 1;

A[4] = 2 * Х * A[3] – A[2] = 2 * 1 * 1 – 1 = 1;

A[5] = 2 * Х * A[4] – A[3] = 2 * 1 * 1 – 1 = 1.

Таким образом, значение A[5] при Х = 1 будет равно 1.

Ответ: 1.

Пример 2. Задан двумерный массив А(n, n). Определить, что вычисляет приведенный фрагмент алгоритма:

Решение. В данном алгоритме переменной S присваивается значение 0. Затем в структуре циклов по переменным i и j каждый из элементов массива А_ij сравнивается с нулем (А[i, j] > 0) и если элементы А_ij положительны, то квадраты А[i, j]^2 положительных элементов А_ij увеличивают значение суммы S (S := S + A[i, j]^2).

Ответ: фрагмент алгоритма вычисляет сумму квадратов положительных элементов массива.

Пример 3. Задан фрагмент алгоритма, использующий двумерный массив (таблицу) М(n, n), два одномерных массива A(n), B(n) и переменную X. Определить назначение массивов А и В и переменной.

Решение. Представим фрагмент алгоритма словесно.

1. Переменной X присвоить значение 0.
2. Переменной i присвоить значение 1.
3. Если i ≤ n, то перейти к следующему пункту; в противном случае — конец фрагмента алгоритма.
4. Элементу одномерного массива А с индексом i присвоить значение элемента двумерного массива М, находящегося в i-й строке и первом столбце.
5. Элементу одномерного массива В с индексом i присвоить значение 1.
6. Переменной j присвоить значение 1.
7. Если j ≤ n, то перейти к следующему пункту; в противном случае — к п. 13.
8. Если М[i, j] < A[i], то перейти к следующему пункту; иначе — к п. 11.
9. Элементу A[i] присвоить значение элемента массива М, находящегося в i-й строке и j-м столбце.
10. Элементу В[i] присвоить значение переменной j.
11. Переменной Х присвоить значение суммы X + M[i, j].
12. Переменной j присвоить значение суммы j + 1 и вернуться к п. 7.
13. Переменной i присвоить значение суммы i + 1 и вернуться к п. 3.

Таким образом, анализ алгоритма показывает, что переменная X накапливала сумму всех элементов массива М; массив А — минимальные элементы соответствующих строк массива М; массив В — индексы (порядковые номера столбцов) минимальных элементов в соответствующих строках массива М.

Пример 4. Составить алгоритм определения наличия среди элементов главной диагонали заданной целочисленной матрицы A(n, m) хотя бы одного положительного нечетного элемента.

Решение. Для всех элементов А_ij главной диагонали выполняется условие i = j. Определение наличия нечетных элементов выполняется с помощью операции mod (остаток от целочисленного деления), при этом, если результат mod равен 1, — число нечетное.

Алгоритм:

Структурирование задачи при ее решении для использования вспомогательного
алгоритма. Вспомогательные алгоритмы: процедуры и функции

Разработка алгоритмов решения задач на компьютере требует определенных навыков. При построении алгоритма нужно стремиться к тому, чтобы запись алгоритма была понятной и наглядной. Кроме того, внося изменения в алгоритм, желательно не перестраивать его полностью. Эти требования можно удовлетворить, если придерживаться структурного подхода.

Самым важным преимуществом структурного подхода является возможность нисходящего программирования, благодаря которой можно двигаться от крупных задач к более мелким. Крупная задача будет разбиваться на менее крупные блоки, те в свою очередь — на меньшие блоки и т. д. Каждый блок алгоритма должен быть максимально самостоятельным и логически завершенным.

Разбиение на блоки должно определяться внутренней логикой задач. Процесс разбиения завершается, когда решение исходной задачи сводится к решению ряда простых задач, для которых легко построить алгоритм. На каждом шаге этого процесса происходит детализация, т. е. переход от общих задач к частным, которые в свою очередь детализируются в виде конкретных подзадач. Такой метод называется методом пошаговой детализации. Таким образом, при структурном подходе можно комбинировать не только базовые структуры (следование, ветвление, цикл), но и подключать алгоритмы, написанные ранее. Алгоритмы, которые целиком используются в составе других алгоритмов, называются вспомогательными, или подалгоритмами.

Если вспомогательный алгоритм в процессе работы программы выполняется многократно, отличаясь только параметрами, то обычно прибегают к оформлению вспомогательного алгоритма в виде подпрограммы — алгоритма-процедуры, или алгоритма-функции.

Подпрограмма — это именованный, логически законченный алгоритм, который оформляется специальным образом и может многократно использоваться при решении более общей задачи.

Описание подпрограмм можно сравнить с записываемой в математике формулой «в общем виде», в которую при расчетах подставляются конкретные значения. Далеко не каждую задачу можно свести к единственной формуле, но всегда можно записать алгоритм ее решения, а значит, подпрограмма — это инструкция по решению некоторой задачи. Как и формулу, подпрограмму можно использовать для обработки различных данных, передаваемых из главной программы или других подпрограмм.

В языках программирования подпрограмма является частью основной программы, ее описание располагается в описательной части программы. Структура подпрограммы такая же, как и основной программы; различие заключается лишь в оформлении заголовка подпрограммы. Заголовок подпрограммы состоит из служебного слова — идентификатора подпрограммы (имени подалгоритма) — и списка формальных параметров (список параметров не обязателен, допускаются подпрограммы без параметров). При вызове процедуры из текста программы вместо формальных параметров подставляются фактические параметры, при этом соблюдаются следующие правила:

• количество формальных и фактических параметров должно совпадать, причем соответствие между параметрами команды вызова и формальными параметрами процедуры устанавливается по порядку следования: первый фактический параметр соответствует первой переменной, записанной в заголовке подпрограммы, второй фактический параметр — второй переменной и т. д.;
• типы соответствующих параметров команды вызова и заголовка подпрограммы должны совпадать.

Команда вызова подпрограммы выполняется в три этапа:

1. вычисление фактических аргументов;
2. исполнение алгоритма подпрограммы;
3. присвоение полученных значений результатов алгоритма-подпрограммы соответствующим фактическим переменным.

Программа может содержать более одной подпрограммы; допускается использование вложенных подпрограмм, которые, в свою очередь, могут содержать свои вложенные подпрограммы.

Различают два вида подпрограмм — процедуры и функции. Имея один и тот же смысл и аналогичную структуру, процедуры и функции различаются назначением и способом их использования. Основное отличие функций от процедур заключается в том, что результатом выполнения функции является некоторое единственное значение. Функция — это алгоритмически вычисляемое выражение, которое присваивается идентификатору функции.

Подпрограммы бывают двух видов: стандартные и пользовательские. Стандартные, или встроенные, подпрограммы входят в состав языка программирования. Эти подпрограммы определенным образом организованы в специальные библиотеки. С помощью встроенных процедур и функций выполняются операции ввода/вывода, работа с файлами, обработка символьной информации, вычисление различных математических функций и т. п.

Подпрограммы, которые написаны пользователем, называются пользовательскими.

Технология программирования

Чтение короткой (30±50 строк) простой программы на алгоритмическом языке (языке программирования)

Запись алгоритма в словесной форме, в виде блок-схемы или на псевдокоде должна быть точна настолько, чтобы позволить исполнителю правильно выполнить алгоритм, при этом изображение команд произвольное. При решении любой задачи на компьютере предполагается, что некоторая информация подвергается обработке по предварительно составленной инструкции, называемой программой. Язык, на котором записывается алгоритм для исполнения компьютером, называется языком программирования. Языки программирования принадлежат к формальным языкам. При записи алгоритма на языке программирования все правила языка должны строго выполняться. Программа — это алгоритм, записанный на языке программирования.

Для записи программ используется конечный набор символов, составляющих алфавит языка программирования. В отличие от привычных алфавитов (например, русского) алфавит языка программирования включает в себя, кроме букв, цифры, знаки препинания, знаки арифметических действий и некоторые другие дополнительные символы. Программа записывается в виде последовательности символов из алфавита своего языка программирования. Естественно, что не любой текст, составленный из символов алфавита, будет правильной программой. Как и в естественных языках, правильность построения программы из символов алфавита можно проверить, используя синтаксис языка программирования.

Синтаксис языка программирования — это набор правил, которые определяют способы построения правильных программ из символов алфавита. Зная синтаксис языка, можно построить алгоритм, который определяет, является ли данный текст правильной программой или нет. Этот алгоритм позволяет компьютеру проверять синтаксическую правильность вводимых в него программ.

Должна быть определена и семантика языка программирования. Семантика языка программирования — это набор правил, по которым исполнитель выполняет программы на этом языке. Пользуясь семантикой языка, можно однозначно определить результат выполнения программы с заданными входными данными.

При чтении программы необходимо сначала определить, к какому виду она относится. Условно программы можно разделить на два вида: простая программа без использования подпрограмм (кроме стандартных процедур вводавывода) и программа, использующая подпрограммы (подалгоритмы). Такая программа может включать в свою структуру как стандартные подпрограммы, так и подпрограммы, написанные пользователем.

Для чтения простой программы необходимо выяснить:

• что является входными данными и как они вводятся в программу;
• какие действия последовательно выполняются с помощью каждого функционального узла программы (операторов), т. е. рассмотреть пошаговое выполнение операторов, при этом обратить внимание на роль вспомогательных переменных, массивов и т.д.;
• что является результаты работы программы;
• каковы ограничения по работе алгоритма.

При чтении программы, использующей подпрограммы, необходимо сначала проанализировать, что и как выполняют подпрограммы, каковы их входные и выходные параметры. Затем в основной программе вызовы каждой из подпрограмм рассматривать уже как результат работы соответствующего подалгоритма.

Существенно облегчает чтение программ наличие комментариев — поясняющего текста. Комментарии можно добавлять в любое место программы. Наличие комментариев — обязательное условие хорошо и грамотно написанной программы.

Примеры чтения программ на языках Pascal, QBASIC

Примечание. В приведенных примерах программа приводится для двух языков программирования. В зависимости от того, какой язык программирования изучается, и следует рассматривать ее вариант записи и соответствующие пояснения.

Пример 1. Дана программа на двух языках программирования. Определить, какую задачу она решает.

Решение. Проанализируем тексты программы:

1. формируется тело программы и описываются переменные;
2. вводятся натуральные числа М и N, причем проверяется условие корректности ввода: числа должны быть положительные. Если введенные значения не удовлетворяют условию, то ввод повторяют, пока условие не будет выполнено;
3. выбирается наименьшее значение из М и N, результат записывается в K;
4. NOD присваивается значение 1;
5. в цикле от двух до K генерируется число I;
6. тело цикла — в условном операторе проверяется, является ли значение переменной I одновременно делителем М и N. Если условие выполняется, то текущее значение I сохраняется в переменной NOD; если условие не выполняется, NOD не изменит своего значения;
7. после перебора всех значений I в NOD или запишется наибольший делитель двух чисел М и N, или останется значение 1;
8. последний оператор программы служит для вывода результата работы программы — значения переменной NOD.

Переменные, используемые в программе:

N, М — исследуемые числа;

I — переменная цикла;

NOD — наибольший общий делитель;

К — наименьшее из М и N.

Ответ: данная программа позволяет определить для двух чисел М и N их наибольший общий делитель NOD.

Примечание. Эту же задачу можно решить, используя алгоритм Евклида.

Пример 2. Дана программа на двух языках программирования. Определить, какую задачу она решает.

Решение. Проанализируем тексты программы:

1. формируется тело программы, описываются переменные и одномерный массив MAS целого типа (для Pascal целый массив длиной 100);
2. вводится фактическая длина массива N с проверкой на положительное значение N;
3. вводится значение первого элемента массива MAS;
4. устанавливается начальное значение МАХ по первому элементу массива;
5. переменной К присваивается значение 1;
6. последовательно, в цикле, просматриваются вводимые элементы массива, и если очередной элемент MAS(I) больше или равен МАХ, то переписывается значение MAS(I) в МАХ и в переменной К запоминается I;
7. выводятся результаты: МАХ — значение максимального элемента массива и К — номер максимального элемента в исходном массиве (если таких элементов несколько, выведется номер самого правого максимума).

Переменные, используемые в программе:

MAS — массив чисел;

N — размер массива;

I — переменная цикла;

МАХ — значение наибольшего элемента;

К — номер наибольшего элемента.

Ответ: программа написана для поиска значения максимального элемента массива и его номера (если таких элементов несколько, то будет найден номер самого правого максимума).

Пример 3. Дана программа на двух языках программирования. Определить, какую задачу она решает.

Решение. Проанализируем тексты программы:

1. формируется тело программы и описываются переменные;
2. вводится строка символов S;
3. определяется длина строки, значение которой заносится в переменную L;
4. в цикле осуществляется замена ‘!’ на ‘.’ в исходной строке;
5. выводится преобразованная строка.

Переменные, используемые в программе:

I — переменная цикла;

L — длина строки;

S — строка текста.

В программе на языке Pascal используется встроенная функция языка:

Length(STR) — она определяет фактическую длину строки STR (длина строки не более 256 символов).

В программе на языке QBASIC используются встроенные функции:

Len(X) — определяет фактическую длину строки X (длина строки не более 256 символов);

M1D$(X$, N, M) — выделяет M символов, начиная с N-го символа в символьном выражении X$ (M можно опустить).

Ответ: данная программа позволяет заменить во введенной строке символов все восклицательные знаки на точки.

Пример 4. Дана программа на двух языках программирования. Определить, какую задачу она решает.

Решение. Проанализируем текст программы на языке Pascal:

1. формируется тело программы и описываются переменные;
2. вводится строка STR и дублируется во вспомогательной переменной S1;
3. определяется местоположение первой точки в тексте; если точка есть, то из S1 вырезается текст до нее;
4. ищется вторая точка; если она есть, то из S1 вырезается текст после нее;
5. в зависимости от присутствия точек результат выводится на экран.

Используемые переменные:

I — номер позиции, которая соответствует точке;

STR — строка текста;

S1 — вспомогательная переменная.

В данной программе используются встроенные функции языка Pascal:

Pos(S1, S2) — поиск подстроки S1 в строке S2 ;

Delete(S, N, M) — удаление из строки S M символов, начиная с позиции N;

Copy(S, N, M) — выделение подстроки из M символов, которые располагаются в строке S начиная с позиции N.

Проанализируем текст программы на языке QBASIC:

1. формируется тело программы, и описываются переменные;
2. вводится строка символов S;
3. определяется местоположение первой точки в тексте — М1;
4. ищется вторая точка в строке (поиск начинается с символа М1 + 1); если в строке есть две точки, то на экран выводится текст, находящийся между двумя точками, если нет — сообщение «В тексте нет двух точек».

Используемые переменные:

S — строка текста;

Ml, M2 — номера позиций двух точек; если точек нет, то значения Ml и М2 равны нулю.

В данной программе используются встроенные функции языка:

INSTR(N, X$, Y$) — поиск подстроки Y в строке X, начиная с N-го символа (N можно опустить);

MID$(X$, N, M) — выделение M символов, начиная с N-го символа в символьном выражении X$ (M можно опустить).

Ответ: данная программа из заданной строки символов выделяет подстроку между первой и второй точкой.

Пример 5. Проанализировать тексты программы.

Решение.

1. Формируется тело программы и описываются переменные и двумерный массив MАS;
2. вводится фактический размер массива MAS и значения его элементов;
3. просматриваются строки массива справа налево, находиться минимальный элемент в строке и запоминаются значения индексов (номер столбца) этого элемента;
4. для каждой строки выводится значение и местоположение самого правого минимального элемента.

Используемые переменные:

MAS — двумерный массив;

N, M — количество строк и столбцов массива;

I, J — переменные цикла;

JM — столбец минимального элемента для данной строки;

MIN — текущий минимум.

Ответ: программа решает задачу поиска в каждой строке двумерной матрицы минимального элемента и его координат. Если таких элементов в строке несколько, то выводится значение и координаты самого правого элемента.

Поиск и исправление ошибок в небольшом фрагменте программы (10±20 строк)

Существует три аспекта проверки программы:

1. на правильность;
2. на эффективность реализации;
3. на вычислительную сложность.

Эти проверки, вместе взятые, направлены на получение экспериментального ответа на вопросы: работает ли алгоритм и насколько хорошо он работает? Предполагается, что проверка правильности удостоверяет, что программа делает в точности то, для чего она была предназначена. Проверка эффективности реализации направлена на поиск способов «заставить» правильную программу работать быстрее или расходовать меньше памяти. Чтобы улучшить программу, пересматриваются результаты этапа реализации в процессе построения алгоритма.

Проверка вычислительной сложности сводится к экспериментальному анализу сложности алгоритма или к экспериментальному сравнению двух или более алгоритмов, решающих одну и ту же задачу.

Наличие ошибок в только что разработанной программе — вполне нормальное, закономерное явление. Составить реальную (достаточно сложную) программу без ошибок практически невозможно. Нельзя делать вывод, что программа правильна, лишь на том основании, что она считает и выдает результаты.

Текст программы можно проконтролировать за столом с помощью просмотра, проверки и прокрутки.

Просмотр. Текст программы просматривается на предмет обнаружения явных ошибок и расхождений с алгоритмом. Нужно просмотреть организацию всех циклов, чтобы убедиться в правильности операторов, задающих кратности циклов. Полезно просмотреть еще раз условия в условных операторах, аргументы в обращениях к подпрограммам и т. п.

Проверка. При проверке программы программист по тексту программы мысленно старается восстановить тот вычислительный процесс, который определяет программа, после чего сверяет его с требуемым алгоритмом.

Прокрутка. Основой прокрутки является имитация программистом за столом выполнения программы на машине. Для выполнения прокрутки приходится задаваться какими-то исходными данными и производить над ними необходимые вычисления.

Прокрутка — трудоемкий процесс, поэтому ее следует применять только для контроля логически сложных участков программы.

После просмотра программы вручную ее необходимо отладить и протестировать на компьютере.

Отладка — это процесс поиска и устранения ошибок в программе, производимый по результатам ее прогона на компьютере.

Тестирование — это испытание, проверка правильности работы программы в целом или ее составных частей.

Отладка и тестирование — два разных этапа:

• при отладке происходит локализация и устранение синтаксических ошибок и явных ошибок кодирования;
• в процессе тестирования проверяется работоспособность программы, не содержащей явных ошибок. Тестирование устанавливает факт наличия ошибок, а отладка выясняет их причину.

Как бы тщательно ни была отлажена программа, решающим этапом, устанавливающим ее пригодность для работы, является контроль программы по результатам ее выполнения на системе тестов. Программу условно можно считать правильной, если ее запуск для выбранной системы тестовых исходных данных во всех случаях дает правильные результаты.

Тестовые данные должны обеспечить проверку всех возможных условий возникновения ошибок. Процесс тестирования можно разделить на три этапа:

1. Проверка в нормальных условиях. Предполагает тестирование на основе данных, которые характерны для реальных условий функционирования программы.
2. Проверка в экстремальных условиях. Тестовые данные включают граничные значения области изменения входных переменных, которые должны восприниматься программой как правильные данные. Типичными примерами таких значений являются очень маленькие или очень большие числа и отсутствие данных. Еще один тип экстремальных условий — граничные объемы данных. Например, когда массивы состоят из слишком малого или слишком большого количества элементов.
3. Проверка в исключительных ситуациях. Проводится с использованием данных, значения которых лежат за пределами допустимой области изменений.

Ошибки могут быть допущены на всех этапах решения задачи. Разновидности характерных ошибок:

• Неправильная постановка задачи — верное решение неверно сформулированной задачи.
• Неверный алгоритм — выбор алгоритма, приводящего к неточному, неэффективному решению задачи.
• Ошибки анализа — неполный учет ситуаций, которые могут возникнуть; логические ошибки.
• Семантические ошибки — неправильный порядок выполнения операций.
• Синтаксические ошибки — нарушение правил, определяемых языком программирования.
• Ошибки при выполнении операций — слишком большое число (переполнение), деление на нуль, извлечение квадратного корня из отрицательного числа и т. п.
• Ошибки в данных — неправильное определение возможного диапазона изменения данных.
• Опечатки — перепутаны близкие по написанию символы, например цифра 1 и буква I.
• Ошибки ввода/вывода — неверное считывание входных данных, неверное задание форматов, отсутствие некоторых данных.

В качестве примера рассмотрим программу, в которой вычисляется значение функции по приведенным формулам в зависимости от значения параметра K, который является номером режима.

$y(x)={table√{a_1x^2+b_1x+c_1}, text»если» K=1; √{a_2x^2+c_2}, text»если» K=2; √{b_3x+c_3}, text»если» K=3;$

Программа имеет вид

Ошибки, допущенные при написании программы:

1. Пропущен ввод исходных данных А1, B1, C1, A2, C2, B3, C3; пропущено описание переменной Y (для языка Pascal).
2. В приведенной программе не предусмотрена обработка ситуации, когда под корнем получается отрицательное значение. Необходимо использовать условный оператор для определения положительности подкоренного выражения.
3. Отсутствует анализ ситуации, когда вместо цифр 1, 2, 3 для переменной К считана другая цифра. В этом случае, можно выдавать, например, сообщение: «Номер режима неверен». Для выдачи такого сообщения в программе в саsе-операторе после строки с меткой 3 нужно добавить строку вида else <Печать сообщения> (вариант 1). Можно также организовать ввод параметра K с проверкой введенного значения, и при ошибочном вводе требовать повторения ввода значения для переменной K (вариант 2).

Пример откорректированной программы (вариант 1).

Пример откорректированной программы (вариант 2).

Создание собственной программы (30±50 строк) для решения простых задач

Процесс создания компьютерной модели можно представить как путь от постановки задачи до реализации модели на компьютере. При разработке компьютерной модели очень важен выбор программного обеспечения (ПО), с помощью которого будет реализована модель. Возможны два основных варианта выбора — это, во-первых, прикладное ПО и, во-вторых, среда программирования. Если в качестве ПО была выбрана среда программирования, то построение компьютерной модели завершается созданием программы.

При написании программы прежде всего следует четко уяснить задачу, которую должна решать программа. Затем предварительно разработанный алгоритм решения задачи записывается в виде упорядоченной последовательности команд (инструкций), т. е. составляется программа, ориентированная на определенную среду программирования.

При написании программы обязательно следует проверять, насколько она соответствует намеченной цели, т. е. делает ли программа для всех наборов данных то, что от нее требуется, не выполняет ли она каких-либо лишних действий. Основное внимание следует сосредоточить на предотвращении логических ошибок. Для этого рекомендуется перед написанием программы построить блок-схему алгоритма решения или словесный алгоритм, что позволит абстрагироваться от конкретного языка программирования и сосредоточиться на анализе алгоритма.

Примеры разработки программ

Пример 1. Составить словесный алгоритм, разработать блок-схему и написать программу проверки принадлежности введенного числа данной арифметической прогрессии. Прогрессия задается двумя последовательными членами.

Решение. Словесный алгоритм.

Начало алгоритма

1. Ввести два последовательных члена арифметической прогрессии: A1, A2.
2. Ввести произвольное целое число C.
3. Найти разность (D) арифметической прогрессии.
4. Найти разность между введенным числом C и членом арифметической прогрессии, например A1.
5. Найти остаток от деления нацело найденной разности на D.
6. Если остаток от деления равен 0, то это значит, что число C принадлежит рассматриваемой арифметической прогрессии»; иначе получаем, что число C не принадлежит рассматриваемой арифметической прогрессии.

Конец алгоритма.

Блок-схема алгоритма:

Программа:

Примечание. Mod — операция, результатом которой является остаток от целочисленного деления.

Пример 2. Составить словесный алгоритм, алгоритм в виде блок-схемы и написать программу поиска в строковом массиве, содержащем фамилии 10 учеников, заданной фамилии, обеспечить запоминание ее порядкового номера (массив фамилий может быть неупорядочен).

Решение.

Словесный алгоритм

Начало алгоритма

1. Ввести все десять фамилий (строковый массив из 10 элементов).
2. Ввести фамилию, которую нужно найти.
3. Сравнивать ее с очередным элементом строкового массива, пока не будет найдена такая же фамилия или пока не закончится список (массив).
4. Если фамилия найдена, вывести ее номер в списке (массиве), если нет — сообщить о том, что фамилия не найдена.

Конец алгоритма.

Блок-схема алгоритма

Программа: