Программирование на языке высокого уровня

Подождите немного. Документ загружается.

Строка — это пример массива из символов. Например:

z = ‘предмет’; z[1]=’п’; z[2] = ‘р’; z[3] = ‘е’.

Если массив подобен строке, то данные, собранные в таб-

лицы, называются матрицами. Например: S =

167

423

169

éù

êú

ëû

. Ана-

логично массиву каждый элемент матрицы имеет свое опреде-

ленное место в таблице, которое определяется двумя индексами:

первый определяет номер строки, в которой находится элемент,

второй определяет номер столбца, в котором находится элемент.

Например, S

2,3

= 3 или S[3,1] = 1.

1.2 Основные конструкции структурного

программирования

Структурное программирование — метод разработки про-

грамм, предполагающий широкое использование абстрагирова-

ния с целью выделения составных частей проблемы и повыше-

ния уверенности в правильности конечной программы. В струк-

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

конструкции. Эти конструкции допускают последовательную,

условную и итеративную передачи управления. Как следствие

применения этих конструкций каждая сложная команда в про-

грамме имеет ровно одну точку входа и ровно одну точку выхо-

да. А это, в свою очередь, облегчает восприятие программы.

Конструкции, описанные в этом разделе, встречаются в ре-

альном мире. Например, запишем в виде алгоритма режим дня:

7.00–7.30 — подъем, водные процедуры.

7.30–7.50 — завтрак

12.00–12.40 — обед

15.00–15.10 — полдник

19.00–19.20 — ужин

23.00 — сон

Действия, ранее описанные, выполняются последовательно,

и их описывает такая конструкция, как следование — выполне-

ние действий алгоритма последовательно, одно за другим.

Следующая конструкция так же взята из реальной жизни —

прежде чем выйти из дома, разумный человек узнает, какая на

улице погода. Рассмотрим упрощенный вариант: если на улице

дождь, нужно одеть плащ и взять зонтик, иначе, все это можно

оставить дома. Такая ситуация описывается конструкцией раз-

вилка — ЕСЛИ условие ТО действия при истинном условии

ИНАЧЕ действия при ложном условии.

Последняя конструкция называется циклом. Например,

циклом может быть описана следующая ситуация — выбрать из

колоды карт все карты заданного номинала. Просматривая одну

за другой карты колоды, поочередно выбирают карты нужного

номинала.

Конструкций циклов несколько:

· цикл с фиксированным числом операций (при известном

количестве повторений);

· цикл по условию — повторения выполняются до тех пор,

пока истинно (или ложно) условие цикла.

Эти три конструкции являются основными и единственны-

ми в структурной алгоритмизации. С помощью этих конструк-

ций может быть записан любой алгоритм.

1.3 Системы кодирования алгоритмов

1.3.1 Система псевдокод

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

каждое отдельное действие выполняется на отдельной строке.

Пример 1. Даны два катета прямоугольного треугольника

k1 = 3, k2 = 4. Найти гипотенузу. Записать решение задачи на

псевдокоде.

13,24

//Задать константы

// Вычислить квадрат

и запомнить в переменной

2:2

// Вычислить квадрат

и запомнить в переменной

g zz

=+ //Вычислить гипотенузу и запомнить в переменной

Вернуть полученное значение

Текст, выделенный курсивом, называется комментарием,

пояснением к выполняемым действиям. Если в решаемой задаче

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

го рода называются вычислительными алгоритмами), то по-

следним, завершающим действием алгоритма будет возвраще-

ние полученного значения.

Развилка в системе псевдокода записывается с помощью

выражения

ЕСЛИ ТО ИНАЧЕ

Пример 2. Даны два произвольных числа. Найти макси-

мальное из них.

Задать числа

ЕСЛИ

ТО

ЕСЛИ

ТО вернуть «

– максимальное число»

ИНАЧЕ вернуть «

– максимальное число»

КОНЕЦ ЕСЛИ

ИНАЧЕ вернуть «числа равны»

КОНЕЦ ЕСЛИ

Указание в алгоритме конца развилки поможет сделать за-

пись более наглядной.

Цикл с конечным числом операций в псевдокоде выглядит

следующим образом:

ЦИКЛ (счетчик действий)

Действия

КОНЕЦ ЦИКЛ

