Запись алгоритмов на языках программирования

§ 7. Запись алгоритмов на языках программирования

Информатика. 11 класса. Босова Л.Л. Оглавление

Язык программирования

Язык программирования — формальная знаковая система, предназначенная для записи компьютерных программ.

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

В основной школе вы познакомились со школьным алгоритмическим языком КуМир и языком программирования Pascal (Паскаль). В 11 классе мы продолжим работать с языком Pascal.

Желательно установить среду программирования на ваш домашний компьютер.

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

Запись алгоритмов на языках программирования

7.1. Структурная организация данных

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

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

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

Различают простые и сложные структуры данных.

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

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

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

Некоторые простые типы данных языка Pascal приведены на рис. 2.10.

Рис. 2.10. Некоторые простые типы данных языка Pascal

7.2. Некоторые сведения о языке программирования Pascal

Основными элементами языка Pascal являются:

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

Все величины имеют имена (идентификаторы), формируемые по определённым правилам:

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

Таблица 2.2

Операции в языке Pascal

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

Таблица 2.3

Приоритет операций в языке Pascal

Программа на языке Pascal имеет следующую структуру:

Обязательными в ней являются два раздела: описания данных и описания действий, которые над этими данными необходимо выполнить.

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

Блок описания действий начинается со слова begin, а заканчивается словом end и знаком точки. Действия представляются операторами (табл. 2.4). Операторы языка Pascal разделяются точкой с запятой. Операторы бывают простые и составные (заключённые в операторные скобки begin … end).

Таблица 2.4

Основные операторы языка Pascal

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

Самый простой путь решения этой задачи — проверить, имеет ли данное число n (n >= 2) делители в интервале [2; n — 1].

Если делители есть, число n — составное, если — нет, то — простое.

В программе будем использовать логическую переменную flag:

• если flag = true, то n — простое число;
• если flag = false, то n — составное число (если у числа n есть делители, то «флаг выключаем» с помощью оператора присваивания flag := false).

В этой программе мы проверяли, нет ли у числа n делителей из интервала [2; n — 1]. Но если п = а • Ь, то меньшее из чисел а, b не больше

(в противном случае оба числа были бы больше

, а следовательно, их произведение было бы больше n). Кроме того, из делимости числа n на а автоматически следует, что n делится и на n/а.

Усовершенствуйте приведённую выше программу с учётом этих соображений.

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

Пример 2. Применим метод перебора для поиска наибольшего общего делителя (НОД) двух натуральных чисел а и b.

Начнём перебор с d — наименьшего из чисел а и Ь. Это первый, очевидный кандидат на роль их наибольшего общего делителя. И далее, пока не найдём d, на которое оба числа делятся нацело, будем уменьшать его на единицу. Как только такое деление произойдёт, останавливаем уменьшение d. Полученное значение d и будет наибольшим общим делителем чисел а и Ь.

7.3. Анализ программ с помощью трассировочных таблиц.

Пример 3

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

Используются трассировочные таблицы двух видов:

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

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

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

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

Из таблицы видно, что в результате работы переменные приняли значения: а = 2 и b = 4.

Пример 4. Определим значение переменной s, полученное в результате выполнения следующей программы:

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

Будем считать, что контрольная точка (КТ) поставлена на строке s := s + d.

Итак, в результате работы программы переменная приняла значение s = 60.

Каким должно быть значение d, чтобы в результате работы программы переменная приняла значение s = 186? Существует ли такое значение d, что в результате работы программы переменная примет значение s = 212?

Пример 5. Определим значение переменной s, полученное в результате выполнения следующей программы:

Трассировочная таблица может иметь вид:

Пример 6. Выясним, для чего предназначена следующая программа:

Прежде всего, обратим внимание на то, что в ней кроме переменной п целого типа используется строка nd, для которой символ « + » обозначает операцию сцепления строк. Начальное значение n вводится с клавиатуры, поэтому зададим его по своему усмотрению, например n = 12.

