Сёмов Основы разработки алгоритмов и программ. Учебное пособие для студентов факультета дистанционных форм обучения миигаик москва 2020 2 Рецензенты
 Скачать 391.34 Kb.
|
|
Министерство науки и высшего образования РФ Московский государственный университет геодезии и картографии А. М. Сёмов Информатика: основы разработки алгоритмов и программ Учебное пособие для студентов факультета дистанционных форм обучения МИИГАиК Москва 2020 2 Рецензенты: Князева М.Д., генеральный директор АНО Центр дополнительного образования «Будущим- космонавтам», к.т.н. Чугреев И.Г., профессор, д.т.н. (МИИГАиК) А. М. Сёмов Информатика: Основы разработки алгоритмов и программ Учеб. пособие / М. :МИИГАиК, 2020.-85 с «Информатика: Основы разработки алгоритмов и программ» предназначено студентам факультета дистанционных форм обучения МИИГАиК. Оно может быть использовано для организации занятий по информатике и на других факультетах. Изложение теоретического материала сопровождается примерами, нацеленными на развитие у студентов и абитуриентов навыков решения конкретных задач, а также вопросами и упражнениями для самостоятельного выполнения. 3 1. Алгоритм и его свойства 1.1. Понятие алгоритма Понятие алгоритма так же фундаментально для информатики, как и понятие информации. Поэтому в нем очень важно как следует разобраться. Само слово “алгоритм” происходит от имени выдающегося математика средневекового Востока Мухаммеда Аль Хорезми (787-850гг.). Им были предложены приемы выполнения арифметических вычислений с многозначными числами (вам они хорошо знакомы из школьной математики). Позже в Европе эти приемы назвали алгоритмами, от Algorithm — латинского написания имени Аль Хорезми. В наше время алгоритм понимается шире, не ограничиваясь только арифметическими вычислениями. Алгоритм — это последовательность команд, управляющих работой какого-либо объекта. Назовем его объектом управления. Им может быть как техническое устройство, так и живое существо. В дальнейшем будем называть его исполнителем алгоритма. Алгоритмы арифметических вычислений сформулированы для исполнителя-человека. С таким же успехом можно назвать алгоритмами множество различных инструкций, предписывающих последовательность действий человека для выполнения какой-либо работы. Например, кулинарный рецепт — это алгоритм работы повара с целью приготовления блюда; инструкция по сборке машинки из деталей детского конструктора — алгоритм для ребенка; инструкция по использованию кухонного комбайна — алгоритм для домохозяйки. Вы, наверное, никогда не задумывались над тем, какое количество алгоритмов вам известно. Жизненный опыт человека растет с увеличением числа освоенных им алгоритмов. Например, чтобы ребенок научился покупать в магазине хлеб, ему нужно сначала рассказать (а лучше показать), как это делается. Освоив “алгоритм покупки хлеба”, он в дальнейшем будет успешно выполнять эту работу. Поиск выигрышной тактики, а, следовательно, и алгоритма несложной игры — интересная и полезная задача. Рассмотрим одну из таких игр, которая называется игрой Баше. Играют двое. Перед ними 21 предмет, допустим, камни (также может быть 11, 16, 26 и т.д. т.е. 5k + 1 камней, k-натуральное число ). Игроки берут камни по очереди. За один ход можно взять 1-2-3-4 камня. Проигрывает тот, кто забирает последний камень, Имеется выигрышная тактика для игрока, берущего камни вторым. Она заключается в том, чтобы брать такое количество камней, которое дополняет число камней, взятых соперником на предыдущем ходе, до пяти. Этот алгоритм можно описать в виде последовательности команд 4 алг Игра_Баше нач 1. Предоставить ход сопернику 2. Взять столько камней, чтобы в сумме с предыдущим ходом соперника получилось 5 камней 3. Если после этого для партнера остался один камень, то объявить о своем выигрыше, иначе после хода партнера вернуться к выполнению команды 2 кон Игрок, строго следующий этому алгоритму, будет всегда выигрывать, даже если он не понимает, почему так происходит. В приведенном примере используется символика учебного Алгоритмического языка (АЯ). Из примера видно, что при записи алгоритма на АЯ в начале находится заголовок, начинающийся со служебного слова алг (сокращенное слово “алгоритм”). Затем указывается название алгоритма, которое автор придумывает сам. Следующая часть называется телом алгоритма. Она начинается служебным словом нач (начало) и заканчивается словом кон (конец). Тело алгоритма представляет собой последовательность команд для исполнителя. Здесь и в дальнейшем служебные слова в алгоритмах на Алгоритмическом языке будут записываться жирным шрифтом. В языках программирования (как и в АЯ) служебными называются слова, для которых определен однозначный смысл. Всякий алгоритм составляется в расчете на конкретного исполнителя с учетом его возможностей. Для того, чтобы алгоритм был выполним, нельзя включать в него команды, которые исполнитель не в состоянии выполнить. Нельзя повару поручать работу токаря, какая бы подробная инструкция ему не давалась. У каждого исполнителя имеется свой перечень команд, которые он может исполнить. Такой перечень называется системой команд исполнителя алгоритмов (СКИ). 1.2. Свойства алгоритма Алгоритм, составленный для конкретного исполнителя, должен включать только те команды, которые входят в систему команд исполнителя. Это свойство алгоритма называется понятностью. Алгоритм должен представлять решение задачи в виде последовательного выполнения отдельных простых шагов (этапов). Это свойство алгоритма называется дискретностью 5 Алгоритм не должен быть рассчитан на принятие каких-либо самостоятельных решений исполнителем. Каждая команда алгоритма должна однозначно определять действие исполнителя. Это свойство алгоритма называется точностью ( или определенностью). Исполнение алгоритма должно завершиться за конечное число шагов. Это свойство алгоритма называется конечностью (или результативностью) алгоритма. Алгоритм решения задачи должен разрабатываться в общем виде. Он должен быть применим для целого класса задач, которые отличаются лишь исходными данными, которые нужно подавать на вход алгоритма, чтобы он привел к решению конкретной задачи. Это свойство алгоритма называется массовостью. Для успешного выполнения любой работы мало иметь ее алгоритм. Всегда требуются еще какие-то исходные данные, с которыми будет работать исполнитель (продукты для приготовления блюда, детали для сбора технического устройства и т.п.). Исполнителю, решающему математическую задачу, требуется исходная числовая информация. Задача всегда формулируется так: дана исходная информация, требуется получить какой-то результат. В математике вы привыкли в таком виде записывать условия задач. Например, Дано: катеты прямоугольного треугольника: а = 3см; b = 4см. Найти гипотенузу с. Алгоритм решения той задачи можно представить в таком виде: алг Гипотенуза нач 1. Возвести а в квадрат, 2. Возвести b в квадрат. 3. Сложить результаты действий 1 и 2, 4. Вычислить квадратный корень из результата 3-го действия и принять его за значение с. кон. Каждую из этих команд может выполнить любой человек, знающий основы математики, следовательно, они входят в его систему команд. Приступая к решению любой задачи, нужно сначала собрать все необходимые для ее решения данные. Еще пример: для поиска номера телефона нужного вам человека исходными данными являются: фамилия, инициалы человека и телефонная книга (точнее, информация, заключенная в телефонную книгу). Однако этого может оказаться недостаточно. Например, вы ищете телефон Смирнова А.И. и обнаруживаете, что в книге пять строк с фамилией Смирнов А.И. 6 Ваши исходные данные оказались неполными для точного решения задачи (вместо одного телефона вы получили пять). Оказалось, что нужно знать еще домашний адрес. Набор: “фамилия — инициалы — телефонный справочник — адрес” является полным набором данных в этой ситуации. Только имея полный набор данных, можно точно решить задачу. Если исходные данные неполные, то задачу либо совсем нельзя решить{ничего нельзя узнать про гипотенузу по одному катету), либо получается неоднозначное решение (пять номеров телефонов). В задачах управления физическими объектами (автомобиль, самолет, станок и т.п.) исходными данными является информация о состоянии объекта управления, об обстановке, его окружающей. Обобщая все сказанное, сформулируем определение алгоритма. Алгоритм — понятное и точное предписание исполнителю выполнить конечную последовательность команд, приводящую от исходных данных к искомому результату. Если алгоритм обладает перечисленными выше свойствами, то работа по нему будет производиться исполнителем формально, (то есть без всяких элементов творчества с его стороны). На этом основана работа программно-управляемых исполнителей-автоматов, например, промышленных роботов. Робот-манипулятор может выполнять работу токаря, если он умеет делать все операции токаря (включать станок, закреплять резец, перемещать резец, замерять изделие). От исполнителя не требуется понимание сущности алгоритма, он должен лишь точно выполнять команды, не нарушая их последовательности. А что такое программа? Отличается ли чем-то программа от алгоритма? Программа это алгоритм, записанный на языке исполнителя. Иначе можно сказать так: алгоритм и программа не отличаются по содержанию, но могут отличаться по форме. Для алгоритма строго не определяется форма его представления. Алгоритм можно изобразить графически, можно — словесно, можно — какими-нибудь специальными значками, понятными только его автору. Но программа должна быть записана на языке исполнителя. 7 2. Алгоритмы работы с величинами для ЭВМ Алгоритм составляется для конкретного исполнителя. Теперь в качестве исполнителя мы будем рассматривать компьютер, оснащенный системой программирования на определенном языке. В качестве такого языка используем учебный алгоритмический язык (АЯ). Компьютер-исполнитель работает с определенными данными по определенной системе команд. 2.1. Типы данных Данные. Компьютер работает с информацией, хранящейся в его памяти. Отдельный информационный объект (число, символ, строка, таблица и пр.) называется величиной. Всякая обрабатываемая программой величина занимает свое место (поле) в памяти ЭВМ. Значение величины — это информация. Существуют три основных типа величин, с которыми работает компьютер: числовой, символьный и логический. Числовые величины, делятся на переменные и константы (постоянные). Например, в формуле (a 2 -2ab+b 2 ), где a, b — переменные, а 2 - константа. Константы записываются в алгоритмах своими десятичными значениями, например: 23, 3.5, 34. Значение константы хранится в выделенной под нее ячейке памяти и остается неизменным в течение работы программы. Переменные в программировании, как и в математике, обозначаются символическими именами. Эти имена называют идентификаторами (от глагола “идентифицировать”, что значит обозначать, символизировать). Идентификатор может быть одной буквой, множеством букв, сочетанием букв и цифр. Как правило, употребляются буквы только латинского алфавита и первый символ в идентификаторе — буква. Примеры идентификаторов: А, X, S3, prim, r25 и т.п. 2.2. Система команд (алгоритмических действий) ЭВМ. Всякий алгоритм строится исходя из системы команд исполнителя, для которого он предназначен. Независимо от того, на каком языке программирования будет написана программа, алгоритм работы с величинами составляется из следующих команд: • присваивание • ввод • вывод • ветвление • цикл 8 • обращение к вспомогательному алгоритму Команда присваивания — одна из основных команд в алгоритмах работы с величинами. Записывать ее мы будем так: <переменная> := < выражение>. Значок “:=” читается “присвоить”. Например: Z := X + Y. Компьютер сначала вычисляет выражение в правой части, затем результат присваивает переменной, стоящей слева от знака “ := ”. Если до выполнения этой команды содержимое ячеек, соответствующих переменным X, Y, Z, было, например, таким: X = 1, Y = 2, Z = – (прочерк в ячейке Z обозначает, что начальное число в ней может быть любым), то после выполнения команды станет следующим: X =1, Y = 2, Z = 3. Если слева от знака присваивания стоит числовая переменная, а справа — математическое выражение, то такую команду называют арифметической командой присваивания, а выражение — арифметическим. В частном случае арифметическое выражение может быть представлено одной переменной или одной константой. Например: Х: = 5; Y: = X. Значения переменных, являющихся исходными данными решаемой задачи, как правило, задаются вводом. Команда ввода в описаниях алгоритмов будет выглядеть так: ввод <список переменных>. Например: ввод А, В, С На современных компьютерах ввод чаще всего выполняется в режиме диалога с пользователем. По команде ввода компьютер прерывает выполнение программы и ждет действий пользователя. Пользователь должен набрать на клавиатуре вводимые значения переменных и нажать клавишу <ВВОД>. Введенные значения присвоятся соответствующим переменным из списка ввода, и выполнение программы продолжится. Вот схема выполнения приведенной выше команды. 1. Память до выполнения команды: A = ---В= ---C= --- 2. Процессор ЭВМ получил команду ввод А, В, С, прервал свою работу и ждет действий пользователя. 3. Пользователь набирает на клавиатуре: 1 3 5 и нажимает клавишу <ВВОД> или Процессор переходит к выполнению следующей команды программы. При выполнении пункта 3 вводимые числа должны быть отделены друг от друга какими- нибудь разделителями. Обычно это пробелы. 9 Из сказанного выше можно сделать вывод: Переменные величины получают конкретные значения в результате выполнения команды присваивания или команды ввода. Если переменной величине не присвоено никакого значения (или не введено), то она является неопределенной. Иначе говоря, ничего нельзя сказать, какое значение имеет эта переменная. Результаты решения задачи сообщаются компьютером пользователю путем выполнения команды вывода. Команда вывода в алгоритмах будет записываться так: вывод <список вывода>. Например: вывод X1, Х2. По этой команде значения переменных X1 и Х2 будут вынесены на устройство вывода (чаще всего это экран). Команда ветвления имеет такой формат: если <условие> то <серия 1> иначе <серия 2> кв Служебное слово кв обозначает конец ветвления. <Серия> — это одна или несколько следующих друг за другом команд. Если <условие> справедливо, то выполняется <серия 1>, в противном случае — <серия 2>. Такое ветвление называется полным. Команды серий следует записывать с отступом в два пробела от вертикали, с которой записывают служебные слова если, то, иначе, кв. В противном случае, читая текст не совсем примитивной программы, понять ее логику практически невозможно. И как показывает опыт многих поколений студентов, программы, написанные без отступов, отладке не поддаются. Рассмотрим пример алгоритма с полным ветвлением: Из двух заданных неравных чисел a и b вывести на печать наибольшее. Алгоритм решения этой задачи можно представить в таком виде: алг Печать1 нач 1. Ввести a и b 2. если a > b то 3. вывод a 10 иначе 4. вывод b кв кон. В некоторых случаях используется неполная форма команды ветвления. Она имеет следующий формат: если <условие> то <серия> кв Здесь <серия> выполняется, если <условие> справедливо. Предыдущую задачу можно решить по алгоритму с неполными ветвлениями: алг Печать1 нач 1. Ввести a и b 2. если a > b то 3. вывести a кв 4. если a < b то 5. вывести b кв кон. Циклическим называют алгоритм, в котором повторяется выполнение последовательности команд (составляющих тело цикла), пока справедливо условие повторения тела цикла. Команда цикла имеет такой формат: пока <условие>, повторять нц <тело цикла> кц Служебное слово нц обозначает начало цикла, кц — конец цикла. В приведенной команде проверяется <условие>. Если оно выполняется, то выполняется <тело цикла>. Затем происходит возврат на проверку условия. Если оно выполняется, то тело цикла повторяется. Если проверка условия дает отрицательный результат, то выполнение цикла завершится, и будет исполняться следующая команда программы. 11 Команды тела цикла следует записывать с отступом в два пробела от вертикали, с которой записывают служебные слова пока, нц, кц. В циклических алгоритмах важно думать о том, чтобы цикл был конечным. Ситуация, при которой выполнение цикла никогда не заканчивается, называется зацикливанием. Пример циклического алгоритма: Найти сумму S последовательных натуральных чисел от заданного числа m до числа n. алг Сумма; нач 1. ввод m, n 2. s:=0 {обнуление сумматора} 3. a:=m {присвоение первого значения переменной a, в которую будем помещать значение каждого очередного слагаемого} 4. пока a <= n повторять нц s:= s + a a:= a + 1 кц 5. вывод s кон. 2.3. Блок – схемы алгоритмов Начиная с 50-х годов, т.е. еще с эпохи ЭВМ первого поколения, программисты стали использовать графические схемы, изображающие алгоритмы, которые получили название блок- схем. Блок-схема состоит из фигур (блоков), обозначающих отдельные действия исполнителя, и стрелок, соединяющих эти блоки и указывающих на последовательность их выполнения. Внутри каждого блока записывается выполняемое действие. Сама форма блока подсказывает характер операции, которую он обозначает. Для придания наглядности и единообразия схемам алгоритмов все графические элементы стандартизированы. 12 В табл. 1 приведены основные блочные символы. Таблица 1 № Блочный символ Функция 1 Начало и конец алгоритма 2 Ввод и вывод данных 3 Простая команда - вычисление 4 Обращение к подпрограмме 5 Блок проверки условия 6 Стрелки передачи управления от блока к блоку. Определяют порядок выполнения алгоритма 7 Соединитель. В него приходят несколько стрелок управления, а выходит только одна Алгоритм, как правило, составляют не из отдельных блоков, а из трех основных управляющих структур: СЛЕДОВАНИЕ, ВЕТВЛЕНИЕ, ЦИКЛ. В структуре следование действия выполняются последовательно одно за другим. Структура ветвления реализована командой ветвления. Логика ее работы разобрана выше и наглядно изображается структурой, показанной на рис. 1. 13 СЕРИЯ "ДА" ДА НЕТ УСЛОВИ Е СЕРИЯ "НЕТ " Рис. 1 Структура ветвление Команда цикла, логика работы которой разобрана выше, изображается структурой, показанной на рис. 2. Такую структуру называют циклом с предусловием (так как условие предшествует телу цикла) или циклом Пока (While) . НЕТ Условие выполнения тела цикла ДА Серия операторов, составляющих тело цикла Рис. 2 Структура цикл с предусловием 14 Частным случаем цикла пока является цикл с параметром (его еще называют арифметический цикл или индексный цикл). Блок-схема цикла с параметром представлена на Рис. 3: Серия операто ров, составляющих тело цикла i : = In , Ik Рис. 3 Цикл с параметром Цикл с параметром обеспечивает повторное выполнение тела цикла, пока целочисленный параметр i пробегает множество всех значений от начального (In) до конечного (Ik) шагом 1. Его запись на АЯ имеет вид: для i от In до Ik, повторять нц <тело цикла> кц Команды тела цикла следует записывать с отступом в два пробела от вертикали, с которой записывают служебные слова для, нц, кц. Пример циклического алгоритма. Найти сумму S натуральных чисел от заданного числа m до числа n. С использованием цикла с параметром алгоритм можно представить в виде: алг Сумма1; нач 1. ввод m , n 15 2. s:=0 {обнуление сумматора} 3. для i от m до n, повторять нц s:= s + i кц 4. вывод s кон. 2.4. Вопросы и упражнения 1. Что такое алгоритм? Откуда произошло это слово? 2. Что такое исполнитель алгоритма? 3. В чем состоят основные свойства алгоритма? 4. Назовите исполнителей следующих видов работы: уборка мусора во дворе, перевозка пассажиров, выдача заработной платы, прием экзаменов, сдача экзаменов, обучение детей в школе. Попробуйте сформулировать СКИ для каждого из этих исполнителей. 5. Определите полный набор данных для решения следующих задач обработки информации: • вычисление стоимости покупок в магазине; • вычисление суммы сдачи от данных вами продавцу денег; • определение времени показа по телевизору интересующего вас фильма; • вычисление площади треугольника; • определение времени падения кирпича с крыши дома; • определение месячной платы за расход электроэнергии; • перевод русского текста на итальянский язык; • перевод итальянского текста на русский язык. 6. Попробуйте сформулировать алгоритмы обработки информации для заданий из пункта 5, если исполнителем являетесь вы сами. Какие команды при этом вы должны уметь выполнять? 7. Какой формат имеет команда ветвления? 8. Какие действия исполнителя она определяет? 9. Чем отличается полное ветвление от неполного? 10. Что такое цикл? Как записывается команда цикла? 11. Что такое условие цикла? 16 12. Что такое тело цикла? 13. В каком случае происходит зацикливание алгоритма? 14. В чем состоят особенности цикла с параметром? 15. Что такое блок-схема? 16. Из каких блоков составляются блок-схемы (как они изображаются и что обозначают)? 17. Что обозначают стрелки на блок-схемах? 18. Нарисуйте блок-схему команды ветвления а) полного б) неполного 19. Нарисуйте блок-схему команды цикла ПОКА. 20. Нарисуйте блок-схему команды индексного цикла. 17 3. Программирование на алгоритмическом языке Назначение программирования — разработка программ управления компьютером с целью решения различных информационных задач. Для составления программ существуют разнообразные языки программирования. Язык программирования — это фиксированная система обозначений для описания алгоритмов и структур данных. Для создания и исполнения на компьютере программы, написанной на языке программирования, используются системы программирования. Система программирования — это программное обеспечение компьютера, предназначенное для разработки, отладки и исполнения программ, записанных на определенном языке программирования. Разработка любой программы начинается с построения алгоритма решения задачи. 3.1. Линейные алгоритмы Программы с линейной структурой составляются из операторов присваивания, ввода, вывода и обращения к подпрограммам. Оператор присваивания можно назвать основным в любом языке программирования. Поговорим о нем более подробно. Рассмотрим последовательность выполнения четырех команд присваивания, в которых участвуют две переменные величины а и b. В приведенной ниже табл. 2 напротив каждой команды указываются значения переменных, которые устанавливаются после ее выполнения. Такая таблица называется трассировочной таблицей, а процесс ее заполнения называется трассировкой алгоритма. Компьютер выполняет команды в порядке их записи в алгоритме. Таблица 2 Команда а b а:= 1 1 — b:= 2*а 1 2 а:=b 2 2 b:= а + b 2 4 Прочерк в таблице обозначает неопределенное значение переменной. Конечные значения, которые получают переменные а и b, соответственно равны 2 и 4. 18 Этот пример иллюстрирует три основных свойства присваивания: 1. Пока переменной не присвоено значения, она остается неопределенной; 2. Значение, присвоенное переменной, сохраняется в ней вплоть до выполнения следующего присваивания нового значения этой переменной; 3. Новое значение, присвоенное переменной, заменяет ее предыдущее значение. Рассмотрим еще один очень полезный алгоритм, с которым при программировании часто приходится встречаться. Даны две переменные величины X и Y. Требуется произвести между ними обмен значениями. Например, если первоначально было X = 1, Y = 2, то после обмена должно стать: X = 2, Y = 1. Хорошим аналогом для решения такой задачи является следующая: даны два стакана, в первом — молоко, во втором — вода; требуется произвести обмен их содержимым. Всякому ясно, что в этом случае нужен дополнительный третий пустой стакан. Последовательность действий будет следующей: 1. Перелить из 1-го в 3-й; 2. Перелить из 2-го в 1-й; 3. Перелить из 3-го во 2-й. Цель достигнута. По аналогии, для обмена значениями двух переменных нужна третья дополнительная переменная. Назовем ее Z. Тогда задача решается последовательным выполнением трех операторов присваивания (Табл. 3). Начальные значения 1 и 2 для переменных X и Y задаются вводом. Таблица 3 Команда X Y Z ввод X, Y 1 2 - Z := X 1 2 1 Х := Y 2 2 1 Y := Z 2 1 1 вывод X,Y 2 1 1 Действительно, в итоге переменные X и Y поменялись значениями. На экран будут выведены значения X и Y в таком порядке: 2, 1. В трассировочной таблице 3 выводимые значения выделены жирным шрифтом. 19 Аналогия со стаканами не совсем точна в том смысле, что при переливании из одного стакана в другой первый становится пустым, В результате же присваивания X:=Y переменная Y, стоящая справа, сохраняет свое значение. И, наконец, рассмотрим пример составления алгоритма для решения следующей математической задачи: даны две обыкновенные дроби; получить дробь, являющуюся результатом их деления. В школьном учебнике математики правила деления обыкновенных дробей описаны так: 1. Числитель первой дроби умножить на знаменатель второй. 2. Знаменатель первой дроби умножить на числитель второй 3. Записать дробь, числителем которой является результат выполнения пункта 1, а знаменателем — результат выполнения пункта 2, В виде формулы это можно записать: (a / b) : (c / d) = (a x d) / (b x c) = m / n Теперь построим алгоритм деления дробей для компьютера. В этом алгоритме сохраним те же обозначения для переменных, которые использованы в записанной выше формуле. Исходными данными являются целочисленные переменные а, b, с, d. Результатом — также целые величины т и п. Ниже алгоритм представлен на Алгоритмическом языке (АЯ). Полученный алгоритм имеет линейную структуру. алг деление_дробей; цел a, b, c, d; нач 1. ввод a, b, c, d 2. m := a * d; 3. n := b * c ; 4. вывод m, n кон. В алгоритме на АЯ строка, стоящая после заголовка алгоритма, называется описанием переменных. Служебное слово цел означает целый тип. Величины этого типа могут принимать только целые значения. 20 3.2. Алгоритмы с ветвящейся структурой Рассмотрим несколько задач, решение которых на компьютере получается с помощью ветвящихся алгоритмов, Первая задача: даны значения двух величин; выбрать большее из них. Пусть исходными данными являются переменные А и В. Их значения будут задаваться вводом. Значение большей из них должно быть присвоено переменной С и выведено на экран компьютера. Например, если А=5, В=8, то должно получиться: С=8. А теперь запишем рассмотренный алгоритм на Алгоритмическом языке (АЯ). Во- первых, нужно решить вопрос о том, как описать переменные в этом алгоритме. Вспомним, что для всех переменных в алгоритме на АЯ необходимо указать их тип. Переменные А, В, С — числовые величины. В этой задаче они могут принимать любые значения. В программировании числовые величины, которые могут иметь любые значения — целые, дробные — называются вещественными. Им ставится в соответствие вещественный тип. На алгоритмическом языке этот тип указывается служебным словом вещ. алг БИД1 вещ a, b, c нач 1. Ввод a, b 2. если a > b то c := a иначе c := b кв 3. вывод с кон. Нетрудно понять смысл этого алгоритма. Если значение переменной А больше, чем В, то переменной С присвоится значение А, В противном случае, когда А < = В, переменной С присвоится значение В. (В качестве упражнения нарисуйте блок-схему этого алгоритма) Условием, по которому разветвляется алгоритм, является отношение неравенства А>В. Такое отношение является логическим выражением. Если оно справедливо, то результатом будет логическая величина “истина” и выполнение алгоритма продолжится по ветви “да” или то; в противном случае логическое выражение примет значение “ложь” и выполнение алгоритма пойдет по ветви “нет” или иначе. 21 До выполнения на компьютере правильность алгоритма можно проверить путем заполнения трассировочной таблицы (Табл. 4). Вот как будет выглядеть трассировка нашего алгоритма для исходных значений А=5, В=8. Таблица 4 Шаг Операция А В С Проверка условия 1 Ввод A,B 5 8 2 А>В 5 8 5>8, нет (ложь) 3 С:=В 5 8 8 4 вывод С 5 8 8 Ветвление является структурной командой. Её исполнение происходит в несколько шагов: проверка условия (выполнение логического выражения) и выполнение команд на одной из ветвей “да” или “нет”. Поэтому в трассировочной таблице записываются не команды алгоритма, а отдельные операции, выполняемые компьютером на каждом шаге, В рассматриваемом алгоритме используется полное ветвление. Эту же самую задачу можно решить, применяя структурную команду неполного ветвления. Запишем такой алгоритм на Алгоритмическом языке. алг БИД2 вещ a,b,c нач 1. Ввод a, b 2. c:=a 3. если b > a то 4. с := b кв 5. вывод с кон. 22 Блок-схема такого алгоритма показана на рис. 4. НЕТ ДА Ввод А, В С : = А В > А С : = B Вывод С Рис. 4 Блок-схема алгоритма БИД2 Выполните самостоятельно трассировку этого алгоритма для вариантов 1. А=0.2, В=0.3; 2. А=7, В=4; 3. А=5, В=5. Для программирования характерно то, что одна и та же задача может быть решена с помощью разных алгоритмов. И чем сложнее задача, тем больше можно придумать различных алгоритмов ее решения. Для больших задач (производственных, научных) практически невозможно точное совпадение алгоритмов, составленных разными программистами. Следующая задача: упорядочить и вывести значения двух переменных X и Y по возрастанию. Смысл этой задачи следующий: если для исходных значений переменных 23 справедливо отношение X (например, Х=2, Y=l), то выполнить обмен значениями. Вывести X и Y. Алгоритм обмена значениями двух переменных был рассмотрен в предыдущем параграфе. Вспомним, что для обмена нужна третья вспомогательная переменная. В алгоритме решения данной задачи используется неполное ветвление. Алгоритм на АЯ имеют следующий вид алг сортировка вещ x,y,c нач 1. Ввод x,y 2 если x > y то с := x x := y y := c кв 3 вывод x,y кон. Здесь роль вспомогательной переменной для обмена выполняет С. 3.3. Вопросы и упражнения 1. Что такое величина? 2. Чем отличаются переменные и постоянные величины? 3. Чем определяется значение величины? 4. Какие существуют основные типы величин в программировании? 5. Как записывается арифметическая команда присваивания? 6. Что такое ввод? Как записывается команда ввода? 7. Что такое вывод? Как записывается команда вывода?. 8. Что такое программирование? 9. Нарисуйте блок-схему алгоритма нахождения большего значения из двух величин. 10. Почему отношение неравенства можно назвать логическим выражением? 11. В каком случае для числовой переменной следует указывать тип целый, в каком — вещественный? 24 12. Опишите алгоритм (в виде блок-схемы и на АЯ) нахождения меньшего значения из двух. 13. Опишите алгоритм (в виде блок-схемы и на АЯ) нахождения меньшего значения из трех заданных. 14. Определите, какая задача решается по следующему алгоритму: алг Задача-6 вещ X нач вывод ‘Введите число не равное нулю’ ввод Х если Х<0 то вывод 'отрицательное число' иначе вывод 'положительное число или ноль' кв кон 15. Составьте алгоритм, по которому на компьютере будет происходить следующее: в переменную S вводится возраст Саши, в переменную М вводится возраст Маши. В качестве результата на экран выводится фраза “Саша старше Маши” или “Маша старше Саши” (предполагаем, что кто-нибудь из них обязательно старше). 16. Решите предыдущую задачу, учитывая возможность одинакового возраста Саши и Маши. В таком случае будет еще и ответ: “Саша и Маша ровесники”. 17. Составьте алгоритм упорядочения значений трех переменных по возрастанию, т.е. при любых исходных значениях А, В, С. Поменять их значения местами так, чтобы стало А<В<С. Проверить алгоритм трассировкой при разных вариантах значений исходных данных. 18. Из каких команд составляется линейный вычислительный алгоритм? 19. Что такое трассировка? Как она производится? 20. В каком случае значение переменной считается неопределенным? 21. Что происходит с предыдущим значением переменной после присваивания ей нового значения? 22. Как вы думаете, можно ли использовать в арифметическом выражении оператора присваивания неопределенную переменную? К каким последствиям это может привести? 23. Напишите на АЯ алгоритм сложения двух простых дробей {без сокращения дроби). 25 24. Напишите на АЯ алгоритм вычисления у по формуле: у= (1 -х 2 +5х 4 ) 2 .где х — данное целое число. Выполните трассировку алгоритма при х=2. Чтобы усложнить вашу задачу вводятся следующие ограничения: в арифметических выражениях можно использовать только операции сложения, вычитания и умножения; выражение может содержать только одну арифметическую операцию. 25. Запишите алгоритм циклического обмена значениями трех переменных А, В, С. Схема циклического обмена такова: например, если до обмена было: А=1,В=2.С=3, то после обмена должно стать: А=3, В=1, С=2. Выполнить трассировку. 26 4. Язык Паскаль 4.1. Основные элементы языка После того, как построен алгоритм решения задачи, составляется программа на определенном языке программирования. Среди современных языков программирования одним иа самых популярных является язык Паскаль. Этот язык разработан в 1971 году и назван в честь Блеза Паскаля — французского ученого, изобретателя механической вычислительной машины. Автор языка Паскаль — швейцарский профессор Никлаус Вирт. Вы будете использовать PascalABC.net- современную версию Паскаля, которая включает в себя как подмножество классический Паскаль и Турбо-Паскаль (ТП), поэтому вы можете просто писать программы на Паскале (ТП) и реализовывать их в среде программирования PascalABC.net. Паскаль — это универсальный язык программирования позволяющий решать самые разнообразные задачи обработки информации. Команду алгоритма, записанную на языке программирования, принято называть оператором. Программа на Паскале близка по своему виду к описанию алгоритма на Алгоритмическом языке. Сравните алгоритм решения уже знакомой вам задачи — деление простых дробей, с соответствующей программой на Паскале (табл.5). Таблица 5 алг деление дробей цел a, b, c, d, m ,n нач ввод а, b, с, d m := a x d n := b х с вывод m, n кон Program Division; var a,b,c,d,m,n : integer; begin readln(a,b,c,d); {Ввод} m:= a*d; {Числитель} n:= b*c; {Знаменатель} write(m, n) {Вывод} end. Заголовок программы начинается со слова Program (программа), за которым следует произвольное имя, придуманное программистом: Program < имя программы>; |