«ОСНОВЫ ИНФОРМАТИКИ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ ПРОБНОЕ УЧЕБНОЕ ПОСОБИЕ для средних учебных заведений В двух частях • ЧАСТЬ ВТОРАЯ Под редакцией А. П. Ершова и В. М. Монахова Рекомендовано Управлением информатики и ...»

Представим себе теперь, что проверка наличия прибора с заданным номером 4наиболее часто выполняемая операция и затраты на ее выполнение хотелось бы сократить.

Нельзя ли тут что-нибудь придумать?

Вспомним, как мы ищем нужное нам слово в словаре. Если бы мы читали словарь подряд, сравнивая нужное слово со всеми cловами, в нем встречающимися, то поиск каждого слова занимал бы несколько часов. К счастью, есть гораздо более быстрый способ.

Ведь слова в словаре упорядочены по алфавиту, и, посмотрев на любое слово из словаря, мы знаем, до или после него находится нужное нам слово. Таким образом, открыв словарь посередине и сравнив наше слово с тем, которое написано посередине, мы сразу же узнаем, в какой половине словаря расположено интересующее нас слово. Открыв эту половину посередине, мы узнаем, в какой из половин этой половины расположено нужное слово, и т. д. Каждый раз область, в которой может находиться нужное слово, сужается примерно вдвое, и довольно быстро нужное слово находится (или мы убеждаемся, что в словаре его нет).

Такая процедура поиска, в которой «круг подозреваемых» все время сужается примерно вдвое, называется двоичным поиском. Прежде чем говорить о применении двоичного поиска в нашей задаче, мы приведем еще несколько примеров его применения.

Все мы знаем детскую игру, в которой один из участников задумывает какой-то объект, а второй должен угадать, что задумал первый. При этом он может задавать первому вопросы, на которые можно отвечать «да» и «нет». Первый отвечает на эти вопросы, и по ответам второй должен узнать, что задумал первый. Рассмотрим вариант игры, в которой первый может задумать любое число от 1 до 100. Как действовать второму?

Самый простой способ состоит в том, чтобы последовательно задавать вопросы:

«Ты задумал 1?», «Ты задумал 2?»— до тех пор, пока первый не ответит: «Да». При этом понадобится задать столько вопросов, каково задуманное число: если задумано число 1, то хватит одного вопроса, но если задумано число 100, то понадобится 100 вопросов.

Двоичный поиск позволяет обойтись гораздо меньшим числом вопросов. Разобьем числа от 1 до 100 на 2 половины: от 1 до 50 и от 51 до 100. Задав один вопрос: «Задуманное число больше 50?», мы узнаем, в какой половине находится задуманное число. Пусть, например, нам ответили «нет», и, следовательно, задуманное число находится среди чисел 1, 2,..., 50. Снова разобьем эти числа на две части: 1, 2,..., 25 и 26,..., 50. Задав вопрос:

«Задуманное число больше 25?», мы узнаем, в какой из этих частей находится задуманное число. Пусть, например, нам сказали «да», т. е. число находится от 26 до 50. Снова разобьем эту область на 2 части (теперь уже только примерно равные, так как количество «подозреваемых» чисел — 25 — нечетно). Это будут области от 26 до 38 и от 39 до 50 (в них 13 и 12 чисел соответственно). Следующий вопрос будет таков: «Задуманное число больше 38?» И т. д.

Из таблицы видно, что после первого вопроса остается максимум 50 «подозреваемых», после второго — максимум 25, после третьего — максимум 13 и т. д. После седьмого вопроса осталось одно-единственное число, которое и будет искомым.

Легко сообразить, что при таком способе отгадывания одного числа из 2" чисел требуется п вопросов. Этот способ является наилучшим в том смысле, что нельзя придумать- способ, который бы гарантировал отгадывание числа с меньшим количеством вопросов. В самом деле, каждый вопрос разбивает круг «подозреваемых» на две части. Если, части окажутся равными, то на следующем этапе количество «подозреваемых» уменьшится вдвое. Если же части неравные, то в худшем случае под подозрением останется большая часть и число «подозреваемых» сократится меньше чем вдвое. Так что наш способ — самый лучший.