Выполните программу для n = 25. Какую задачу, по вашему мнению, решает эта программа?

Функциональный подход к анализу программ

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

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

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

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

Трассировка алгоритма

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

Прочерк в таблице обозначает неопределенное значение переменной. Конечные значения, которые получают переменные а и b, соответственно равны 2 и 4.

Этот пример иллюстрирует три основных свойства присваивания. Вот эти свойства:

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

7.4. Другие приёмы анализа программ.

Пример 7

Трассировочная таблица — наглядный, но не универсальный инструмент анализа программ. Например, её затруднительно строить, если в алгоритме много шагов.

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

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

1. Выясним, какую функцию выполняет каждая из переменных, задействованных в программе. Начальное значение переменной s = 400. При каждом выполнении тела цикла к значению s прибавляется число 12. Начальное значение переменной n = 0. При каждом выполнении тела цикла значение переменной увеличивается на 2: n — 2, если тело цикла выполнено 1 раз; n = 4 — если 2 раза; n = 6 — если 3 раза и т. д. Таким образом, искомое значение n — это 2 • k, где k — число выполнений тела цикла.

2. Выясним, при каком условии произойдёт выход из цикла. Цикл выполняется, пока s < 2992. Следовательно, цикл завершится при достижении s значения, равного или большего 2992.

3. Выясним, сколько раз выполнится тело цикла, вычислив значение выражения: (2992 — 400)/12 = 216. После того как тело цикла выполнится 216 раз, значение переменной s будет равно 2992, что является условием выхода из цикла. При этом n = 2 • 216 = 432.

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

1) s < 2990;

2) s <= 2992;

3) s <= 300.

Пример 8. Получив на вход некоторое натуральное число х, эта программа выводит два числа — m и n.

Известно, что при некотором значении х были выведены числа 5 и 25. Выясним, сколько существует разных значений х, при вводе которых может быть получен такой результат.

Выясним, какие именно данные накапливаются в переменных.

Начальное значение переменной х задаётся пользователем. Тип этой переменной integer, следовательно, она не может превышать 32 767. В цикле значение переменной х изменяется по правилу, заданному командой:

х:=х div 10

При таком преобразовании значение переменной х уменьшается в 10 раз и дробная часть результата отбрасывается. Можно сказать, что при каждом выполнении тела цикла от значения переменной х «отсекается» одна цифра справа.

Начальное значение переменной m = 0. При каждом выполнении цикла значение переменной m увеличивается на единицу. Можно сказать, что в m подсчитывается количество цифр, «отсечённых» от х.

Начальное значение переменной n = 1. В цикле значение переменной n изменяется по правилу, заданному командой:

n: =n*(х mod 10)

Здесь х mod 10 — не что иное, как последняя цифра числа х. Таким образом, в переменной n накапливается произведение цифр числа х, взятых справа налево.

Выход из цикла осуществляется при х <= 0, т. е. когда все значащие цифры этого числа будут рассмотрены.

Следовательно, если на экран первой выводится цифра 5, то исходное число пятизначное. Второе число указывает на то, что 25 — это произведение всех цифр исходного числа х.

Рассмотрим варианты пятизначных чисел, произведение цифр которых равно 25. Например, 11551, 51151 и т. д. Очевидно, в записи любого из таких чисел должны быть две пятёрки и три единицы. Применение известной вам формулы из комбинаторики позволяет вычислить количество разных чисел, удовлетворяющих такому условию, — это 10.

О какой формуле идёт речь? Приведите эту формулу и выполните соответствующие вычисления.

Укажите наибольшее и наименьшее числа, удовлетворяющие условию задачи.

Выпишите все числа, удовлетворяющие условию задачи.

САМОЕ ГЛАВНОЕ

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

В основной школе вы познакомились со школьным алгоритмическим языком КуМир и языком программирования Pascal (Паскаль). В 11 классе мы продолжаем работать с языком Pascal.

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

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

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

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