[ «ОСНОВЫ ИНФОРМАТИКИ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ ПРОБНОЕ УЧЕБНОЕ ПОСОБИЕ для средних учебных заведений В двух частях • ЧАСТЬ ВТОРАЯ Под редакцией А. П. Ершова и В. М. Монахова Рекомендовано Управлением информатики и ...»
Английское слово WHILE означает пока. Работает эта команда так: проверяется условие, стоящее после WHILE. Если оно соблюдается, то выполняются все команды, стоящие после слова WHILE, но до слова WEND, играющего ту же роль, что и кц в алгоритмическом языке. После этого снова проверяется условие. Как только выяснится, что условие не соблюдается, выполнение команды WHILE закончится и начнется выполнение команды, следующей за WEND.
Второй тип команды повторения аналогичен команде повторения с параметром и выглядит следующим образом:
10 DIM A(10) 15 B% = 20 FOR I% = 0 TO B% 30 A(I%)= 40 NEXT 1% Эта программа делает то же самое, что и предыдущая. Приведенная в программе команда работает так же, как и команда повторения с параметром в алгоритмическом языке: переменная 1% меняется последовательно с шагом 1 от 0 до В% и для каждого значения 1% выполняются команды, стоящие между FOR и NEXT. (Перевод английских слов FOR, TO и NEXT такой: для, до, следующий.) После слова NEXT можно указывать имя параметра.
Как и в алгоритмическом языке, значение параметра может изменяться с шагом, отличным от 1. Для этого используется служебное слово STEP (шаг). Например, запись означает, что шаг изменения переменной 1% равен 2.
3. Команда обращения к подпрограмме — GOSUB. Это слово происходит от двух английских слов go — идти, subroutine — подпрограмма. Команда позволяет перейти к исполнению программы с той строки, номер которой указан в команде. Как только первый раз после выполнения команды GOSUB встретится команда RETURN (вернуться), исполнение программы продолжится со строки, следующей за командой GOSUB. Рассмотрим следующий пример:
10 IF у$ = "да" THEN GOSUB 100 ELSE GOSUB 20 PRINT name$ 25 PRINT age 100 name$ = "ВОЗРАСТ КОЛИ" 110 age = 120 RETURN 130 name$ = "ВОЗРАСТ ПЕТИ" 140 age = 150 RETURN Если при исполнении этой программы значение литерной переменной у$ окажется равным "да", то будет выполнена команда GOSUB 100. Произойдет переход к строке 100, переменная name| получит значение "ВОЗРАСТ КОЛИ", а переменная age — значение 12.
После этого команда RETURN (в строке 120) вернет нас на строку 20 и на экране появится
ВОЗРАСТ КОЛИ
На этом исполнение закончится (в строке 30 стоит команда END).Если же у$ "да", то на экране появится
ВОЗРАСТ ПЕТИ
Команда END (конец) — команда окончания исполнения программы.Команда REM позволяет вносить в текст Бейсик-программы комментарии: любой текст от слова REM (от английского слова remark — пояснение) до конца строки игнорируется во время исполнения программы.
Например, в предыдущую программу можно добавить строку 4. Команды ввода-вывода. Мы познакомились с командами языка Бейсик, похожими на те, которые уже встречались при изучении алгоритмического языка.
Теперь перейдем к командам вывода информации на экран и приема данных с клавиатуры. Именно команды ввода-вывода позволяют писать программы, «ведущие диалог с человеком».
Команда PRINT используется для вывода на экран цифровой и буквенной информации. Она уже встречалась в наших примерах (см. с. 71).
Команда INPUT позволяет приостановить исполнение программы и ввести с клавиатуры значения переменных, имена которых следуют за командой INPUT. Например, команда позволяет ввести два вещественных числа, одно целое и одну литерную величину, сделав их значениями переменных величин А, В, N% и ТЕХТ$.
Следующая программа 10 INPUT А, В, С 20 PRINT А + В + С 30 END напечатает на экране сумму трех введенных с клавиатуры чисел.
1. Какой тип имеют величины a, b, c%, d%?
2. Приведите примеры переменных: а) целого; б) вещественного; в) литерного типа.
3. Какой тип имеют константы 2; 3; 2.0; "константа"; "целое"?
4. Приведите примеры констант: а) целого; б) вещественного; в) литерного типа.
1. Напишите на Бейсике программу, в которой используется по крайней мере один раз каждая из указанных команд:
а) присваивания;
в) повторения WHILE — WEND;
г) повторения FOR — NEXT;
д) ввода данных INPUT.
Результат работы программы должен быть выведен на дисплей с помощью команды PRINT. Поясните, что делает ваша программа.
2. Что появится на экране после исполнения такой программы?
10 А = 20 В = 30 IF A > В THEN C = A ELSE C = B 40 PRINT А, В, С 3. Напишите программу, которая вводит с клавиатуры два числа и выводит на экран их произведение.
4. Напишите программу, которая вводит с клавиатуры два числа и выводит на экран большее из них.
5. Напишите программу, которая вводит с клавиатуры два числа и выводит на экран разность между большим и меньшим.
РОЛЬ ЭВМ В СОВРЕМЕННОМ ОБЩЕСТВЕ.
ПЕРСПЕКТИВЫ РАЗВИТИЯ
ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ
§16. КРАТКАЯ ИСТОРИЯ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ
Возникновение электронных вычислительных машин. Еще в XVII в. в связи с бурным развитием мореплавания и астрономии появилась потребность в быстром и точном составлении различных математических таблиц, в том числе таблиц синусов, логарифмов, квадратных корней и др. Возникла мысль создать устройство, облегчающее проведение арифметических операций над большим количеством чисел.В 1642 г. французский ученый Б. Паскаль сконструировал первый механический вычислитель, позволяющий складывать и вычитать числа. В 1673 г. немецкий ученый Г.
Лейбниц разработал счетное устройство, в котором использовал механизм, известный под названием «колеса Лейбница». Его счетная машина выполняла не только сложение и вычитание, но и умножение и деление. Механические счетные машины — арифмометры — с видоизмененными «колесами Лейбница» использовались до середины нашего столетия, пока не были вытеснены электрическими цифровыми вычислителями, а впоследствии современными электронными калькуляторами.
В середине 30-х годов XIX столетия английский математик Ч. Беббидж предложил структуру автоматического вычислителя, названного им «аналитической машиной», состоящего из двух отдельных устройств: устройства хранения, где находятся команды и данные, введенные в машину, и перерабатывающего устройства (процессора), которое выполняет операции, пользуясь находящимися в памяти командами и данными. Самому автору реализовать идею «аналитической машины» не удалось.
В начале 40-х годов XX в. болгарский инженер Д. Атанасов и американский ученый Д. Моучли предложили использовать радиолампы для выполнения вычислений, предполагая тем самым полностью исключить механические узлы компьютера.
Первая вычислительная матица, полностью реализующая эту идею, была создана в США в 1946 г. Она получила название ЭНИАК — по первым буквам полного английского названия, которое по-русски выглядит как «электронный числовой интегратор и вычислитель». Именно с этого времени начинается эра электронных вычислительных машин.
Прошло, однако, еще несколько лет, пока не сложились основные принципы устройства, или, как говорят, архитектура современных ЭВМ. Эти принципы были обоснованы выдающимся математиком Дж. фон Нейманом в 1946 г. Первая ЭВМ, основанная на этих принципах, — ЭДСАК была создана в Англии в 1949 г. ученым и конструктором М.
Уилксом.
Первая советская электронная вычислительная машина (получившая впоследствии название МЭСМ — малая электронная счетная машина) была создана в 1949 г. в Киеве, а еще через три года, в 1952 г., в Москве вошла в строй машина БЭСМ (быстродействующая электронная счетная машина). Обе машины были созданы под руководством выдающегося советского ученого Сергея Алексеевича Лебедева (1902-1974), основоположника советской электронной вычислительной техники.
Поколения ЭВМ. Компьютер состоит из очень большого числа электронных компонент, имеющих самые простые функции. Различных простейших функций совсем немного.
Эти функции элементов компьютера за истекшие 35-40 лет почти не изменялись, в то время как их физическое устройство менялось очень сильно. Каждый этап развития компьютеров определялся совокупностью элементов, из которых строились компьютеры, — элементной базой.
С изменением элементной базы ЭВМ значительно изменялись характеристики, внешний вид и возможности компьютеров.
Ни одно техническое устройство, изобретенное человеком до сих пор, не развивалось так стремительно, как электронные вычислительные машины. Каждые 10-12 лет происходил резкий скачок в конструкции и способах производства ЭВМ. Появляющиеся в результате такого скачка новые модели ЭВМ быстро вытесняли старые, при этом область применения ЭВМ постоянно расширялась.
Именно поэтому уместно говорить о поколениях ЭВМ, сменявших друг друга в ходе общего развития вычислительной техники.
Итак, в основе смены поколений вычислительной техники лежит смена элементной базы ЭВМ. Появление новой элементной базы, в свою очередь, обычно связано с прогрессом в области физики и химии, который приводит к открытию новых принципов работы компонент ЭВМ, новых свойств материалов и новых способов производства.
Смена элементной базы требует полной перестройки заводов, производящих вычислительную технику, разработки новых технологических линий, станков и другого оборудования. Поэтому такая смена оправдана лишь тогда, когда переход на новую элементную базу существенно улучшает характеристики вычислительной техники.
Естественно, что смена поколений заключалась не только в обновлении элементной базы. С каждым новым поколением в практику применения ЭВМ входили новые, способы решения задач и новые компоненты программного обеспечения.
В настоящее время основу вычислительной техники составляют ЭВМ третьего и четвертого поколений и ведутся экспериментальные разработки машин пятого поколения.
В ЭВМ п е р в о г о п о к о л е н и я все элементы электронных схем изготовлялись в виде отдельных деталей. Важнейшими среди них были вакуумные электронные лампы, которые сейчас еще можно увидеть в телевизорах и старых радиоприемниках. Несколько таких ламп устанавливалось на металлической панели — шасси, которое вставлялось в корпус ЭВМ. На этом же шасси укреплялись и другие элементы схемы.
Сама ЭВМ имела вид большого количества металлических шкафов (стоек), сплошь заполненных шасси с электронными лампами. Машины первого поколения занимали громадные залы, весили сотни тонн и расходовали сотни киловатт электроэнергии.
Появление ЭВМ в т о р о г о п о к о л е н и я стало возможным благодаря изобретению транзисторов. Резкое уменьшение размеров транзисторов по сравнению с радиолампами позволило делать блоки ЭВМ в виде так называемых печатных плат. Такая плата представляет собой пластмассовую пластинку, на которую с одной ее стороны вставляются и припаиваются транзисторы и другие элементы, а с другой стороны прямо на поверхности располагаются проводники в виде металлических полосок, соединяющих элементы схемы.
Использование транзисторов и печатных плат позволило частично автоматизировать производство ЭВМ и значительно сократить их размеры и потребление энергии.
Основу ЭВМ т р е т ь е г о п о к о л е н и я составляют так называемые интегральные схемы. Элементы компьютеров предыдущих поколений производились в виде отдельных деталей и лишь потом соединялись друг с другом, образуя нужную схему.
Исследования в области физики и химии показали, что схемы можно формировать на небольшом участке пластинки из чистого кристаллического кремния, нанося на этот участок в нужной комбинации тончайшие пленки разных веществ. Формирование элементов можно осуществлять сразу на многих участках пластинки.
Такая схема, имеющая вид многослойной пленки веществ, нанесенных на кристаллы кремния, получила название интегральной схемы. Уже в первых интегральных схемах на одном кристалле размещалось до сотни элементов.
Изобретение интегральных схем открыло перспективы дальнейшего развития элементной базы ЭВМ, которые до сих пор далеко не исчерпаны. Сразу резко повысился уровень надежности электронных схем при столь же резком падении их стоимости благодаря уменьшению размеров и, главное, автоматизации их проектирования и производства.
Ступени прогресса в разработке интегральных схем стали измеряться количеством элементов, которые можно разместить на одном кристалле кремния стандартных размеров. В ЭВМ третьего поколения применялись интегральные схемы, содержащие более тысячи элементов на одном кристалле.
ЭВМ ч е т в е р т о г о п о к о л е н и я используют большие интегральные схемы (БИС), в которых количество переключательных элементов на кристалле кремния равно десяткам тысяч. Замечательным достижением XX в. стало создание процессора ЭВМ, который целиком размещается на одном кристалле кремния. Такие однокристальные процессоры получили название микропроцессоров. В результате на одной плате оказалось возможным разместить электронные схемы всех устройств ЭВМ, а саму ЭВМ, которая еще двадцать лет назад занимала большой зал, сделать по габаритам и по стоимости доступной для индивидуального применения на рабочем месте пользователя. Так появились персональные ЭВМ, а также карманные и настольные микрокалькуляторы. Итак, мы видим, что развитие технологии производства ЭВМ позволяет сделать компьютер с заданными вычислительными ресурсами все более и более дешевыми доступным.
В настоящее время появляется возможность изготавливать «супер-ЭВМ», рекордные по скорости работы, объему памяти и т. п. Такие ЭВМ изготавливаются на самой современной элементной базе, выпускаются в небольшом количестве и очень дороги, но они незаменимы во многих областях науки и техники.
Одним из основных направлений экономического и социального развития СССР на период до 2000 года является всемерное ускорение научно-технического прогресса, повсеместное применение его результатов в производстве и управлении, сфере обслуживания и в быту. Катализатором научно-технического прогресса является использование вычислительной техники. Именно поэтому перед нашей страной в нынешней пятилетке стоит задача ускоренного развития выпуска средств автоматизации инженерного труда, малых ЭВМ высокой производительности и персональных ЭВМ.
Мы уже говорили, что за несколько десятков лет, прошедших со времени изобретения компьютеров, они стали в тысячи раз производительнее и в тысячи раз дешевле.
Возможность такого быстрого развития связана с тем, что компьютер, в отличие от других машин, является устройством для обработки информации.
Поясним сказанное. Можем ли мы надеяться, что через несколько лет автомобиль станет в десять раз меньше по размеру? Нет, конечно: ведь тогда человек в него просто не поместится. Размеры и другие параметры автомобиля тесно связаны со свойствами окружающего мира, в котором он должен работать. Размеры же компьютера никак не связаны с его функциями по переработке информации и определяются лишь технологией производства, которая все время совершенствуется.
Это привело к тому, что уже сейчас затраты на изготовление компьютера невелики по сравнению с затратами на разработку программ. Это парадоксально. Ведь разработать программы нужно всего лишь раз, а потом их можно почти без затрат копировать в любом количестве экземпляров. В то же время каждый экземпляр компьютера нужно сделать заново. Тем не менее даже после деления на число выпускаемых компьютеров данного типа затраты на разработку программ остаются весьма значительными.
Такое развитие привело к изменениям во взглядах на соотношение аппаратуры компьютера и программ. Если раньше считалось, что задача программистов — наиболее полно использовать все возможности аппаратуры, то теперь стало ясно, что аппаратура компьютера должна максимально облегчать главную задачу — разработку программ. Если раньше программы предназначались для управления машинами, то теперь машины предназначаются для исполнения программ. Это приводит к повышению роли науки программирования в индустрии информатики.
Как мы уже знаем, ЭВМ не может работать без программы. Только поместив программу в память ЭВМ, можно заставить ее сделать что-нибудь полезное. Сменив программу в памяти ЭВМ, можно переключить ЭВМ с одной работы на другую. Именно благодаря этой особенности одни и те же ЭВМ могут применяться в разных областях человеческой деятельности. Сфера применения конкретной ЭВМ определяется набором созданных для нее программ. Этот набор называется программным обеспечением. Программное обеспечение современных ЭВМ включает десятки и сотни тысяч программ: от широко распространенных компьютерных игр и программ обработки текстов до программ специального назначения (например, программ расчета ядерных реакторов).
Рассмотрим различные применения ЭВМ и тем самым различные виды программного обеспечения.
Обработка текстов. Одно из наиболее распространенных применений компьютеров, особенно персональных,— обработка текстов. Всем нам время от времени приходится писать какие-то тексты — письма друзьям, школьные сочинения, заметки в стенгазету и т. д. Многие профессии связаны с обработкой и подготовкой большого количества текстов. Это приходится делать инженеру и служащему, писателю и программисту. Нет особого смысла использовать сейчас компьютер для писания писем своим близким — проще написать их от руки. Однако в будущем, когда компьютеры появятся в каждой семье и будут соединены друг с другом в сеть (как сейчас телефоны), может оказаться удобным быстро передать по такой сети подготовленный на компьютере текст и не прибегать к услугам почты.
Уже сегодня компьютер оказывается неоценимым помощником при оперативной профессиональной обработке текстов, например в редакциях газет. Удобен компьютер и при тщательной подготовке текстов большого объема, например книг. Сейчас книга обычно готовится так. Автор отдает рукопись книги машинистке для перепечатки. После этого он дает читать перепечатанную рукопись рецензенту, редактору и другим специалистам. Их замечания обычно требуют изменений в тексте. Эти изменения нужно аккуратно сделать во всех экземплярах. Когда, наконец, все поправки сделаны, книга отдается в типографию, наборщик садится за клавиатуру наборной машины и буква за буквой набирает текст (неизбежно допуская при этом некоторое количество ошибок).
Применение ЭВМ позволяет в корне упростить и ускорить описанную работу. Для этого необходимо заменить пишущую машинку компьютером и вместо печатания на машинке вводить текст в компьютер в помощью специальной программы — редактора текстов. С введенным в ЭВМ текстом легко работать: его можно напечатать в любом количестве экземпляров (для рецензента, редактора и т. п.), в него можно вносить изменения и улучшения. Наконец, гибкий диск с записанным на нем окончательным текстом книги можно поместить в установленный в типографии компьютер, который соединен с фотонаборной машиной, и сделать набор автоматически, с помощью ЭВМ.
Такая технология в последнее время находит все большее распространение. При ее применении отпадает необходимость в корректорах, сверяющих набранный текст книги с рукописью автора, облегчается исправление замеченных ошибок, уменьшается количество опечаток и т. д.
Как же выглядит работа с редактором текстов? Работая над рукописью с помощью такой программы, мы видим на экране дисплея текст, или, точнее, ту его часть, которая умещается на экране.
Нажимая специальные клавиши, можно осмотреть любой интересующий нас фрагмент текста. Можно впечатать в любое место текста любую букву (вместо той, которая была в этом месте раньше) и таким образом исправить опечатку, заменить неудачно выбранное слово другим, вставить в любое место текста новые слова, строчки и т.д..
Программы текстовой обработки составляют сейчас наиболее часто используемые программы для микрокомпьютеров.
Языки программирования. Работа ЭВМ состоит в исполнении программы, состоящей из размещенных в памяти ЭВМ машинных команд. Однако создать вручную текст на машинном языке очень сложно, Гораздо проще записать алгоритм на алгоритмическом языке и «научить» ЭВМ исполнять программы, написанные на алгоритмическом языке или на языке, близком к нему. Таких языков сейчас существует много, и называются они языками программирования.
Один из языков программирования — Фортран (от англ. Formula Translator — переводчик формул) был создан в конце 50-х годов и получил широкое распространение. Он был предназначен для программирования научно-технических расчетов. Другой язык, оказавший большое влияние на развитие информатики, — Алгол-60 (от англ. Algorithmic — алгоритм и Language — язык, его название отражает дату создания — 1960 г.) послужил основой для разработки многих языков, например языка Паскаль (назван в честь ученого Б. Паскаля), который является одним из наиболее распространенных языков программирования для микрокомпьютеров.
Число относительно широко используемых языков программирования в настоящее время исчисляется десятками, а общее их число — тысячами. Существуют узкоспециализированные языки, скажем для программирования определенного вида технологических процессов, и более универсальные. Развитие и распространение языков программирования, как и вообще всего программного обеспечения, происходит медленнее, чем развитие элементной базы ЭВМ. Для того чтобы новый язык программирования получил широкое распространение, нужно, чтобы его выучило достаточное количество программистов, чтобы на этом языке было написано достаточно большое количество программ и т. п.
Существуют два типа программ-переводчиков с языка программирования на машинный язык. Они называются компиляторами и интерпретаторами. Программакомпилятор читает текст на языке программирования от начала и до конца, создавая эквивалентную программу на машинном языке. Интерпретатор читает исходную программу по частям, сразу выполняя соответствующие действия. Разницу между использованием компиляторов и интерпретаторов можно пояснить таким сравнением. Если у нас имеется книга на малознакомом нам языке, можно поступить двояко. Можно перевести ее целиком и в дальнейшем пользоваться только переводом. Этот способ соответствует действиям компилятора. А можно пользоваться книгой в оригинале, переводя только нужную ее часть по мере надобности. При этом нам придется переводить кое-какие места много раз, если они нам многократно понадобятся (ведь результаты перевода не запоминаются). Зато другие разделы, которые не понадобятся ни разу, не придется переводить вовсе. Этот вариант соответствует применению интерпретатора.
И компиляторы, и интерпретаторы имеют и преимущества, и недостатки. Из упоминавшихся языков программирования Фортран, Алгол-60, Паскаль обычно компилируются, а Бейсик и Рапира — интерпретируются (хотя это и необязательно: существуют и интерпретаторы для Паскаля, и компиляторы для Бейсика).
Автоматизация труда программиста. Использование ЭВМ позволяет повысить производительность труда в любой области человеческой деятельности. Не является исключением и труд программиста.
На заре программирования программы составлялись в машинных кодах, записывались на бумаге и вручную заносились в память ЭВМ. Позже появились специальные устройства, позволяющие вводить в память ЭВМ информацию, закодированную с помощью отверстий на специальных тонких картонных карточках — перфокартах. Это облегчило работу по вводу программы в память ЭВМ. Появление программ-компиляторов и программ-интерпретаторов избавило программистов от необходимости работать в машинных кодах и коренным образом повысило производительность их труда. Программы, однако, по-прежнему писались на бумаге, а затем пробивались на перфокартах. Следующим шагом в повышении производительности труда программистов стало использование текстовых редакторов для подготовки текстов программ сразу на ЭВМ.
Если при этом используется компилятор, то общая схема работы оказывается такой: (1) человек вводит в память ЭВМ текст программы на языке программирования с помощью текстового редактора; (2) подготовленный текст обрабатывается компилятором, который проверяет, не нарушены ли правила записи программ на данном языке, и, если все правильно, создает программу в машинных кодах; (3) эта программа в машинных кодах исполняется на ЭВМ. Если на этапе (2) или (3) в программе обнаруживается ошибка, то все приходится повторять заново. Для сложных программ такой цикл приходится повторять многократно.
Следующий этап повышения производительности труда программиста — использование вместо редактора текстов так называемого редактора программ, учитывающего правила записи программ на используемом языке программирования. Например, редакторы программ на языке Бейсик, как правило, могут автоматически нумеровать строчки программы и вставлять в текст программы служебные слова при нажатии на одну кнопку клавиатуры. Это убыстряет ввод текста программы и избавляет от ошибок в записи служебных слов.
Редактор программ можно совместить с компилятором или интерпретатором. В этом случае ЭВМ сможет проверять правильность программы по мере ее ввода человеком.
Такой редактор программ может, кроме того, при нажатии на специальные клавиши формировать не только служебные слова, но и целые конструкции языка, делая невозможными ошибки в записи этих конструкций.
Приведем примеры работы редактора программ для алгоритмического языка.
При создании новой программы при нажатии на специальную кнопку клавиатуры на экране дисплея появляется конструкция «алгоритм», т. е. должным образом расположенные служебные слова АЛГ, АРГ, РЕЗ, НАЧ, КОН (рис. 22). Курсор (маленький прямоугольник) устанавливается после слова АЛГ, как бы приглашая человека ввести имя алгоритма. Если в процессе составления алгоритма человек нарушит правила алгоритмического языка, то редактор программ поможет человеку немедленно обнаружить и исправить ошибку. Пусть, например, при составлении алгоритма КВУР человек забыл написать знак умножения между А и С в формуле для дискриминанта. Тогда редактор программ воспримет АС как имя переменной величины, а так как правила алгоритмического языка требуют, чтобы тип любой величины был описан, то редактор программ сообщит на полях справа, что величина с именем АС не описана, и установит курсор под этой ошибкой (рис.
23). После того как человек вставит между А и С знак умножения, сообщение об ошибке исчезнет.
Редактор программ может и исполнять их, показывая в ходе их исполнения на полях программы результаты проверок условий и выполнения операций присваивания. На рисунке 24 изображен результат исполнения программы вычисления первых 60 простых чисел: видно, что 60-е простое число (результат присваивания "П[ЧИСЛО_ПРОСТЫХ] := К") равно 281.
Существуют и другие способы автоматизации труда программиста. Самый радикальный — вообще избавить программиста от необходимости явно описывать в программе последовательность действий. Достаточно описать (на специальном языке), что должна сделать программа, а не как это она должна делать. Такие языки называются непроцедурными языками программирования.
Операционная система. Мы уже знаем, что перед исполнением программы, написанной на языке машинных команд, необходимо разместить ее в памяти ЭВМ и поместить в Счетчик Команд процессора адрес первой команды программы. На одной и той же ЭВМ обычно исполняют много разных программ. Эти программы хранят во внешней памяти ЭВМ — чаще всего на диске. Следовательно, необходима специальная программазагрузчик, которая найдет нужную нам программу на диске, скопирует («загрузит») ее в память ЭВМ и установит начальное значение Счетчика Команд. Если наша программа использует вспомогательные алгоритмы (подпрограммы), то их также надо найти и поместить в память ЭВМ.
Большинство программ использует внешние устройства ЭВМ: дисплей, клавиатуру, диски и др. При управлении ими в разных программах постоянно приходится повторять одни и те же последовательности действий. Эти часто встречающиеся действия можно записать в виде специальных вспомогательных подпрограмм для работы с внешними устройствами.
Во внешней памяти ЭВМ (на диске) могут храниться не только машинные программы, но и другая информация. Порция информации, хранящаяся во внешней памяти, называется файлом. Для организации записи, хранения, поиска и считывания файлов используется комплекс специальных программ, который называется файловой системой.
Поскольку быстродействие ЭВМ велико, то она может одновременно делать несколько дел. Например, она может одновременно печатать текст на печатающем устройстве, выяснять, сколько свободного места осталось на диске, и обрабатывать символы, набираемые человеком на клавиатуре. Каждое такое «дело» называется процессом. Для организации параллельного (одновременного) выполнения нескольких процессов также нужны специальные управляющие программы.
Итак, для любой работы на ЭВМ нужен целый комплекс специальных вспомогательных программ (как перечисленных выше, так и многих других). Этот комплекс программ называется операционной системой и входит в так называемое базовое программное обеспечение ЭВМ.
Прикладные программы для научно-технических расчетов. Покажем работу таких программ на примере программы-решателя задач на треугольники.
Из курса математики известны следующие соотношения между элементами треугольника (рис. 25):
Используя эти соотношения, программа-решатель задач позволяет найти одни элементы треугольника, если известны другие. Пусть, например, известны площадь S, высоты ha и hb треугольника. Требуется найти стороны а и b, угол.
Получив такого рода условие, программа пытается найти цепочку равенств из числа соотношений (1)-(7), ведущую от известных величин к искомым.
Предполагается, что из каждого равенства можно выражать одну из входящих в него величин через остальные. Например, из равенства (6) вытекает, что При поиске цепочки равенств, ведущих от аргументов задачи к ее результатам, возникает задача типа поиска пути в лабиринте, игры в домино или отгадывания головоломки.
В нашем примере требуемая цепочка может быть такойиз (4): а по S и ha, В ряде случаев получение из уравнения явных формул, выражающих одну величину через другие, может быть выполнено программой автоматически. В более трудных случаях соответствующие явные формулы и реализующие их алгоритмы находятся разработчиками заблаговременно.
При решении нашей задачи ЭВМ согласно найденной цепочке уравнений автоматически выстраивает и затем исполняет следующую программу решения поставленной задачи:
Информационные системы. Задачи, решаемые такими системами, поясним на примере библиотеки. Каждая библиотека имеет каталог. Этот каталог состоит из большого числа ящиков, заполненных карточками. Каждая карточка содержит информацию об одной из книг: кто ее автор, как она называется, в каком году издана и т. д. Наконец, на карточке указан «адрес» книги — в каком шкафу и на какой полке эту книгу следует искать. Обращаясь к библиотекарю, читатель должен назвать ему этот адрес — иначе библиотекарь не сможет найти нужную книгу среди множества книг библиотеки.
Если бы карточки стояли в беспорядке, то найти карточку интересующей нас книги было бы практически невозможно. Поэтому их располагают в алфавитном порядке по фамилиям авторов — вначале идут книги, авторы которых имеют фамилии, начинающиеся на Д, затем — на Б, после них — на В и так далее. Это позволяет найти нужную книгу (точнее, ее карточку) довольно быстро — конечно, в том случае, если мы знаем фамилию ее автора. А что делать, если фамилия автора нам неизвестна, а известно только название книги? Приходится заводить еще одну картотеку, где карточки расположены в алфавитном порядке названий. А если у книги два автора? Вероятно, нужно включить эту карточку в алфавитный каталог дважды — по фамилии каждого из авторов. Уже из сказанного видно, что работа по составлению и поддержанию в рабочем состоянии библиотечного каталога связана с огромным количеством проблем, причем о многих из них мы даже и не упоминаем. (Что делать, если карточка из картотеки потеряна? Что делать, если книга отдана на некоторое время в переплет и на это время читателям недоступна? Что делать, если из-за переезда библиотеки расположение книг в шкафах изменилось?) В решении этих проблем существенную помощь может оказать компьютер, а также специальная программа, которая организует хранение в памяти компьютера сведений о всех книгах библиотеки и позволяет читателям получать необходимые им сведения. Например, такая программа должна уметь выдавать список всех книг данного автора или всех книг с данным названием (если их много). Хорошо бы даже, чтобы она могла, например, выдать список всех книг, в названии которых есть слово «зубофрезерование» или слова «мелиорация болот». Кроме выполнения такого рода запросов, программа должна позволять работникам библиотеки вносить изменения в информацию, хранящуюся в памяти компьютера (например, регистрировать приобретаемые книги).
Такая программа может создать много удобств читателям и работникам библиотеки. Например, читателям уже не понадобится переписывать сведения об интересующей их книге на отдельный листок и нести его библиотекарю. Достаточно будет, выбрав нужное название книги на экране дисплея, нажать специальную клавишу — и заказ на эту книгу будет принят. Но есть и много опасностей, которые могут сделать эксплуатацию такой компьютерной программы бесполезной и даже вредной. Что, если в какой-то момент из-за неполадок в аппаратуре, или ошибки в программе, или просто из-за плохого качества компьютера список книг библиотеки будет утрачен? Что, если дисплеев для читателей окажется слишком мало и за простейшей справкой придется стоять в очереди? Что, если программа окажется неудобной и читатели будут ежесекундно звать сотрудников библиотеки, требуя научить пользоваться программой? Потенциальные опасности тут столь же велики, как и потенциальные выгоды. Таким образом, внедрение информационных систем требует всестороннего предварительного анализа и решения возникающих проблем.
До сих пор мы предполагали, что сами книги и способ их хранения остаются прежними, а компьютеры применяются лишь в качестве информационно-справочной службы.
В будущем может оказаться выгодным хранить книги не напечатанными на бумаге, а записанными в памяти машины. Тогда пользование библиотекой еще упростится. Текст интересующей нас книги будет выдаваться на экран дисплея без всякого участия библиотекаря. Необязательно при этом пользоваться дисплеем, установленным в самой библиотеке. Вместо этого можно соединить стоящий дома компьютер с библиотечным и пользоваться библиотекой, не выходя из дома. Если при этом все библиотеки соединены в единую сеть и могут обмениваться информацией, то мы, не выходя из своего дома, получаем доступ ко всем фондам библиотек этой сети.
Но и здесь одновременно с большими удобствами возникают и опасности, которые трудно сейчас даже предвидеть. Например, если книги перестанут выпускаться в обычном печатном виде, а будут храниться в памяти библиотечных компьютеров, то возрастает опасность уничтожения какой-либо книги.
Приведем еще несколько примеров использования информационно-поисковых систем.
1. Большое значение для развития физики имеют опыты на ускорителях элементарных частиц. Многократно ускоряясь в кольцевых вакуумных камерах огромного диаметра, частицы, сталкиваясь с мишенью или друг с другом, создают новые частицы, которые разлетаются от места столкновения. Специальные средства наблюдения позволяют зафиксировать траектории разлетающихся частиц в виде картинки. Использование ЭВМ при проведении физического эксперимента на ускорителях позволило записывать эти картинки с большой скоростью прямо в память ЭВМ и затем использовать эту же ЭВМ для автоматического анализа изображений и предварительного отбора тех из них, которые могут быть интересны экспериментатору. В современных экспериментах для обнаружения физического явления, ради которого проводится исследование, иногда приходится фиксировать и анализировать сотни тысяч изображений, накапливая их в памяти машины. Без ЭВМ и соответствующих информационно-поисковых систем такие эксперименты были бы невозможны.
2. Волжский автомобильный завод в г. Тольятти ежегодно выпускает около миллиона легковых автомашин «Жигули», «Лада» и «Нива». Сборочный конвейер в главном корпусе этого завода работает под управлением ЭВМ. Ее задача — следить за своевременным поступлением деталей на конвейер со складов и из цехов вспомогательных производств.
Для выполнения своей работы управляющая ЭВМ программа должна хранить сведения о тысячах деталей, образующих автомобиль, о наличии деталей на складах, об их движении по транспортным линиям, о поступлении на рабочие места конвейера и т. д.
3. В настоящее время во многих населенных пунктах нашей страны существует автоматическая междугородная телефонная связь. При обеспечении этой связи серьезной проблемой является организация учета длительности разговора и последующей оплаты за разговор. На междугородней АТС средних размеров приходится одновременно поддерживать несколько сот междугородных телефонных разговоров, а общее число абонентов может насчитывать больше ста тысяч.
Для каждого абонента нужно знать его номер телефона, фамилию, имя и отчество и почтовый адрес. Для каждого телефонного разговора нужно зафиксировать его продолжительность, запомнить номера телефонов говорящих, найти нужный тариф, подсчитать стоимость разговора, а затем автоматически подготовить бланк счета за телефонный разговор и напечатать его в виде служебного письма, которое потом будет послано по почте абоненту. Все это стало возможным только благодаря применению ЭВМ.
Численное моделирование физических процессов. В первой части учебника говорилось об использовании компьютеров для моделирования различных процессов. Моделироваться может состояние земной атмосферы, поведение плазмы в термоядерном реакторе, распространение радиоволн, биологическая эволюция, экономическое развитие.
Остановимся на одном из примеров моделирования. Пусть необходимо спроектировать новый пассажирский самолет. Самолет должен обладать заданной грузоподъемностью и быть экономичным — расходовать наименьшее количество топлива. Для обеспечения экономичности нужно, в частности, выбрать самую подходящую форму отдельных деталей самолета и самолета в целом — такую форму, для которой, скажем, сопротивление воздуха при заданной скорости полета было бы наименьшим. Как это сделать? С самого начала самолетостроения и до 50-х годов нашего века использовался один способ:
уменьшенные модели нужных деталей помещались в устройство, называемое аэродинамической трубой, через которую с большой скоростью продувался воздух. Такой эксперимент позволял получать достоверные данные о сопротивлении воздуха в реальном полете.
К сожалению, необходимым условием получения таких данных является большой размер аэродинамической трубы. Дело в том, что при малых размерах трубы (а значит, и модели самолета) существенно изменяется физическая картина исследуемого явления.
Из сказанного выше видно, что эксперименты с аэродинамической трубой и конструирование самолета очень дороги. Физический процесс обтекания самолета потоком воздуха можно смоделировать совсем иначе, не изготовляя никаких физических моделей и не пользуясь аэродинамической трубой. Дело в том, что еще задолго до первого полета самолета была построена математическая модель полета. Эта модель основана на системе уравнений. Решив ее, мы можем найти, в частности, интересующую нас силу сопротивления воздуха.
Зачем же тогда строились аэродинамические трубы? Неужели конструкторы, которые их использовали, ничего не знали о существовании столь нужной им системы уравнений? Конечно, знали. Дело в том, что сколько-нибудь точно математически описать обтекание воздухом самолета можно, только разбив его поверхность. и прилегающий к ней слой воздуха на очень мелкие части и для каждой из этих частей построив свои уравнения.
Решение этих уравнений отчасти напоминает процесс нахождения температуры в отдельных точках пластинки, рассмотренный в первой части учебника, только задача гораздо сложнее.
Итак, математическая модель существовала, но инженеры не могли ее применять.
Ситуация изменилась с появлением компьютеров. Уже первые из них назывались «быстродействующими» и действительно работали существенно быстрее человека. Все же пришлось немного подождать, пока компьютеры стали использоваться для решения сначала самых простых задач аэродинамики, а потом все более и более сложных.
В 60-е годы ЭВМ использовались для моделирования обтекания воздухом простых деталей. Сейчас наиболее мощные ЭВМ позволяют моделировать обтекание самолета целиком (хотя и для малых скоростей). Потребуется еще несколько лет, чтобы моделирование стало возможным для самолета в целом и сверхзвуковых скоростей. Однако уже сейчас многие из используемых самолетов были бы созданы со значительно большими затратами времени и материальных ресурсов, если бы не помощь ЭВМ.
Станки с числовым программным управлением. Все, конечно, видели в своей жизни винты, но задумывались ли о том, как их изготавливают? Один из возможных способов таков. Круглую заготовку, на которой нужно нарезать резьбу, зажимают в патрон токарного станка и вращают. В это время резец движется параллельно оси заготовки, прорезая в ней винтовую канавку. При этом необходимо, чтобы за то время, пока заготовка повернется на один оборот, резец сдвигался на строго определенное расстояние (называемое шагом резьбы). Если мотор, вращающий заготовку, начнет крутиться чуть быстрее, то и резец должен начать двигаться быстрее.
Как же этого достичь? Давно известный способ состоит в том, чтобы двигать заготовку и резец с помощью одного и того же мотора. При этом механизм, передвигающий резец, с помощью зубчатых колес соединяется с механизмом, вращающим заготовку, и работают они согласованно.
Но шаг резьбы может потребоваться разный. Из-за этого необходимо иметь в станке систему зубчатых колес, которые могли бы зацепляться по-разному, давая разные соотношения между скоростью вращения заготовки и скоростью движения резца. На стройка такой системы на данный шаг резьбы — непростое дело. (Да и не всякий шаг можно получить таким способом.) Как видим, даже при изготовлении такой простой вещи, как винт, встречается много трудностей. А современные изделия неизмеримо сложнее, и для их изготовления еще больше разных частей станка должно двигаться согласованно. Добиться такой согласованности чрезвычайно трудно. Если, например, нужно изготовить криволинейную поверхность заданной формы, то часто вначале вручную изготовляют модель, имеющую такую поверхность, а только затем с ее помощью на копировальном станке делают нужную деталь.
Современная технология позволяет упростить этот процесс. Рассчитав нужную деталь с помощью компьютера (рис. 26), можно с помощью того же компьютера рассчитать, как должен двигаться резец и остальные части станка, чтобы такую деталь изготовить.
Далее нужно дать компьютеру возможность управлять этими движениями, Для этого используются специальные двигатели, перемещающие части станка по командам ЭВМ. Оснащенные таким образом станки называются станками с ЧПУ (числовым программным управлением). Применение таких станков совместно с компьютерами позволяет изготавливать сложные детали, причем переход от изготовления одного типа деталей к другому осуществляется легко и быстро путем смены программы в управляющей ЭВМ.
Системы машинной графики. Прежде чем станет возможным изготовление детали на станке с ЧПУ, необходимо создать в компьютере модель детали. Эта модель играет ту же роль, что и чертеж при изготовлении детали традиционным способом. При создании таких моделей применяются специальные устройства. Опишем некоторые из них.
С в е т о в о е п е р о имеет вид авторучки, соединенной проводом с ЭВМ. На кончике светового пера находится электронное устройство, при поднесении которого к выбранной точке экрана, в ЭВМ поступает информация о координатах точки на экране, к которой поднесено световое перо. Двигая перо, можно указывать на экране нужные точки, рисовать линии и т. д.
Ш а р о в о й р ы ч а г имеет вид шарового шарнира, от которого отходит стержень.
Поворот стержня поворачивает шаровой шарнир, и информация об углах поворота (вперед, назад, влево, вправо) передается в ЭВМ.
« М ы ш ь » имеет вид коробочки, лежащей на поверхности стола и соединенной проводом с ЭВМ. Коробочка свободно катается по столу. При ее движении информация о положении «мыши» поступает в ЭВМ.
С помощью «мыши» можно также рисовать линии, например перемещая ее по поверхности стола.
Опишем в общих чертах работу при подготовке модели детали с помощью ЭВМ.
Перемещая, например, «мышь» и вводя с клавиатуры числа, человек может создать чертеж интересующей его детали (рис. 27) примерно так же, как это делается с помощью циркуля и линейки.
Однако можно не только построить чертеж. Возможности ЭВМ позволяют создать объемную модель детали, рассматривать ее с разных точек зрения (рис. 28 и 29) и даже строить поверхность детали автоматически по нескольким основным линиям, которые указывает человек (рис. 30, 31).
Когда модель уже создана, можно с помощью ЭВМ заняться ее анализом. Например, можно задать нагрузки, которые будут действовать на шатун (см. рис. 27), произвести прочностной расчет и узнать, выдержит ли шатун эти нагрузки, в каких местах его надо усилить, а где, наоборот, можно сэкономить часть металла.
После этого ЭВМ может, как мы уже говорили, изготовить деталь «в натуре», управляя станками с ЧПУ. Таким образом, при использовании ЭВМ чертежи становятся ненужными. Такую технологию принято называть безбумажной.
Чего не могут ЭВМ. Развитие информатики и вычислительной техники за последние 40 лет превзошло самые смелые ожидания и опрокинуло самые оптимистические прогнозы. Создатели первых ЭВМ не поверили бы, если бы услышали, что через несколько десятков лет компьютеры станут в тысячи раз быстрее и в тысячи раз дешевле. В то же время в области применения компьютеров иногда наблюдается противоположная картина.
Некоторые задачи, о которых еще на заре «компьютерной эры» говорилось как о доступных машинам, до сих пор остаются недоступными компьютерам, и прогресс в их решении гораздо меньше ожидавшегося. Представление о таких задачах помогает понять, каковы возможности компьютеров, каковы границы этих возможностей и где использование компьютеров наиболее целесообразно.
Посмотрев на фотографию, где собака играет со щенками, легко можно сказать, где на снимке собака, где щенки и сколько видно щенков. Прослушав песенку один или несколько раз, можно записать ее слова. Каждый человек может разобрать свой почерк и даже почерк своих товарищей. Все эти задачи кажутся совсем простыми, и трудно поверить, что для компьютера (во всяком случае, сегодняшнего) они непосильны. И дело тут не в том, что компьютер «не видит» фотографии или не «слышит» песенки, как раз эта часть задачи проста: изображение и звук нетрудно автоматически закодировать в доступной для ЭВМ форме. Дело в том, что совершенно непонятно, каков должен быть алгоритм обработки закодированных таким образом изображений и звуков. Все мы легко отличаем на фотографии собаку от кошки, но при попытке составить алгоритм, позволяющий отличить закодированную соответствующим образом фотографию собаки от фотографии кошки, мы встречаемся с непреодолимыми (во всяком случае, на сегодняшнем уровне развития науки) трудностями.
Таким образом, задачи, легкие для человека, могут оказаться трудными для компьютера, и, напротив, трудные для человека задачи (например, поиск информации в огромном массиве или вычисления большого объема) могут быть простыми для компьютера. Это и хорошо — если бы трудные для нас задачи были бы трудны и для компьютера, то чем бы он нам смог помочь? Подытоживая все сказанное, можно сказать:
работ большого объема.
Поучительна история попыток написать программу для игры в шахматы. Говоря совсем грубо, можно разделить деятельность шахматистов за доской на две части — расчет вариантов и оценку позиций. Первая из них носит рутинный характер, и компьютер справляется с ней гораздо быстрее человека. Благодаря этому быстро работающие специализированные шахматные компьютеры в состоянии играть на уровне мастера спорта.
Однако неумение запрограммировать интуицию шахматиста, которая сразу же подсказывает ему, что некоторая позиция безнадежна или что такой-то ход оптимален, приводит к тому, что более высокий уровень игры пока компьютерам недоступен.
Итак, Вы познакомились с основами информатики и вычислительной техники.
Знание этих основ поможет Вам, независимо от того, в какой отрасли народного хозяйства Вы будете трудиться, решать возникающие задачи, грамотно используя ЭВМ.
УПРАЖНЕНИЯ ДЛЯ ПОВТОРЕНИЯ
1. Найдите число ненулевых элементов в таблице цел таб А[1:100].2. Найдите количество элементов в таблице вещ таб А[1:1000], абсолютная величина которых больше 7.
3. Составьте алгоритм, дающий ответ «да» или «нет» в зависимости от того, встречается или нет число 7 в таблице цел таб А[1:100].
4. Дана целочисленная таблица A[1:100]. Найдите разность наибольшего и наименьшего чисел в этой таблице.
5. Даны две целочисленные таблицы А[1:100], В[1:100]. Подсчитайте количество тех i, для которых: а) А [i] < B[i]; б) А[i] = B[i]; в) А[i] > B[i].
6. Дана целочисленная таблица А[1:100]. Подсчитайте количество таких i, что A [i] не меньше всех предыдущих элементов таблицы (А[1], А[2],..., A[i 1]).
7. Дана таблица вещ таб А[1:100]. Найдите количество элементов этой таблицы, больших среднего арифметического всех ее элементов.
8. Дана целочисленная таблица А[1:100]. Заполните вещественную таблицу В[1:100], i-й элемент которой равен среднему арифметическому первых i элементов таблицы А:
9. Дана целочисленная таблица А[1:100]. Подсчитайте, сколько раз встречается в этой таблице максимальное по величине число.
10. Дана целочисленная прямоугольная таблица А[1:100, 1:50]. Измените все элементы этой таблицы на противоположные по знаку.
11. Дана целочисленная прямоугольная таблица А[1:100, 1:50]. Найдите наибольшее из чисел, встречающихся в этой таблице.
12* 1. Дана целочисленная таблица A[1:100]. Проверьте, есть ли в ней элементы, равные нулю. Если есть, найдите номер первого из них, т. е. наименьшее i, при котором A[i] = 0.
13*. Дана целочисленная таблица A[1: 100]. Проверьте, есть ли в ней отрицательные элементы. Если есть, найдите наибольшее i, при котором A[i] < 0.
14*. Проверьте, является ли прямоугольная таблица цел таб A[1:100, 1:100] «магическим квадратом» (это значит, что суммы чисел во всех ее вертикалях, всех горизонталях и двух диагоналях одинаковы).
15*. Дана целочисленная таблица А[1:1000]. Подсчитайте наибольшее число одинаковых идущих в ней подряд элементов.
16*. Подсчитайте количество различных чисел, встречающихся в таблице цел таб А[1:100]. Повторяющиеся числа учитывайте один раз.
17*. Дана таблица цел таб А[1:1000]. Постройте таблицу цел таб В[1:1000], которая содержит те же числа, что и таблица А, но в которой все отрицательные элементы предшествуют всем неотрицательным.
18*. Даны целочисленные таблицы А[1:100], В[1:100], причем Постройте таблицу цел таб С[1 :200], содержащую все элементы таблиц А и В, в которой Знаком * отмечены трудные задачи.
19*. Дана прямоугольная целочисленная таблица А[1:100, 1:50]. Найдите количество тех чисел i от 1 до 100, для которых А[i, j] = 0 при некотором j от 1 до 50.
20*. Дана прямоугольная целочисленная таблица А[1:100, 1:50]. Найдите наименьшее целое число К, обладающее таким свойством: хотя бы в одной строке таблицы все элементы не превосходят К.
21*. Дана прямоугольная целочисленная таблица А[1:100, 1:50]. Найдите наибольшее целое число К, обладающее таким свойством: в любой строке таблицы есть элемент, больший или равный К.
22*. Постройте алгоритм разложения натуральных чисел на простые множители. В какой форме будут представлены результаты работы этого алгоритма?
23*. Натуральное число называют совершенным, если оно равно сумме всех своих делителей, не считая его самого (например, 6 = 1 + 2 + 3 — совершенное число). Напишите алгоритм, проверяющий, является ли заданное число совершенным.
24*. Напечатайте в порядке возрастания первые 1000 чисел, которые не имеют простых делителей, кроме 2, 3 и 5. (Начало списка: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15,....) 25*. Придумайте способ нахождения самой легкой и самой тяжелой Из 100 монет различной массы, если можно сделать не более 150 взвешиваний на чашечных весах без гирь. (На каждую чашку весов помещается по одной монете; весы показывают, какая из них тяжелее.) 26*. Имеется 1000 монет, из которых одна фальшивая (она легче других). Докажите, что нельзя придумать способ, гарантирующий нахождение фальшивой монеты за взвешиваний на чашечных весах без гирь. Придумайте способ, гарантирующий нахождение фальшивой монеты за 7 взвешиваний.
27*. Среди 2N + 1 различных по массе монет нужно найти среднею (т. е. такую, которая тяжелее N монет и легче N других монет). Придумайте способ, позволяющий сделать это не более чем за 100N взвешиваний на чашечных весах без гирь.
28*. Последовательность a1, а2, а3, … определяется так:
Напишите алгоритм, вычисляющий ап по известному п.
29*. Дана целочисленная таблица A[1:1000]. Найдите наименьшее число К элементов, которые нужно выкинуть из последовательности А[1], А[2],..., А[1000], чтобы осталась возрастающая последовательность.
30*. Даны три целочисленные таблицы А [1:1000], В [1:1000], С[1:1000]. Известно, что существуют целые числа, встречающиеся во всех трех таблицах. Найдите одно из таких чисел.
31*. Даны две литерные величины А и В. Проверьте, можно ли из букв, входящих в А, составить В. (Буквы можно переставлять, но каждую букву можно использовать не более одного раза.) 32*. Составьте алгоритм, находящий по целым величинам A, В и С такие целые числа X и Y, что АХ + BY = С (если такие X и Y есть).
33*. Перестановкой К чисел называется последовательность А[1], А[2],..., А[К], в которой встречаются по одному разу все числа от 1 до К. (Например, перестановками трех чисел являются: (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1) и других перестановок трех чисел нет.) Постройте алгоритм, печатающий все перестановки 100 чисел. Используйте в качестве вспомогательного алгоритм «печать (цел таб А[1:100])», печатающий элементы таблицы А.
34*. Дана таблица нат таб А[1: 100]. Найдите наименьшее натуральное число X, не обладающее следующим свойством: «можно так вычеркнуть некоторые числа таблицы А, чтобы сумма оставшихся равнялась X».
35*. Составьте алгоритм подсчета числа способов, которыми можно уплатить К, рублей купюрами в 1, 3, 5, 10, 25, 50 и 100 рублей.
36*. В стране имеется 50 городов, соединенных авиационным сообщением. Стоимость билета из i-го города в j-й записана в прямоугольной таблице цена [1:50, 1:50]. Составьте алгоритм, находящий стоимость перелета из i-го города в j-й по самому дешевому маршруту (возможно, с пересадками).
37*. Существует способ обойти шахматным конем шахматную доску, побывав на каждом поле по одному разу. Составьте алгоритм отыскания такого способа.
38*. Существуют способы расстановки 8 ферзей на шахматной доске так, чтобы они не били друг друга. Составьте алгоритм, отыскивающий один из таких способов.
39*. Некоторые натуральные числа могут быть представлены в виде суммы кубов целых неотрицательных чисел: например, 9 = 23 + 13, 27 = 33 + 03. Составьте алгоритм, отыскивающий наименьшее натуральное число, имеющее два разных таких представления. (Представления 9 = 23 + 13 = 13 + 23 считаются одинаковыми.) 40*. Составьте алгоритм, вычисляющий по заданным вещественным числам а, b, с, d величины ас + bd и ad bc. Этот алгоритм может использовать промежуточные величины, операции сложения, вычитания и умножения, причем умножение должно выполняться не более трех раз.
ПРИЛОЖЕНИЕ
1. ОСНОВНЫЕ КОНСТРУКЦИИ
АЛГОРИТМИЧЕСКОГО ЯЗЫКА
1. Общий вид алгоритма.алг название (список аргументов и результатов с указанием типов) арг перечень аргументов рез перечень результатов список промежуточных величин алг КВУР (вещ а, b, с, вещ х1, х2, лит у) В заголовке алгоритма решения квадратного уравнения указано, что этот алгоритм называется КВУР, аргументами его являются вещественные величины а, b, с (коэффициенты квадратного уравнения), а результатами — литерная величина у (есть или нет» решения) и вещественные величины х1, х2 (корни). Далее, после слова нач, указано, что в алгоритме используется вещественная промежуточная величина D. После этого следует серия команд, которые должен выполнить исполнитель алгоритма.
2. Общий вид алгоритма вычисления значений функций.
алг тип название (список аргументов с указанием типов) список промежуточных величин В заголовке алгоритма вычисления наибольшего общего делителя указано, что функция НОД (а, b) принимает натуральные значения и что аргументы ее также натуральные числа. Далее, после слова нач, указано, что используются две промежуточные величины х и у. Затем идут команды, которые должен выполнить исполнитель алгоритма. Последняя из них:
указывает, что значением функции является значение величины х 3. Команда ветвления.
1) Полная форма:
Команда ветвления выполняется так. Сначала исполнитель проверяет, соблюдается ли условие. Если оно соблюдается, то выполняется серия 1 и на этом выполнение команды ветвления заканчивается. Если же условие не соблюдается, то выполняется серия 2. В приведенном примере команды ветвления при а b значением величины max становится число а, а в противном случае (при а < b) значением величины max становится число b.
2) Сокращенная форма:
Команда ветвления в сокращенной форме выполняется так. Сначала исполнитель проверяет, соблюдается ли условие. Если оно соблюдается, то выполняется указанная серия команд. Если же нет, то выполнение команды ветвления на этом заканчивается.
В приведенном примере при х < 0 выполняется команда х := х (в данном случае серия состоит из единственной команды), величина х меняет знак и становится положительной. При х 0 величина х остается без изменений.
4. Команда выбора.
1) Полная форма:
Команда выбора выполняется так. Одно за другим проверяются условия команды.
Как только исполнитель находит условие, которое соблюдается, он выполняет серию идущих за ним команд (и на этом выполнение команды выбора заканчивается). Если ни одно из условий не соблюдается, то выполняется серия команд, идущая после слова иначе.
В нашем примере при а > 100 соблюдается первое условие и значением величины b становится текст "очень большое". При 10 < а 0: пол := пол + В сокращенной форме команды выбора отсутствует слово иначе и серия идущих за ним команд. В этом случае, если ни одно из условий команды выбора не соблюдается, выполнение команды выбора на этом заканчивается.
5. Команда повторения.
При выполнении команды повторения входящая в нее серия команд повторяется столько раз, сколько нужно, чтобы условие перестало соблюдаться. (Если условие не соблюдается с самого начала, то серия не выполняется ни разу.) В нашем примере значение величины х будет уменьшаться каждый раз на 10, пока оно не станет меньше 10. Если начальное значение переменной х — целое положительное число, то после выполнения команды повторения ее новым значением станет остаток от деления исходного числа на 10.
6. Команда повторения с параметром.
В команде повторения с параметром х — целочисленная переменная, называемая параметром, a Xmin Xmax и xшaг — целочисленные выражения, причем хшаг должно быть больше 0. Выполняется команда так: входящая в нее серия выполняется для последовательности значений i = Xmin, Xmin + хшаг, Xmin + 2хшаг, которая продолжается до тех пор, пока не будет пройдено значение Xmax. В нашем примере команда будет выполнена для i = 2, затем для i = 1, затем для i = 4, i = 7 и, наконец, для i = 10. Это значение i будет последним, поскольку следующее значение i = 13 уже больше граничного значения 11.
Наиболее употребительна команда повторения с параметром, в которой значение хшаг равно 1. В этом случае слово «шаг 1» можно опустить и писать, например, В этом примере команда S := S + i будет выполнена последовательно при i 1, i = 2,..., i = 10.
7. Команда присваивания.
В команде присваивания имя — имя некоторой величины. В результате выполнения команды значение этой величины становится равным указанному в команде выражению, которое должно иметь соответствующий тип. При записи выражений могут быть использованы операции и функции, приведенные в таблице 20, а также функции, алгоритмы вычисления значений которых включены в библиотеку вспомогательных алгоритмов.
В левой части команды присваивания может стоять выражение:
y[i, j], если у — прямоугольная таблица, s[i : j], если s — литерная величина.
Например, при выполнении команды элемент х [3] линейной таблицы х становится равным 7. При выполнении команды значение элемента у[5, 4] прямоугольной таблицы у увеличивается на 1.
При выполнении команды значение литерной переменной s меняется: пятой буквой становится буква "а", шестой — буква "б" и седьмой — буква "в".
8. Команда вызова вспомогательного алгоритма.
Имеющийся в библиотеке алгоритм можно использовать, записав команду вызова этого алгоритма. Для этого указывается его имя, аргументы, к которым его нужно применять, и величины, которые будут его результатами.
Например, заголовок алгоритма решения квадратного уравнения ах2 + bx + с = был такой:
алг КВУР (вещ а, b, с, вещ х1, х2, лит у) В результате вызова алгоритм будет применен к уравнению с коэффициентами а = 1, b 5, с = 2m + 1, значение переменной ответ будет "есть решения" или "нет решения" в зависимости от наличия или отсутствия решений у уравнения х2 + 5х + (2m + 1) = 0, и, если решения есть, они станут значениями переменных р и q.
Если вспомогательный алгоритм вычисляет значение функции, то вызов этого вспомогательного алгоритма происходит, когда при вычислении значения выражения встречается эта функция. Например, при выполнении команды трижды вызывается вспомогательный алгоритм abs, а при выполнении команды перед вызовом вспомогательного алгоритма КВУР происходит вызов вспомогательного алгоритма abs.
9. Запись условий в алгоритмическом языке.
Простое условие в алгоритмическом языке имеет вид:
Составное условие состоит из простых, соединенных служебными словами и, или, не.
Примеры составных условий:
Выражения в условиях составляются по тем же правилам, что и в команде присваивания. В качестве знака можно использовать = и, а также (для выражений с целыми и вещественными значениями) знаки,. Условия встречаются в командах ветвления, выбора и повторения.
II. БИБЛИОТЕКА АЛГОРИТМОВ
1. Алгоритм вычисления абсолютной величины действительного числа.2. Алгоритм нахождения максимальной из двух величин.
алг вещ max 2 (вещ а, b) кон 3. Алгоритм решения квадратного уравнения ах2 + bх + с = 0, где а, b, с — произвольные вещественные числа (а 0).
алг КВУР (вещ а, b, с, вещ х1, х2, лит у) 4. Алгоритм Евклида вычисления наибольшего общего делителя двух натуральных чисел.
5. Алгоритм вычисления факториала натурального числа.
алг цел факториал (нат п) 6. Алгоритм нахождения остатка при делении целого положительного числа (делимое) на целое положительное число (делитель).
алг цел остаток (цел делимое, делитель) Пояснение. В этом алгоритме из величины делимое вычитают делитель до тех пор, пока это можно (т. е. остается неотрицательное число). После этого знач равно остатку от деления делимого на делитель.
7. Алгоритмы деления с остатком целых положительных чисел.
алг деление с остатком (цел делимое, делитель, цел частное, остаток) остаток := остаток — делитель; частное. := частное + кон П о я с н е н и е. Между выполнениями серии, входящей в команду повторения, соблюдается условие После выполнения команды повторения это условие продолжает соблюдаться и, кроме того, условие, остаток ^ делитель не соблюдается, т. е. остаток < делитель, что и требовалось.
8. Алгоритм подсчета количества отрицательных, нулевых и положительных элементов в таблице.
алг подсчет (цел таб а[1:100], цел отр, нул, пол) 9. Алгоритм нахождения наименьшего делителя целого положительного числа х (не считая единицы).
алг цел наименьший делитель (цел х) кон П о я с н е н и е. В этом алгоритме значение i увеличивается до тех пор, пока не найдено такое значение i, при котором остаток (х, i) = О, т. е. х делится на I. Этот алгоритм использует алгоритм 6 как вспомогательный.
Замечание. Приведенные алгоритмы (нахождение остатка, наименьшего делителя) далеко не наилучшие в отношении количества действий, которые должен проделать исполнитель.
10. Алгоритм замены букв а на буквы б III. ДОПОЛНИТЕЛЬНЫЕ СВЕДЕНИЯ ОБ УСТРОЙСТВЕ ЭВМ
Рассмотрим пример программы, читающей информацию из памяти ЭВМ. Пусть первые три элемента линейной таблицы целых чисел расположены в ячейках памяти с адресами 2000, 2002 и 2004 и надо поместить в регистр R1 их сумму. Будем считать, что в начальный момент СК = 1000, R0 = 2000, R2 = 2 и расположим соответствующую программу в памяти ЭВМ, начиная с адреса 1000 (табл. 21):
очистить регистр R добавить слово (R0) к R добавить слово R2 к R добавить слово (R0) к R добавить слово R2 к R добавить слово (R0) к R стоп Приведем таблицу значений (табл. 22) для этой программы, считая, что по адресам 2000, 2002, 2004 находятся числа 5, 6, 7.
Команды для работы с табличными величинами. Заметьте, что в предыдущей программе после добавления к R1 слова по адресу, записанному в R0 (шаги 2 и 4), регистр R0 сразу увеличивается на 2 (шаги 3 и 5). Таким образом, при исполнении этой программы регистр R0 «скользит» по адресам памяти, переходя от одного элемента целочисленной таблицы к другому. Такое скольжение часто используется при работе с табличными величинами, и для его организации существуют специальные команды: если в любой известной нам команде имя регистра не только заключить в скобки, но и написать после скобок знак « + », то процессор не только возьмет содержимое ячейки по адресу, записанному в регистре, но и автоматически увеличит содержимое этого регистра на 2, т. е. перейдет к следующему слову. Например, по команде процессор не только добавит к R1 содержимое ячейки по адресу, записанному в R0, но и увеличит R0 на 2, т. е. перейдет к следующему элементу таблицы.
Таким образом приведенную выше программу можно записать короче, не используя регистр R2 (табл. 23):
Приведем теперь программу, которая не только читает, но и записывает информацию в память ЭВМ. Пусть требуется скопировать линейную таблицу чисел, находящуюся в 200 ячейках памяти, начиная с адреса 2000, в другую таблицу из 200 слов, начинающуюся с адреса 3000. Будем считать, что в начальный момент СК = 1000, R0 = 2000, R1 = 3000, R2 = 200, и расположим программу в памяти ЭВМ, начиная с адреса 1000 (табл. 24):
В процессе работы этой программы R0 содержит адрес очередного еще не скопированного элемента таблицы (слова), R1 — адрес, куда надо переслать это слово, a R2 — число еще не скопи рованных слов (элементов таблицы). Перед началом работы программы R2 = 200, т. е. ни один элемент таблицы еще не скопирован. По окончании работы программы R2 = 0, т. е. все элементы таблицы скопированы.
Установка начальных значений регистров. До сих пор мы всегда предполагали, что перед началом работы программы в регистры уже записаны нужные адреса и числа.
Например, в предыдущей программе предполагалось, что R0 = 2000, R1 = 3000, R2 = 200.
Поместить нужную информацию в регистры может и сама программа (табл. 25):
переслать слово (СК) + в R переслать слово (СК) + в R переслать слово (СК) + в R переслать слово (R0) + в (R1)+ уменьшить слово R 2 на единицу если больше, переход на 3 слова В этой программе по адресам 1002, 1006 и 1010 записаны не команды, а информация, которая в процессе работы программы будет помещена в регистры.
Первая команда этой программы отличается от рассмотренной выше команды только именами регистров. При выполнении этой первой команды процессор в соответствии с основным алгоритмом:
1) читает адрес из СК (1000);
2) читает слово из памяти по этому адресу (команду "переслать слово (СК) + в R0");
3) увеличивает СК на 2 (до 1002);
4) выполняет прочитанную команду. (Поскольку в команде написано (СК) +, а в этот момент СК = 1002, то процессор пересылает в R0 содержимое слова памяти по адресу 1002, сам регистр СК увеличивает на 2 (до 1004).
В соответствии с основным алгоритмом на следующем шаге процессор выполнит команду, адрес которой (1004) Записан в СК, т. е. перешлет 3000 в регистр R1. Затем он перешлет 200 в R2, после чего оставшаяся часть программы будет исполняться в точности так, как было описано выше.
2. Подпрограммы. В первой части курса мы знакомились с вспомогательными алгоритмами и командами их вызова. Теперь покажем, как записываются и вызываются вспомогательные программы — подпрограммы.
Подпрограмма очень похожа на программу;— она также состоит из команд и также должна быть размещена в памяти ЭВМ. Единственное отличие заключается в том, что в конце подпрограммы вместо команды стоп должна стоять специальная команда Предположим, что мы составили подпрограмму, поместили ее в память, начиная с адреса 1400 (этот адрес — адрес первой команды подпрограммы — называется адресом подпрограммы). Тогда вызвать эту подпрограмму можно с помощью команды вслед за которой в памяти ЭВМ расположен адрес подпрограммы (табл. 26):
(Будем считать, что команда вызова подпрограммы расположена в ячейке с адресом 1000.) Как и любая другая, команда "вызов подпрограммы" выполняется за один шаг работы процессора и в соответствии с основным алгоритмом. Мы уже знаем, что при работе процессора по основному алгоритму регистр R7, т. е. СК, играет особую роль. При работе с подпрограммой особую роль будет играть и еще один регистр — R6. При выполнении команды "вызов подпрограммы" процессор 1) читает адрес из СК (1000);
2) читает команду из ячейки памяти по этому адресу (вызов подпрограммы);
3) увеличивает СК на 2 (до 1002);
4) выполняет полученную команду, а именно:
а) получает адрес подпрограммы, т. е. берет содержимое СК (1002), читает слово по этому адресу (1400) и увеличивает СК на 2 (до 1004);
в) записывает СК (1004) в ячейку памяти по адресу, указанному в R6;
г) записывает в СК адрес подпрограммы (1400).
Таким образом, после выполнения этой команды адрес возврата (т. е. 1004 — адрес первой следующей за "вызов подпрограммы" команды) будет записан в некоторую ячейку памяти. Адрес самого этого слова будет содержаться в регистре R6, а в СК будет находиться адрес первой команды подпрограммы.
В соответствии с основным алгоритмом на следующем шаге процессор выполнит команду, адрес которой (1400) записан в СК, т. е. первую команду подпрограммы. Затем он выполнит вторую команду подпрограммы и т. д. до тех пор, пока не встретит команду При выполнении пункта 4 для команды "возврат из подпрограммы" процессор а) помещает в СК содержимое ячейки памяти с адресом, записанным в R6;
б) увеличивает регистр R6 на 2.
В результате R6 примет то же значение, что и до вызова подпрограммы, а в СК окажется адрес возврата — 1004— адрес первой команды, следующей за "вызов подпрограммы". В соответствии с основным алгоритмом именно эта команда и будет выполнена на очередном шаге процессора.
Хорошо было бы проиллюстрировать вызов подпрограммы на каком-нибудь интересном примере. Однако интересные примеры длинные, поэтому мы сейчас приведем пример, который только для иллюстрации и годится: задача, которая в нем решается, могла бы быть решена проще, без всяких подпрограмм.
Рассмотрим пример программы, которая увеличивает регистр R1 на 2 с помощью подпрограммы, увеличивающей R1 на 1 (табл. 27).
...
Таблица значений для этой программы при начальных значениях СК= 1000, R6 = 1000, R1 = 1 выглядит так (табл. 28):
Как и требовалось, после исполнения программы регистр R1 увеличился на 2, т. е.
стал равен 1.
Естественно, что подпрограмма также может вызывать другие подпрограммы и т.
д. Проиллюстрируем это на простейшем примере: программа А вызывает подпрограмму В, которая, в свою очередь, вызывает подпрограмму С (табл. 29).
Таблица 30 значений для этой программы при начальных значениях СК = 1000, R = 1000 помещена на с. 122.
Стрелки на таблице показывают последовательность действий процессора при выполнении третьего шага.
З а м е ч а н и е. Рассказывая про команды "вызов подпрограммы" и "возврат из подпрограммы", мы несколько погрешили против истины: на самом деле эти команды имеют аргументы и выполняются более сложным образом. Так, как описано выше, эти команды работают только при некоторых фиксированных значениях аргументов.
На примере последней программы проследим еще раз, как записываются в память и как извлекаются из нее адреса возвратов при вызовах подпрограмм. Будем изображать только область памяти с адресами, меньшими 1000, а адрес, содержащийся в регистре R6, покажем стрелкой, указывающей на соответствующее слово:
Таким образом, при каждом вызове подпрограммы (например, подпрограммы G) на уже существующие слова с адресами возвратов сверху кладется еще один «кирпичик» — слово с очередным адресом возврата. При следующем вызове сверху добавляется еще один «кирпичик» и т. д.
По команде возврата из подпрограммы верхний «кирпичик» снимается, при следующем возврате снимается еще один и т. д.
«Кирпичики» подчиняются правилу «положил позже — взял раньше». Любую структуру, элементы которой подчиняются этому правилу, принято называть стеком. В качестве примеров стеков можно привести детскую пирамидку (первым снимается колечко, надетое последним) или железнодорожный тупик (вагоны вывозят из тупика в порядке, обратном порядку их помещения туда).
Так как регистр R6 в каждый момент времени содержит адрес самого верхнего элемента стека (или, как принято говорить, указывает на вершину стека), то его называют указателем стека. В целом алгоритм записи и извлечения из памяти адресов возвратов при вызовах подпрограмм принято описывать фразой: при вызовах подпрограмм адреса возвратов сохраняются в стеке.
3. Кодировка команд. Каждая команда в ЭВМ кодируется последовательностью из 16 нулей и единиц (16 бит), т. е. словом. Для разных команд разные группы битов кодируют разную информацию. Например, для команды "очистить ячейку (R1)" эти 16 битов можно разбить на три группы: 10 битов — код операции (КОП), 3 бита — вид использования регистра и 3 бита — номер регистра.
КОП содержит, информацию о том, что должна делать команда (очистить ячейку, уменьшить слово на единицу, переслать слово и пр.). Номер фигурирующего в команде регистра (от R0 до R7) кодируется 3 битами и может быть равен 000, 001, 010, 011, 100, 101, 110, 111 соответственно. Вид использования регистра указывает, надо ли очистить сам регистр (вид 000) или ячейку памяти по адресу, записанному в регистре (вид 001), или же, кроме очистки ячейки памяти по адресу, записанному в регистре, надо еще сам регистр увеличить на 2 (вид 010). Существуют и другие виды использования регистров (011, 100, 101, 110, 111), которые мы не рассматривали.
Примеру конкретных кодировок разных команд приведены в таблицах 31 и 32.
Таким образом, команда "переслать слово (R4) в R7", например, кодируется последовательностью 0001001100000111.
В командах перехода КОП занимает половину слова (8 битов), а оставшиеся 8 битов используются для указания, на сколько слов надо сместиться (на +2, на 3 и т. п.). Это число слов (его принято называть смещением) кодируется примерно так же, как и целые числа. Однако, поскольку используется только 8 битов, диапазон значений смещения меньше: от 128 до +127 (табл. 33).
Таким образом, команда "если меньше, переход на +2 слова" имеет код 0000010100000010.
4. Работа с внешними устройствами. Разберемся теперь, как процессор управляет внешними устройствами, т. е. каким образом можно, например, что бы то ни было изобразить на экране дисплея или напечатать на печатающем устройстве (см. рис. 10).
Прежде всего отметим, что нет ни специальных команд для управления внешними устройствами, ни специальных форм записи аргументов при таком управлении. Все управление внешними устройствами осуществляется обычными командами, такими, как "переслать слово".
Посмотрим, что же происходит при выполнении этой команды и как с ее помощью можно управлять внешними устройствами.
Мы уже говорили, что при выполнении, например, команды "переслать слово R1 в (R0)" процессор записывает содержимое регистра R1 в память по адресу, указанному в регистре R0. Это верно лишь в том случае, если в регистре R0 содержится адрес памяти.
Дело в том, что все множество адресов слов от 0 до 65534 поделено между различными устройствами ДВК-2М и аналогичных ЭВМ. К памяти относятся лишь адреса от 0 до 57342. Большие адреса относятся к различным внешним устройствам и процессору. Например, у устройства печати есть два слова с адресами 65356 и 65358, а у экрана дисплея — два слова с адресами 65396 и 65398.
Поэтому правильнее было бы описывать действие команды "переслать слово R1 в (R0)" так:
процессор берет содержимое регистра и посылает эту информацию через магистраль по адресу, записанному в R0.
Можно представлять себе магистраль как своего рода почтовую службу, по которой процессор посылает письмо. Дальнейшие действия зависят не от процессора, а от адресата — от того, кому адресовано «письмо». Если это память, то полученная информация (содержимое регистра R1) просто запоминается в соответствующей ячейке памяти, как мы это и описывали раньше. Если же, к примеру, R0 — 65358, т. е. адресатом является устройство печати, то полученная информация воспринимается как некоторая команда и печатающее устройство выполняет соответствующие действия (печатает символ на бумаге, прогоняет бумагу до границы страницы и т. п.).
Аналогичным образом происходит и чтение информации по некоторому адресу.
Например, по команде процессор посылает по адресу, указанному в R0, «письмо» с просьбой прислать информацию. Дальнейшие действия опять зависят от адресата. Память просто посылает обратно содержимое соответствующей ячейки. Устройство печати (при R0 = 65356) посылает обратно информацию о своем состоянии. Проанализировав эту информацию, находящуюся теперь в регистре R1, можно, например, узнать, включено ли устройство в сеть, закончено или нет выполнение предыдущей команды и пр.
Заметим, что «письма» по магистрали не обязаны проходить через процессор. Точно так же обмениваться информацией между собой и с памятью могут любые внешние устройства. Скорость передачи информации по магистрали велика и составляет миллионы байтов в секунду.
5. Магистрально-модульный принцип построения ЭВМ. Наличие магистрали позволяет собирать ЭВМ из отдельных функционально и конструктивно законченных блоков, называемых модулями. Модуль может содержать несколько компонент ЭВМ, например процессор и память (см. рис. 4). Наоборот, одна компонента ЭВМ может быть изготовлена в виде нескольких модулей. Подсоединяя к магистрали разные наборы модулей, можно получать различные ЭВМ. Такой магистрально-модульный принцип построения ЭВМ получил сейчас широкое распространение, так как обладает несколькими важными достоинствами:
1. Процессор может эффективно управлять внешними устройствами с помощью тех же команд, которыми он работает с памятью, т. е. для работы с внешними устройствами не нужны специальные команды процессора.
2. Можно конструировать и подключать к магистрали новые внешние устройства.
При этом не требуется никаких изменений в уже существующих устройствах, процессоре, памяти.
3. Из готовых модулей можно легко составлять ЭВМ разной мощности и назначения. Состав ЭВМ можно легко изменять в процессе ее эксплуатации.
1. В чем различие команд "очистить регистр R0", "очистить ячейку (R0)" и "очистить ячейку (R0) + "?
2. Что такое: а) подпрограмма, б) команда вызова подпрограммы, в) команда возврата из подпрограммы, г) адрес подпрограммы, д) адрес возврата?
3. Может ли одна подпрограмма вызывать другую? Может ли одна и та же подпрограмма вызываться разными командами вызова из разных мест памяти?
4. Как используется регистр R6 при вызовах подпрограмм?
5. Что такое: а) стек, б) вершина стека, в) указатель стека?
6. Какое колечко детской. пирамидки является вершиной стека?
7. Какой двоичный код имеет команда "уменьшить слово (R4)-f на единицу"?
8. Какой команде соответствует двоичный код 0001000001001010?
9. Как процессор управляет внешними устройствами?
10. Что такое магистраль? Для чего она служит?
1. Напишите программу, после исполнения которой в регистре R0 будет содержаться:
б) число, адрес которого лежит в R1;
в) содержимое R1, увеличенное на 200;
г) максимум из чисел, адреса которых лежат в Rl, R2;
д) максимум из чисел, адреса которых лежат в R0, R1.
2. В памяти, начиная с адреса 2000, расположена целочисленная таблица из элементов. Напишите программу, после исполнения которой:
а) все элементы таблицы увеличатся на 1;
б) все элементы таблицы станут равны 0;
в) в таблице будет записана арифметическая прогрессия с первым членом 1 и разностью — 1;
г) все элементы таблицы изменят знак на противоположный.
3. В памяти, начиная с адреса 2000, расположена целочисленная таблица из элементов. Напишите программу, после исполнения которой в регистре R0 будет содержаться:
а) сумма элементов таблицы;
б) сумма модулей элементов таблицы;
в) сумма положительных элементов таблицы;
г) минимальный элемент таблицы;
д) адрес первого минимального элемента таблицы;
е) число положительных элементов таблицы;
ж) число элементов таблицы, больших 100.
IV. АЛГОРИТМЫ ПОИСКА ИНФОРМАЦИИ
Мы уже говорили о том, что одно из важнейших применений компьютеров — учет и обработка экономической информации. Рассмотрим пример. Разумеется, он является лишь упрощенной моделью реальной обработки информации, которая часто требует больших и сложных программ.Итак, мы с вами на складе. На нем хранится 1000 различных измерительных приборов, которые выдаются по мере необходимости, а затем возвращаются обратно. Заведующий складом решил использовать компьютер для учета хранящихся на складе приборов.
Для этого каждый прибор должен иметь свой номер: от 1 до 1000, а компьютер должен уметь отвечать на вопрос, имеется ли на складе прибор с заданным номером. Сведения о наличии всех приборов будут храниться в таблице наличие [1:1000], при этом наличие [i] = 1, если i-й прибор есть на складе, и наличие [i] = 0, если i-го прибора нет на складе.
Теперь можно написать такой алгоритм:
алг лит есть на складе (цел номер, цел таб наличие [1:10,00]) Нужно еще уметь регистрировать выдачу прибора со склада и его возвращение.
Это делается так:
алг выдача (цел номер, цел таб наличие [1:1000]) алг возврат (цел номер, цел таб наличие [1:1000]) наличие [номер]: = кон Эти алгоритмы должны применяться, когда со склада берут или на склад возвращают очередной прибор. Перед применением алгоритма «выдача» полезно убедиться, что соответствующий прибор числится имеющимся на складе, а перед применением алгоритма «возврат» — что он числится выданным.
Имея таблицу наличие, можно выполнять и другие учетные операции. Например, можно быстро узнать, сколько приборов есть на складе в данный момент. Поскольку в таблице наличие стоят только нули и единицы и отсутствие прибора обозначается нулем, то количество приборов на складе будет равно просто сумме элементов этой таблицы.
алг цел количество (цел таб наличие [1:10000]) Описанный выше способ хранения информации с помощью сквозной нумерации приборов и таблицы наличие по разным причинам не очень удобен. Например, при покупке организацией любой вещи: стула, телевизора, станка, прибора и т, д.— эта вещь получает в организации специальный номер для учета — инвентарный номер. Все эти номера различны, и удобнее не нумеровать приборы на складе специально, а воспользоваться уже имеющимися инвентарными номерами.
Можно было бы хранить информацию в таблице наличие [1:N], где N — достаточно большое число (настолько большое, что любой инвентарный номер не больше N). К сожалению, для хранения такой таблицы в памяти ЭВМ потребуется много места. Большая часть этого места будет пропадать зря — ведь инвентарные номера приборов составляют очень небольшую часть всех инвентарных номеров, используемых в данной организации.
Хотелось бы хранить информацию более экономно.
Один из возможных способов хранения информации таков. Пусть, например, на складе имеются приборы с номерами 2543, 7207 и 10628. Тогда можно хранить информацию об этом в таблице номера:
При этом объем, занимаемый таблицей в памяти, будет зависеть не от величины номеров, а от числа приборов на складе.
Плохо только, что размер таблицы номера должен меняться с изменением числа приборов, а правила алгоритмического языка требуют заранее задать размер таблицы и не позволяют изменить этот размер во время работы программы. Тут можно поступить следующим образом. Введем величину количество, значение которой будет равно текущему числу приборов на складе. Тогда числа будут инвентарными номерами приборов, хранящихся на складе. При этом оставшиеся, «запасные», места в таблице могут быть заполнены чем угодно. Они понадобятся, если впоследствии количество приборов на складе увеличится.
Таким образом, размер таблицы номера нужно выбрать исходя из наибольшего возможного числа приборов на складе.
Поясним сказанное на примере. Пусть нам известно, что на складе будет храниться не более 1000 приборов одновременно с инвентарными номерами от 1 до 40 000. В этом случае вместо таблицы наличие [1:40 000] нам будет достаточно иметь таблицу номера [1:1000] и величину количество, которая принимает значения от 0 до 1000.
Пусть на складе имеются приборы с номерами 2543, 7207 и 10628. Чтобы зарегистрировать это, достаточно выполнить команды Можно было бы вместо этих команд выполнить команды Получившиеся значения величин номера и количество соответствуют той же самой ситуации на складе, поскольку порядок расположения в таблице номера не существен.
Чтобы привыкнуть к такому способу записи информации о номерах имеющихся на складе приборов, попробуем ответить на следующий вопрос. Пусть количество = 5, а таблица номера такова:
Какие приборы имеются на складе? Прежде всего мы знаем, что их там 5 штук.
Выбрав 5 первых элементов таблицы номера, находим, что на складе имеются приборы с номерами Если при той же таблице номера значение переменной количество будет равно 2, то это будет означать, что на складе имеются приборы с номерами 57 и 2. А если количество — 0, то это значит, что на складе не осталось ни одного прибора.
Не всякие значения величин количество и номера возможны. Например, количество не может быть равно — 7 или 1001. Подобным же образом мы не допускаем, например, ситуации количество = 3 и номера:
потому, что номер 37 встречается в последовательности более одного раза (в данном случае дважды).
Другими словами, допустимы только такие значения переменных количество и номера, при которых 0 количество 1000 и все числа различны. Это соответствует той ситуации, когда на складе имеются приборы с номерами Мы договорились о новом способе хранения информации о наличии приборов на складе с помощью двух величин номера и количество. Как же теперь узнать, есть ли на складе прибор с заданным номером? Для этого прежде всего нужно построить новый алгоритм «есть на складе» с заголовком алг лит есть на складе (цел номер, цел количество, который давал бы ответ "да", если номер встречается среди и ответ "нет" в противном случае. Запишем этот новый алгоритм:
алг лит есть на складе (цел номер, цел количество, Работает этот алгоритм так. Вначале значением алгоритма становится величина "нет". Затем мы сравниваем значение величины номер со всеми значениями номера [ i ] при всех i от i = 1 до i = количество. Если условие номер = номера [ i ] соблюдается при некотором i, то значением алгоритма становится величина "да". Если же условие номер = номер [ i ] не соблюдается ни при одном i, то значением алгоритма остается величина "нет".
Теперь нам нужно научиться регистрировать выдачу приборов со склада и возвращение их на склад. Начнем со второго. Если мы хотим зарегистрировать тот факт, что на склад принесли прибор с данным номером, то переменную количество нужно увеличить на 1, записав в очередную клеточку таблицы номера номер помещенного на склад прибора. Приходим к такому алгоритму:
алг возврат (цел номер, цел количество, арг номер, количество, номера Алгоритм «возврат» можно применять только в том случае, когда количество < 1000 (т. е. склад не полон), а есть на складе (номер, количество, номера) = "нет" (т. е. элемент с указанным номером отсутствует).
Например, если значение переменной количество равнялось 3, а таблица номера была заполнена так:
то после возвращения на склад прибора номер 57 значением переменной количество станет число 4, а таблица номера станет такой:
Если мы после этого захотим зарегистрировать взятие со склада только что положенного туда прибора с номером 57, то достаточно снова уменьшить на 1 величину количество. (При этом в таблице номера нет необходимости вычеркивать число 57, так как элементы номера [i] при i > количество не играют для нас никакой роли.) Хуже, если понадобится зарегистрировать взятие со склада прибора с номером 72. Возможное решение тут таково — переставив его с элементом 57, получим таблицу:
После этого нужно уменьшить значение переменной количество с 4 до 3. Этот способ действий мы и будем применять в общем случае: исключаемый из таблицы элемент мы вначале поменяем местами с последним, а затем уменьшим величину количество на 1.
Таким образом, исключение заданного номера из таблицы происходит в три этапа:
1) находим его в таблице;
2) переставляем его местами с последним элементом таблицы;
3) уменьшаем количество на 1.
Записывая это более подробно, приходим к такому алгоритму:
алг выдача (цел номер, количество, цел таб номера [1:1000]) арг номер, количество, номера номера [i] := номера [количество] количество := количество кон Замечание. Этап 2 можно упростить. Нам нет необходимости переставлять местами элементы поскольку после уменьшения переменной количество на 1 значение одного из них будет несущественно. Достаточно выполнить команду Приходим к такому варианту алгоритма:
алг выдача (цел номер, количество, цел таб номера [1:1000]) арг номер, количество, номера номера [i] := номера [количество] В обоих вариантах алгоритма предполагается, что исключаемый из таблицы номер в ней имеется.
Посмотрим теперь, сколько действий придется выполнить исполнителю наших алгоритмов. Чтобы выяснить, есть ли прибор с заданным номером на складе (алгоритм «есть на складе»), исполнитель сравнивает его номер поочередно со всеми номерами Поэтому число выполняемых действий пропорционально числу приборов на складе. Примерно таково же будет число необходимых действий в алгоритме «выдача». Правда, при его исполнении исполнителю может повезти и исключаемый номер может найтись быстро (если он стоит в начале таблицы). Но в худшем случае если этот номер стоит в конце таблицы, то число действий исполнителя также будет пропорционально числу приборов на складе. Алгоритм «возврат» — самый простой из трех; при его исполнении число действий не зависит от числа приборов на складе.
«