Это рассуждение объясняет, почему, например, при отгадывании задуманной известной исторической личности вопрос: «Является ли задуманное лицо генетиком?» — неудачен: среди возможных кандидатов в задуманные фигуры генетики составляют лишь небольшую часть. Скорее всего ответ будет отрицательным, а круг «подозреваемых» сузится лишь очень немного. Гораздо лучше вопрос: «Является ли задуманное лицо ученым?», при котором круг возможных задуманных лиц делится на более близкие по размеру части.

Еще одним примером двоичного поиска является алгоритм отыскания корня функции на отрезке (см. первую часть учебного пособия). Там отрезок, на котором функция меняет знак, делился пополам и выбиралась та из половин этого отрезка, на которой знак тоже менялся. В результате нескольких таких шагов мы находили корень с заданной точностью.

В нашем случае для применения алгоритма двоичного поиска к таблице номера необходимо, чтобы номера приборов располагались в таблице в порядке возрастания, т. е.

чтобы соблюдались условия:

Если это так, то с помощью двоичного поиска можно найти интересующий нас номер (или убедиться в его отсутствии) быстрее. Будем сужать круг «подозреваемых» мест в таблице, считая «подозреваемыми» все числа таблицы от Здесь левая граница и правая граница — две переменные величины, отмечающие границы участка таблицы номера, находящегося «под подозрением». Вначале «под подозрением» находятся все числа таблицы, и потому левая граница должна быть равна 1, а правая граница равна количество + 1. (Напомним, что мы «подозреваем» числа от левой границы, включая ее, до правой границы, исключая ее.) Затем мы сужаем «подозреваемый» участок. Выберем число середина, находящееся в нем:

Если номера [середина] номер, то элемент номер может находиться только в правой половине «подозреваемого» участка (от середина включительно до правая граница невключительно). Если же номера [середина] > номер, то элемент номер может находиться только в левой половине (от левая граница включительно до середина невключительно). Приходим к такой схеме алгоритма:

правая граница := количество + примерно равные половины при номера [середина] номер:

при номера [середина] > номер:

правая граница := середина Число «подозреваемых» чисел равно (правая граница — левая граница). Когда «подозреваемое» число останется одно, т. е. правая граница = левая граница + 1, достаточно будет сравнить его с искомым. Если же их не останется вовсе, т. е. левая граница = правая граница (так будет, если количество = 0), то нужного числа в таблице нет.

Осталось уточнить в алгоритме два места, записанных нами пока неформально.

«Подозреваемых» чисел больше одного» означает правая граница > левая граница + 1.

Выбрать число середина между левой и правой границами можно так: надо взять их полусумму и (на случай, если она окажется не целой) взять ближайшее к ней слева целое число (рис. 32).

При этом нам понадобится функция «ближайшее слева целое», которую будем обозначать целая часть (х).

Итак, получим окончательно такой алгоритм:

алг лит есть на складе (цел номер, цел количество, правая граница := количество + пока правая граница > левая граница + середина := целая часть ((левая граница + правая граница)/2) при номера [середина] номер:

при номера [середина] > номер:

правая граница := середина при левая граница = правая граница:

при левая граница.+ 1 = правая граница и номера [левая граница] = номер:

при левая граница + 1 = правая граница и номера [левая граница] номер:

кон Решив хранить таблицу номеров в порядке возрастания, мы должны изменить и алгоритмы «выдача» и «возврат»: их применение не должно нарушать упорядоченности элементов таблицы.

V. ПРОГРАММИРОВАНИЕ — ВТОРАЯ ГРАМОТНОСТЬ

Еще несколько лет назад сравнение программирования с грамотностью могло бы показаться неправомерным. Сейчас же, когда предмет «Основы информатики и вычислительной техники» изучают в каждой школе, такое сравнение поможет нам разобраться в том, какое место знание этого предмета занимает в общекультурном багаже современного человека и какую роль оно будет играть в будущем. Заметим, что мы используем слово «программирование» в широком смысле, понимая под ним общее умение использовать ЭВМ.

Программирование легче сравнивать с грамотностью, если вспомнить, что грамотность — это историческая категория, имеющая свое возникновение и развитие. СССР — страна практически сплошной грамотности: 15 лет назад грамотные у нас составляли 99,7% от общего числа населения в возрасте 9 лет и старше. 100 лет назад этот процент был чуть выше 20%.

Мы знаем, что и в основе грамотности, и в основе программирования лежит техническое изобретение — печатный станок и ЭВМ соответственно. Если развитие и распространение книгопечатания привели к всеобщей грамотности, то развитие и распространение ЭВМ приведут к всеобщему знанию основ программирования.

Несмотря на то, что возникновение книгопечатания и вычислительной техники разделено периодом в пять столетий, их сопоставление обнаруживает много сходства. И в том и в другом мы найдем «смену поколений», основанную на изменениях производственной базы и технологических процессов.

Приведем лишь некоторые данные, которые характеризуют темп, размах и взаимообусловленность развития книгопечатания и грамотности.

Появление первых изданий изобретателя печатного станка Иоганна Гутенберга датируется 1445 г. (латинская грамматика Элия Доната и др.), не прошло и 50 лет, а в мире уже работало свыше тысячи типографий, выпустивших около 10 млн. экземпляров книг.

Таким образом, почти мгновенно был превышен наличный фонд рукописных изданий. В 1962 г. во всем мире было напечатано 10 млрд. книг.

На рисунке 33 показана взаимозависимость между грамотностью и книгопечатанием в нашей стране за последнее столетие.

Если мы поверим в справедливость наших аналогий, то это даст нам некоторое представление о размахе и объеме работы, которую надо предпринять для подготовки встречи людей с миром ЭВМ.

Средства массовой информации, научно-популярные издания "и рекламные проспекты уже создали привычное видение вычислительной машины. Ее атрибуты — экран и клавиатура дисплея, бобины магнитных лент, кружево перфоленты, длинные бумажные полотна выдачи быстродействующих печатающих устройств, мигающие огоньки инженерного пульта, угловатые шкафы, забитые электронными деталями. Подобное представление о месте ЭВМ в жизни человека не только поверхностно, но и в чем-то ошибочно.

ЭВМ будущего — это прежде всего крошечный срез кристалла кремния, оправленный в миниатюрную рамку с паутиной тончайших проводов и встроенный в большинство промышленных изделий: от наручных часов и бытовых приборов до станков и космических кораблей.

Речь идет, конечно, о микропроцессорах, которые хотя и появились всего чуть больше десяти лет назад, но уже производятся десятками миллионов штук в год. Первое, наиболее заметное сейчас их применение — это выпуск самых разнообразных карманных калькуляторов. Но это лишь небольшая часть из всего многообразия применений микропроцессоров. Появление и развитие микропроцессоров — по мнению специалистов — самое революционное техническое новшество XX века: микроЭВМ, построенная на базе микропроцессора, работает со скоростью сотни тысяч операций в секунду, хранит в своей оперативной памяти десятки тысяч чисел (слов), способна обмениваться информацией с внешней памятью емкостью в сотни тысяч знаков, помещается в объеме спичечного коробка, требует для своего изготовления несколько человеко-часов и может производиться практически в неограниченных количествах.

Микропроцессор, встроенный в промышленное изделие, будь то бытовой прибор или средство производства, придает ему совершенно новые качества и сильно влияет на характер взаимодействия человека с этим изделием.

Не менее сильно включение микропроцессора в схему изделия влияет на способ его проектирования, во время которого должны быть замечены, осмыслены и реализованы новые возможности изделия.

Широкое применение микропроцессоров приводит к тому, что тысячи профессий меняют свое лицо. Миллионы людей — операторов производства, наладчиков, машинисток, банковских служащих, продавцов-контролеров, библиотекарей, монтажников, секретарей, сборщиков на конвейере — начинают работать на полностью переоборудованных рабочих местах.

Мы уже сейчас говорим о миллионах людей, вовлеченных в этот процесс, а в ближайшем будущем это коснется практически каждого человека, занятого в общественном производстве.

На пути этого лавинного развития возникает, однако, одно принципиальное препятствие. В настоящее время способность человека к передаче знания машине сильно отстает от возможности создать эту машину. Если затраты общественного труда на изготовление микропроцессора и микроЭВМ исчисляются в человеко-часах, то затраты на создание программного обеспечения до сих пор выражаются в человеко-месяцах и человекогодах.

На рисунке 34 приведена кривая, показывающая динамику отношения стоимости программ к стоимости оборудования при проектировании систем обработки информации.

Специалисты по программированию напряженно работают над тем, чтобы сделать труд программиста гораздо более производительным. Однако даже если им удастся создать необходимые условия для десятикратного увеличения производительности труда при традиционном процессе создания программ, то и тогда, как показывают элементарные расчеты, примерно через двадцать лет придется посадить за программирование чуть ли не все взрослое население земного шара для того, чтобы обеспечить программами все производимые микропроцессоры.

Фантасты, которые силой своего воображения уже побывали в XXI в., утверждают, что в будущем человека, не знающего точных наук, с полным правом можно будет сравнить с неграмотным средневековым бароном, который с гордостью говорил, что счетом и письмом у него занимаются секретари.

То же должно случиться и с программированием. Каждый специалист, в какой бы области науки, производства и т. д. он ни работал, должен будет уметь эффективно использовать ЭВМ, уметь программировать, что и называется второй грамотностью.

Итак, мы переходим от мира машин к миру программ.

Герой Мольера, месье Журден, был в высшей степени удивлен, когда узнал, что всю жизнь говорил прозой, не подозревая этого. Благодаря появлению ЭВМ и вызванному этим возникновению вычислительной науки человечество оказывается в положении месье Журдена, с удивлением обнаруживая, что оно живет в мире программ.

Да, мы живем в мире программ и сами постоянно программируем, не сознавая этого.

Несомненно, что одно из самых выдающихся достижений биологической науки XX в.— это открытие того, что развитие организма есть исполнение генетической программы, записанной в его генном наборе. Заметим, что использование здесь программистских терминов «исполнение» и «программа» не является метафорой, а выражает суть внутриклеточных процессов роста и развития, по отношению к которым молекулярные структуры и химические процессы — своего рода элементная база и способ реализации команд.

Можно сказать, что очень многие физиологические процессы, происходящие в нашем организме,— это огромная, тщательно отлаженная и сложно устроенная библиотека программ. Анализ структуры программ этой библиотеки и их информационных связей позволяет делать выводы о состоянии организма в настоящее время и прогнозировать его поведение в будущем.

Практически весь производственный процесс на любом предприятии— это работа по программам. Причем эффективность производственного процесса зависит от степени отлаженности этих программ.

Даже если процесс включает элемент случайности, таковы, например, охота или вождение автомашины, то случайность и непредсказуемость сказываются лишь на выстраивании цепочки ситуаций, но не на реакции на эти ситуации, которая почти всегда выполняется по заранее разученной программе.

Наконец, обучение, т. е. приобретение знаний, это тоже работа по определенной программе. Действительно, ребенок научается что-то делать только после того, как он понимает, как это делается. Только после выработки такого понимания повторительная тренировка достигает успеха. Заметим, что это касается не только программ, представляющих собой цепочки логических реакций на заранее известные воздействия, но и программ, исполняемых человеком в процессе сложных движений в спорте, музыке, играх и т. д.

Повседневная жизнь человека — это во многом тоже деятельность по программам.

Каждый человек, придерживающийся режима, с гордостью чувствует себя программистом. Вспомните свои утренние часы, начиная от звонка будильника и кончая выходом из дома. Эти часы заполнены до предела привычными утренними процедурами: уборка постели, умывание и т. д. Поразмышляйте над процедурой уборки квартиры, и вы увидите, что она не проста. Разработка эффективной программы уборки сделает честь любому профессиональному программисту.

Таким образом, мир программ это далеко не только начинка памяти ЭВМ. Это прежде всего огромный запас операционного знания, накопленный человечеством и теперь лишь актуализируемый вычислительными машинами, роботами, автоматическими устройствами. Еще больший запас программ хранится в генофонде всего живого: его актуализация в значительной степени составляет предмет биологии и ее новых разделов, включая генную инженерию.

Итак, мы стоим на пороге практически беспредельного развития и распространения электронно-вычислительной техники в обществе. Машина становится «партнером» практически во всех сферах деятельности человека, освобождая его от рутинных работ и усиливая его интеллект.

Существенным ускорителем этого процесса развития человеческого интеллекта должны быть законы обработки информации, способы перехода от знания к действию, способность строить программы, рассуждать о них и предвидеть результаты их исполнения. Сумма знаний по этим вопросам должна стать фундаментальной компонентой общего образования — второй грамотностью — каждого члена общества.

В Политическом докладе Центрального Комитета КПСС XXVII съезду Генеральный секретарь ЦК КПСС М. С. Горбачев отметил:

«Интересы дела требуют более глубоко поставить изучение научных основ современного производства, ведущих направлений его интенсификации. И что особенно неотложно, обеспечить компьютерную грамотность учащихся» (Правда.— 1986.— 26 февр.).

СОДЕРЖАНИЕ

Раздел I. Устройство ЭВМ § 1. Общая схема устройства ЭВМ § 2. Основной алгоритм работы процессора § 3. Команда ветвления и команда повторения § 4. Представление информации в ЭВМ § 5. Физические принципы работы ЭВМ Раздел II. Знакомство с программированием § 7. Команда повторения с параметром § 8. Вспомогательные алгоритмы вычисления значений функций §9. Алгоритмы работы с литерными величинами § 10. Запись алгоритмов в виде процедур на Рапире § 11. Запись алгоритмов вычисления значений функций на Рапире § 14. Общие сведения о языке Бейсик Раздел III. Роль ЭВМ в современном обществе. Перспективы развития вычислительной техники § 16. Краткая история вычислительной техники § 17. Программное обеспечение ЭВМ Упражнения для повторения I. Основные конструкции алгоритмического языка II. Библиотека алгоритмов III. Дополнительные сведения об устройстве ЭВМ IV. Алгоритмы поиска информации V. Программирование—вторая грамотность

ОСНОВЫ ИНФОРМАТИКИ

И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ

Сдано в набор 23.01.86. Подписано к печати 19.02.86. Формат 60X90'/i6- Бумага офсетная № 2.

Гарнитура литературная. Печать офсетная. Усл. печ. л. 9 4 форзац 0,25. Усл. кр.-отт. 18,69. Уч.-изд. л.

6,94 + форзац 0,4. Тираж 4 000 000 (1 — 1 700 000) экз. Заказ № 1210. Цена 45 коп.

Ордена Трудового Красного Знамени издательство «Просвещение» Государственного комитета РСФСР по делам издательств, полиграфии и книжной торговли. 129846, Москва, 3-й проезд Марьиной рощи, 41. Отпечатано с диапозитивов ордена Трудового Красного Знамени фабрики «Детская книга» № 1 Росглавполиграфпрома Государственного комитета РСФСР по делам издательств, полиграфии и книжной торговли на Смоленском полиграфкомбинате Росглавполиграфпрома Государственного комитета РСФСР по делам издательств, полиграфии и книжной торговли. Смоленск, 20, ул. Смольянинова, 1.