Слайд 1
Линейные вычислительные алгоритмы. Операция п рисваивание. Трассировочная таблица.
Слайд 2
В линейных алгоритмах присваивание является важнейшей операцией в алгоритмах, работающих с величинами, поговорим о ней более подробно. Переменная величина получает значение в результате присваивания. Присваивание производится компьютером при выполнении одной из двух команд из представленной выше системы команд: команды присваивания или команды ввода. Рассмотрим последовательность выполнения четырех команд присваивания, в которых участвуют две переменные: а и b . В приведенной ниже таблице против каждой команды указываются значения переменных, которые устанавливаются после ее выполнения. Такая таблица называется трассировочной таблицей, а процесс ее заполнения называется трассировкой алгоритма.
Слайд 3
х:= 2 у:=х*х у:=у*у х:=у*х s:= x+y Шаг алгоритма Переменные x y s 1 2 3 4 5 2 2 4 2 32 32 16 16 48 16 — — — — — Вычисления по алгоритму Алгоритм Ответ : s = 48 Прочерк в таблице означает неопределенное значение переменной. Конечные значения, которые получают переменные а и b , соответственно равны 2 и 4 .
Слайд 4
Трассировочная таблица иллюстрирует три основных свойства присваивания. Вот эти свойства: 1) пока переменной не присвоено значение, она остается неопределенной; 2) значение, присвоенное переменной, сохраняется вплоть до выполнения следующего присваивания этой переменной нового значения; 3) новое значение, присвоенное переменной, заменяет ее предыдущее значение.
Слайд 5
Обмен значениями двух переменных Рассмотрим еще один очень полезный алгоритм, с которым при программировании часто приходится встречаться. Даны две переменные величины: X и Y . Требуется произвести между ними обмен значениями. Например, если первоначально было: X = 1; Y = 2 , то после обмена должно стать: X = 2, Y = 1 . Хорошим аналогом для решения такой задачи является следующая: даны два стакана, в первом — молоко, во втором — вода; требуется произвести обмен их содержимым. Всякому ясно, что в этом случае нужен дополнительный, третий, пустой стакан.
Слайд 6
Последовательность действий будет следующей: 1) перелить из 1-го стакана в 3-й; 2) перелить из 2-го стакана в 1-й; 3) перелить из 3-го стакана во 2-й. Цель достигнута! По аналогии для обмена значениями двух переменных нужна третья дополнительная переменная. Назовем ее Z. Тогда задача решается последовательным выполнением трех операторов присваивания (пусть начальные значения 1 и 2 для переменных X и Y задаются вводом):
Слайд 7
В трассировочной таблице выводимые значения выделены жирным шрифтом. Аналогия со стаканами не совсем точна в том смысле, что при переливании из одного стакана в другой первый становится пустым. В результате же присваивания ( Х:=Y ) переменная, стоящая справа ( Y ), сохраняет свое значение. Действительно, в итоге переменные X и Y поменялись значениями. На экран будут выведены значения X и Y: 2,1 .
Слайд 8
Описание линейного вычислительного алгоритма Алгоритмы, результатами выполнения которых являются числовые величины, будем называть вычислительными алгоритмами. Рассмотрим пример решения следующей математической задачи: даны две простые дроби; получить дробь, являющуюся результатом деления одной на другую. В школьном учебнике математики правила деления обыкновенных дробей описаны так: 1. Числитель первой дроби умножить на знаменатель второй. 2. Знаменатель первой дроби умножить на числитель второй. 3. Записать дробь, числителем которой является результат выполнения пункта 1, а знаменателем — результат выполнения пункта 2.
Слайд 9
В алгебраической форме это выглядит следующим образом: Теперь построим алгоритм деления дробей для компьютера. В этом алгоритме сохраним те же обозначения для переменных, которые использованы в записанной выше формуле. Исходными данными являются целочисленные переменные а, b , с, d . Результатом — также целые величины m и n . Ниже алгоритм представлен в двух формах: в виде блок-схемы и на Алгоритмическом языке (АЯ).
Слайд 10
Раньше прямоугольник в схемах алгоритмов управления мы называли блоком простой команды. Для вычислительных алгоритмов такой простой командой является команда присваивания. Прямоугольник будем называть блоком присваивания , или вычислительным блоком . В форме параллелограмма рисуется блок ввода/вывода . Полученный алгоритм имеет линейную структуру.
Слайд 11
В алгоритме на АЯ строка, стоящая после заголовка алгоритма, называется описанием переменных . Служебное слово цел означает целый тип. Величины этого типа могут иметь только целочисленные значения. Описание переменных имеет вид: <тип переменных> <список переменных> Список переменных включает все переменные величины данного типа, обрабатываемые в алгоритме. В блок-схемах типы переменных не указываются, но подразумеваются. Запись алгоритма на АЯ ближе по форме к языкам программирования, чем блок-схемы.
Слайд 12
Коротко о главном Трассировочная таблица пошаговое исполнение команд алгоритма с указанием значений переменных, которые устанавливаются после выполнения команд. Трассировка алгоритма – процесс заполнения трассировочной таблицы Основные свойства присваивания: • значение переменной не определено, если ей не присвоено никакого значения; • новое значение, присваиваемое переменной, заменяет ее старое значение; • присвоенное переменной значение сохраняется в ней вплоть до нового присваивания.
Слайд 13
Обмен значениями двух переменных можно производить через третью дополнительную переменную . Трассировочная таблица используется для «ручного» исполнения алгоритма с целью его проверки . В алгоритмах на АЯ указываются типы всех переменных . Такое указание называется описанием переменных . Числовые величины, принимающие только целочисленные значения, описываются с помощью служебного слова цел (целый).
Слайд 14
1) A : =1 B: =2 A: =A+B B: =2*A Задание. Постройте трассировочные таблицы для следующих алгоритмов: 2) A : =1 B: =2 C: =A A: =B B: =C 3) A: =1 B: =2 A: =A+B B: =A-B A: =A-B
§ 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) таблицы, каждая строка которых отражает результат выполнения группы действий.
Вопросы и задания
1. Что такое язык программирования? Опишите состав и интерфейс среды разработки программ на используемом вами языке программирования.
2. Приведите примеры структур данных, используемых в языке программирования Pascal.
3. Кратко охарактеризуйте основные элементы языка программирования Pascal.
4. Опишите структуру программы на языке Pascal.
5. Для чего предназначены трассировочные таблицы?
6. Вещественные числа х, у, z являются исходными данными для следующего алгоритма:
7. Определите значение переменной n, которое будет получено в результате выполнения следующей программы:
8. Определите значение переменной s, которое будет получено в результате выполнения следующей программы:
9. Требуется выяснить, какое число будет выведено в результате выполнения следующей программы:
10. Получив на вход число х, приведённая ниже программа выводит два числа — m и n.
11. Напишите программу, выводящую на экран все чётные трёхзначные числа.
12. Напишите программу, подсчитывающую сумму квадратов всех чисел от 1 до n.
13. Напишите программу, позволяющую определить, входит ли заданная цифра в некоторое целое неотрицательное число.
14. Разработайте программу перевода десятичного натурального числа n в троичную систему счисления.
15. Разработайте программу, которая выводит сообщение «Да», если точка с координатами (х, у) принадлежит закрашенной области, и «Нет» в противном случае.
16. Шифр кодового замка является двузначным числом. Буратино забыл код, но помнит, что сумма цифр этого числа, сложенная с их произведением, равна самому числу. Напишите все возможные варианты кода, чтобы Буратино смог быстрее открыть замок. Решите задачу методом перебора.
§ 6. Алгоритмические структуры
§ 7. Запись алгоритмов на языках программирования
§ 8. Структурированные типы данных. Массивы
Трассировка
– это метод пошаговой фиксации динамического состояния алгоритма на некотором тесте. Часто осуществляется с помощью трассировочных таблиц, в которых каждая строка соответствует определённому состоянию алгоритма, а столбец – определённому состоянию параметров алгоритма (входных, выходных и промежуточных). Трассировка облегчает отладку и понимание алгоритма.
Процесс поиска и исправления (явных или неявных) ошибок в алгоритме называется отладкой алгоритма.
Некоторые (скрытые, труднообнаруживаемые) ошибки в сложных программных комплексах могут выявиться только в процессе их эксплуатации, на последнем этапе поиска и исправления ошибок – этапе сопровождения. На этом этапе также уточняют и улучшают документацию, обучают персонал использованию алгоритма (программы).
Пример. Определим функцию фрагмента алгоритма вида на тесте n=2; x[1]=4; x[2]=9:
k:=1; s:=x[1]; for i:=1 to n if (s<x[i]) then begin s:=x[i] k:=i end; writeln (k);
Если выписать трассировочную таблицу вида
| i | S | x[i] | K | s<x[i] | i<=n |
|---|---|---|---|---|---|
| 1 | 4 | 4 | 1 | Нет | Да |
| 2 | 4 | 9 | 2 | Да | Да |
| 3 | — | — | — | — | Нет |
то функция алгоритма становится более понятной – эта функция состоит в нахождении индекса максимального элемента ряда.
В заключение данного раздела приведем общую структуру алгоритмического обеспечения. Критерии, по которым алгоритмы могут быть классифицированы, бывают разными, поэтому предлагаемая ниже схема отражает основные элементы структуры и в некоторых случаях является условной, в том смысле, что блоки приведенной на рис. 9.1 структуры могут «перекрываться».
Рис.
9.1.
Структура алгоритмического обеспечения
Основные формы использования алгоритмов – автономное, библиотечное, пакетное.
Автономный алгоритм определяется решаемой задачей, структурой используемых данных, структурой логических связей частей (модулей) алгоритма и языком псевдокодов, на котором представлен, описан алгоритм.
Библиотека алгоритмов определяется множеством задач, решаемых с помощью библиотеки, множеством алгоритмов для решения типовых задач некоторой предметной области и структурой используемых данных.
Пакет алгоритмов, как и библиотека, определяется множеством задач, решаемых с помощью пакета, множеством алгоритмов для решения типовых задач или их составных частей из некоторой предметной области, структурой используемых данных и обменов данными между задачами (модулями), специальным языком, на котором формулируется задание (последовательность этапов решаемой задачи, последовательность задач задания).
Видеоурок:
Запись алгоритмов на языках программирования.
Язык программирования
Язык программирования – формальная знаковая система, предназначенная для записи компьютерных программ.
Компьютерную программу можно считать последовательностью строк символов некоторого алфавита.
Современные системы программирования допускают использование визуальных элементов (окон, иконок и др.) для построения программ, в частности, для создания интерфейса пользователя. Такое
программирование называют визуальным. Тем не менее, основная, алгоритмическая часть любой программы строится с использованием символьных средств.
Структурная организация данных
Информация, представленная в виде, пригодном для автоматизированной обработки, называется
данными.
Компьютер оперирует только одним видом данных – отдельными битами, или двоичными
цифрами.
Под структурой данных в общем случае понимают множество элементов данных и множество связей
между ними.
Различают простые и сложные структуры данных.
Простые структуры данных не могут быть разделены на составные части больше, чем бит.
К ним относятся:
— числовые,
— символьные,
— логические и др.
На основе простых структур строятся сложные структуры данных:
— массивы,
— списки,
— графы,
— деревья и др.
Информация по каждому типу однозначно определяет:
— множество допустимых значений, которые может иметь тот или иной объект описываемого типа;
— множество допустимых операций, которые применимы к объекту описываемого типа;
— объём выделенной памяти для хранения данных указанного типа
Основные элементы языка Pascal
— алфавит языка:
ü латинские буквы;
ü арабские цифры;
ü специальные символы;
— служебные слова, значение которых в языке программирования строго определено;
— постоянные и переменные величины;
— знаки операций;
— стандартные функции;
— выражения;
— операторы (языковые конструкции, с помощью которых в программах записываются действия, выполняемые над
данными в процессе решения задачи)
Идентификаторы
Все величины имеют имена (идентификаторы), формируемые по определённым правилам:
— имя может состоять из буквы или последовательности букв латинского алфавита, цифр и символа подчёркивания,
но начинаться такая последовательность должна с буквы или символа подчёркивания;
— желательно, чтобы имя отражало смысл величины;
— имя не должно совпадать ни с одним из зарезервированных слов.
Операции в языке
Pascal
Структура программы
Данные, обрабатываемые компьютером, хранятся в памяти. С точки зрения языка Pascal она разделена на секции, называемые
переменными. Каждая переменная имеет имя, тип и значение; значения переменных могут меняться в ходе выполнения программы.
Блок описания действий начинается со слова begin, а заканчивается словом end и знаком точки. Действия
представляются операторами. Операторы разделяются точкой с запятой.
Основные операторы языка Pascal
Анализ программ. Трассировочные таблицы
Для анализа свойств алгоритма и проверки его соответствия решаемой задаче используются
трассировочные таблицы. В них фиксируется пошаговое исполнение алгоритма (программы), что позволяет наглядно представлять значения переменных, изменяющиеся при его выполнении. Поэтому
трассировочные таблицы иначе называют таблицами значений.
Используются трассировочные таблицы двух видов:
1) Таблицы, каждая строка которых отражает результат одного действия.
2) Таблицы, каждая строка которых отражает результат выполнения группы действий.
Трассировочная таблица первого вида
Пример 1. Дана программа:
program Number;
var X, Y: longint;
begin
readln(X);
Y := 0;
while X > 0 do
begin
Y
:= Y * 10 + X mod 10;
X
:= X div 10
end;
writeln (Y)
end.
Составить трассировочную таблицу при Х = 356.
Решение:
В заголовке таблицы поместим имена всех переменных, используемых в программе. В отдельном столбце будем записывать команды
и условия, имеющиеся в программе. Каждая строка таблицы соответствует одному шагу алгоритма.
Трассировочная таблица второго вида
Пример 2. Дана программа:
program Summa;
var k, x, S: integer;
begin
S := 0;
for k := 0 to 4 do
begin
x := k * 3 + 2;
S := S + x
end;
writeln (S)
end.
Определите, что будет напечатано в результате выполнения программы.
Решение:
Построим трассировочную таблицу второго вида, отражая в каждой строке результат группы действий. Группу действий ограничим
контрольной точкой (КТ): выполнение алгоритма продолжается до контрольной точки и приостанавливается после выполнения отмеченной ею строки.
Будем считать, что контрольная точка поставлена на заголовке цикла.
Ответ: S =
40
Но кроме трассировочных таблиц можно использовать и другие приёмы анализа программ.
В качестве примера рассмотрим следующий метод:
Анализ программ методом рассуждений
Пример 3. Определите, какое число
будет напечатано в результате выполнения программы.
var n, s: integer;
begin
n := 1;
s := 0;
while n <= 625 do
begin
s := s + 30;
n := n * 5
end;
write(s)
end.
Решение:
Выясним, какую функцию выполняет каждая из переменных, задействованных в программе.
Начальное значение переменной S = 0. При каждом выполнении тела цикла S увеличивается на 30. Таким образом, искомое значение S =
30 * k, где k — число выполнений тела цикла.
Начальное значение переменной n = 1. При каждом выполнении тела цикла значение n увеличивается в 5 раз, т.е. n = 5, 25, 125 …, 5k.
Выясним, при каком условии произойдёт выход из цикла. Цикл выполняется, пока n ≤
625. Следовательно, цикл завершится при достижении S значения, большего 625 = 54, т.е. при n =
55.
Таким образом, цикл выполнится 5 раз. Следовательно, S = 30 * 5 =150.
Презентация на тему: » 1 Правила заполнения трассировочной таблици. 2 1. Записать алгоритм в левой части. A:=2 B:=3 A:=A*A B:=3*B A:=B+10 B:=A-B.» — Транскрипт:
1
1 Правила заполнения трассировочной таблицы
2
2 1. Записать алгоритм в левой части. A:=2 B:=3 A:=A*A B:=3*B A:=B+10 B:=A-B
3
3 2. Построить таблицу для трассировки. AB A:=2 B:=3 A:=A*A B:=3*B A:=B+10 B:=A-B Количество столбцов в таблице равно количеству переменных используемых в программе в данном примере переменных 2 A и B
4
4 3. Последовательно заполнить трассировочную таблицу. AB A:=2 B:=3 A:=A*A B:=3*B A:=B+10 B:=A-B В каждой строчке выполняется действие указанное в алгоритме. В данном алгоритме присваивание значения переменной.
5
5 3. Последовательно заполнить трассировочную таблицу. AB A:=22- B:=3 A:=A*A B:=3*B A:=B+10 B:=A-B В каждой строчке выполняется действие указанное в алгоритме. В данном алгоритме присваивание значения переменной.
6
6 3. Последовательно заполнить трассировочную таблицу. AB A:=22- B:=323 A:=A*A B:=3*B A:=B+10 B:=A-B В каждой строчке выполняется действие указанное в алгоритме. В данном алгоритме присваивание значения переменной.
7
7 3. Последовательно заполнить трассировочную таблицу. AB A:=22- B:=323 A:=A*A43 B:=3*B A:=B+10 B:=A-B В каждой строчке выполняется действие указанное в алгоритме. В данном алгоритме присваивание значения переменной.
8
8 3. Последовательно заполнить трассировочную таблицу. AB A:=22- B:=323 A:=A*A43 B:=3*B49 A:=B+10 B:=A-B В каждой строчке выполняется действие указанное в алгоритме. В данном алгоритме присваивание значения переменной.
9
9 3. Последовательно заполнить трассировочную таблицу. AB A:=22- B:=323 A:=A*A43 B:=3*B49 A:=B B:=A-B В каждой строчке выполняется действие указанное в алгоритме. В данном алгоритме присваивание значения переменной.
10
10 3. Последовательно заполнить трассировочную таблицу. AB A:=22- B:=323 A:=A*A43 B:=3*B49 A:=B B:=A-B1910 В каждой строчке выполняется действие указанное в алгоритме. В данном алгоритме присваивание значения переменной.
11
11 4. Результат выполнения данного алгоритма. AB A:=22- B:=323 A:=A*A43 B:=3*B49 A:=B B:=A-B1910 В результате выполнения данного алгоритма переменная A = 19, B = 10.