Пример 3. Дана строка символов x длины n. Найти количе-

ство вхождений символа y в строку x.

Задать

// в строке

не найдено еще ни одного символа.

ЦИКЛ (

= ) // если в цикле не указан шаг изменения переменной, то по

// умолчанию он считается равным 1. Таким образом,

// переменная

принимает значения 1,2,3, …

ЕСЛИ

[

]

xjy

ТО

// если текущий

-тый символ строки

// равен

, то увеличить текущее

// значение переменной

на 1.

КОНЕЦ ЕСЛИ

КОНЕЦ ЦИКЛ

Вернуть

Пример 4. Найти количество символов произвольной стро-

ки x до первой встреченной точки.

Задать

;

; // начинаем просмотр строки с первого символа

; //считаем количество символов равным нулю

ПОКА

[

]

'.'

длины строки // пока не встречена точка и не найден

// конец строки

; // увеличиваем счетчик найденных символов

: 1;

// увеличиваем счетчик длины строки

КОНЕЦ ЦИКЛА

ЕСЛИ

длине строки ТО вернуть «Точки в данной строке нет»

ИНАЧЕ вернуть «Длина строки до точки равна

ВСЕ ЕСЛИ

В рассмотренном примере в цикле использовалось сложное

условие — два условия, связанные союзом И. Такое условие

считается истинным только тогда, когда истинны оба условия. В

сложных условиях может так же использоваться союз ИЛИ —

такое условие считается ложным только тогда, когда ложны оба

условия.

1.3.2 Блок-диаграммы

Алгоритм можно задать, используя схему, которая носит

название блок-диаграммы.

Основные конструкции структурного программирования в

блок-диаграмме обозначаются следующим образом:

Следование — Внутри прямоугольников описываются

выполняемые действия.

Условие — Внутри ромба описывается условие.

…

Да Нет

Цикл в блок-диаграммах описывается через условие.

Пример 5. Дана строка символов S. Заменить все вхождения

символа «1» на «0», а «0» на «1».

Задать строку

:= длина

Да

Нет

[ ] '0'

Нет

[ ]: '1'

[ ] '1'

[ ]: '0'

Вернуть

Нет

Да Да

В рассмотренном примере использовались следующие кон-

струкции:

· следование — действия «Задать строку», «Переменной

присвоить длину строки», «переменной

присвоить значе-

ние 1» выполняются последовательно;

· развилка — «Если

[]

равен

'0'

, то заменить этот сим-

вол на

'1'

, иначе, если

[]

равен

'1'

, то заменить его на

'0'

»;

· цикл с фиксированным числом операций — «от 1 и до

проверить все символы строки».

1.3.3 Диаграммы Насси-Шнайдермана

Основные конструкции структурного программирования в

диаграмме Насси-Шнайдермана обозначаются следующим об-

разом:

Следование —

Развилка —

Цикл —

Действие 1

Действие 2

Условие

Да Нет

Действия

при

истинном

условии

Действия

при

ложном

усл

вии

Условие выполнения цикла

Действия в цикле

Пример 6. Дано число натуральное число n <10. Вывести на

экран грамматически верную фразу (n лет — 1 год, 2 года, 10

лет и т.д.).

Задать

Да Нет

Вернуть

год»

Да Нет

Вернуть

года»

Вернуть

лет»

1.4 Основные алгоритмы

1.4.1 Алгоритмы суммы и произведения

Условие: найти сумму чисел от заданного числа N1 до за-

данного числа N2 с шагом 1.

Алгоритм.

Положим начальное значение суммы равное нулю —

;

ЦИКЛ (

2;1: NNi = )

iSS

КОНЕЦ ЦИКЛА

Вернуть

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

ней постепенно накапливалась вся сумма.

Условие: найти произведение чисел от заданного N1 до за-

данного числа N2 с шагом 1.

Алгоритм.

Положим начальное значение произведения равное единице —

;

ЦИКЛ(

: 1;2

i NN

= )

P Pi

КОНЕЦ ЦИКЛА

Вернуть

В данном примере роль накопителя сыграла переменная

В ней на каждом шаге цикла накапливалось произведение.

1.4.2 Алгоритмы поиска

Алгоритм поиска элемента с заданным значением

Условие: найти элемент с заданным значением a в массиве

