Типы величин в алгоритмическом языке
Методика преподавания основ алгоритмизации на базе системы «КуМир». Лекция 6
Мы находимся на финальной прямой изучения алгоритмического языка.
Но это не очень удобно, так как можно забыть о присваивании начального значения перед циклом или увеличении величины i внутри цикла. Поэтому цикл для вводится здесь просто, как компактная форма записи.
При работе с табличными величинами циклы для встречаются очень часто. К табличным величинам мы сейчас и перейдем.
Лекция 2. Практическое знакомство с системой “КуМир”: исполнитель Робот. Понятие алгоритма. Управление исполнителем Робот с помощью пульта. Линейные алгоритмы. Запись алгоритма. Отступление: Карел-Робот в начальном курсе программирования Стэнфордского университета.
Лекция 3. Методы “визуальной” записи алгоритма. Программное управление Роботом. Цикл “n раз”. Использование вспомогательных алгоритмов. Запись алгоритмов на алгоритмическом языке.
Контрольная работа № 1.
Лекция 4. Арифметические выражения и правила их записи. Алгоритмы с “обратной связью”. Команда “пока”. Условия в алгоритмическом языке. Команды “если” и “выбор”. Команды контроля. “Визуальное” представление команд. Отступление: правила и форма записи арифметических выражений в Фортране XXI века.
Лекция 5. Величины в алгоритмическом языке. Команды ввода/вывода информации. Команда присваивания. Вспомогательные алгоритмы. Алгоритмы с результатами и алгоритмы-функции. Цикл “для”. Табличные величины. Логические, символьные и литерные величины.
Контрольная работа № 2.
Лекция 6. Методы алгоритмизации. Рекуррентные соотношения. Метод итерации. Инвариант цикла. Рекурсия.
Общий вид цикла для :
нц для i от i1 до i2
Общий вид цикла для с шагом :
нц для i от i1 до i2 шаг i3
Линейные таблицы соответствуют классической модели памяти ЭВМ. Фактически у самой ЭВМ основным хранилищем информации служит одна большая линейная таблица байтов.
являются правильными. Размерность таблицы и границы изменения индексов указываются после имени каждой величины.
Здесь k — линейная таблица, состоящая из 11 элементов целого типа. Индексы элементов принимают значения от –5 до 5. Этот пример не типичный. Чаще всего элементы таблицы нумеруют, начиная с 1, как в языке Паскаль, или начиная с 0, как в языке Си.
Табличная величина имеет одно общее для всех ее элементов имя, а элементы таблицы отдельных имен не имеют. Именно этим табличная величина отличается от просто набора из нескольких величин. За счет этого мы можем компактно описать большое количество “элементарных” величин. Так, например, запись
нц для i от 1 до 1000
Выполняя этот фрагмент, ЭВМ присваивает значение 0 тысяче элементов таблицы, то есть изменяет большой объем информации — целую тысячу чисел. А ведь в приведенном фрагменте программы всего три строчки. Таким образом, использование табличных величин позволяет составлять компактные алгоритмы, обрабатывающие огромное количество информации, задействовать не только быстродействие, но и объем памяти ЭВМ.
Поле Робота можно рассматривать как таблицу, в каждой клетке которой записаны два числа — радиация и температура. Для лучшего усвоения понятия таблицы можно использовать аналогии с соответствующими фрагментами поля Робота. Так, горизонтальный коридор на поле Робота с заданной в каждой клетке коридора радиацией аналогичен линейной таблице с вещественными элементами (см. пример). А все поле Робота с заданной в каждой клетке температурой — это аналог прямоугольной таблицы, то есть аналог массива с двумя измерениями. Такие массивы на бумаге и на “доске” изображаются обычно в виде прямоугольных таблиц, откуда и название.
Предположим, что Робот находится в левом конце горизонтального коридора из 16 клеток, и требуется провести “радиационную разведку” этого коридора, то есть измерить радиацию в каждой клетке коридора и подсчитать какие-то характеристики измеренных данных: суммарную радиацию, максимальную радиацию, номер клетки с минимальным значением радиации и т.п.
Для решения подобных задач применимы два разных подхода. При первом подходе Робот перемещается по коридору, для каждой клетки проводит измерение уровня радиации в каждой клетке и немедленно проводит все требуемые подсчеты. При таком подходе нет необходимости запоминать все измеренные значения уровня радиации, обработка данных проводится “на ходу”. Второй подход состоит в том, чтобы разделить во времени этап получения информации и этап ее последующей обработки. При втором подходе Робот идет по коридору, измеряет уровень радиации в каждой клетке и “накапливает” где-то полученную информацию. Далее Робот “отдыхает”, а накопленная информация обрабатывается нужным образом, то есть с этой информацией ЭВМ проводит требуемое вычисление. При этом на этапе проведения вычисления совершенно неважно, откуда взялись исходные данные для этого вычисления: в процессе измерения радиации Роботом или в результате каких-то других действий. Важно только, чтобы эти данные были представлены в какой-то стандартизованной форме. В школьном алгоритмическом языке таких форм две. Данные можно накапливать в таблицах или в файлах.
Для определенности далее мы рассмотрим задачу подсчета суммарной радиации коридора с сохранением “накопленной” информации в линейной таблице.
Составляя алгоритм, можно рассуждать так. Перед началом перемещения по коридору Робот побывал только в одной клетке коридора — в самой левой, и нужно запомнить в S значение радиации в этой клетке:
Далее Робот должен сместиться вправо, измерить значение радиации в следующей клетке и добавить его к S :
вправо; S := S + радиация
Этот процесс нужно продолжать до тех пор, пока коридор не кончится, то есть пока справа от Робота свободно. Для описания такого повторяющегося процесса используется цикл “пока справа свободно”. Тем самым мы получаем такой алгоритм:
| известно, что Робот находится
| в самой левой клетке
| требуется найти суммарную радиацию
| во всех клетках коридора
| и запомнить ее в S
нц пока справа свободно
При таком подходе нам не нужно знать длину коридора, алгоритм будет успешно работать для коридора любой длины.
Применим теперь второй подход и будем запоминать информацию, получаемую Роботом, в линейной таблице. Длина таблицы должна быть задана в момент ее описания, так что в этом случае нам важно знать, что длина коридора равна 16, чтобы создать таблицу, в которой уместится вся информация о радиации в коридоре:
| известно, что Робот в самой левой клетке
| горизонтального коридора длины 16
| требуется измерить радиацию во всех
| клетках коридора и
| запомнить ее в вещтаб r[1:16]
| Робот находится в клетке номер 1:
нц для i от 2 до 16
На этом сбор информации, в котором активно участвовал Робот, закончился. Вся информация об уровнях радиации в клетках исследуемого коридора собрана в памяти ЭВМ. Остальную работу можно выполнить без помощи Робота. Даже если Робот после сбора информации сломается, ЭВМ, располагая данными измерений радиации, сумеет завершить работу.
Теперь нам нужно проделать вычислительный этап работы, найти суммарную радиацию. Для этого с линейной таблицей r нужно проделать стандартную процедуру обработки информации — найти сумму элементов этой таблицы. Это делается так:
нц для i от 1 до 16
Замечание. Подсчет суммы элементов вещественной линейной таблицы — это часто встречающаяся операция, и обычно такие операции оформляют как универсальные программы. Поэтому мы составим универсальный вспомогательный алгоритм-функцию сумма, которым и воспользуемся для решения задачи.
Составим теперь полный алгоритм подсчета суммарной радиации в коридоре, включая универсальный алгоритм-функцию
Настало время снова вернуться к простым величинам. Мы познакомились с числовыми величинами и встречали в примерах литерные величины. В алгоритмическом языке существуют еще логические и символьные величины.
Для деления с остатком на положительное целое число в “КуМире” встроены две функции:
| частное от деления m
| остаток от деления m
В отличие от многих других языков программирования, где допускаются отрицательные остатки, в алгоритмическом языке остаток никогда не бывает отрицательным, при делении на положитель-
ное число n остаток может прини-
мать только значения от 0 до n–1. В функциях div и mod второй аргумент должен быть положителен.
Числа можно сравнивать, в алгоритмическом языке есть обозначения для 6 операций сравнения: “ ”, “ =”, “=” и “<>”. Операции сравнения “=” и “<>” в алгоритмическом языке применимы к значениям любого типа, остальными операциями сравнения можно без опаски пользоваться для числовых величин и с некоторой опаской для текстовых величин, так как результат сравнения текстовых величин не соответствует алфавитному упорядочению. Наконец, целочисленная величина может появиться в левой части команды присваивания
Величины логического типа можно использовать в условиях в алгоритмическом языке. Для примера рассмотрим такую задачу. От горизонтального коридора на поле Робота кое-где вверх отходят тупики разной высоты. Надо отметить клетки коридора напротив тех тупиков, высота которых больше трех клеток (мы их назвали “длинными тупиками”). Если мы начнем решать эту задачу, т.е. составлять алгоритм, у нас, конечно, будет цикл, потому что неизвестно, сколько клеток в коридоре. Условием окончания цикла служит условие “справа стена”. Внутри цикла надо идти по коридору вправо и, если сверху обнаружится “длинный” тупик, то соответствующую клетку коридора закрасить.
Теперь, после введения величин логического типа, мы, в соответствии с методом последовательного уточнения, эту изложенную выше идею решения можем записать прямо на алгоритмическом языке:
алг отметить клетку
дано | выше клетки имеется
надо | закрасить входную клетку тупика,
| если «сверху длинный тупик»
если сверху длинный тупик
Здесь условие “сверху длинный тупик” — вызов вспомогательного алгоритма-функции, значением которого является логическое значение. Многие конструкции в алгоритмическом языке вводятся именно для того, чтобы, произнеся нормальную человеческую фразу типа “если сверху длинный тупик, то закрасить клетку коридора”, мы могли бы ее примерно в таком же нормальном виде записать в алгоритм, но уже в виде фрагмента алгоритма на алгоритмическом языке. После того как мы написали этот фрагмент, мы должны еще написать вспомогательный алгоритм-функцию, который будет анализировать, есть ли сверху “длинный” тупик.
И, наконец, скажем несколько слов о символьных и литерных величинах. Значением символьной величины может быть любой символ, всего имеется 256 символов. Некоторые символы можно найти на клавиатуре или увидеть на экране, а другие символы называются “непечатными” и увидеть их нельзя. Зато у каждого символа имеется код — целое число от 0 до 255, и есть встроенные функции “КуМира”, преобразующие символ в код и обратно. Попробуем напечатать все символы с кодами от 32 до 127:
Мы видим, что среди этих символов есть цифры, латинские буквы, знаки препинания и спецзнаки, но нет русских букв. Это и неудивительно, символы с кодами от 0 до 127 — это символы американской кодировки ASCII. Чтобы увидеть русские буквы, нужно напечатать символы с кодами от 128 до 255 (так называемые “символы кодировки KOI-8r”) — см. скриншот.
Литерная величина строится из символьных. Для литерных величин и их значений часто используется термин строка. С некоторой натяжкой литерную величину можно представлять себе в виде линейной таблицы, элементами которой являются символы, к которым можно обращаться по номеру, как к элементам таблицы. Но в отличие от числовых линейных таблиц длина литерной строки (т.е. количество “элементов таблицы”) может меняться в ходе выполнения алгоритма, а при задании литерной величины длина не указывается.
Вторая строка пуста, в ней нет ни одного символа. В “КуМир” встроена функция
подсчитывающая длину строки:
длин(стр1) = 8, длин(стр2) = 0
нц для i от 1 до длин(стр)
В отличие от линейных таблиц над литерными величинами определены еще две операции: “вырезка” куска строки и добавление одной строки в конец другой. Приведем ровно один пример. Пусть
Тогда стр1[1:4] = «паро» и стр1+стр2 = «пароход»
Вырезка из строки снова является строкой и обозначается так:
вырезка := строка[старт : финиш]
В отличие от арифметических, логических операций и операций сравнения операция вырезки из строки имеет целых три аргумента:
лит строка, цел старт, цел финиш
лит строка, вырезка
При изучении величин литерного типа можно сформулировать достаточное количество задач, в которых аргументами и/или результатами являются строки. Эта область подобна играм с шифровкой и дешифровкой, которые так любят многие дети. Наверняка в классе найдутся ученики, которым работа со словами понравится больше, чем управление Роботом. Связать эти два непохожих внешне клас-
са задач можно следующим образом. Закодируем
5 команд Робота буквами
Закодируем программу управления Роботом в виде строки путь из этих пяти букв. Тогда можно будет поставить несколько задач, в которых результат выполнения Роботом данной программы нужно определить, анализируя строку путь и не используя массивы.
Легкая задача. По строке путь определить, вернулся ли Робот в исходное положение.
Средняя по трудности задача. Робот начал движение на пустом поле. В строке путь ровно две буквы “З”. Определить, сколько клеток закрасил Робот.
Трудная задача. Робот начал движение на пустом поле. В строке путь не менее одной буквы “З”. Определить, закрасил ли Робот более одной клетки.
И, наконец, еще об одних командах в алгоритмическом языке — командах контроля.
Все три команды выполняются так. Проверяется условие. Если условие не соблюдается (равно нет), то “КуМир” прекращает выполнение алгоритма и сообщает, что возник отказ. Если же условие соблюдается, то выполнение алгоритма нормально продолжается так, как если бы команды контроля не было вовсе.
В этих командах может быть либо записано так называемое контрольное условие, либо не написано ничего, либо написан только комментарий. Последний случай — самый частый в примерах, когда дано и надо используются для пояснения алгоритмов ученику, а не для формальной проверки условий в ходе выполнения алгоритма ЭВМ:
дано |Робот в начале горизонтального
|Вверх от коридора отходят тупики
надо |Закрасить клетки коридора напротив
|тех тупиков, высота которых больше
Для простоты в начале освоения “КуМира” можно считать эти конструкции “предназначенными для комментариев” и объяснение их реального смысла пропустить.
“НЕ открывайте дверь лифта, пока не убедитесь, что кабина находится перед вами. Это может привести к падению в шахту”.
Очевидно, что такая проверка спасла от серьезных травм не одного человека. Игнорирование этого требования, например, в скоростных лифтах главного здания МГУ на Ленинских горах в Москве привело к ряду трагедий.
В системе “КуМир” школьник, пишущий программу, естественно, не подвержен такой опасности.
В программе, как и в жизни, — если контрольное условие выполнено, то надо просто продолжать дальше выполнять алгоритм. Убедились, что все в порядке, — и работаем дальше. Если же контрольное условие не выполнено (лифта нет!), значит, где-то есть ошибка: либо алгоритм неверен, либо он применяется в недопустимой для него ситуации.
С содержательной точки зрения значимость дано и надо состоит в том, что в них описываются условия, которым должны удовлетворять состояние Робота, значения величин и пр.
Даже если условия записаны в виде комментариев, они позволяют понять, что должен делать алгоритм, не разбираясь с тем, как он это делает. Это полный аналог формулировки теоремы в математике, средство, позволяющее нам структурировать и накапливать знания (алгоритмы). Аналогично, если команда утв используется для комментариев, пояснения алгоритма, то некоторые его части становится возможным понимать статически, понимать, что делает данный фрагмент алгоритма. Это отличается от анализа и восприятия того, какие действия происходят при выполнении алгоритма.
1 В производственных языках программирования вместо термина “таблица” используется термин “массив” (массив данных, массив информации). “Линейные таблицы” называются “одномерными массивами”, “прямоугольные таблицы” — “двумерными массивами”, а также существуют трех-, четырех-, пяти- и пр. “мерные массивы”.
§ 12. Алгоритмы и величины
Этапы решения задачи на компьютере
Часто эту последовательность называют технологической цепочкой решения задачи на компьютере. Непосредственно к программированию в этом списке относятся пункты 3, 4, 5.
На этапе постановки задачи должно быть четко определено, что дано и что требуется найти. Здесь очень важно определить полный набор исходных данных, необходимый для решения задачи.
Второй этап — формализация задачи. Здесь чаще всего задача переводится на язык математических формул, уравнений, отношений. Если решение задачи требует математического описания какого-то реального объекта, явления или процесса, то формализация равносильна получению соответствующей математической модели.
Третий этап — построение алгоритма. Опытные программисты часто сразу пишут программы на языках программирования, не прибегая к каким-либо специальным способам описания алгоритмов (блок-схемам, псевдокодам). Однако в учебных целях полезно использовать эти средства, а затем переводить полученный алгоритм на язык программирования.
Первые три этапа — это работа без компьютера. Дальше следует собственно программирование на определенном языке в определенной системе программирования. Последний (шестой) этап — это уже использование разработанной программы в практических целях. Выполнение учебных заданий на программирование обычно заканчивается пятым этапом, т. е. доказательством правильности составленной программы.
Основой программистской грамотности является развитое алгоритмическое мышление.
Понятие алгоритма
Одним из фундаментальных понятий в информатике является понятие алгоритма. Сам термин «алгоритм» пришел из математики. Это слово происходит от «Algorithmi» — латинского написания имени Мухамеда аль-Хорезми (787-850 гг.), выдающегося математика средневекового Востока. В XII веке был осуществлен латинский перевод его математического трактата, из которого европейцы узнали о десятичной позиционной системе счисления и правилах арифметики многозначных чисел. Именно эти правила в то время называли алгоритмами. Сложение, вычитание, умножение «столбиком», деление «уголком» многозначных чисел — вот первые алгоритмы в математике. Правила алгебраических преобразований, вычисление корней уравнений также можно отнести к математическим алгоритмам.
В наше время понятие алгоритма трактуется шире. Алгоритм — это последовательность команд управления каким-либо исполнителем. В школьном курсе информатики с понятием алгоритма, с методами построения алгоритмов ученики впервые знакомятся на примерах учебных исполнителей: Робота, Черепашки, Чертежника и др. В нашем учебнике для 9 класса описан графический исполнитель — ГРИС. Эти исполнители ничего не вычисляют. Они создают рисунки на экране, перемещаются в лабиринтах, перетаскивают предметы с места на место. Таких исполнителей принято называть исполнителями, работающими в обстановке.
В разделе информатики под названием «Программирование» изучаются методы программного управления работой компьютера. Следовательно, в качестве исполнителя выступает компьютер. Он работает с величинами — различными информационными объектами: числами, символами, кодами и пр. Поэтому алгоритмы, предназначенные для управления компьютером, принято называть алгоритмами работы с величинами.
Данные и величины
Совокупность величин, с которыми работает компьютер, принято называть данными. По отношению к программе данные делятся на исходные, результаты, (окончательные данные) и промежуточные данные, которые получаются в процессе вычислений (рис. 3.1).
Рис. 3.1. Уровни данных относительно программы
Для успешного освоения программирования необходимо усвоить следующее правило: всякая величина занимает свое определенное место в памяти компьютера. Иногда говорят — ячейку памяти. Хотя термин «ячейка», с точки зрения архитектуры современных компьютеров, несколько устарел, однако в учебных целях его удобно использовать.
У всякой величины имеются три основных свойства: имя, значение и тип. На уровне команд процессора величина идентифицируется адресом ячейки памяти, в которой она хранится. В алгоритмах и языках программирования величины делятся на константы и переменные. Константа — неизменная величина, и в алгоритме она представляется собственным значением, например: 15, 34.7, ‘к’, true. Переменные величины могут изменять свои значения в ходе выполнения программы и представляются символическими именами — идентификаторами, например: X, S2, cod15. Любая константа или переменная занимают ячейку памяти, а значение этих величин определяется двоичным кодом в этой ячейке.
Теперь о типах величин — типах данных. С понятием типа данных вы уже встречались, изучая в курсе информатики основной школы электронные таблицы и базы данных. Это понятие является фундаментальным для программирования.
В каждом языке программирования существует своя концепция типов данных, своя система типов. Однако в любой язык входит минимально необходимый набор основных типов данных, к которому относятся целый, вещественный, логический и символьный типы. С типом величины связаны три ее свойства: множество допустимых значений, множество допустимых операций, форма внутреннего представления. В таблице 3.1 представлены эти свойства основных типов данных.
Таблица 3.1
Типы констант определяются по контексту (т. е. по форме записи в тексте), а типы переменных устанавливаются в описаниях переменных.
Есть еще один вариант классификации данных: классификация по структуре. Данные делятся на простые и структурированные. Для простых величин (их еще называют скалярными) справедливо утверждение: одна величина — одно значение. Для структурированных: одна величина — множество значений.
К структурированным величинам относятся массивы, строки, множества и др.
Компьютер — исполнитель алгоритмов. Как известно, всякий алгоритм (программа) составляется для конкретного исполнителя, в рамках его системы команд. О каком же исполнителе идет речь в теме «Программирование обработки информации»? Ответ очевиден: исполнителем является компьютер. Точнее говоря, исполнителем является комплекс: компьютер + система программирования (СП). Программист составляет программу на том языке, на который ориентирована СП. Схематически это изображено на рис. 3.2, где входным языком исполнителя является язык программирования Паскаль.
Рис. 3.2. Взаимодействие программиста с компьютером
Для описания алгоритмов в дальнейшем мы будем использовать блок-схемы и учебный Алгоритмический язык, применяемый в школьном курсе информатики.
Описание презентации по отдельным слайдам:
Домашнее задание: § 2.3 – 2.4.1 РТ. №115, 116, 122, 135(а)
Проверка домашней работы: РТ. № 98(б), 99(а) 111,113 По 1 баллу
Вопросы на повторение: Что называется алгоритмом? Приведи примеры исполнителей алгоритма. Почему их так называют? Перечисли и поясни характеристики исполнителей. В каких формах может быть представлен алгоритм? По 1 баллу
Разгадай ребусы и познакомься с основными терминами урока: Следование Величина По 1 баллу
Тема урока: Алгоритмическая конструкция «следование». Понятие величины. Кутепова Н.В, МОАУ «СОШ №4 г.Соль- Илецка Оренбургской обл.»2016 г.
Задачи урока: Познакомиться: с понятием «величина». Узнать: об алгоритмической конструкции «следование». По 1 баллу Цели: Научиться: применять правила работы с величинами при составлении алгоритмов.
Алгоритмические величины в системе программирования Кумир
Выражения: I) Арифметические: Правила записи математических функций Язык алгебры Алгоритмический язык Модульчисла Х |X | abs ( x) Корень из числа Х √X sqrt(x) Число Х в квадрате X2 sqr(x) Число Х в любой степени Xn X **n Остаток от деленияaнаb mod( 5, 3)=2 mod(a, b) Целая часть от деленияaнаb div (5, 3)=1 div ( a, b)
Пример алгоритма в системе Кумир
Выполни вместе с учителем: РТ. № 117(а, б, в) № 118(б, д) № 128( б, в) По 1 баллу
Выполни в паре: РТ. № 117(г, д, е), № 118(а, в, г) № 128( а, г, д)
Проверь себя: По 1 баллу
Проверь себя: По 1 баллу
Выполни с помощью компьютера: №129 2 балла
Номер материала: ДБ-1650024
Не нашли то что искали?
Вам будут интересны эти курсы:
Оставьте свой комментарий
Подарочные сертификаты
Ответственность за разрешение любых спорных моментов, касающихся самих материалов и их содержания, берут на себя пользователи, разместившие материал на сайте. Однако администрация сайта готова оказать всяческую поддержку в решении любых вопросов, связанных с работой и содержанием сайта. Если Вы заметили, что на данном сайте незаконно используются материалы, сообщите об этом администрации сайта через форму обратной связи.
Все материалы, размещенные на сайте, созданы авторами сайта либо размещены пользователями сайта и представлены на сайте исключительно для ознакомления. Авторские права на материалы принадлежат их законным авторам. Частичное или полное копирование материалов сайта без письменного разрешения администрации сайта запрещено! Мнение администрации может не совпадать с точкой зрения авторов.