50
В связи с включением курса «Основы информационных и вычислительной техники» в программу средней школы начальная с 1985—86 учебного года, мы возобновляем результаты публикации в разделе «Искусство программирования», открытом на страницах «Кванта» еще в 1979 году. Публикуемые нами материалы признаны разъясняться, развищать и углублять школьный курс. Этот учебный код мы начнем с двух статей члена нашего Редакционного совета академика А. П. Ершова. Основная цель этих статей — научить грамотно записывать алгоритмы. Читая их, следует обратить внимание на слова, набранные курсивом — это специальные термины из информационных, точный смысл которых стоит сверять с учёнымом.
Компьютер – алгоритм – алгоритмический язык
Академик А. П. ЕРШОВ
ЭВМ сегодня и завтра
Нет необходимости доказать, как важны ЭВМ в нашей повседневной жизни. Уже сегодня компьютеры не только производят всевозможные вычисления, они еще и распределяют ав苞илеты, играют в шахматы, рисунок кузовы проектируемых автоматизии, сочиняют музыку, судят спортивные совершения, ставят диагнозы больным, управляют электростанциями. Более того — роль ЭВМ в обществе возрастает все стремительней.
Меняется и наше представление о них: это уже не внутренательные нагромождания мигающих лампочек в огромных шкафах, а скорее скромные — но элегантные — гибридные телевизора с пишущей машинкой.
А на самом деле ЭВМ — это прежде всего тончайший сред кристалла кремния, размером в почтиую марку, опутанный付иткой тончайших проводов, который в будущеем найдет место практически в каждом промышленном изделия. Научное название такого кристалла — микропроцессор. Промышленный выпуск микропроцессоров, по моему глубокому убежданию,— самоое революционное техническое новшество XX века. А по мнению некоторых футурологов в не очень отделенном будущеем оно приведет к тому, что общественное производство будет в основном осуществляться роботами и контролировать компьютерами, а больше часть насе缕ия будет занята составлением программ для их обеспечения.
Так или иначе, люди, трудовая жизнь которых пройдет в основном в двадцать первом веке, не могут быть полноценными членами общества, если они не умют общаться с компьютером, если они не предолели порог второй (компьютерной) грамотности. Для этой цели в школе введен новый курс «Основ информационных вычислительных технологий».
Серодия решения научной или практической задачи на ЭВМ — это совместная постановая работа человека и машины. Мы начнем с краткого описания основных этапов.
51
Этапы решения задачи на ЭВМ
-
Создание алгоритма
Прежде всего необходимо найти подходящий алгоритм для решения поставленной задачи. Алгоритмы для серверных задач обычно придумывают и записывают математики или специализы по информацией, иногда целые коллективы ученых. А в более простых случаях это сделают программы — профессиональные или …начинающие. Для многих задач хорошее алгоритм уже известны — примеры таких алгоритмов имеются в вашем учебнике и будут приводиться на страницах «Кванта», но, как правило, мы будем найти решение задачи с понска подходящого алгоритма. -
Составление программы
Чтобы ЭВМ могла использовать созданный нами алгоритм, его нужно записать в виде программы на одном из тех языков программирования, которые поннимает данной машина. Программы обычно пишут программы на таких языках, как алгоритм, фортран, базийск, пакаль, ранша. Готовые, часто использовемые программы хранятся в библиотеках стандартных программ. В «Кванте» на начальных порах мы будем записать алгоритмы на алгоритмическом языке, основы которого изложены в вашем учебнике. -
Ввод программы в ЭВМ
На современном этапе есть два основных способа вводить написанную программу в компьютер. Первый, уходящий в прошлое способ использования при работе в пакетном режиме: программа записывает (кодируется) в виде перфорации (дырочек) на перфокартах, и колода перфокарта вставляется в машину. Второй способ связыван с работой в диалоговом режиме: программа или оператор набирает программу на клавиатуре дисплея и одновременно следит за правильностью ввода на экран. -
Отладка программы
Obviously okазывается, что в программе есть ошибки (так почти всегда бывают в больших программах). О части ошибок (так называемых синтаксических ошибках, или блоках) сразу сигнализирует компьютер при вводе программы, другие может обнаружить программист при анализе результатов (тестирование или обката программы). Отладка программы — это процесс устранения замеченных в ней ошибок. Делать это «вручную» (без помощи ЭВМ) нельзя: для этого нужно себя поставить на место использователя и попробовать «прокрутить программу» в простейших ситуациях.
52
-
Трансляция программы
Чтобы машина могла исполнить введенную в нее программу или найти ошибку, у нее должен быть транслятор с того языка программирования, на котором программа написана. Transлятор — как бы электронный переводчик — превращает предписания программы в простейшие операции, непосредственно выполняемые машиной. Хотя создание реализации трансляторов — работа очень сложная, требующая высококвалифицированных системных программств, мы будем делать нечто похожое при работе с микрокалькулятором. -
Исполнение программы
При традиционном пакетном режиме этот этап работы машина выполняет сама, без помощи человека: с колоссальной скоростью ЭВМ выполняет все операции, предусмотренные оттраслированной программиной, одну за другой. В некоторых диалоговых программах в процессе работы компьютер может задавать вопросы пользователю и затем продолжать работу. Так или иначе, на этом этапе хозяйчина машина; здесь сказывается ее приемущество над человеком в скорости, точности, аккуратности. -
Выдача результата
Современные компьютерные умелот представлять результат исполнения программы в разном виде. Результат (число, текст, таблица, рисунок) может быть высвечен на экране дисплея, на печатан на АЦПУ (печатающий устройство), нарисован на листе бумаги графопостроителем. Некоторые персональные компьютерные сабжены электронным звуковомулятором, на котором они «играют» результат, когда результаты — мелодия.
А если нет ЭВМ?
Мы в первую очередь ориентируемся на учащся, начинающих в этом учебном году заниматься информацией в школе, еще не основенной вычислительными кабинетами. Такие ученики часто спрашивают — зачем же писать программу, если она все равно не будет пропущена на настоящей ЭВМ?
Этот вопрос очень похож на такой — зачем же писать сочинение, если оно все равно не будет отправлено в типографию? И ответ при мерно такой же: компьютерной грамотностью можно овладеть и без машинны, так же как обычной грамотностью можно овладеть без типографии.
Впрочем, ваши занятия программырованием в любом случае не остаются в области чистой теории. Если в вашей школе (или пользовости) нет больших ЭВМ, часть ваших программ можно будет пропускать на программируемом микрокалькуляторе (например, на «Электронке БЗ-34» или «МК-52»), который обязательно должен быть у вас в школе.
53
Однако мы не будем стремиться превращать своих читателей в виртуозов программирования на микрокалькуляторе. Главным для нас будет поиск алгоритмов, решающих те или иные задачи, умение записать программу на специальном алгоритмческом языке, описанием в вашем учебнике. (Как правило, программы на микрокалькуляторе мы будем исходя из этой алгоритмической записи, то есть сами будем транслеровать (переводить) эту запись в коды операций калькулятора.)
Ниже вы ознакомитесь с некоторыми примерами алгоритмов, а в следующей статье мы подробнее поговорим об их записи на алгоритмческом языке.
Алгоритмы
Слово «alгоритм» происходит от имени великого ученого средневековая ал-Xорезми (см. «Кваант», 1984, № 8, с. 29), но огромное значение этого понятия проясилось лишь во второй половине XX века в связи с развитием вычислительной техники и информационных технологий. Определенно роль этого понятие играет и в математике (об этом см. «Кваант», 1985, № 7, с. 9) — математическая теория алгоритмов примыкает к одной из наиболее известных области математики — математический логик. Однако алгоритмы встречаются и в повседневной жизни, притом на каждом шагу, под таким называнием, как «инструция», «предписание», «решит», «общий способ решения» и тому подобное. Более точно можно сказать, что алгоритм — это понятие и точное представление исполнителя совершить последовательность действия, направленных на достижение определенной цели или на решение поставленной задачи.
Исполнитель алгоритма может быть человек или автоматическое устройство (компьютер, калькулятор, робот), способное воспринять предписание и выполнить указанные в нем действия.
Приерами алгоритмов являются не только многое общие математические приемы, такие, как сложение чисел стольником или алгоритм
Евклида для нахождения Н. О. Д., но также и кулинарные рецепты, указания о проезде по городскому транспорту в определенное место, многое руководства по эксплуатации, также инструкции, как правило пользования международным телефоном, отдельные предписания воинского установки. Не всякое предписание, однако, является алгоритмом. Известное из мира сказаок «Поди туда, не знаю куда, принеси то, не знаю что», конечно же, нельзя считать алгоритмом: оно недостаточно точно и понятно, не указывает на конкретную последовательность действия. То же можно сказать об общим приказе разведкику «Действу по обстановке!» Алгоритм должен предусмотреть все ситуации, которые могут возникнуть при его исполнении, и четко указывать, что делать в каждой из них.
Разберем несколько примеров задачи и алгоритмов, доставляющих их решения.
Задача нахождения остатка. Даны натуральные числа x и y; требуется найти остаток от деления x на y.
Первый алгоритм (для исполнителя — школьника 4—10 класса):
— Напиши x и y рядом в одну строку;
— отдели их уголком;
— выполни деление x на y уголком до цифры единиц делимого (x);
— выдай в качестве решения результат последнего вычитания.
Второй алгоритм (для исполнителя — первоклассика):
— Сравни x и y;
— если x < y, выдай x в качестве решения;
— иначе вычиту y из x и запомни разность;
— если разность меньше y, выдай ее в качестве решения;