Лекция: Задача 4.
Сколько клеток лабиринта соответствуют требованию, что, выполнив предложенную программу, Робот (смотри задачу 2) остановится в той же клетке, с которой он начал движение?
| A | B | C | D | E | F |
НАЧАЛО
ПОКА < справа свободно> вправо
ПОКА < сверху свободно> вверх
ПОКА < слева свободно> влево
ПОКА < снизу свободно> вниз
КОНЕЦ
Решение.
Чтобы избежать полного рассмотрения всех клеток, проанализируем условие последнего из циклов. Он завершит работу, если снизу не свободно. Это означает, что если какая-то клетка будет удовлетворять требованию задачи, то она должна быть не только начальной, но и конечной. А для этого, в ней условие последнего цикла должно нарушаться. Таким образом, нам достаточно рассмотреть только те клетки, под которыми есть стена.
Это клетки A6, B5, C4, D3, E2, F3 и вся первая строка. Выполнив алгоритм, стартуя из указанных клеток, получаем, что нам подходят клетки A6, C4, A1, C1. Таким образом, ответ задачи 4.
Понятие типа данных
При создании алгоритмов практически невозможна ситуация, когда нам ничего не приходится хранить. В процессе хранения различных величин необходимо различать – что это за величины. Возникает понятие типа данных. Это тем более актуально, поскольку в соответствии с одним из принципов фон-Неймана, все в компьютере хранится в виде чисел в двоичной системе счисления. Типы позволяют отличать данные друг от друга.
Прежде всего, определим, что такое переменная.
Переменной принято называть некоторую величину, значение которой может меняться в процессе работы алгоритма. Например, можно определить переменные а и b и совершать с ними некоторые действия, например, а:=3, b:=5, а:=7*2, b:=a+b.
Для того чтобы переменная изменила свое значение она должна использоваться в левой части операции присваивания. Упоминание ее в правой части, т.е. в вычисляемом выражении, приводит к ее использованию, не изменяя ее значение.
Рассмотрим решение задачи из предыдущего раздела о вычислении наибольшего из двух значений.
Нач
ввести А, В
если А>В
товывести А
иначевывести В
Все
Кон
Можно предложить и другое решение той же задачи, благодаря использованию дополнительных переменных.
Нач
ввести А, В
если А>В
то C:=А
иначе C:=В
Все
вывести C
Кон
Не стоит экономить на отдельных переменных. Такой текст более нагляден, лучше структурирован и за счет этого при необходимости легче превращается во вспомогательный алгоритм.
То же самое можно сказать, сравнивая два разных подхода к обмену значениями двух переменных a и b.
| Способ 1. c := a a := b b := c | Способ 2. b := a + b a := b – a b := b – a |
Несмотря на то, что второй способ, вроде бы, лучше, т.к. не требует введение дополнительной переменной, но он менее наглядный, менее понятный и дольше выполняется. Предпочтительнее способ 1.
Как уже было сказано, переменные могут быть разных типов. Мы знаем, что такое целые числа, вещественные числа, строки, символы и т.п. Что же такое тип?
Концепция типа данных появилась в языках программирования высокого уровня как естественное отражение того факта, что обрабатываемые программой данные могут иметь различные множества допустимых значений, храниться в памяти компьютера различным образом, занимать различные объёмы памяти и обрабатываться с помощью различных команд процессора.
Понятие типа данных определяет
· диапазон значений переменной
· способ и формат хранения
· набор допустимых операций
Наиболее важным здесь является набор допустимых операций. Для величин одного типа он может быть одним, а для другого типа – другим. Например, мы можем находить остаток от деления одного натурального числа на другое, но эта операция отсутствует для вещественных чисел.
Сложнее обстоит дело с делением. С одной стороны, мы умеем делить и целые числа друг на друга, и вещественные. Но при этом деление вещественных числе дает вещественное число, т.е. оставляет нас в рамках этого типа данных. А при делении целых чисел получение целого результата не гарантируется. В этом случае говорят, что операция деления не замкнута для целых чисел.
Для разных типов данных могут встречаться операции, которые обозначаются одинаково, но имеют под собой совершенно разный смысл. Так, для числовых данных операция «+» соответствует сложению, а при использовании ее для строк мы имеем конкатенацию, или сцепление строк. В случае же работы с данными, которые представляют собой множества, тот же «плюс» обычно соответствует объединению множеств. В программировании это обычно называют полиморфизмом.
Преимущества от использования типов данных:
Надёжность.
Типы данных защищают от трёх основных видов ошибок:
· Некорректное присваивание. Пусть переменная объявлена как имеющая числовой тип. Тогда попытка присвоить ей символьное или какое-либо другое значение в случае статической типизации приведёт к ошибке компиляции и не даст такой программе запуститься.
· Некорректная или недопустимая операция. Позволяет избежать выражений вида ‘строка’ + 1. Поскольку, как уже говорилось, все переменные в памяти хранятся как наборы битов, то при отсутствии типов подобная операция была выполнима. Такие ошибки отсекаются уже на этапе компиляции благодаря контролю типов.
· Некорректная передача параметров. Если некоторая функция ожидает, что ей будет передан числовой аргумент, то передача ей в качестве параметра строки может иметь непредсказуемые последствия. При помощи контроля типов такие ошибки также отсекаются на этапе компиляции.
Стандартизация.
Благодаря соглашениям о типах, поддерживаемых большинством систем программирования, программисты могут быстро менять средства программирования, а программы не требуют больших переделок при переносе исходных текстов в другую среду.
Наглядность.
Использование того или другого типа данных объясняет намерения программиста. Например, логический тип в языке не обязателен, и вместо него можно использовать целый тип, храня там 0 или 1, но использование логической переменной означает, что перед нами не целая величина, а некоторый ответ на вопрос.
Целые числа
Рассмотрим целые числа как тип данных. Можно создавать алгоритмы, абстрагируясь от способа хранения чисел в конкретных программных системах, но как только мы начинаем использовать конкретный язык программирования, каждый из них имеет свой способ внутреннего представления целых чисел. Известны такие подходы как прямой код, дополнительный код, символьное представление целых чисел. В рамках данной темы мы не будем рассматривать особенностей этих вариантов внутреннего представления, для нас важным является то, что каждый из этих способов накладывает ограничение на хранимые величины. У нас нет возможности работать с бесконечно большими целыми числами. Речь идет о допустимом диапазоне значений для данного типа.
Для целых чисел определены следующие операции: сложение, вычитание, умножение, вычисление частного и остатка от деления одного числа на другое. Все дополнительные операции, например, возведение в степень, как правило, не являются базовыми и реализуются с помощью вспомогательных алгоритмов, расширяя возможности языка.
В качестве примера рассмотрим выполнение действий над целыми переменными а, b и с:
a :=50
b :=17
c :=(b + a) div b + а
a :=(a div b)*b
b := (с – а) mod 3
В результате этих действий получим: а = 34, b = 1, с = 53.