X размерности n.

Схема поиска будет следующей: просмотрим все элементы

массива X[i] и сравним их значения с заданным значением a.

Если просматриваемое значение X[i] равно a, то вернем в каче-

стве результата индекс найденного элемента. Предусмотрим

ситуацию промаха при поиске — в массиве нет элементов с за-

данным значением. Для разрешения этой проблемы введем в

алгоритм флаговую переменную f, которой в начале решения

присвоим значение нуля. Если при просмотре массива найдено

заданное значение, то присвоим переменной f значение едини-

цы. После работы цикла останется только проверить значение

флаговой переменной.

Алгоритм:

Задать массив

из

элементов;

Задать

;

Задать 0:=f ;

ЦИКЛ (

: 1,

= )

ЕСЛИ []

xia

ТО вернуть

;

КОНЕЦ ЦИКЛА

ЕСЛИ

ТО вернуть «В массиве нет элементов с заданным значением»

Алгоритмы поиска максимума и минимума в массиве.

Условие: найти минимальный элемент в массиве.

Схема поиска может быть следующей: положим за мини-

мальный элемент первый элемент массива. Начнем просматри-

вать массив со второго элемента и до последнего. Если текущее

значение минимума стало больше просматриваемого элемента

массива, то заменим текущее значение минимума на значение

просматриваемого элемента массива.

Алгоритм:

Задать массив

из

элементов;

Минимуму присвоить значение

[1]

–

min [1]

= ;

ЦИКЛ (

: 2;

= )

ЕСЛИ

[ ] min

Xi< ТО

min : [ ]

КОНЕЦ ЦИКЛА

Вернуть

min

;

Используя эту же схему, попытайтесь самостоятельно

записать алгоритм нахождения максимального элемента в

массиве.

1.5 Пример решения задания для

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

Записать следующие алгоритмы:

· дана матрица A[nxm], найти максимальные элементы

всех столбцов матрицы. Для записи алгоритма использовать

систему кодирования псевдокод;

· дана произвольная строка символов S. Найти количество

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

ограниченная пробелами и не имеющая пробелов внутри себя.

Для записи алгоритма использовать блок-диаграмму;

· сформировать массив X из n элементов по следующему

правилу — X[i+1]=X[i]+2; i изменяется от 1 до n – 1; X[1] = 15.

Для записи алгоритма использовать диаграмму Насси-

Шнайдермана.

Решение.

Схема решения первой задачи будет следующей: зафикси-

руем номер столбца j=1, положим за максимальный элемент

A[1][j] — т.е. элемент, лежащий в первой строке столбца j. Да-

лее начнем просматривать элементы столбца j, начиная со вто-

рого элемента. Если в процессе поиска найдено значение матри-

цы, превышающее значение максимума, то заменим текущий

максимум на найденное значение. После того, как весь столбец j

будет просмотрен, вернем в качестве результата найденное зна-

чение максимума. Таким образом, будет найден максимальный

элемент в столбце 1. Повторим описанный алгоритм для

j:=2,3,…,m . Запишем решение на псевдокоде:

Задать

— количество строк,

— количество столбцов.

Задать элементы матрицы ][

ЦИКЛ ( mj ;1:= )

]][1[:max

;

ЦИКЛ(

ni ;2:= )

ЕСЛИ ]][[max

ТО ]][[:max

КОНЕЦ ЦИКЛА

Вернуть «В столбце»

«максимальное значение»

max

;

КОНЕЦ ЦИКЛА

Для второй задачи можно предложить следующую схему

решения: так как не оговорено, что между словами строки ровно

один пробел, то между словами может быть и группа пробелов.

Для подсчета слов используем переменную-счетчик k. Начнем

просматривать строку с первого символа, если первый символ

не пробел, то в строке уже найдено первое слово, увеличим зна-

чение переменной k на единицу. Далее циклически просматри-

ваем строку и ищем сочетания: i-тый символ равен пробелу, а

i+1-ый символ не равен пробелу, фиксируем начало каждого

слова строки и увеличиваем в этом случае счетчик слов k на

единицу. Просмотр заканчивается при достижении переменной i

значения n – 1, где n — длина строки. Блок-диаграмма описан-

ного алгоритма представлена на рис. 1.2.