Занятие 5. Алгоритмическая конструкция следование
Алгоритм — это предписание исполнителю, состоящение из понятных для него команд, выполнение которого должно привести к решению определённой задачи. Таким образом, алгоритмы, как и программы, состоят из команд, и вообще оба эти понятия настолько похожи, что иногда используются как синонимы. Однако алгоритм — это прежде всего описание способа решения задачи в понятной для исполнителя форме, а программа — это запись алгоритма в виде, пригодном для непосредственного выполнения.
Например, для исполнителя, который умеет прыгать, шагать и поворачиваться налево, алгоритм рисования квадрата можно записать в виде последовательности слов:
налево, налево, налево, шагни, шагни, налево, шагни, шагни, налево, шагни, шагни, налево, шагни, шагни.
Или, если действие шаг обозначить буквой Ш , действие прыжок — буквой П , а действие поворот — буквой Л , то этот же самый алгоритм запишется в виде:
Л, Л, Л, Ш, Ш, Л, Ш, Ш, Л, Ш, Ш, Л, Ш, Ш.
Для наглядности алгоритм можно записать в виде графической схемы, например, как показано на рис. 5.1.
Рис. 5.1. Запись алгоритма в виде графической схемы.
Все три приведенные записи алгоритма верны, но ни одна из них не может быть использована в среде ГРИС Букашка для того, чтобы исполнитель нарисовал квадрат. Для практического использования алгоритма придётся написать программу, реализующую алгоритм в соответствии с правилами языка программирования, который принят в среде ГРИС. Это было сделано на предыдущем занятии.
Линейный алгоритм
Вернёмся к нашему исполнителю, который умеет выполнять всего три действия: прыгать, шагать и поворачиваться налево. Эти действия являются простыми в том смысле, что команды, соответствующие им, всегда выполняются одинаково. Выполнение этих действий не зависит от обстановки вокруг исполнителя. Если алгоритм содержит только такие действия, то все они будут выполнены последовательно, одно за другим, от первого до последнего, пока не будет решена задача, которой посвящён алгоритм (или пока не возникнет аварийная ситуация, которую в данный момент мы не рассматриваем). Причём каждое действие алгоритма будет выполнено только один раз.
Алгоритмы, шаги которых описываются такими простыми действиями, называются линейными. Важно понимать, что линейность относится к способу выполнения алгоритма, а не к тому результату, который им достигается. Например, линейным алгоритмом можно описать построение сложного рисунка, но сами действия при его построении будут выполняться линейно , как только что было описано. Линейность алгоритма наглядно демонстрирует схема, показанная на рис. 5.1.
Идущие друг за другом действия линейного алгоритма образуют алгоритмическую конструкцию следование . Это — самая простая и естественная алгоритмическая конструкция, и она уже использовалась, например, в программах рисования квадратов, только не называлась. На графических схемах алгоритмов конструкция следование изображается в виде идущих друг за другом (сверху вниз или слева направо) прямоугольников, соединённых линиями или стрелками, показывающими направление выполнения алгоритма (рис. 5.2).
Рис. 5.2. Графическое изображение алгоритмической конструкции следование .
Пример программы
В качестве ещё одного примера реализации линейного алгоритма, состоящего только из конструкций следование , рассмотрим программу, которая рисует на рабочем поле флажок. Текст программы приведён ниже. Программа довольно большая, поэтому, чтобы упростить её использование, под текстом программы есть кнопка Выполнить , при нажатии на которую откроется среда ГРИС Букашка с уже загруженной программой в режиме выполнения программы. Чтобы ГРИС открылась в отдельной вкладке веб-браузера, при щелчке по кнопке надо удерживать нажатой клавишу <CTRL>.
Учитель информатики
Сайт учителя информатики. Технологические карты уроков, Подготовка к ОГЭ и ЕГЭ, полезный материал и многое другое.
Запись алгоритмов на языках программирования
§ 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.
Выясните, каким будет результат работы программы, если в ней условие выхода из цикла будет изменено на:
Пример 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) таблицы, каждая строка которых отражает результат выполнения группы действий.
Вопросы и задания
1. Что такое язык программирования? Опишите состав и интерфейс среды разработки программ на используемом вами языке программирования.
2. Приведите примеры структур данных, используемых в языке программирования Pascal.
3. Кратко охарактеризуйте основные элементы языка программирования Pascal.
4. Опишите структуру программы на языке Pascal.
5. Для чего предназначены трассировочные таблицы?
6. Вещественные числа х, у, z являются исходными данными для следующего алгоритма:
1) переменной m присвоить значение х;
2) сравнить значения m и у: если у больше m, переменной m присвоить значение у;
3) сравнить значения m и z: если z больше m, переменной m присвоить значение z.
Выясните, какую задачу решает этот алгоритм. Запишите его на языке программирования Pascal. Решите аналогичную задачу для чисел х, у, z и w.
7. Определите значение переменной n, которое будет получено в результате выполнения следующей программы:
8. Определите значение переменной s, которое будет получено в результате выполнения следующей программы:
9. Требуется выяснить, какое число будет выведено в результате выполнения следующей программы:
10. Получив на вход число х, приведённая ниже программа выводит два числа — m и n.
Известно, что при некотором значении х были выведены числа 4 и 8. Укажите наибольшее и наименьшее из таких чисел х. Сколько всего существует таких х?
11. Напишите программу, выводящую на экран все чётные трёхзначные числа.
12. Напишите программу, подсчитывающую сумму квадратов всех чисел от 1 до n.
13. Напишите программу, позволяющую определить, входит ли заданная цифра в некоторое целое неотрицательное число.
14. Разработайте программу перевода десятичного натурального числа n в троичную систему счисления.
15. Разработайте программу, которая выводит сообщение «Да», если точка с координатами (х, у) принадлежит закрашенной области, и «Нет» в противном случае.
16. Шифр кодового замка является двузначным числом. Буратино забыл код, но помнит, что сумма цифр этого числа, сложенная с их произведением, равна самому числу. Напишите все возможные варианты кода, чтобы Буратино смог быстрее открыть замок. Решите задачу методом перебора.
Можно ли нарушить последовательность выполнения команд в программе? для чего это может потребоваться? всегда ли в новом компьютере есть какая-либо программа? просьба ответить с обоснованием.
эти знаки изображали человека и части его тела, орудия труда, оружие, лодки, животных, птиц, рыб, растения, поля, воды, горы, звёзды и т. д. — т.е. конкретные предметы. это было начало письма. письменные знаки, засвидетельствованные древнейшими памятниками, могут быть без труда возведены к их первоначальному рисуночному образу.
на вход «черного ящика»подается число 125. о чем в этом случае говорит отказ: кажеться а
var a,b,c,d,x,res: integer;
c: =x div 100 mod 10;
d: =x mod 100 div 10;
var a: integer; c1, c2, c3, c4: integer;
begin for a : = 1000 to 9999 do begin c1 : = a div 1000; c2 : = (a div 100) mod 10; c3 : = (a div 10) mod 10; c4 : = a mod 10; if (c1 < > c2) and (c1 < > c3) and (c1 < > c4) and (c2 < > c3) and (c2 < > c4) and (c3 < > c4) then writeln(a); end; end.