Тема № 4 (стр. 1 )

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

Что нужно знать.

Блок-схема — графический способ описания алгоритма с использованием геометрических фигур.

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

Линейный алгоритм

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

Разветвляющийся алгоритм

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

Если условие выполнено, то для решения задачи используется ветвь да, в противном случае — ветвь нет.

Циклический алгоритм

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

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

Параметр цикла — величина, от которой зависит число повторений в цикле.

Цикл со счетчиком

Цикл с предусловием

Цикл с постусловием

Операция присваивания

Операция присваивания в блок-схемах, а также на языках Паскаль и Алгоритмический выглядит как :=, а на Бейсике записывается просто знаком равенства в форме:

Имя переменной = выражение.

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

Например, K:=1 означает, что число 1 запишется в ячейку с именем K.

В случае когда запись выглядит как K:=K+1, сначала вы­числяется выражение, находящееся справа от знака равенст­ва с последним имеющимся значением K, а потом итоговый результат присваивается переменной К, стирая предыдущее значение.

Операции div и mod

Операция \ (div) вычисляет результат деления нацело пер­вого аргумента на второй, то есть:

7\5=1                14 div 5=2

Операция MOD (mod) вычисляет остаток от деления пер­вого аргумента на второй, то есть:

7 MOD 5=2                14 mod 5=4

Операции \ и MOD (Бейсик), div и mod (Паскаль и Алго­ритмический), — операции, вычисляющие результат деле­ния нацело первого аргумента на второй и остаток от деления соответственно.

Работа с массивами

Массив — упорядоченный набор данных, обозначаемый одним именем.

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

Типы обрабатываемых данных

В основном массивы обрабатывают числовые (содержа­щие числа) и строковые (содержащие текст и символы) дан­ные.

Одномерный массив

Например: А[10] — одномерный массив, содержащий 10 ячеек, где [i] — указывает на номер ячейки. Например, содер­жимое ячейки A[5] будет равно 2.

Двумерный массив

Такой массив можно представить в виде квадратной та­блицы, в которой для элемента массива А[i, j] величина i яв­ляется номером строки, а величина j — номером столбца, в котором расположен элемент.

Например, содержимое ячейки A[5,6] будет равно 1.

Двумерный массив, так как происходит работа вло­женных циклов, заполняется по строкам, то есть сначала последовательно заполняются ячейки первой строки (от A[1,1] до A[1,j]), потом второй (от A[2,1] до A[2,j]) и т. д. Считывание данных происходит в той же последователь­ности.

Основные функции

Примеры заданий.

Пример 1.

Определите значение переменной c после выполнения следующего фрагмента программы.

a := 5;

a := a + 6;

b := –a;

c := a – 2*b;

1)  -5        2) 17        3) 33        4) -11

Решение:

для решения нужно использовать «ручную прокрутку» программы, то есть, выполнить вручную все действия наиболее удобно и наглядно это получается при использовании таблицы, где в первом столбце записаны операторы программы, а в остальных показаны изменения переменных при выполнении этих операторов здесь используются три переменные: a, b, c; до выполнения программы их значения нам неизвестны, поэтому ставим в  таблице знаки вопроса:

a	b	c
?	?	?

после выполнения оператора a := 5; изменяется значение переменной a:

a	b	c
?	?	?
a := 5;	5

оператор a := a + 6; означает «вычислить значение выражения a + 6 используя текущее значение a (равное 5), и записать результат обратно в переменную a»; таким образом, новое значение  равно 5 + 6 = 11:

a	b	c
?	?	?
a := 5;	5
a := a + 6;	11

следующий оператор, b := - a; изменяет значение переменной b, записывая в нее –a; учитывая, что в a записано число 11, находим, что b будет равно –11:

a	b	c
?	?	?
a := 5;	5
a := a + 6;	11
b := –a;	–11

последняя команда, c := a – 2*b, изменяет значение переменной c; при текущих значениях  a = 11 и b = –11 результат выражения  равен 11 – 2*(–11) = 33, это число и будет записано в переменную c:

a	b	c
?	?	?
a := 5;	5
a := a + 6;	11
b := –a;	–11
c := a – 2*b;	33

таким образом, правильный ответ 3.

Пример 2.

Определите значение целочисленных переменных a и b после выполнения фрагмента программы:

a := 3 + 8*4;

b := (a div 10) + 14;

a := (b mod 10) + 2;

1) a=35; b=49  2)  a=3; b=19 

3)  a=7; b=19        4) a=9; b=17

Решение:

для решения нужно использовать «ручную прокрутку» программы, то есть, выполнить вручную все действия наиболее удобно и наглядно это получается при использовании таблицы, где в первом столбце записаны операторы программы, а в остальных показаны изменения переменных при выполнении этих операторов здесь используются три переменные: a, b, c; до выполнения программы их значения нам неизвестны, поэтому ставим в  таблице знаки вопроса:

a	b
?	?

после выполнения оператора a := 3 + 8*4;изменяется значение переменной a:

a	b
?	?
a := 3 + 8*4;	35

оператор b := (a div 10) + 14;означает «вычислить сумму результата целочисленного  деления числа a  на 10 и числа 14. Результат записать в переменную b»; таким образом, новое значение b равно 3 + 14 = 17:

a	b
?	?
a := 3 + 8*4;	35
b := (a div 10) + 14;	17

следующий оператор, a := (b mod 10) + 2; «вычислить сумму остатка от  деления числа b  на 10 и числа 2. Результат записать в переменную a»; таким образом, новое значение  a равно 7 + 2 = 9:

a	b
?	?
a := 3 + 8*4;	35
b := (a div 10) + 14;	17
a := (b mod 10) + 2;	9

таким образом, правильный ответ 4.

Пример 3.

Дан фрагмент программы, обрабатывающей двухмерный массив A размера nЧn.