|
|||||||||||||||||||||||
Методика преподавания основ алгоритмизации на базе системы "КуМир". Лекция 6Цикл "для". Табличные величины. Логические, символьные и литерные величиныМы находимся на финальной прямой изучения алгоритмического языка. Сейчас нам надо изучить еще одну конструкцию алгоритмического языка — цикл для. Вспомним задачу про подсчет суммы первых N нечетных чисел. В этой задаче нужно сложить все числа арифметической прогрессии с шагом 2, начиная от числа 1 и заканчивая числом 2N–1. С помощью цикла для это записывается так: S := 0 нц для k от 1 до 2*N - 1 шаг 2 . S := S + k кц Действие внутри цикла, а именно S := S + k, будет выполнено сначала для k = 1, затем для k = 3, затем для k = 5 и последний раз для k = 2*N - 1. Цикл для и придуман для упрощения перебора членов арифметических прогрессий с известными начальным и конечным членами и шагом. Как и команда выбор, цикл для является избыточной конструкцией в том смысле, что абсолютно любой алгоритм можно записать и без этого цикла, заменив его циклом пока: i := i1 нц пока i <= i2 тело цикла i := i + 1 кц Но это не очень удобно, так как можно забыть о присваивании начального значения перед циклом или увеличении величины i внутри цикла. Поэтому цикл для вводится здесь просто, как компактная форма записи. При работе с табличными величинами циклы для встречаются очень часто. К табличным величинам мы сейчас и перейдем.
Соотношение между “табличными величинами” и просто “величинами” примерно такое же, как между “циклами” и просто “командами”. Если циклы позволяют коротко описывать огромные последовательности действий для ЭВМ, то табличные величины дают возможность коротко описывать огромные массивы информации, которые должны быть обработаны1.
Линейные таблицы соответствуют классической модели памяти ЭВМ. Фактически у самой ЭВМ основным хранилищем информации служит одна большая линейная таблица байтов. Табличная величина состоит из “элементов”, доступ к элементу таблицы мы получаем, указывая его номер — индекс, а элемент таблицы Т с индексом i в алгоритмическом языке записывается как T[i]. Для описания таблиц после описания типа нужно указать ключевое слово таб. Название типа и ключевое слово таб разрешается писать и слитно, и раздельно. Обе формы записи вещ таб Т[1:10] и вещтаб Т[1:10] являются правильными. Размерность таблицы и границы изменения индексов указываются после имени каждой величины. Пример: цел таб k[-5:5] Здесь k — линейная таблица, состоящая из 11 элементов целого типа. Индексы элементов принимают значения от –5 до 5. Этот пример не типичный. Чаще всего элементы таблицы нумеруют, начиная с 1, как в языке Паскаль, или начиная с 0, как в языке Си. Табличная величина имеет одно общее для всех ее элементов имя, а элементы таблицы отдельных имен не имеют. Именно этим табличная величина отличается от просто набора из нескольких величин. За счет этого мы можем компактно описать большое количество “элементарных” величин. Так, например, запись цел таб Т[1:1000] заставляет ЭВМ выделить память для тысячи целых чисел. Используя имя таблицы Т и вычисленное в алгоритме значение величины i, можно получить или изменить i-й элемент таблицы, написав Т[i]. Мы получаем возможность компактно записать обработку большого количества информации. Рассмотрим, например, фрагмент алгоритма нц для i от 1 до 1000 Т[i] := 0 кц Выполняя этот фрагмент, ЭВМ присваивает значение 0 тысяче элементов таблицы, то есть изменяет большой объем информации — целую тысячу чисел. А ведь в приведенном фрагменте программы всего три строчки. Таким образом, использование табличных величин позволяет составлять компактные алгоритмы, обрабатывающие огромное количество информации, задействовать не только быстродействие, но и объем памяти ЭВМ. Поле Робота можно рассматривать как таблицу, в каждой клетке которой записаны два числа — радиация и температура. Для лучшего усвоения понятия таблицы можно использовать аналогии с соответствующими фрагментами поля Робота. Так, горизонтальный коридор на поле Робота с заданной в каждой клетке коридора радиацией аналогичен линейной таблице с вещественными элементами (см. пример). А все поле Робота с заданной в каждой клетке температурой — это аналог прямоугольной таблицы, то есть аналог массива с двумя измерениями. Такие массивы на бумаге и на “доске” изображаются обычно в виде прямоугольных таблиц, откуда и название. Предположим, что Робот находится в левом конце горизонтального коридора из 16 клеток, и требуется провести “радиационную разведку” этого коридора, то есть измерить радиацию в каждой клетке коридора и подсчитать какие-то характеристики измеренных данных: суммарную радиацию, максимальную радиацию, номер клетки с минимальным значением радиации и т.п. Для решения подобных задач применимы два разных подхода. При первом подходе Робот перемещается по коридору, для каждой клетки проводит измерение уровня радиации в каждой клетке и немедленно проводит все требуемые подсчеты. При таком подходе нет необходимости запоминать все измеренные значения уровня радиации, обработка данных проводится “на ходу”. Второй подход состоит в том, чтобы разделить во времени этап получения информации и этап ее последующей обработки. При втором подходе Робот идет по коридору, измеряет уровень радиации в каждой клетке и “накапливает” где-то полученную информацию. Далее Робот “отдыхает”, а накопленная информация обрабатывается нужным образом, то есть с этой информацией ЭВМ проводит требуемое вычисление. При этом на этапе проведения вычисления совершенно неважно, откуда взялись исходные данные для этого вычисления: в процессе измерения радиации Роботом или в результате каких-то других действий. Важно только, чтобы эти данные были представлены в какой-то стандартизованной форме. В школьном алгоритмическом языке таких форм две. Данные можно накапливать в таблицах или в файлах. Для определенности далее мы рассмотрим задачу подсчета суммарной радиации коридора с сохранением “накопленной” информации в линейной таблице. При первом подходе — подсчете “на ходу” — для подсчета суммарной радиации нам понадобится всего одна величина вещ S, которая будет хранить суммарную радиацию в клетках, где уже побывал Робот. Составляя алгоритм, можно рассуждать так. Перед началом перемещения по коридору Робот побывал только в одной клетке коридора — в самой левой, и нужно запомнить в S значение радиации в этой клетке: S := радиация Далее Робот должен сместиться вправо, измерить значение радиации в следующей клетке и добавить его к S: вправо; S := S + радиация Этот процесс нужно продолжать до тех пор, пока коридор не кончится, то есть пока справа от Робота свободно. Для описания такого повторяющегося процесса используется цикл “пока справа свободно”. Тем самым мы получаем такой алгоритм: | известно, что Робот находится | в самой левой клетке | горизонтального коридора, | требуется найти суммарную радиацию | во всех клетках коридора | и запомнить ее в S S := радиация нц пока справа свободно . вправо . S := S + радиация кц При таком подходе нам не нужно знать длину коридора, алгоритм будет успешно работать для коридора любой длины. Применим теперь второй подход и будем запоминать информацию, получаемую Роботом, в линейной таблице. Длина таблицы должна быть задана в момент ее описания, так что в этом случае нам важно знать, что длина коридора равна 16, чтобы создать таблицу, в которой уместится вся информация о радиации в коридоре: вещтаб r[1:16] Для правильного заполнения этой таблицы необходимо помнить, в какой по счету клетке коридора (нумерация от 1 до 16, слева направо) находится Робот в момент очередного измерения радиации. Введя для запоминания номера целочисленную величину i, получим такой алгоритм: | известно, что Робот в самой левой клетке | горизонтального коридора длины 16 | требуется измерить радиацию во всех | клетках коридора и | запомнить ее в вещтаб r[1:16] | Робот находится в клетке номер 1: r[1] := радиация нц для i от 2 до 16 . вправо . r[i] := радиация кц На этом сбор информации, в котором активно участвовал Робот, закончился. Вся информация об уровнях радиации в клетках исследуемого коридора собрана в памяти ЭВМ. Остальную работу можно выполнить без помощи Робота. Даже если Робот после сбора информации сломается, ЭВМ, располагая данными измерений радиации, сумеет завершить работу. Теперь нам нужно проделать вычислительный этап работы, найти суммарную радиацию. Для этого с линейной таблицей r нужно проделать стандартную процедуру обработки информации — найти сумму элементов этой таблицы. Это делается так: вещ S, цел i S := 0 нц для i от 1 до 16 . S := S + r[i] кц Замечание. Подсчет суммы элементов вещественной линейной таблицы — это часто встречающаяся операция, и обычно такие операции оформляют как универсальные программы. Поэтому мы составим универсальный вспомогательный алгоритм-функцию сумма, которым и воспользуемся для решения задачи. Составим теперь полный алгоритм подсчета суммарной радиации в коридоре, включая универсальный алгоритм-функцию
Настало время снова вернуться к простым величинам. Мы познакомились с числовыми величинами и встречали в примерах литерные величины. В алгоритмическом языке существуют еще логические и символьные величины. Величина целочисленного типа, как следует из ее названия, может принимать только целые значения. Величины такого типа можно складывать, вычитать, умножать. К делению целых чисел нужно относиться с осторожностью и помнить, что при делении целых чисел всегда получается вещественное число, даже если возможно деление нацело. Например, 5/2 равно 2.5, 4/2 равно 2.02. Таким образом, деление целых чисел всегда дает вещественный результат и, во многих случаях, выполняется приближенно. Для нахождения целой части вещественного числа в алгоритмическом языке есть встроенная функция цел int(вещ x) Например, int(5/2) = 2, int(4/2) = 2, int(-1/2) = -1. Для деления с остатком на положительное целое число в “КуМире” встроены две функции: цел div(цел m, цел n) | частное от деления m |на n с остатком цел mod(цел m, цел n) | остаток от деления m |на n В отличие от многих других языков
программирования, где допускаются отрицательные
остатки, в алгоритмическом языке остаток никогда
не бывает отрицательным, при делении на
положитель- Числа можно сравнивать, в алгоритмическом языке есть обозначения для 6 операций сравнения: “<”, “>”, “<=”, “>=”, “=” и “<>”. Операции сравнения “=” и “<>” в алгоритмическом языке применимы к значениям любого типа, остальными операциями сравнения можно без опаски пользоваться для числовых величин и с некоторой опаской для текстовых величин, так как результат сравнения текстовых величин не соответствует алфавитному упорядочению. Наконец, целочисленная величина может появиться в левой части команды присваивания величина := значение .Величина логического типа (лог) может принимать только одно из двух значений: да, нет3. Над значениями логического типа допустимы три логические операции: и , или, не.Типы, которые мы уже изучали (цел, вещ), и новые (лог, сим, лит) являются так называемыми встроенными, предопределенными типами алгоритмического языка. Других (не предопределенных) типов в алгоритмическом языке нет. Средств для построения новых, “своих” типов в алгоритмическом языке тоже нет. Величины логического типа можно использовать в условиях в алгоритмическом языке. Для примера рассмотрим такую задачу. От горизонтального коридора на поле Робота кое-где вверх отходят тупики разной высоты. Надо отметить клетки коридора напротив тех тупиков, высота которых больше трех клеток (мы их назвали “длинными тупиками”). Если мы начнем решать эту задачу, т.е. составлять алгоритм, у нас, конечно, будет цикл, потому что неизвестно, сколько клеток в коридоре. Условием окончания цикла служит условие “справа стена”. Внутри цикла надо идти по коридору вправо и, если сверху обнаружится “длинный” тупик, то соответствующую клетку коридора закрасить. Теперь, после введения величин логического типа, мы, в соответствии с методом последовательного уточнения, эту изложенную выше идею решения можем записать прямо на алгоритмическом языке: алг отметить клетку дано | выше клетки имеется | вертикальный тупик надо | закрасить входную клетку тупика, | если "сверху длинный тупик" нач если сверху длинный тупик то закрасить все кон Здесь условие “сверху длинный тупик” — вызов вспомогательного алгоритма-функции, значением которого является логическое значение. Многие конструкции в алгоритмическом языке вводятся именно для того, чтобы, произнеся нормальную человеческую фразу типа “если сверху длинный тупик, то закрасить клетку коридора”, мы могли бы ее примерно в таком же нормальном виде записать в алгоритм, но уже в виде фрагмента алгоритма на алгоритмическом языке. После того как мы написали этот фрагмент, мы должны еще написать вспомогательный алгоритм-функцию, который будет анализировать, есть ли сверху “длинный” тупик.
И, наконец, скажем несколько слов о символьных и литерных величинах. Значением символьной величины может быть любой символ, всего имеется 256 символов. Некоторые символы можно найти на клавиатуре или увидеть на экране, а другие символы называются “непечатными” и увидеть их нельзя. Зато у каждого символа имеется код — целое число от 0 до 255, и есть встроенные функции “КуМира”, преобразующие символ в код и обратно. Попробуем напечатать все символы с кодами от 32 до 127:
Мы видим, что среди этих символов есть цифры, латинские буквы, знаки препинания и спецзнаки, но нет русских букв. Это и неудивительно, символы с кодами от 0 до 127 — это символы американской кодировки ASCII. Чтобы увидеть русские буквы, нужно напечатать символы с кодами от 128 до 255 (так называемые “символы кодировки KOI-8r”) — см. скриншот.
Литерная величина строится из символьных. Для литерных величин и их значений часто используется термин строка. С некоторой натяжкой литерную величину можно представлять себе в виде линейной таблицы, элементами которой являются символы, к которым можно обращаться по номеру, как к элементам таблицы. Но в отличие от числовых линейных таблиц длина литерной строки (т.е. количество “элементов таблицы”) может меняться в ходе выполнения алгоритма, а при задании литерной величины длина не указывается. лит стр стр2 стр1:= "паровозик" стр2:= "" В этом примере заданы две строки с именами стр1 и стр2. Первая строка состоит из 8 символов: стр1[1]='п' стр1[2]='a' ... стр1[8]='к' Вторая строка пуста, в ней нет ни одного символа. В “КуМир” встроена функция цел длин(лит стр) подсчитывающая длину строки: длин(стр1) = 8, длин(стр2) = 0 Эта функция облегчает работу со строками: чтобы подсчитать какую-то характеристику строки, перебирая все ее элементы, можно использовать функцию длин в цикле для. Например, для подсчета числа пробелов в строке можно написать цел i, n, лит стр n := 0 нц для i от 1 до длин(стр) . если стр[i] = " " . . n := n + 1 . все кц В отличие от линейных таблиц над литерными величинами определены еще две операции: “вырезка” куска строки и добавление одной строки в конец другой. Приведем ровно один пример. Пусть стр1 = "паровозик" стр2 = "ход" Тогда стр1[1:4] = "паро" и стр1+стр2 = "пароход" Вырезка из строки снова является строкой и обозначается так:
При изучении величин литерного типа
можно сформулировать достаточное количество
задач, в которых аргументами и/или результатами
являются строки. Эта область подобна играм с
шифровкой и дешифровкой, которые так любят
многие дети. Наверняка в классе найдутся ученики,
которым работа со словами понравится больше, чем
управление Роботом. Связать эти два непохожих
внешне клас-
Закодируем программу управления Роботом в виде строки путь из этих пяти букв. Тогда можно будет поставить несколько задач, в которых результат выполнения Роботом данной программы нужно определить, анализируя строку путь и не используя массивы. Легкая задача. По строке путь определить, вернулся ли Робот в исходное положение. Средняя по трудности задача. Робот начал движение на пустом поле. В строке путь ровно две буквы “З”. Определить, сколько клеток закрасил Робот. Трудная задача. Робот начал движение на пустом поле. В строке путь не менее одной буквы “З”. Определить, закрасил ли Робот более одной клетки. И, наконец, еще об одних командах в алгоритмическом языке — командах контроля.
В этих командах может быть либо записано так называемое контрольное условие, либо не написано ничего, либо написан только комментарий. Последний случай — самый частый в примерах, когда дано и надо используются для пояснения алгоритмов ученику, а не для формальной проверки условий в ходе выполнения алгоритма ЭВМ: дано |Робот в начале горизонтального |коридора |Вверх от коридора отходят тупики |разной высоты надо |Закрасить клетки коридора напротив |тех тупиков, высота которых больше |трех клеток Для простоты в начале освоения “КуМира” можно считать эти конструкции “предназначенными для комментариев” и объяснение их реального смысла пропустить. В отличие от конструкций дано и надо, являющихся частью записи алгоритма, команда утв может быть помещена в произвольное место в теле алгоритма. Если условие в дано проверяется перед началом выполнения алгоритма, а надо — после окончания выполнения алгоритма, то утв — в том месте, где эта команда написана. Ответ на вопрос “зачем нужна команда утв?” можно свести к бытовой аналогии: в прошлом веке на дверях лифта, которые еще часто были не автоматическими, висело красочное объявление: “НЕ открывайте дверь лифта, пока не убедитесь, что кабина находится перед вами. Это может привести к падению в шахту”. Очевидно, что такая проверка спасла от серьезных травм не одного человека. Игнорирование этого требования, например, в скоростных лифтах главного здания МГУ на Ленинских горах в Москве привело к ряду трагедий. В системе “КуМир” школьник, пишущий программу, естественно, не подвержен такой опасности. В программе, как и в жизни, — если контрольное условие выполнено, то надо просто продолжать дальше выполнять алгоритм. Убедились, что все в порядке, — и работаем дальше. Если же контрольное условие не выполнено (лифта нет!), значит, где-то есть ошибка: либо алгоритм неверен, либо он применяется в недопустимой для него ситуации. С содержательной точки зрения значимость дано и надо состоит в том, что в них описываются условия, которым должны удовлетворять состояние Робота, значения величин и пр. Даже если условия записаны в виде комментариев, они позволяют понять, что должен делать алгоритм, не разбираясь с тем, как он это делает. Это полный аналог формулировки теоремы в математике, средство, позволяющее нам структурировать и накапливать знания (алгоритмы). Аналогично, если команда утв используется для комментариев, пояснения алгоритма, то некоторые его части становится возможным понимать статически, понимать, что делает данный фрагмент алгоритма. Это отличается от анализа и восприятия того, какие действия происходят при выполнении алгоритма. 1 В производственных языках программирования вместо термина “таблица” используется термин “массив” (массив данных, массив информации). “Линейные таблицы” называются “одномерными массивами”, “прямоугольные таблицы” — “двумерными массивами”, а также существуют трех-, четырех-, пяти- и пр. “мерные массивы”.2 В других языках программирования операции деления с остатком и нахождения остатка обозначаются другими способами. Например, в языке Си частное и остаток от деления двух целых чиселm, n обозначаются m/n и m%n соответственно. 3 Точнее говоря, значением логической величины может быть либо да, либо нет, либо значение величины может быть не определено. Кроме того, для значений да и нет предусмотрены синонимы true и false, которыми мы пользоваться не будем.
Ан. Ге. Кушниренко ;
| |||||||||||||||||||||||
|
|
