Создание трассировочной таблицы
Алекс
Ученик
(88),
закрыт
7 лет назад
Помогите пожалуйста разобраться, как составляются трассировочные таблицы при решении задач в Turbo Pascal на циклы (while и for). А то я что-то совсем не понимаю в этом, программки вроде как могу писать, а вот решение студенческих задач не могу делать. . Представьте мне какую-нибудь задачу на циклы, а затем внизу напишите трассировочную таблицу, как вы это делали. Очень нужна ваша помощь. Заранее за помощь.
Дополнен 12 лет назад
P.S. У меня даны задачи, которые нужно найти (например, в таком духе: чему равна переменная s или сколько раз выполниться цикл) . Компьютером пользоваться нельзя. Т. е вариант один – эта трассировочная таблица, которую нужно составлять для помощи самому себе. Может кто может помочь?
Алексей Арыков
Мудрец
(13103)
12 лет назад
трассировочная таблица – это вывод значений цикла на каждом шаге.. .
for i := 1 to 100 do
begin
…
writeln(i,’ ‘,res1[ i ],’ ‘,res2[ i ],’ ‘, sum);
end;
n/е. на каждом шаге выводишь текущий значения переменных, которые используешь, например “текущая сумма”, “текущий элемент массива” и т. д.
ЕВА ЕВА
Знаток
(339)
6 лет назад
помогите пожалуйста закончить программу к заданию
А вот и программа
var
S,i, N: integer;
begin
read(N);
s:=1;
for i := 2 to n do
s:=s+i;
writeln(S);
end.
§ 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. Структурированные типы данных. Массивы
Теория
Второй вид циклов, используемых в Pascal – это цикл с предусловием.
Форма записи:
While условие do оператор;
Пока условие истинно, выполняется оператор (или несколько), как только условие станет ложным, произойдет выход из цикла.
Условие проверяется в начале, перед циклом поэтому, если условие сразу же ложно, то цикл не повторяется ни разу.
После do ставить точку с запятой нельзя!
Если в теле цикла несколько операторов, то необходимо их заключить в операторные скобки begin … end
While условие do begin
оператор 1;
оператор 2;
…
end;
Переменные, участвующие в записи условия, должны изменяться в теле цикла, иначе может произойти зацикливание!
Задание 1. Какое значение примет переменная x в результате выполнения следующих фрагментов программ?
1) x:=1;
while x<10 do
x:=x+3;
x:=x+1;
В теле цикла только один оператор, так как нет скобок begin end. Построим трассировочную таблицу.
Ответ: x=11
2) x:=1;
while x<10 do begin
x:=x+3;
x:=x+1;
end;
В теле цикла только два оператора, так как есть скобки begin end. Построим трассировочную таблицу.
Ответ: x=13
3) x:=1;
while x<>1 do begin
x:=x+3;
x:=x+1;
end;
Построим трассировочную таблицу.
Ответ: x=1. Цикл не повторится ни разу, так как условие сразу ложно.
4) x:=50;
while x<100 do
begin
x:=x-10;
end;
Построим трассировочную таблицу.
Ответ: Программа зациклится, так как условие никогда не станет ложно.
Задание 2. Составить программу, вычисляющую сумму натурального ряда чисел от 1 до 100
S = 1+2+3+4+…+100
i 1 2 3 4 100
1 способ: с помощью цикла for
s:=0;
for i:=1 to 100 do s:=s+i;
Параметр i увеличивается автоматически на 1 с каждым шагом.
2 способ: с помощью цикла while
Параметр i необходимо увеличивать на 1 в теле цикла. Также необходимо задать начальное значение параметра
i:=1;
S:=0;
while i<=100 do begin
S:=S+i;
i:=i+1;
end;
Сколько раз выполнится цикл? Для чего необходимо S:=0; i:=1? Что будет, если забудем begin end?
Задание 3. Составить программу для решения следующей задачи: Ввести целое число n с клавиатуры. Подсчитать сумму всех целых чисел от 1 до n с шагом 3.
S = 1+4+7+10+…+n
i = 1 4 7 10
read(n)
i:=1;
S:=0;
while i<=n do begin
S:=S+i;
i:=i+3;
end;
writeln(‘S= ’, S);
Задание 4. Составить программу для решения следующей задачи: Найти наибольший общий делитель NOD по алгоритму Евклида.
Например, NOD(20, 25)= NOD(20, 5)= NOD(15, 5)= NOD(10, 5)= NOD(5, 5)
while m<>n do if m>n then m:=m-n
else n:=n-m;
writeln(‘NOD=’,m)
Задание 5. Составить программу для решения следующей задачи: В первый день пловец проплыл 3 км. В каждый последующий день он проплывал на 10% больше, чем предыдущий.
-
-
В какой по счету день пловец начнет проплывать более 5 км?
-
К какому дню он суммарно проплывет более 30 км?
-
var n,s:real;
d:integer;
begin
{найдем в какой день пловец начнет проплывать более 5 км}
n:=3; {количество км.}
d:=1; {количество дней}
while n<=5 do
begin
n:=n+0.1*n;
d:=d+1;
end;
writeln(‘дней – ‘, d);
{найдем к какому дню он суммарно проплывет более 30 км?}
n:=3; s:=3;d:=1;
while s<=30 do
begin
n:=n+0.1*n;
s:=s+n;
d:=d+1;
end;
writeln(‘дней – ‘,d);
end.
ЗАПИСЬ АЛГОРИТМОВ НА ЯЗЫКАХ ПРОГРАММИРОВАНИЯ
ОСНОВНЫЕ СВЕДЕНИЯ ОБ АЛГОРИТМАХ
- языки программирования
- данные
- структура данных
- идентификаторы
- операторы
- трассировочные таблицы
Язык программирования
Язык программирования – формальная знаковая система, предназначенная для записи компьютерных программ.
Компьютерную программу можно считать последовательностью строк символов некоторого алфавита. Современные системы програм-мирования допускают использование визуальных элементов (окон, иконок и др.) для построения программ, в частности, для создания интерфейса пользователя. Такое программирование называют визуальным . Тем не менее, основная, алгоритмическая часть любой программы строится с использованием символьных средств.
PascalABC.NET
КуМир
Структурная организация данных
Информация, представленная в виде, пригодном для автоматизирован-ной обработки, называется данными .
Компьютер оперирует только одним видом данных – отдельными битами, или двоичными цифрами.
Под структурой данных в общем случае понимают множество элементов данных и множество связей между ними.
!
Различают простые и сложные структуры данных.
На основе простых структур строятся сложные структуры данных :
- массивы,
- списки,
- графы,
- деревья и др.
Простые структуры данных не могут быть разделены на составные части больше, чем бит.
К ним относятся:
- числовые,
- символьные,
- логические и др.
Некоторые простые типы данных
Некоторые простые типы данных
логический
числовые
Boolean (1 байт)
символьный
Char (1 байт)
целые
Integer
вещественные
Real (8 байт)
Информация по каждому типу однозначно определяет:
- множество допустимых значений, которые может иметь тот или иной объект описываемого типа;
- множество допустимых операций, которые применимы к объекту описываемого типа;
- объём выделенной памяти для хранения данных указанного типа
Комментарии
Типы данных и, отводимое под них место, могут различаться в разных версиях Паскаля
Основные элементы языка Pascal
- алфавит языка:
- латинские буквы; арабские цифры; специальные символы;
- латинские буквы;
- арабские цифры;
- специальные символы;
- служебные слова, значение которых в языке программирования строго определено;
- постоянные и переменные величины;
- знаки операций;
- стандартные функции;
- выражения;
- операторы (языковые конструкции, с помощью которых в программах записываются действия, выполняемые над данными в процессе решения задачи)
Идентификаторы
Все величины имеют имена ( идентификаторы ), формируемые по определённым правилам:
- имя может состоять из буквы или последовательности букв латинского алфавита, цифр и символа подчёркивания, но начинаться такая последовательность должна с буквы или символа подчёркивания;
- желательно, чтобы имя отражало смысл величины;
- имя не должно совпадать ни с одним из зарезервированных слов.
!
12N
N12
Summa X
Summa_X
Факториал
Factorial
Program
MyProgram
меньше умножение div деление больше целочисленное деление = меньше или равно mod остаток от целочисленного деления больше или равно Логические операции Приоритет операций 1 not 2 and not логическое отрицание *, /, div, mod, and 3 or логическое И 4 xor логическое ИЛИ +, –, or, xor =, , , =, исключающее ИЛИ ” width=”640″
Операции в языке Pascal
Операции отношений
Арифметические операции
=
+
равно
сложение
–
вычитание
не равно
*
/
меньше
умножение
div
деление
больше
целочисленное деление
=
меньше или равно
mod
остаток от целочисленного деления
больше или равно
Логические операции
Приоритет операций
1
not
2
and
not
логическое отрицание
*, /, div, mod, and
3
or
логическое И
4
xor
логическое ИЛИ
+, –, or, xor
=, , , =,
исключающее ИЛИ
; begin ; end. Заголовок программы Блок описания данных Блок описания действий (программный блок) Данные, обрабатываемые компьютером, хранятся в памяти. С точки зрения языка Pascal она разделена на секции, называемые переменными . Каждая переменная имеет имя, тип и значение; значения переменных могут меняться в ходе выполнения программы. Блок описания действий начинается со слова begin , а заканчивается словом end и знаком точки. Действия представляются операторами . Операторы разделяются точкой с запятой. Комментарии Текст появляется ” width=”640″
Структура программы
program ;
var ;
const ;
begin
;
end.
Заголовок программы
Блок описания данных
Блок описания действий (программный блок)
Данные, обрабатываемые компьютером, хранятся в памяти. С точки зрения языка Pascal она разделена на секции, называемые переменными . Каждая переменная имеет имя, тип и значение; значения переменных могут меняться в ходе выполнения программы.
Блок описания действий начинается со слова begin , а заканчивается словом end и знаком точки. Действия представляются операторами . Операторы разделяются точкой с запятой.
Комментарии
Текст появляется
Основные операторы языка Pascal
Название
Общий вид
Присваивание
Имя переменной := Значение
Ввод с клавиатуры
readln ( список ввода )
Вывод на экран
writeln ( список вывода )
Условный
If Условие then Оператор1
Цикл с предусловием
Цикл с постусловием
else Оператор2
while Условие do Тело цикла
repeat
Цикл с параметром с шагом +1
Тело цикла
for Переменная := Нач_знач to Кон_знач do Тело цикла
Цикл с параметром с шагом –1
until Условие
for Переменная := Нач_знач downto Кон_знач do Тело цикла
Анализ программ. Трассировочные таблицы
Для анализа свойств алгоритма и проверки его соответствия решаемой задаче используются трассировочные таблицы . В них фиксируется пошаговое исполнение алгоритма (программы), что позволяет наглядно представлять значения переменных, изменяющиеся при его выполнении. Поэтому трассировочные таблицы иначе называют таблицами значений .
Используются трассировочные таблицы двух видов:
2
1
таблицы, каждая строка которых отражает результат выполнения группы действий
таблицы, каждая строка которых отражает результат одного действия
Комментарии
Кнопки «Далее» – переходы на два скрытых слайда с примерами трассировочных таблиц (выбирается на усмотрение учителя)
Пробел / щелчок на поле – переход на 14-й слайд
0 do begin Y := Y * 10 + X mod 10; Команда или условие X := X div 10 Y X № end ; writeln (Y) end. Составить трассировочную таблицу при Х = 356 . 356 356 readln (X) 1 0 2 Y := 0 0 В заголовке таблицы поместим имена всех переменных, используемых в программе. В отдельном столбце будем записывать команды и условия, имеющиеся в программе. Каждая строка таблицы соответствует одному шагу алгоритма. да X 0 3 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. 6 4 6 Y := Y*10 + X mod 10 35 35 X := X div 10 5 да 6 X 0 65 7 65 Y := Y*10 + X mod 10 3 8 X := X div 10 3 да 9 X 0 653 653 10 Y := Y*10 + X mod 10 0 0 11 X := X div 10 нет X 0 12 13 writeln (Y) ” width=”640″
Трассировочная таблица первого вида
Пример 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
Y
X
№
end ;
writeln (Y)
end.
Составить трассировочную таблицу при Х = 356 .
356
356
readln (X)
1
0
2
Y := 0
0
В заголовке таблицы поместим имена всех переменных, используемых в программе. В отдельном столбце будем записывать команды и условия, имеющиеся в программе. Каждая строка таблицы соответствует одному шагу алгоритма.
да
X 0
3
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.
6
4
6
Y := Y*10 + X mod 10
35
35
X := X div 10
5
да
6
X 0
65
7
65
Y := Y*10 + X mod 10
3
8
X := X div 10
3
да
9
X 0
653
653
10
Y := Y*10 + X mod 10
0
0
11
X := X div 10
нет
X 0
12
13
writeln (Y)
Трассировочная таблица второго вида
Пример 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.
Определите, что будет напечатано в результате выполнения программы.
Результат в КТ
x
k
S
–
0
–
Начальные значения
0
2
2
1
Построим трассировочную таблицу второго вида, отражая в каждой строке результат группы действий. Группу действий ограничим контрольной точкой ( КТ ): выполнение алгоритма продолжается до контрольной точки и приостанавливается после выполнения отмеченной ею строки.
Будем считать, что контрольная точка поставлена на заголовке цикла.
1
2
5
7
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.
2
3
8
15
3
26
4
11
4
5
14
40
Ответ: S = 40
Другие приёмы анализа программ
Решение:
Пример 3. Определите, какое число будет напечатано в результате выполнения программы.
Выясним, какую функцию выполняет каждая из переменных, задействованных в программе.
Начальное значение переменной S = 0 . При каждом выполнении тела цикла S увеличивается на 30 . Таким образом, искомое значение S = 30 ∙ k , где k — число выполнений тела цикла.
Начальное значение переменной n = 1 . При каж-дом выполнении тела цикла значение n увеличивается в 5 раз, т.е. n = 5, 25, 125 …, 5 k .
var n, s: integer; begin n := 1; s := 0; while n do begin s := s + 30; n := n * 5 end ; write(s) end .
var n, S: integer; begin n := 1; S := 0; while n do begin S := S + 30; n := n * 5 end ; write(s) end .
Выясним, при каком условии произойдёт выход из цикла. Цикл выполняется, пока n ≤ 625 . Следовательно, цикл завершится при достижении S значения, большего 625 = 5 4 , т.е. при n = 5 5 .
Таким образом цикл выполнится 5 раз. Следовательно, S = 30 ∙ 5 =150 .
Ответ: S = 150
13
Компьютерную программу можно считать последовательностью строк символов некоторого алфавита. Современные системы програм-мирования и языки допускают использование визуальных элементов (окон, иконок и др.) для построения программ и создания интерфейса пользователя. Тем не менее, основная, алгоритмическая часть любой программы строится с использованием символьных средств.
Компьютер оперирует только одним видом данных – отдельными битами, или двоичными цифрами. Задачи, решаемые с помощью компьютера, оперируют данными, имеющими форму чисел, символов, текстов и более сложных структур. Алгоритмы для обработки этих данных создаются с учётом их структуры – множества элементов данных и множества связей между ними.
Различают простые и сложные структуры данных. Простые структуры данных не могут быть разделены на составные части больше, чем бит. К ним относятся числовые, символьные, логические и другие данные. Простые структуры данных служат основой для построения сложных структур данных – массивов, списков, графов, деревьев и др.
Для анализа свойств алгоритма и проверки его соответствия решаемой задаче используются трассировочные таблицы. В них фиксируется пошаговое исполнение алгоритма (программы), что позволяет наглядно представлять значения переменных, изменяющиеся при его выполнении. Используются трассировочные таблицы двух видов:
- таблицы, каждая строка которых отражает результат одного действия;
- таблицы, каждая строка которых отражает результат выполнения группы действий.
0 do begin d := x mod 10; R := 10*R + d; x := x div 10 end ; writeln(R) end . var x, d, R: longint; begin readln(x); R := 0; while x 0 do begin d := x mod 10; R := 10*R + d; x := x div 10 end ; writeln(R) end . Решение: Сложность этого задания состоит в том, чтобы разобраться, что делает программа. Нетрудно заметить, что данная программа «переворачивает» исходное число х . Таким образом, надо найти двузначное число, сумма цифр которого равна 16 : 16 = 7 + 9 16 = 8 + 8 16 = 9 + 7 Наименьшее число: 79 Ответ: 79 Комментарии Задание 20 из Демоверсии ЕГЭ-2017 Ответ 13 ” width=”640″
Вопросы и задания
Задание 1. Ниже дана программа. Получив на вход натуральное число x , программа печатает число R . Укажи-те такое число x , при вводе которого будет напечатано двузначное число, сумма цифр которого равна 16 . Если таких чисел несколько, укажите наименьшее из них.
var x, d, R: longint; begin readln(x); R := 0; while x 0 do begin d := x mod 10; R := 10*R + d; x := x div 10 end ; writeln(R) end .
var x, d, R: longint; begin readln(x); R := 0; while x 0 do begin d := x mod 10; R := 10*R + d; x := x div 10 end ; writeln(R) end .
Решение:
Сложность этого задания состоит в том, чтобы разобраться, что делает программа.
Нетрудно заметить, что данная программа «переворачивает» исходное число х . Таким образом, надо найти двузначное число, сумма цифр которого равна 16 :
16 = 7 + 9
16 = 8 + 8
16 = 9 + 7
Наименьшее число: 79
Ответ: 79
Комментарии
Задание 20 из Демоверсии ЕГЭ-2017
Ответ
13
100 ), программа печатает число M . Укажите наименьшее значение переменой x , при вводе которого алгоритм печатает 26 . var x, L, M: integer; begin readln(x); L := x; M := 52; while L M do if L M then L := L – M else M := M – L; writeln(M) end . var x, L, M: integer; begin readln(x); L := x; M := 52; while L M do if L M then L := L – M else M := M – L; writeln(M) end . Решение: Данная программа реализует алгоритм Евклида для вычисления наибольшего общего делителя двух чисел – НОД ( M , L ). Тогда, по условию задачи НОД ( 52 , х ) = 26 . Отсюда, х = 104, 130, 156 … Наименьшее х = 104, но НОД ( 52 , 104 ) = 52. Следовательно, х = 130 . Ответ: 130 Комментарии Задание 20 из ЕГЭ-2017 Ответ 13 ” width=”640″
Вопросы и задания
Задание 2. Получив на вход натуральное число x ( x 100 ), программа печатает число M . Укажите наименьшее значение переменой x , при вводе которого алгоритм печатает 26 .
var x, L, M: integer; begin readln(x); L := x; M := 52; while L M do if L M then L := L – M else M := M – L; writeln(M) end .
var x, L, M: integer; begin readln(x); L := x; M := 52; while L M do if L M then L := L – M else M := M – L; writeln(M) end .
Решение:
Данная программа реализует алгоритм Евклида для вычисления наибольшего общего делителя двух чисел – НОД ( M , L ).
Тогда, по условию задачи НОД ( 52 , х ) = 26 .
Отсюда, х = 104, 130, 156 …
Наименьшее х = 104, но НОД ( 52 , 104 ) = 52.
Следовательно, х = 130 .
Ответ: 130
Комментарии
Задание 20 из ЕГЭ-2017
Ответ
13
Вопросы и задания
Задание 3. Дана программа. Что будет напечатано после выполнения программы?
var k, S: integer; begin k := 10; S := 0; while k do begin S := S + k; k := k + 5 end ; write (s) end .
Решение:
Данная программа находит сумму арифметической прогрессии:
S = 10 + 15 + 20 + … + 115 .
Формула для вычисления суммы первых n членов арифметической прогрессии:
В нашем случае:
n = ( 115 –10 ) : 5 + 1 = 22 .
Тогда:
S = ( 10 + 115 ) ∙ 22 / 2 = 1375 .
Ответ: 1375
var k, S: integer; begin k := 10; S := 0; while k do begin S := S + k; k := k + 5 end ; write (s) end .
Комментарии
Задание 8 из ЕГЭ-2017
Ответ
13
Видеоурок:
Запись алгоритмов на языках программирования.
Язык программирования
Язык программирования – формальная знаковая система, предназначенная для записи компьютерных программ.
Компьютерную программу можно считать последовательностью строк символов некоторого алфавита.
Современные системы программирования допускают использование визуальных элементов (окон, иконок и др.) для построения программ, в частности, для создания интерфейса пользователя. Такое
программирование называют визуальным. Тем не менее, основная, алгоритмическая часть любой программы строится с использованием символьных средств.
Структурная организация данных
Информация, представленная в виде, пригодном для автоматизированной обработки, называется
данными.
Компьютер оперирует только одним видом данных – отдельными битами, или двоичными
цифрами.
Под структурой данных в общем случае понимают множество элементов данных и множество связей
между ними.
Различают простые и сложные структуры данных.
Простые структуры данных не могут быть разделены на составные части больше, чем бит.
К ним относятся:
– числовые,
– символьные,
– логические и др.
На основе простых структур строятся сложные структуры данных:
– массивы,
– списки,
– графы,
– деревья и др.
Информация по каждому типу однозначно определяет:
– множество допустимых значений, которые может иметь тот или иной объект описываемого типа;
– множество допустимых операций, которые применимы к объекту описываемого типа;
– объём выделенной памяти для хранения данных указанного типа
Основные элементы языка 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.
