Учебник Информатика 9 класс Горячев Островский часть 2

Федеральный государственный образовательный стандарт Образовательная система «Школа 2100» А.В. Горячев, С.Л. Островский, А.В. Паволоцкий, Т.Л. Чернышёва, Д.В. Широков ИНФОРМАТИКА 9 класс • Часть 2 Москва Б/тх 2015 УДК 373.167.1:004+004(075.3) ББК 32.81я721 Г67 Федеральный государственный образовательный стандарт Образовательная система «Школа 2100» Совет координаторов предметных линий Образовательной системы «Школа 2100» — лауреат премии Правительства РФ в области образования за теоретическую разработку основ образовательной системы нового поколения и её практическую реализацию в учебниках На учебник получены положительные заключения по результатам научной экспертизы (заключение РАН от 14.10.2011 № 10106-5215/449), педагогической экспертизы (заключение РАН от 24.01.2014 № 000384) и общественной экспертизы (заключение НП «Лига образования» от 30.01.2014 № 177) Руководитель издательской программы -чл.-корр. РАО, доктор пед. наук, проф. Р.Н. Бунеев Авторский коллектив: А.В. Гиглавый - научный редактор, А.В. Горячев - автор концепции курса, научный руководитель, С.Л. Островский (часть 1: модуль «Хранение и обработка больших объёмов данных»), А.В. Паволоцкий (часть 2: модуль «Алгоритмизация и программирование»), А.А. Семёнов (часть 1: модуль «Моделирование»), Т.Л. Чернышёва (часть 2: модуль «Знакомство с математической логикой»), Д.В. Широков (часть 1: модуль «Создание электронных изданий»; часть 2: модуль «Web-конструирование. Основы мастерства») Горячев, А.В. Г67 Информатика. 9 кл. : учеб. для организаций, осуществляющих образовательную деятельность. В 2 ч. Ч. 2 /А.В. Горячев, С.Л. Островский, А.В. Паволоцкий, Т.Л. Чернышёва, Д.В. Широков. - М. : Баласс, 2015. - 192 с. : ил. (Образовательная система «Школа 2100»). ISBN 978-5-85939-997-0 ISBN 978-5-85939-942-0 (ч. 2) Учебник «Информатика» для 9 класса соответствует Федеральному государственному образовательному стандарту основного общего образования. Является продолжением непрерывного курса информатики и составной частью комплекта учебников развивающей Образовательной системы «Школа 2100». Содержание учебника представлено в виде отдельных учебных модулей, из которых учитель может выбрать нужные в соответствии с требованиями основной образовательной программы школы. Учебный материал предлагается на необходимом и повышенном уровнях. Может использоваться как учебное пособие. УДК 373.167.1:004+004(075.3) ББК 32.81я721 Данный учебник в целом и никакая его часть не могут быть скопированы без разрешения владельца авторских прав ISBN 978-5-85939-997-0 ISBN 978-5-85939-942-0 (ч. 2) © Горячев А.В., Островский С.Л., Паволоцкий А.В., Чернышёва Т.Л., Широков Д.В., 2012 © ООО «Баласс», 2012 Дорогие читатели! Вы открыли книгу 2 учебника информатики, которая позволит вам получить умения, лежащие в основе профессий, связанных с разработкой или активным использованием компьютерной техники и компьютерных программ. Вы любите играть в компьютерные игры? А вы задумывались над тем, что многочисленные миры из ваших игр никогда не существовали в действительности, а появились на свет благодаря силе воображения и профессиональному мастерству создателей этих игр. Вы представляете, как это заманчиво - создавать собственные миры? Профессии, связанные с созданием компьютерных программ не только пользуются хорошим устойчивым спросом, но и очень увлекательны. Зачастую программисты работают, даже не замечая, как летит время. Надеемся, вы помните, что в книге 2 нашего учебника мы разместили учебные модули, с помощью которых вы сможете изучить теоретические основы информатики, сквозную линию модулей с 7-го по 9-й класс, нацеленную на обучение программированию, а также модули профессиональной ориентации, с помощью которых можно научиться основам профессий, опирающихся на применение компьютеров. В книге 2 вы встретитесь со всеми тремя этими видами модулей. С помощью модуля «Web-конструирование. Основы мастерства» вы сможете познакомиться с некоторыми секретами создателей сайтов. В модуле «Алгоритмизация и программирование» вы сможете продолжить обучение программированию на языке Паскаль. Модуль «Знакомство с математической логикой» относится к теоретическим модулям, с его помощью можно научиться составлять логические формулы и решать с их помощью задачи. Как работать с учебником Просмотрите «Содержание», перелистайте учебник. Вы заметите, что он разделён на модули. Вы будете изучать модули в том порядке, который предложит учитель. Практически в каждом модуле мы предусмотрели пять основных параграфов. Изучив эти параграфы, вы напишете проверочную работу, по итогам которой узнаете, как вы освоили новый материал: ниже необходимого уровня, на необходимом или повышенном уровне. Далее вы будете работать самостоятельно, выполняя по указанию учителя задания того уровня, которого вы пока не достигли. Если проверочная работа покажет, что вы освоили и повышенный уровень, то вы будете выполнять задания самого высокого - максимального уровня. Учитель в любой момент может предложить вам перейти на выполнение заданий более высокого уровня. По окончании выполнения заданий учебника учитель проведёт итоговую проверочную работу. Далее в модуле расположены дополнительные параграфы, задания к ним и проверочные работы. Основные параграфы выделены в учебнике зелёной полосой вверху страницы, дополнительные - розовой полосой. Дополнительный материал, который вы не изучите на уроках, вы сможете использовать на факультативах и кружках. На уроках информатики вы сможете освоить умения, которые помогут вам более эффективно использовать компьютеры и компьютерные сети для решения возникающих в вашей жизни задач. Кроме того, учитель может решить, что вам надо освоить умения, которые помогут вам заниматься разработкой новых компьютерных программ или заложат основы профессиональной деятельности, тесно связанной с применением компьютерной техники. Кроме того, наш учебник, как и все учебники Образовательной системы «Школа 2100», поможет вам в развитии универсальных учебных действий. В учебнике вам могут встретиться задания, обозначенные кружками и фоном разного цвета - это условные знаки. Каждый цвет соответствует определённой группе умений: • - организовывать свои действия: ставить цель, планировать работу, действовать по плану, оценивать результат; • - работать с информацией: самостоятельно находить, осмысливать и использовать её; 4 ' 1^ - общаться и взаимодействовать с другими людьми, владеть устной и письменной речью, понимать других, договариваться, сотрудничать; ' I - развивать качества своей личности, оценивать свои и чужие слова и поступки; 0, так обозначены задания, где нужно применить разные группы умений, мы называем их жизненными задачами и проектами. Для успешного изучения информатики и овладения универсальными учебными действиями на уроках используется проблемно-диалогическая образовательная технология. Поэтому структура параграфа, где вводится новый материал, имеет в учебнике следующий вид. ПОСТАНОВКА ПРОБЛЕМЫ УРОКА Это подведение к теме (вопросу, цели) урока: вы обсуждаете проблему в предложенном материале и формулируете главный вопрос урока (всем классом, в группе или в паре). Сравните свой вариант вопроса с авторским. Авторские вопросы к параграфам расположены в «Содержании» под названиями параграфов и выделены курсивом. НЕОБХОДИМЫЕ БАЗОВЫЕ ЗНАНИЯ Так обозначены вопросы и задания по изученному материалу, который вам необходим для открытия нового знания. РЕШЕНИЕ ПРОБЛЕМЫ Вы в группе, в паре или совместно с учителем, ведя диалог, осуществляете поиск решения проблемы. Для решения проблемы вы работаете с текстом. ОБОБЩЕНИЕ НОВЫХ ЗНАНИЙ На этом этапе вы формулируете вывод и проверяете свои предположения, сравнивая их с авторским решением проблемы - научными формулировками правил или определений. ПРИМЕНЕНИЕ ЗНАНИЙ Так обозначены задания на применение новых знаний. Задания, помеченные «звёздочкой», имеют повышенную сложность. ОПЕРАЦИИ Раздел «Операции» позволит вам научиться выполнять действия с компьютерными программами, необходимые для решения учебных задач. В конце модуля вы найдёте раздел «Решаем жизненные задачи и работаем над проектами». Задачи и проекты могут выполняться как на уроках, так и на факультативах и кружках. Там же находится очень важный раздел «О профессиях». Прочитайте его и подумайте, какие профессии вам больше по душе. Что такое жизненные задачи? Это проблемы, с которыми вы можете столкнуться в жизни и для решения которых вам понадобятся разные знания и умения. Они оформлены следующим образом: Название задачи Ваша роль. Человек, в роли которого вы должны себя представить, решая проблему. Описание. Условия, в которых возникла проблема. Задание. То, что нужно сделать и получить в итоге. Что такое проект? Это любое самостоятельное дело, которое предполагает: 1) оригинальный замысел (цель); 2) выполнение работы за определённый отрезок времени; 3) конкретный результат, представленный в итоге. Что можно считать результатом проекта? • Предметы, сделанные своими руками: макеты, модели или вещи для практического использования. • Мероприятия: спектакли, фотовыставки, викторины, конференции, праздники и тому подобное - при условии, что они подготовлены самими учениками. • Информационные продукты: газеты, книжки, плакаты, карты, стихотворения, рассказы, доклады, отчёты об исследованиях и т. д. • Решение конкретных проблем: изменение, улучшение конкретной ситуации, например уборка мусора на школьном дворе. 6 Правила проектной деятельности 1. Каждый может начать собственный проект. 2. Каждый может объединиться с другими в ходе работы над проектом. 3. Каждый может выйти из проекта при условии, что он не подводит других. 4. Каждый может не участвовать ни в одном проекте. Как оценить свои учебные достижения? Для этого надо освоить алгоритм самооценки: 1. Какова была цель задания (что нужно было получить в результате)? 2. Вы выполнили задание (получен ли результат)? 3. Вы выполнили задание верно или с ошибкой? 4. Вы выполнили задание самостоятельно или с чьей-то помощью? 5. Вспомните, как вы ставите отметки. Определите свою отметку. 8 Модуль 1. Алгоритмизация и программирование Этот модуль поможет вам: • узнать, что такое двоичные данные и как компьютер с ними работает; • разобраться в новых типах данных; • улучшить свои навыки в практическом программировании. Для этого вам надо научиться: • разбираться в логических конструкциях языка Паскаль; • работать с массивами; • пользоваться подпрограммами; • работать в интегрированной среде разработки программ; • искать ошибки в программах - отлаживать их. 9 10 Модуль 1. Алгоритмизация и программирование Введение Дорогие друзья! В этом году мы с вами продолжим изучать программирование. В 7-м и 8-м классах мы научились многому: • познакомились с понятием «алгоритм» и со способами его записи; • узнали о структуре программы на языке программирования; • изучили различные типы данных языка Паскаль; • работали в интегрированной среде разработки и отлаживали программы; • разобрали различные алгоритмы. Однако впереди у нас с вами ещё много важного и интересного. Поэтому давайте скорее перевернём эту страницу и перейдём к новому материалу. Удачи вам! § 1. Системы счисления 11 § 1. Системы счисления ПОСТАНОВКА ПРОБЛЕМЫ УРОКА Учитель подошёл к доске и нарисовал на ней: 123. — Что я нарисовал? — спросил учитель. — Вы написали число 123, — сказала Маша. - Нет, - запротестовал Вася, - вы нарисовали три цифры: 1, 2 и 3. — Хорошо, — сказал учитель, — а теперь посмотрите на это, — и написал: CXXIII. - Ну, это просто, - обрадовался Петя, - это тоже число 123, только его так римляне записывали! - Правильно, - сказал учитель, - я могу записывать числа различными способами. • Как вы думаете, есть ли ошибки в высказываниях ребят или каждый из них прав? Сформулируйте основной вопрос урока. Сравните свою формулировку с авторской (с. 1 91 учебника). РЕШЕНИЕ ПРОБЛЕМЫ ЧИСЛА И ЦИФРЫ Как вы думаете, что такое число? Как ни странен этот вопрос, но он является основополагающим не только в математике и информатике, но и в философии. Легендарный Пифагор считал, что «всё в мире есть число». Конечно, это аллегория, однако и в ней есть доля истины. С помощью чисел человек описывает такую характеристику окружающего мира, как количество. С древних времён людям приходилось что-то мерить в количественном отношении, и такой мерой стало число. Со временем это понятие развивалось, обогащалось и превратилось в итоге в важнейшее математическое понятие. Итак, число - это количественная мера. Что же такое цифра? Цифры - это символы: значки, рисунки, с помощью которых люди стали записывать числа. С течением времени образовались устойчивые наборы таких символов, каждый набор образует цифровой алфавит. Например, мы используем арабские цифры: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9; а древние римляне использовали свои римские цифры: I, V, X, L, C, D, M. Мы можем сами придумать свой набор, например такой: ^, ^, ^, ^, ^, ^, ^, ^, Количество символов в алфавите называется размерностью алфавита. 12 Модуль 1. Алгоритмизация и программирование В привычном нам цифровом алфавите Ю цифр, следовательно, его размерность равна 10. • Какова размерность алфавита римских цифр? Итак, у нас есть цифры, с помощью которых мы хотим записать число. Можем ли мы это сделать? Необходимы правила, следуя которым мы запишем число, которое будет понятно другим людям. Такие правила называются системой счисления. СИСТЕМЫ СЧИСЛЕНИЯ Система счисления - это способ записи чисел с помощью алфавита цифр. Как вы видели, одно и то же число можно записать по-разному. Например, число 1 5, записанное в привычной нам десятичной системе счисления, в римской системе счисления будет выглядеть как XV. Все системы счисления делятся на две большие группы: позиционные и непозиционные. Давайте их рассмотрим. ПОЗИЦИОННЫЕ СИСТЕМЫ СЧИСЛЕНИЯ Система счисления называется позиционной, если количественное значение каждой цифры (говорят также: вес, привносимый цифрой в число) зависит от её местоположения в записи числа. Примером позиционной системы счисления является десятичная система счисления, которую люди используют повсеместно уже много веков. Своим названием десятичная система обязана размерности используемого алфавита. А количество цифр - 10 связано с тем, что когда-то для счёта человек использовал только пальцы на руках. Размерность алфавита системы счисления (например, число 10 в десятичной системе счисления) называют также основанием системы счисления. Поясним, что такое вес цифры в числе. Рассмотрим число 1213. Отдельную позицию в записи числа называют разрядом. Каждый разряд имеет свой номер. Примем следующий принцип нумерации разрядов: 1) будем нумеровать разряды справа налево; 2) будем нумеровать разряды с нуля (в принципе, можно нумеровать и с единицы). В нашем примере нумерация разрядов будет такой: 3 2 10 12 13 § 1. Системы счисления 13 В записи этого числа цифра 1 присутствует два раза: первый раз в первом разряде, а второй раз - в третьем. Первый раз цифра 1 привносит в число 1 десяток (101), а во второй - 1 тысячу (103). Цифра 2 привносит в число 2 сотни (2 • 102), а число 3 - 3 единицы (3 • 100). Таким образом, вес цифры - это количество, которое цифра привносит в число. Тогда получается, что наше число выражает следующее количество: Число = 1 •Ю3 + 2 •Ю2 + 1 •Ю1 + 3 •Ю0. Такая запись называется развёрнутой формой записи числа. Она несколько громоздка, поэтому на практике пользуются сокращённой записью чисел. Наше число в сокращённом виде будет выглядеть так: Число = 123410. Нижний индекс, расположенный после записи числа, обозначает основание системы счисления, в которой записано число. Когда мы говорим о десятичной системе счисления, то обычно этот индекс не записывается. В качестве тренировки переведём запись числа 1 532110 из сокращённой формы в развёрнутую. 1) Расставим номера разрядов над этим числом: 4 3 2 1 0 1 5 3 2 1 2) Запишем развёрнутую форму числа: 1532110 = 1 •Ю4 + 5 •Ю3 + 3 •Ю2 + 2 •Ю1 + 1 •Ю0. Конечно, из позиционных систем счисления десятичная система далеко не единственная. Скажем больше: позиционных систем счисления существует бесконечно много. Некоторыми из них вы пользуетесь постоянно, зачастую сами того не замечая. Например, широко распространена двенадцатеричная система счисления. Она используется как для счёта времени (1 2 часов), так и в английской системе мер и весов (1 английский пенс = 12 шиллингов, 1 дюйм = 1/12 фута, 1 дюжина = 12 единиц). В вычислительной технике применяется двоичная система счисления. О ней мы будем говорить в дальнейшем более подробно. 14 Модуль 1. Алгоритмизация и программирование НЕПОЗИЦИОННЫЕ СИСТЕМЫ СЧИСЛЕНИЯ В отличие от позиционных систем счисления, в непозиционных системах цифра всегда весит одинаково, независимо от места её расположения в числе. Самой простой непозиционной системой является единичная система счисления. Вы все с ней знакомились, когда учились в начальной школе считать на счётных палочках. Каждая палочка (или чёрточка) привносит в число всегда одну единицу, независимо от того, где мы её расположим. Например, число 5 мы можем записать как | | | | | , а число 10 в виде | | | | | | | | | | . Недостаток этой системы счисления виден сразу. Запись больших чисел в ней будет очень громоздкой. Следующая весьма популярная система, которая используется с давних времён до наших дней, - это римская система счисления. Алфавит этой системы показан на рис. 1.1. Цифра Значение I 1 V 5 X 10 L 50 C 100 D 500 M 1000 Рис. 1.1 Римлянам вполне хватало этих 7 цифр для того, чтобы удовлетворить все свои потребности в счёте. В римской системе счисления число 12 будет записано как XII, а число 80 - как LXXX. Но вы справедливо можете заключить, что число 1 2 можно записать как VVII или вообще как ШШШШ. Как такое может быть? Самый главный недостаток любой непозиционной системы заключается в том, что любое число может быть в ней представлено множеством способов. Чтобы этого избежать, нужно ввести дополнительные правила. Римляне так и поступали. Чтобы записать число 1 2, они находили ближайшее к нему слева (то есть не большее его) число, которое можно было записать одной цифрой алфавита. В нашем случае это будет число 10. Они записывали его: X. Затем римляне вычитали из числа 12 число 10 и проводили § 1. Системы счисления 15 аналогичную операцию с остатком. И так до тех пор, пока не получался ноль (хотя у римлян обозначения для числа ноль не было). Ещё римляне придумали правило сокращения записи, которое заключалось в том, что если меньшую цифру расположить перед большей, то она будет вычитаться из большей, а не складываться с ней. Это позволило записывать, например, число 9 не как VIIII, а как IX, а число 99 - не как LXXXXVIIII, а как IC. • Как вы думаете, сколько подобных ситуаций существует? Теперь давайте попробуем перевести число 149 из десятичной системы счисления в римскую. Найдём ближайшее слева к числу 149 число, которое можно записать одной римской цифрой. Этим числом является 100. Значит, первая цифра нашего римского числа - C. Вычтем из 149 число 100, получим 49. Теперь переведём в римскую систему число 49. Принцип тот же. Найдём ближайшее слева число, которое можно записать одной римской цифрой. Это 10. Значит, вторая цифра будет X. Вычтем 10, получим 39. Следующая цифра - X, останется 29, опять цифра Х, в остатке 1 9, опять Х, в остатке 9. Но для 9 мы уже получили раньше римскую запись - IX. Итак, ответ: 149 = CXXXXIX. Но в нашем алгоритме есть место, где можно было применить правило сокращения записи. Где же оно? В числе 49. Его можно представить как 50 - 1 и записать как IL. Поэтому другая, короткая запись нашего числа будет выглядеть так: CIL. Перевод из римской системы счисления в десятичную совсем прост. Необходимо воспользоваться таблицей соответствия римских цифр десятичным числам, не забыть о правиле сокращения записи и просуммировать все числа. Переведём число MCMXCIX из римской системы счисления в десятичную. Читаем число слева направо. Первая цифра M. Следующая за ней - С: меньше, чем М. Значит, первое слагаемое - это 1000. Следующая цифра - С. Но за ней следует М. Применяя правило сокращения, получаем новое слагаемое: 1000 - 100 = 900. М мы уже использовали, поэтому дальше его не рассматриваем. Настала очередь X - это 10, но за ней идёт С. Опять работает правило сокращения, и мы получим 100 - 10 = 90. Читаем символ I: это единица. За ней идёт Х. Получаем 9. Складываем полученные значения: 1000 + 900 + 90 + 9 = 1999. И, конечно, отметим, что 1999 можно было записать как MIM для большей краткости. 16 Модуль 1. Алгоритмизация и программирование ОБОБЩЕНИЕ НОВЫХ ЗНАНИЙ Число - это количественная мера, необходимая человеку для счёта и других измерений. Цифра - это символ, с помощью которого записываются числа. Система счисления - это способ записи чисел с помощью алфавита цифр. Системы счисления бывают позиционными и непозиционными. В системах первого типа каждая цифра имеет вес в зависимости от её месторасположения в числе, а в системах второго типа такого условия нет. К позиционным системам относятся десятичная, двоичная, двенадцате-ричная и многие другие. Самые известные непозиционные системы счисления - единичная и римская. ПРИМЕНЕНИЕ ЗНАНИЙ 1. Объясните, чем отличаются понятия числа и цифры. 2. Что такое система счисления? На какие группы делятся системы счисления? 3. Какова размерность алфавита в двенадцатеричной системе счисления? 4. Запишите в развёрнутой форме числа 234, 512, 135762. 5. Какой вес привносит цифра 8 в числа: 1 28, 1 82, 821 ? 6. Переведите из римской системы счисления в десятичную числа: IXCLX, IXIC, CLXVI. 7. Переведите из десятичной системы счисления в римскую числа: 512, 144, 44, 1 328. Попробуйте найти несколько форм записи этих чисел. § 2. Двоичная система счисления, или Как хранятся данные в компьютере 17 § 2. Двоичная система счисления, или Как хранятся данные в компьютере ПОСТАНОВКА ПРОБЛЕМЫ УРОКА Вася читал книгу по истории вычислительной техники. В ней говорилось, что компьютер представляет собой сложную систему из множества приборов сродни электрической лампочке. Каждый прибор может или быть включённым, или быть выключенным. А самое странное заключалось в том, что с помощью таких приборов компьютер может хранить числа и другую информацию! • Что удивило Васю? Сформулируйте основной вопрос урока. Сравните свою формулировку с авторской (с. 191 учебника). НЕОБХОДИМЫЕ БАЗОВЫЕ ЗНАНИЯ Вспомните, что вы узнали о системах счисления. (§ 1) РЕШЕНИЕ ПРОБЛЕМЫ ВСЕГО ЛИШЬ ДВА СОСТОЯНИЯ Электронная вычислительная техника конструируется на устройствах, которые имеют только лишь два устойчивых состояния: включено/ выключено (истина/ложь). Такими устройствами сначала были электронные лампы, затем - пришедшие им на смену транзисторы, а после - интегральные схемы. Для хранения данных с помощью подобных устройств лучше всего подойдёт такая система счисления, алфавит которой содержит тоже только два символа. Тогда каждому символу будет соответствовать своё состояние. И такая система счисления есть - она называется двоичной. Один разряд в двоичной системе имеет собственное название - бит. Слово «бит» происходит от английского сокращения bit (binary digit) и означает «двоичная цифра». С помощью двоичных цифр (в цифровом виде) в компьютере представляются любые данные: числовые, текстовые, графические, звуковые. Посмотрите, как выглядят двоичные числа: 110001101012, 110012, -11012. Мы видим, что для записи двоичных чисел применяются только цифры 0 и 1. Первое из записанных выше двоичных чисел соответствует десятичному 1589. Нельзя не обратить внимание на то, что в двоичной системе запись числа становится гораздо длиннее, чем в десятичной (4 разряда против 11). В чём же тогда преимущество двоичной системы? В простоте проведения операций. 18 Модуль 1. Алгоритмизация и программирование СЛОЖЕНИЕ И УМНОЖЕНИЕ В ДВОИЧНОЙ СИСТЕМЕ СЧИСЛЕНИЯ Для того чтобы уметь складывать и умножать числа, необходимо задать правила выполнения этих операций. Вы, безусловно, учили таблицы сложения и умножения в десятичной системе. Они даже размещены на обратных сторонах школьных тетрадей. Освежите в памяти эти таблицы. Теперь мы предлагаем вам посмотреть по очереди на таблицы сложения и умножения в двоичной системе счисления (рис. 1.2). + 0 1 0 0 1 1 1 10 * 0 0 0 0 0 1 0 1 Рис. 1.2 Поскольку в алфавите двоичной системы счисления всего две цифры, таблицы имеют по три строки и три столбца (одна строка и один столбец - это заголовки), а количество вариантов каждой операции равно четырём. Сложение и умножение - это бинарные операции. Таблицы сложения и умножения в десятичной системе счисления имеют по 11 строк и столбцов. Проверьте это. Рассмотрим четыре варианта операции сложения: 1) 0 + 0 = 0 2) 0 + 1 = 1 3) 1 + 0 = 1 4) 1 +1 = 1 Поясним четвёртый вариант. Складывая 1 и 1, мы должны перенести единицу в следующий разряд, поскольку цифры 2 в двоичной системе счисления нет. Аналогичная ситуация возникает, когда мы складываем, например, 9 и 1 в десятичной системе. Мы превышаем максимальное значение разряда единиц и вынуждены добавить единицу в разряд десятков. Поэтому 9 + 1 = = 10, то есть 0 в разряде единиц и 1 в разряде десятков. Сложим в двоичной системе числа 101 и 111. Будем складывать «в столбик» (по аналогии с тем, как мы это делаем в десятичной системе), в соответствии с таблицей сложения в двоичной системе: 1 0 1 + 1 1 1 110 0 1. Сложим 1 и 1 (значения в крайних правых разрядах). По таблице сложения результат этой операции - 10. Поэтому запишем в нулевой разряд результата цифру 0, а единицу перенесём в следующий разряд. § 2. Двоичная система счисления, или Как хранятся данные в компьютере 19 2. Теперь сложим 0 и 1, получим 1. Но нельзя забывать про перенос (1). Добавим и его, получим снова 10, 0 запишем в первый разряд результата, а 1 перенесём далее. 3. Складываем 1 и 1, получаем 10, добавляем 1 из переноса. Получаем 11. Единицу пишем во второй разряд результата и переносим 1 в старший разряд. 4. Последняя единица просто пишется в третий разряд результата. Итак, 1012 + 1112 = 11002. • Сколько битов занимает полученный результат? Варианты операции умножения: 1) 0 • 0 = 0 2) 0 • 1 = 0 3) 1 • 0 = 0 4) 1 • 1 = 1 Давайте умножим «столбиком» те же числа, что мы складывали ранее: 1 1 1 0 1 1 1 0 0 0 1 1 Посмотрите, насколько умножение в двоичной системе проще, чем в десятичной. Мы просматриваем число 101 справа налево. Первая цифра - 1, поэтому просто переписываем первый сомножитель: 111. Затем мы встречаем 0. Ничего не записываем. Идём дальше, снова 1 - переписываем сомножитель 111, со сдвигом влево на два разряда (поскольку ноль пропущен). После этого складываем поразрядно получившиеся числа. Мы видим, что умножение на 1 первого сомножителя означает просто его копирование с соответствующим сдвигом по разрядам, без вычислений, а умножение на 0 вообще пропускается. Результат: 111, 1012 = 1000112. ТАБЛИЦА СООТВЕТСТВИЯ ДВОИЧНЫХ И ДЕСЯТИЧНЫХ ЧИСЕЛ Вы научились складывать двоичные числа. Настало время составить таблицу соответствия двоичных и десятичных чисел. Начнём с нуля и будем прибавлять на каждом шаге по единице в одной и другой системе счисления, а результаты записывать в таблицу. В итоге таблица примет следующий вид (рис. 1.3). •к + 20 Модуль 1. Алгоритмизация и программирование Десятичная с. с. Двоичная с. с. 0 0 1 1 2 10 3 11 4 100 5 101 6 110 7 111 8 1000 9 1001 10 1010 11 1011 12 1100 13 1101 14 1110 15 1111 Рис. 1.3 Мы специально рассмотрели числа от 0 до 1 5, чтобы показать, как заполняются четыре разряда двоичного числа. С помощью этой таблицы можно быстро переводить числа из диапазона [0..1 5] из двоичной системы счисления в десятичную и обратно. ПЕРЕВОД ЧИСЕЛ ИЗ ДВОИЧНОЙ СИСТЕМЫ СЧИСЛЕНИЯ В ДЕСЯТИЧНУЮ А что же делать, если необходимо перевести в десятичную систему число, большее 11112? Конечно, можно продолжать заполнение таблицы. Но это же неудобно! Нужно найти более разумный и быстрый способ перевода. И такой способ есть! Давайте вспомним, что такое развёрнутая форма записи числа и применим её к двоичной системе счисления. Правило перевода: 1. Пронумеровать разряды числа справа налево, начиная с нуля. 2. Представить число в виде суммы произведений цифр числа на веса соответствующих разрядов - получить развёрнутую форму записи двоичного числа. (Надо только помнить, что в двоичной системе счисления вес разряда определяется степенью числа 2 - основания системы счисления, по аналогии с тем, что в десятичной системе это степень числа 10.) § 2. Двоичная система счисления, или Как хранятся данные в компьютере 21 3. Вычислить значение полученного выражения в десятичной системе счисления. Результат - число, записанное в десятичной системе счисления. Переведём из двоичной системы счисления в десятичную число 1000112. (Напомним, что мы его получили в результате умножения чисел 1112 и 1012.) Итак, расставим номера разрядов над цифрами числа: 5 4 3 2 1 0 1 0 0 0 1 1 Запишем развёрнутую форму числа и вычислим его значение в десятичной системе: 1000112 = 1 •г5 + 0^24 + 0^23 + 0^22 + 1^2' + 1^2° = 32 + 2 + 1 = 3510. Проверим правильность нашего перевода следующим образом. Число 1000112 мы получили в результате умножения чисел 1112 и 1012. Переведём их в десятичную систему счисления по нашей таблице соответствия. Получим 7 и 5. 7^5 = 35. Значит, наш перевод правильный. ПЕРЕВОД ЧИСЕЛ ИЗ ДЕСЯТИЧНОЙ СИСТЕМЫ СЧИСЛЕНИЯ В ДВОИЧНУЮ Естественно, существует и обратный перевод чисел: из десятичной системы счисления в двоичную. Он немного сложнее, поэтому будьте внимательнее. Правило перевода: 1. Разделить число на 2 нацело. 2. Частное снова разделить на два. 3. Продолжать деление (пункт 2) до тех пор, пока не получится частное, равное 0. 4. Записать остатки от деления в обратном порядке. Это и будет ответ. Переведём в двоичную систему счисления число 1 3: Результат: 1101, 22 Модуль 1. Алгоритмизация и программирование Проверим его, переведя 1Ю12 в десятичную систему: 3 2 10 110 1 11012 = 1^23 + 1^22 + □•21 + 1^2° = 8 + 4 + 1 = 1310. ЕДИНИЦЫ ИЗМЕРЕНИЯ ИНФОРМАЦИИ Бит (двоичный разряд) - одно из основополагающих понятий в информатике, поскольку в этих единицах измеряют информацию. Но мы уже неоднократно видели, что в двоичной системе счисления запись числа занимает очень много места. Для измерений это неудобно. Поэтому на практике пользуются производными от бита величинами. 8 битов образуют 1 байт. В байтах измеряется размер, который переменная занимает в памяти. Например, переменная типа integer занимает в памяти компьютера 4 байта, то есть 32 бита. 1024 байта образуют 1 килобайт. Обратите внимание, что приставка «кило» в килобайте и в привычных нам единицах измерения, например веса и длины (килограмм, километр и пр.), обозначает разные коэффициенты. Их нельзя путать. Килограмм - это 103 = 1000 граммов, а килобайт - это 210 = 1024 байта. 1024 килобайта составляют 1 мегабайт. Сколько байтов в мегабайте? 1 мегабайт = 1024 килобайта = 1024 • 1024 = 220 байтов. СКОЛЬКО ЧИСЕЛ МОЖНО ХРАНИТЬ В ОДНОМ БАЙТЕ? В завершение давайте зададимся вопросом: какой диапазон целых чисел можно записать в 1 байт? 1 байт - это 8 битов. Представим его таблицей из 8 ячеек. Минимальное целое число, которое можно записать в 8 ячеек, - это 000000002, а максимальное - это 111111112: 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 Переведём максимальное число в десятичную систему: 76543210 11111111 111111112 = 1^27 + 1^26 + 1^25 + 1^24 + 1^23 + 1^22 + 1^21 + 1^20 = = 128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = 25510 = 28 - 1. Значит, максимальное целое число, которое мы можем записать в 1 байт, -это 255. Следовательно, диапазон хранимых чисел выглядит так: [0..255]. Размер этого диапазона - 256 (28) чисел. § 2. Двоичная система счисления, или Как хранятся данные в компьютере 23 Заметьте, что мы рассматривали только положительные числа. Если значение старшего (седьмого) разряда будет отвечать за знак числа (0 - положительное число, 1 — отрицательное), то диапазон чисел, которые можно записать в 1 байт, будет выглядеть иначе: [-1 28..+1 27]. Но количество хранимых чисел всё равно будет равно 256. ОБОБЩЕНИЕ НОВЫХ ЗНАНИЙ В компьютере числа и другие данные хранятся в двоичном представлении (в двоичной системе счисления). Алфавит двоичной системы счисления состоит из цифр {0, 1}. Бит - это один двоичный разряд. Для перевода числа из двоичной системы счисления в десятичную необходимо представить двоичное число в виде суммы произведений цифр числа на веса соответствующих разрядов. Надо помнить, что в двоичной системе счисления вес разряда определяется степенью числа 2, по аналогии с тем, что в десятичной системе это степень числа 10. Для перевода числа из десятичной системы счисления в двоичную необходимо делить число на 2 нацело, пока целая часть не станет равна нулю, затем остатки от деления записать в обратном порядке. Информация измеряется в битах и производных от него величинах, поскольку в двоичной системе счисления запись числа очень длинная. 1 байт = 8 битов, 1 килобайт = 1024 байта. В 1 байте можно хранить 256 целых чисел. ПРИМЕНЕНИЕ ЗНАНИЙ 1. Какой алфавит у двоичной системы счисления? Почему она так удачно подходит для использования в цифровых устройствах? 2. Что такое бит, байт и килобайт? 3. В какой системе счисления запись числа длиннее: в двоичной или десятичной? 4. Сложите в двоичной системе числа: 10012 и 1012, 112 и 10112. Переведите полученный результат в десятичную систему счисления и проверьте свои вычисления. 5. Умножьте в двоичной системе числа: 11102 и 1012. Переведите полученный результат в десятичную систему счисления и проверьте свои вычисления. 6. Переведите из десятичной системы счисления в двоичную числа: 1 8, 41,33. 7. Каков диапазон чисел, который можно хранить в переменной типа integer (она занимает в памяти 4 байта)? 24 Модуль 1. Алгоритмизация и программирование § 3. Символьный тип данных ПОСТАНОВКА ПРОБЛЕМЫ УРОКА Мы обсуждали с вами, что цифра — это символ, с помощью которого записываются числа. Но символы служат для записи не только чисел, но также слов и текста. Получается, что символ — это важнейший элемент человеческой культуры. А что же компьютер? Умеет ли он работать с символами? Какие средства для этого предоставляются программисту? • Сформулируйте основной вопрос урока, который объединит все приведённые здесь вопросы. Сравните свою формулировку с авторской (с. 191 учебника). НЕОБХОДИМЫЕ БАЗОВЫЕ ЗНАНИЯ Вспомните структуру программы на языке Паскаль и основные конструкции языка. (Учебники для 7-го и 8-го классов, модули «Алгоритмизация и программирование».) Вспомните свой опыт работы в интегрированной среде разработки программ. (Учебники для 7-го и 8-го классов, модули «Алгоритмизация и программирование».) РЕШЕНИЕ ПРОБЛЕМЫ ЧИСЛА И СИМВОЛЫ До текущего момента (в 7-м и 8-м классах) мы с вами, программируя, имели дело только с числами и логическими значениями. Программы, которые мы создавали, могли обрабатывать ввод данных с клавиатуры, анализировать и преобразовывать их, организовывать вывод чисел и логических значений на экран. Кроме того, мы умеем просто выводить информационные строки, такие как: «Введите число», «Ввод заканчивается нулём» и т. д. Настало время научиться работать с символьной информацией. Мы постоянно пользуемся символами, когда пишем программы. Собственно, сам текст программы из них и состоит. Кроме того, из символов состоит алфавит любого языка. Но языков много, а символов, следовательно, ещё больше. Как же символы хранятся в компьютере и как нам, программистам, с ними работать? Символы в компьютере хранятся и обрабатываются как целые числа. Человек придумал специальные таблицы, которые назвал кодовыми. Эти таблицы задают соответствие между символами и числами. Таким образом, у каждого символа есть свой код. § 3. Символьный тип данных 25 • Обратное утверждение «Любому числу может соответствовать некоторый символ» верно не всегда. Как вы думаете, почему? Кодовых таблиц существует множество, и у каждой есть своё имя. Сначала для каждого языка создавалась отдельная таблица. Этот процесс никто не контролировал, поэтому постоянно возникали нестыковки. Дело доходило даже до того, что одному языку соответствовало несколько вариантов таких таблиц. Например, для русского языка существуют таблицы Windows1251, KOI8-R и т. д. Наследие тех времён мы наблюдаем сегодня, когда пытаемся открыть web-страницу в браузере, а она открывается в нечитаемом виде. Приходится менять кодировку. В результате родилась идея спроектировать такую кодовую таблицу, которая будет хранить все существующие символы. Это позволяет избежать путаницы с многими таблицами. И такая таблица была создана в 1991 году. Она получила название Unicode. Для хранения одного символа было выделено 2 байта (1 6 битов). Старые кодировки использовали для хранения символа 1 байт. • Какое количество целых чисел можно хранить в двух байтах? Со временем стандарт Unicode модифицировался, изменялся и усложнялся. Однобайтовые кодировки применяются и по сей день, однако, согласно статистике компании Google, на начало 2010 года доля web-сайтов, использующих кодировку семейства Unicode, составила порядка 50%. СИМВОЛЬНЫЙ ТИП В ПАСКАЛЕ Для работы с символами в языке Паскаль определён специальный тип char. Это название происходит от английского слова character - символ. В различных компиляторах языка Паскаль для хранения переменной типа char выделяется или 1, или 2 байта. В среде ABCPascal.NET, в которой мы с вами работаем, для хранения типа char выделено 2 байта. Для создания переменной символьного типа в разделе описания var необходимо указать: var c: char; Такой текст говорит о том, что мы создали переменную типа char. К символьным переменным применимы операции присваивания вида с := 'A';. Символьная константа при этом указывается в апострофах. Кроме того, в языке применяются выражения специального вида # число, где число должно находиться в диапазоне от 0 до 65 535. Данное выражение возвращает Unicode-символ, код которого равен указанному числу. 26 Модуль 1. Алгоритмизация и программирование Примеры: c := #21056; с := #65; Символы можно сравнивать. При этом большим будет тот символ, код которого больше. Например: #21056 > #65. Ввод и вывод символьных переменных оформляется аналогично вводу и выводу чисел с помощью процедур readln и writeln: program c1; var c: char; begin write('Введите символ: '); readln(c); writeln('Вы ввели: ', c); end. Для преобразования символов в их коды в однобайтовой кодировке Windows1251 и обратно используются встроенные функции: Chr (n) -возвращает символ с кодом n и Ord (с) - возвращает код символа c. Для преобразования символов в их коды в кодировке Unicode и обратно используются функции: ChrUnicode (w) - возвращает символ с кодом w в кодировке Unicode и OrdUnicode (с) - возвращает код символа c в кодировке Unicode. Рассмотрим примеры. Пример 1 Требуется написать процедуру, выводящую все строчные латинские буквы. program c1; procedure print; var ch: char; begin for ch := 'a' to 'z' do write(ch); writeln; end; begin print; end. Этот пример показывает, что, поскольку символьные переменные можно сравнивать, то становится возможным их перебирать в цикле. § 3. Символьный тип данных 27 Пример 2 Символы вводятся с клавиатуры до нажатия клавиши Enter. Необходимо подсчитать, сколько введено цифр. program c2; var ch: char; s: integer; begin s := 0; writeln('Вводите цифры до нажатия клавиши Enter'); read(ch); while (ch <> chrUnicode(13)) do begin if (ch <= '9') and (ch >= #48) then s := s + 1; read(ch); end; writeln('Введено цифр: ', s); end. В этой программе приведены варианты работы с символьными переменными. В начале программы мы обнуляем переменную s, в которой будем накапливать искомое количество цифр. Затем вводим символ ch. Условие продолжения цикла в переводе на русский язык звучит как «пока ch не равен символу с кодом 1 3^. А код 1 3 имеет символ, соответствующий клавише Enter. В теле цикла, при условии что символ ch больше или равен символу с кодом 48 (это ноль) и меньше или равен символу ' 9 ', мы увеличиваем на единицу значение s. И снова читаем с клавиатуры ch. В результате мы выводим подсчитанное значение s. Пример 3 Требуется написать программу с процедурой print, которая выводит коды всех цифр. program c3; procedure print; var ch: char; begin writeln('Символ | Код '); writeln ('-------------'); for ch := '0' to '9' do writeln(ch:4, ' |', ord(ch):4); end; 28 Модуль 1. Алгоритмизация и программирование begin print; end. В этом примере показано, что символьные переменные можно форматировать при выводе, так же как и целочисленные. ОБОБЩЕНИЕ НОВЫХ ЗНАНИЙ В компьютере символы хранятся и обрабатываются как целые числа. Каждому символу ставится в соответствие целое число - его код, поэтому существуют кодовые таблицы. Существует множество кодовых таблиц, в которых код символа занимает один байт. Unicode - это стандарт, который описывает единую кодовую таблицу для всех языков. Для работы с символьной информацией в языке Паскаль определён тип char. Конструкция вида #число означает «символ с кодом «число». Символы можно присваивать и сравнивать. В языке Паскаль определены функции по работе с символами и их кодами: ord, chr, ordUnicode, chrUnicode ПРИМЕНЕНИЕ ЗНАНИЙ 1. Объясните, что такое кодировка. Что такое символ с точки зрения программиста? 2. Какие кодировки вам известны? 3. Сколько символов может содержать кодировка, в которой под хранение одного символа выделен один байт? 4. Сколько символов может хранить таблица Unicode? 5. Напишите программу, содержащую процедуру print, которая выводит таблицу кодов строчных английских букв. Отформатируйте вывод красиво. 6. Напишите программу, содержащую процедуру print, которая выводит последовательность: AABABCAbCd _ ABC _ XYZ. 7*. Напишите функцию function char2digit (ch: char): integer, которая переводит символ-цифру в число. Подсказка: воспользуйтесь кодами цифр и отдельно нуля. § 4. Строки символов 29 § 4. Строки символов ПОСТАНОВКА ПРОБЛЕМЫ УРОКА Откройте любую книгу или текстовый документ на компьютере. Вы увидите части, главы, абзацы, предложения, слова. Но из чего, в свою очередь, состоят все эти элементы? Из символов: букв, цифр, пробелов, других знаков. Вы можете выделить любой фрагмент — цепочку, последовательность таких символов. Вы уже научились работать на компьютере с символами. А как работать не с одним символом, а с целой последовательностью — строкой символов? • Как вы думаете, что вам предстоит узнать в этом параграфе? Сформулируйте основной вопрос урока. Сравните свой вариант с авторским (с. 1 91 учебника). НЕОБХОДИМЫЕ БАЗОВЫЕ ЗНАНИЯ Вспомните структуру программы на языке Паскаль и основные конструкции языка. (Учебники для 7-го и 8-го классов, модули «Алгоритмизация и программирование».) Вспомните свой опыт работы в интегрированной среде разработки программ. (Учебники для 7-го и 8-го классов, модули «Алгоритмизация и программирование».) Что такое символьный тип данных? (§ 3) РЕШЕНИЕ ПРОБЛЕМЫ ЧТО ТАКОЕ СТРОКА? Строка - это несколько символов, расположенных друг за другом и идентифицируемых как единое целое. Например, мама мыла раму - это строка и abcd125 - тоже строка. А как быть с такой записью: 12345? Что это: число или строка? В данном случае последовательность 12345 можно интерпретировать и как число, и как строку, в зависимости от контекста, в котором эта последовательность употребляется. Для того чтобы однозначно отличать строку от числа, обычно её заключают в апострофы. Поскольку строка - это последовательность символов, то наилучшим образом она представляется массивом, элементами которого являются символы. В связи с этим на языке Паскаль строку можно описать следующим образом: str: array [1..100] of char; 30 Модуль 1. Алгоритмизация и программирование Приведённый фрагмент кода описывает строку, состоящую из 100 символов. Однако, поскольку обрабатывать строки приходится очень часто, в любой язык программирования включён специальный тип данных, предназначенный для работы с ними. В языке Паскаль таким типом является тип string. ТИП STRING Тип string позволяет описывать строки. Для того чтобы описать строку, в разделе var необходимо написать следующий текст: var str: string,- В старых компиляторах размер строки был ограничен 256 символами, но в системе PascalABC.NET строки могут иметь произвольную длину. Так, строка str из примера «бесконечна». Однако программист может при необходимости ограничивать размер описываемых им строк. Для этого после ключевого слова string необходимо в квадратных скобках указать максимальный размер строки: var str: string[100]- Максимальный размер означает то, что в переменной str может храниться любая строка, длина которой не превышает 100 символов. ОСНОВНЫЕ ОПЕРАЦИИ СО СТРОКАМИ Для ввода и вывода строк необходимо пользоваться хорошо нам известными процедурами readln и writeln. Следующий пример демонстрирует это. Код программы Вывод program s1; var str: string; begin write('Введите ваше имя: '); readln(str); writeln('Приветствуем Вас, ', str, '!'); end. Введите ваше имя: Вова Приветствуем Вас, Вова! Теперь мы понимаем, что когда мы с помощью процедуры writeln выводим что-то в «апострофах», это не что иное, как строка. § 4. Строки символов 31 Поскольку строка - это видоизменённый массив, то мы должны иметь возможность получать доступ к конкретному символу (элементу) этой строки. Такая возможность есть. Чтобы получить символ строки с номером i (i-й элемент), мы должны написать такую конструкцию: str[i]. К какому типу будет относиться элемент строки? Конечно, он описывается типом char. Рассмотрим пример. Код программы Вывод program s2; var str: string; ch: char; begin write('Введите ваше имя: '); readln(str); ch := str[1]; writeln('d Вы знаете, ', str, имени первая буква - end. что в Вашем ch, '?'); Введите ваше имя: Витя А Вы знаете, Витя, что в Вашем имени первая буква - В? Элементы строки можно не только читать, но и записывать. Посмотрите, что происходит со строкой, если изменить её элементы. Код программы Вывод program s3; var name: string; begin name := 'Маша'; writeln('Было имя name[1] := 'Д' writeln('Стало имя end. Было имя - Маша Стало имя - Даша Единственное, чего надо избегать при работе с элементами строки, - это выход за её границы! Это означает, что если в строке str находится значение 'квадрат' (7 элементов), то обращение к элементу str[10] вызовет ошибку. По этой же причине нельзя обращаться к элементам строки и с отрицательными индексами. Строки можно присваивать, при этом строки-константы заключаются в апострофы. 32 Модуль 1. Алгоритмизация и программирование Код программы Вывод program s4; var name: string; begin name := 'Вова' ; writeln('Приветствуем Вас, ', name, '!'); end. Приветствуем Вас, Вова! К строкам применимы операции отношения, а именно: = (проверка на равенство), <> (проверка на неравенство), < (меньше), > (больше), <= (меньше или равно), >= (больше или равно). • Результат какого типа возвращает каждая из приведённых выше операций? Сравнение строк производится слева направо посимвольно до первого несовпадающего символа или до конца какой-либо из строк. Большей считается та строка, в которой первый несовпадающий символ имеет больший код в кодовой таблице. Если строки имеют разную длину, но символы короткой строки совпадают с начальными символами длинной строки, считается, что короткая строка меньше. Строки равны, если они имеют равную длину и соответствующие символы совпадают. Говоря другими словами, если строки разместить в алфавитном порядке, то меньшей будет та, которая раньше встретится. Проведите эксперимент: 1) возьмите любой словарь русского языка, откройте в нём любую страницу и выберите два произвольных слова; 2) то слово, которое находится ближе к началу словаря, - меньшее. Приведём примеры сравнения строк: 1) 'abc' = 'abc '; 2) 'abc' > 'Abc' (поскольку код символа 'a' больше кода символа 'A'; проверьте это); 3) 'строка' <> 'строку'; 4) 'минута' <= 'час'. Складывать строки в том смысле, в котором мы складываем числа, конечно, нельзя. Оператор «+» применяется к строкам, но обозначает иную операцию, которая на научном языке называется конкатенацией. Если к двум строкам применить операцию «конкатенация», то вторая «приклеится» к первой. § 4. Строки символов 33 Код программы Вывод program s5; var fio, name, surname, familyname: string; begin write('Введите Ваше имя: '); readln(Name); write('Введите Ваше отчество: '); readln(Surname); write('Введите Вашу фамилию: '); readln(FamilyName); fio := FamilyName + ' ' + Name + ' ' + Surname; writeln('Приветствуем Вас, ', fio, '!'); end. Введите Ваше имя: Иван Введите Ваше отчество: Петрович Введите Вашу фамилию: Сидоров Приветствуем Вас, Сидоров Иван Петрович! Давайте проследим, как образуется значение в переменной fio. Сначала к значению переменной FamilyName (' Сидоров ') добавляется пробел и получается 'Сидоров '. Теперь к этому значению «приклеивается» содержание переменной Name (' Иван '), получается ' Сидоров Иван '. Снова «прицепляем» пробел, получаем 'Сидоров Иван '. И, наконец, дописываем значение переменной SurName (' Петрович '). Итог - ' Сидоров Иван Петрович ' - заносится в переменную fio и выводится. ДЛИНА СТРОКИ Мы уже неоднократно говорили о таком понятии, как «длина строки», обращали ваше внимание на то, что нельзя обращаться к элементу, номер которого больше, чем длина строки. Но как определить длину строки? В случае, когда мы заносим в переменную строку-константу, мы уже знаем эту длину. Например, после выполнения оператора: name := 'Маша' длина строки name равна 4 символа. А какова длина строки fio из нашего последнего примера? Мы же её формируем в процессе работы программы, причём из данных, которые вводит пользователь. Существует функция, которая сможет решить наши проблемы. Она называется length (в переводе с английского - длина). В неё поступает строка, а результат, который функция возвращает, есть длина строки. Функция length описана следующим образом: function length(s: string): integer,- Давайте напишем программу, которая продемонстрирует работу функции length. 34 Модуль 1. Алгоритмизация и программирование Код программы Вывод program s2; var name: string; begin write('Введите Ваше имя: '); readln(name); writeln('Длина Вашего имени - length(name) ' символов'); end. Введите Ваше имя: Агриппина Длина Вашего имени - 9 символов В этой программе мы вводим имя и заносим его в переменную name. Затем в процедуру writeln сначала поступает строка-константа 'Длина Вашего имени - ', затем целое число, которое возвращает функция length(name), и в заключение опять строка-константа ' символов '. В итоге получается тот вывод, который мы и наблюдаем. РЕШАЕМ ЗАДАЧУ С клавиатуры вводится строка. Требуется определить, сколько в ней цифр. Вывести это значение. Мы уже решали эту задачу, когда изучали символьный тип данных. Теперь мы можем решить её более эффектно. program dcalc; var s: string,- function calcdigits(str: string): integer; var i, col: integer; begin col := 0; for i := 1 to length(str) do if (str[i] >= '0') and (str[i] <= '9') then col : = col + 1 calcdigits := colend; begin write('Введите строку: '); readln(s); writeln('Во введённой Вами строке ' цифр'); end. calcdigits(s), Вся «изюминка» этой программы находится в функции calcdigits в выделенных строках. В переменной col мы будем вычислять количество цифр. Из- § 4. Строки символов 35 начально в эту переменную заносится значение 0. Затем с помощью цикла с параметром for мы перебираем все элементы строки от первого до последнего (значение параметра цикла равно номеру элемента строки). Если элемент строки (Str [i]) - это цифра, то мы увеличиваем значение переменной col, которую в результате и возвращаем. ОБОБЩЕНИЕ НОВЫХ ЗНАНИЙ Строка - это последовательность символов, которая идентифицируется как единое целое. Строка формируется по принципу массива, поэтому имеется возможность получать доступ непосредственно к каждому элементу строки. Нельзя обращаться к элементу по номеру строки, который больше её длины. К строкам применимы операции отношения. Оператор «+» по отношению к строкам выполняет операцию конкатенации (слияния, «склеивания») двух или более строк. Длину строки возвращает встроенная функция length. ПРИМЕНЕНИЕ ЗНАНИЙ 1. • Расскажите, как вы понимаете, что такое строка. 2. • Верно ли утверждение: строка - это массив символов? 3. Что означает следующее описание? var s: string[25]; 4. Какие функции по работе со строками в языке Паскаль вам известны? 5. • Что будет выведено на экран в результате выполнения следующего фрагмента программы? var str: string; begin str := 'Трансформация'; str [14] := ' .'; writeln(str); end. 6. С клавиатуры вводится слово длиной более 5 символов. Вывести на экран его третий символ и дважды - последний. 7. С клавиатуры вводятся два слова. Напишите функцию, отвечающую на вопрос: верно ли, что первое слово начинается на букву, на которую заканчивается второе? 36 Модуль 1. Алгоритмизация и программирование § 5. Эффективная работа со строками ПОСТАНОВКА ПРОБЛЕМЫ УРОКА У ребят возникли вопросы к учителю: «Мы же не первые, кто начинает решать задачи на строки! Неужели все профессиональные программисты заново создают все необходимые им процедуры и функции для работы со строками? Такого не может быть». Какую проблему увидели ребята? Сформулируйте основной вопрос урока. Сравните свой вариант с авторским (с. 1 91 учебника). НЕОБХОДИМЫЕ БАЗОВЫЕ ЗНАНИЯ Вспомните структуру программы на языке Паскаль и основные конструкции языка. (Учебники для 7-го и 8-го классов, модули «Алгоритмизация и программирование».) Вспомните свой опыт работы в интегрированной среде разработки программ.) (Учебники для 7-го и 8-го классов, модули «Алгоритмизация и программирование».) Что такое строки символов в Паскале? (§ 4) РЕШЕНИЕ ПРОБЛЕМЫ КАКИЕ ЗАДАЧИ РЕШАЮТСЯ С ПОМОЩЬЮ СТРОК? Строки - это настолько часто используемый в программировании объект, что для эффективной работы с ними разработчики создали большое количество вспомогательных подпрограмм. Но перед их разбором давайте уточним, каковы самые популярные действия, производимые со строками. 1. Поиск подстроки в строке. В рамках этой задачи можно узнать, встречается ли (и сколько раз) искомая подстрока в большой строке? Такая задача очень распространена в областях лингвистического анализа данных, систем управления базами данных и т. д. 2. Вставка (удаление) подстроки в строку (из строки). В качестве примера можно привести задачу по вычислению значения сложного выражения: x = у • (5 + ); у = 3 - (1 + i86). Вместо у в первую строку надо подставить его значение из второй. § 5. Эффективная работа со строками 37 3. Получение подстроки из строки. 4. Преобразование строк в числа и обратно. 5. Преобразование строки с разделителями в массив отдельных строк. 6. Уничтожение повторов в строке и т. д. ПОДПРОГРАММЫ ПО РАБОТЕ СО СТРОКАМИ В ЯЗЫКЕ ПАСКАЛЬ Все реализации языка Паскаль имеют в своём составе функции и процедуры по работе со строками. Система PascalABC.NET не стала исключением. Предлагаем вам рассмотреть средства, предоставляемые этой системой программирования. Предупреждаем, что все описываемые ниже подпрограммы работают в системе PascalABC.NET. Если вы решите программировать в другой среде, то необходимо внимательно прочитать её документацию, поскольку список используемых процедур и функций может заметно различаться. Подпрограмма и описание Пример использования function Pos(subs, s: string): integer; Возвращает номер элемента, с которого подстрока subs входит в строку s. Если subs в s не встречается, то возвращается 0 program s1; var s, s1: string; p: integer; begin readln(s); readln(s1); p := Pos(s1, s); if (p > 0) then writeln(s1 + ' входит в ' + s + ',начиная с ', p, ' символа. ' ) else writeln(s1 + ' не входит в ' + s); end. function Copy(s: string; index, count: integer): integer; Возвращает подстроку из строки s, начиная с номера index, подстрока при этом имеет длину count program s2; var data, year: string; p: integer; begin write('Введите дату в формате: ДД-ММ-ГГГГ: '); readln(data); year := Copy(data, 7, 4); writeln('Введенный вами год -', year); end. 38 Модуль 1. Алгоритмизация и программирование Подпрограмма и описание Пример использования procedure Insert(source: string; var s: string; index: integer); Вставляет подстроку source в строку s с номера index program s3; var s, s1: string; begin s := 'мама раму'; s1 := 'мыла '; Insert(s1, s, 6); writeln(s); // Вывод: мама // мыла раму end. procedure Delete(var s: string; index count: integer); Удаляет из строки s count символов, начиная с номера index program s4; var s: string; begin s := 'мама дважды мыла раму' Delete(s, 6, 7); writeln(s); end. // Вывод: мама мыла раму function TryStrToInt(s: string; var value: integer):boolean; Пробует преобразовать строку s в целое число value. При успешном преобразовании возвращает true, в противном случае - false program s5; var s: string; a: integer; begin write('Введите строку: '); readln(s); if TryStrToInt(s, a) then writeln('Перевели в число и получили: ', a) else writeln('Эту строку перевести в целое число нельзя'); end. function TryStrToFloat (s: string; varvalue: real): boolean; Пробует преобразовать строку s в вещественное число value. При успешном преобразовании возвращает true, в противном случае - false program s6; var s: string; a: real; begin write('Введите строку: '); readln(s); if TryStrToFloat(s, a) then writeln('Перевели в число и получили: ', a) else writeln('Эту строку перевести в вещественное число нельзя'); end. § 5. Эффективная работа со строками 39 Подпрограмма и описание Пример использования function IntToStr(value: integer): string; Преобразует целое число в строку program s7; var s: string; a: integer; begin write('Введите целое число: ' ) ; readln(a); s := 'Вы ввели число: ' + IntToStr(a); writeln(s); end. function FloatToStr(value: real) string; Преобразует вещественное число в строку program s8; var s: string; a: real; begin write('Введите вещественное число: '); readln(a); s := 'Вы ввели число: ' + FloatToStr(a); writeln(s); end. function Trim(s: string): string; Возвращает строку с удалёнными начальными и конечными пробелами program s9; var s: string; begin s := ' В этой строке много начальных и конечных пробелов ' ; writeln('Было: ' + s, '!'); Trim(s); writeln('Стало: ', s, ' !'); end. В описанных выше функциях и процедурах нет ничего экстраординарного. Их написали люди. Давайте и мы с вами потренируемся в эффективной обработке строк. Пример 1 Напишем функцию delspace, которая удаляет из строки все пробелы. function DelSpace(s: string): string,-var res: string; i: integer; 40 Модуль 1. Алгоритмизация и программирование . — t t begin res : = for i := 1 to length(s) do if (s[i] <> ' ') then res DelSpace := res; end; : = res + s[i Смысл функции заключается в следующем. 1. Будем формировать итоговую строку res, которая изначально пуста. 2. Будем последовательно идти по строке s и переносить в res только те символы, которые не равны пробелу. 3. В качестве возвращаемого значения используем res. Обратите внимание на то, что для добавления к строке res нового символа мы используем операцию конкатенации (+), поэтому строка res всё время «растёт». Пример 2 Напишем функцию DelTemplate, которая удаляет из строки s все вхождения подстроки temp. function DelTemplate(s, temp: string): string; var p: integer; begin p := pos(temp, s); while (p > 0) do begin Delete(s, p, length(temp)); p := pos(temp, s); end; DelTemplate := s; end; Как работает эта функция? 1. Получим в p результат поиска temp в s. 2. Если p больше нуля (подстрока найдена), то удалим её и заново осуществим поиск. 3. Будем повторять шаг 2 пока образец (temp) присутствует в s. 4. В результате вернём s. • Как вы думаете, оптимальна ли функция DelTemplate? Если нет, то почему? § 5. Эффективная работа со строками 41 Пример 3 Напишем функцию ChangeTemplate, которая заменяет в строке s все вхождения подстроки temp на source. function ChangeTemplate(s, temp, source: string): string,-var p: integer-begin p := pos(temp, s), while (p > 0) do begin Delete(s, p, length(temp))-Insert(source, s, p), p := PosEx(temp, s, p), end- ChangeTemplate := send- Разберём работу этой функции. 1. Так же, как и в предыдущем примере, сначала мы получим в p результат поиска temp в s. 2. Если нашли, то удалим из s temp. 3. В позицию p вставим source. 4. Осуществим поиск заново. Обратите внимание, что мы воспользовались для поиска функцией PosEx, которая, в отличие от Pos, принимает ещё и третий параметр - номер, с которого необходимо начинать поиск. 5. Перейдём к шагу 2. 6. В результате вернём s. Пример 4 Напишем функцию WordCalc, которая подсчитывает количество отдельно стоящих в тексте слов. Отдельно стоящие слова - это слова, разделённые пробелом или несколькими пробелами. // Функция удаляет из строки s повторы символа ch function DelRep(s: string- ch: char): string-var i: integer-begin i := 1- while (i < length(s)) do 42 Модуль 1. Алгоритмизация и программирование begin if (s[i] = ch) and (s [i + 1] = ch) then delete(s, i, 1) else i := i + 1; end; DelRep := s; end; // Функция подсчитывает количество символов ch в строке s function SymbolStr(s: string; ch: char): integer; var i, res: integer; begin res := 0; for i := 1 if (s[i] SymbolStr end; to length(s) do = ch) then res := res + 1; = res; function WordCalc(s: string): integer; begin SymbolStr(Trim(DelRep(s, ' ')), ' '); end; Для того чтобы написать функцию WordCalc, нам понадобится создать две вспомогательные подпрограммы: 1) функцию DelRep, которая удаляет из строки s все повторы символа ch. Например, если из строки aaasssddssa удалить все повторы символа s, то получится строка: aaasddsa. То есть вместо всех повторяющихся символов s останется по одному. Обратите внимание, что в этой функции используется цикл while, поскольку мы изменяем строку; 2) функцию SymbolStr, которая подсчитывает, сколько раз символ ch входит в строку str. Когда у нас есть эти вспомогательные подпрограммы, содержание функции WordCalc будет следующим. 1. Удалим из строки s все повторы пробелов (используем DelRep), а затем начальные и конечные пробелы (используем Trim). 2. После этого подсчитаем количество оставшихся пробелов и прибавим к найденному количеству единицу. 3. Полученное число и будет означать количество слов в строке, поскольку если в строке n слов, то они разделяются n - 1 пробелами. § 5. Эффективная работа со строками 43 • Обратите внимание на выделенные участки программ. Объясните, что они означают. ОБОБЩЕНИЕ НОВЫХ ЗНАНИЙ Для того чтобы работа со строками была удобной, разработчики языка написали множество функций и процедур, которые вы можете использовать в своих программах. В разных средах программирования набор подпрограмм может различаться, поэтому надо пользоваться документацией по конкретному диалекту языка. Основные подпрограммы по работе со строками в языке Паскаль: Length, Pos, Copy, Insert, Delete, TryStrToInt, TryStrToFloat, IntToStr, FloatToStr, Trim. Все эти функции написаны на языке Паскаль, поэтому вы их можете создать самостоятельно! ПРИМЕНЕНИЕ ЗНАНИЙ 1. Предложите вариант разобранной в параграфе функции DelTemplate, отвечающий на вопрос, приведённый в примере 2. 2. Как быстро получить из заданной строки s строку s1, равную s без последнего символа? 44 Проверь себя Задание 1 С клавиатуры вводится строка - десятичные цифры. Необходимо проверить, может ли эта строка быть записью числа в двоичной системе счисления. Задание 2 С клавиатуры вводится символ ch, а за ним - число n. Напишите функцию, которая сформирует и вернёт строку, состоящую из n символов ch. Например, из пары 'q' и 4 должна получиться строка 'qqqq'. Задание 3 С клавиатуры вводятся строки s и s1. Узнайте, сколько раз s1 встречается в s. Оформите решение в виде функции. 45 ПРИМЕНЕНИЕ ЗНАНИЙ [необходимый уровень) Задание 1 Напишите программу, на вход которой поступает четырёхзначное число, состоящее только из нулей и единиц (в двоичной системе счисления). Переведите его в десятичную систему. Задание 2 С клавиатуры вводятся названия трёх городов. Выведите на экран самое короткое и самое длинное из них. Задание 3 Напишите программу, в которой есть функция, которая переворачивает вводимую с клавиатуры строку (пример: маша ^ ашам). Задание 4 Напишите программу, которая поможет пользователю переводить число из римской системы счисления в десятичную. Пользователь вводит символ (I, V, X и т. д.), а программа должна сказать, какому числу в десятичной системе счисления соответствует данный символ. Учтите, что пользователь может ввести как строчную (маленькую) букву, так и прописную (большую). Задание 5 С клавиатуры вводится слово. Добавьте в конец этого слова столько пробелов, сколько в нём символов. Задание 6 Напишите функцию LeftTrim, в которую поступает строка. Функция должна убрать из строки все начальные пробелы. ПРИМЕНЕНИЕ ЗНАНИЙ (повышенный уровень] Задание 1 С клавиатуры вводятся два корректных трёхразрядных двоичных числа. Они представляются целыми числами. Сложите их и выведите результат. Задание 2 С клавиатуры вводится строка. Проверьте, может ли эта строка быть записью числа в десятичной системе счисления. Учтите, что число может быть не обязательно целым. Задание 3 С клавиатуры вводится строка, содержащая число в римской системе счисления. Напишите функцию, которая переведёт это число в десятичную систему счисления. 46 Задание 4 С клавиатуры вводится строка, представляющая собой двоичное число. Переведите его в десятичную систему счисления и выведите результат на экран. Задание 5 С клавиатуры вводится строка s и шаблон temp. Удвойте каждое вхождение шаблона в строку. Например: s = ' qweasdzxc123asd', а temp = ' asd'. В результате работы программы мы должны получить: ' qweasdasdzxc123asdasd '. Задание 6 С клавиатуры вводится строка. Проверьте, является ли эта строка после удаления из неё всех пробелов перевертышем. Примеры перевертышей: АРГЕНТИНА МАНИТ НЕГРА А РОЗА УПАЛА НА ЛАПУ АЗОРА ПРИМЕНЕНИЕ ЗНАНИЙ (максимальный уровень] Задание 1 С клавиатуры вводятся два числа в двоичной системе счисления (представляются типом Integer], Сложите их и выведите на экран результат. Задание 2 С клавиатуры вводится число в десятичной системе счисления. Напишите функцию, которая переводит это число в двоичную систему счисления. Задание 3 С клавиатуры вводится строка, состоящая из натуральных чисел, разделённых пробелами. Найдите и выведите на экран их сумму. Задание 4 С клавиатуры вводится целое число. Напишите функцию, которая переводит это число в римскую систему счисления. Задание 5 Напишите программу, в которой есть функция, вычисляющая наибольшее количество подряд идущих цифр в строке. Задание 6* Дан текст. Определите, сколько в нём различных символов. Подсказка: для решения этой задачи воспользуйтесь массивом, индексами элементов которого являются символы. 47 Итоговая проверочная работа Задание 1 а) Выполните перевод чисел: 1101Ю12 - в десятичную систему счисления; 3510 - в двоичную систему счисления. б) Напишите программу, в которой есть функция, вычисляющая количество пробелов в передаваемой в неё строке. Задание 2 а) Напишите функцию del - аналог процедуры Delete. В эту функцию поступает строка s и два числа index и len. Она должна удалить из строки s подстроку, начиная с символа с номером index, длиной len. б) С клавиатуры вводится строка, состоящая из цифр и знаков арифметических операций ' + ' и '-', например '12+232-311 '. Вычислите значение выражения. Задание 3 а) C клавиатуры вводится предложение - строка, в которой есть слова, разделённые пробелом без повторов. Выведите слова в порядке уменьшения их длин. б) Напишите программу, которая будет кодировать введённое предложение шифром Цезаря. Суть кодирования в том, что каждый символ строки заменяется на символ, отстоящий в алфавите от заданного вправо на три позиции. Например, слово ' mama' превратится в ' pepe ' (между символами 'm' и ' р' 3 символа). В программе используйте только латинские символы. 48 Модуль 1. Алгоритмизация и программирование § 6. Шестнадцатеричная система счисления ПОСТАНОВКА ПРОБЛЕМЫ УРОКА В процессе изучения систем счисления мы обращали ваше внимание на то, что человек использует множество систем счисления, а их общее количество бесконечно. Двоичная система является «родной» для вычислительной техники, но обладает несколькими существенными недостатками, затрудняющими удобство её использования человеком. Есть ли другие системы счисления, удобные для использования в вычислительной технике и программировании? Какая проблема здесь поставлена? Сформулируйте основной вопрос урока. Сравните свой вариант с авторским (с. 1 91 учебника). НЕОБХОДИМЫЕ БАЗОВЫЕ ЗНАНИЯ Что такое системы счисления? (§ 1,2) Что вы знаете о двоичной системе счисления? (§ 2) Вспомните правила перевода из двоичной системы счисления в десятичную и обратно. (§ 2) РЕШЕНИЕ ПРОБЛЕМЫ Г,п1 lO , ] IJJ0 70 70 701» to ‘’‘'^'°'°'°°'°o'^wiowio loitototl CIOIWIOIOW1IOH»0 70 JO 700170 о j dSS2S2K?.L'?o»oooo 7 JO J ДОСТОИНСТВА И НЕДОСТАТКИ ДВОИЧНОЙ СИСТЕМЫ СЧИСЛЕНИЯ Мы с вами очень подробно раоома-тривали двоичную систему счисления, поскольку именно она является тем математическим фундаментом, на котором построена вся современная цифровая вычислительная техника. Самым большим преимуществом двоичной системы счисления является её простота. Давайте вопомним, чем она определяетоя: 1) всего две цифры в алфавите; 2) элементарные основные операции; 3) и, что самое главное, лёгкость аппаратной реализации. Всё это говорит о том, что цифровые устройства, базирующиеся на двоичной системе счисления, технологически сделать гораздо проще, чем опирающиеся, например, на троичную систему счисления. Хотя, не станем скрывать, такие попытки были, причём весьма успешные. Однако, выигрывая в одном, обязательно проигрываешь в другом. За простоту двоичной системы счисления мы расплачиваемся громоздкостью за- § 6. Шестнадцатеричная система счисления 49 писи в ней чисел. Но поскольку отказаться от неё мы не можем (уж очень привлекательной для инженеров она оказалась), то необходимо найти способ решить проблему длинной записи. И этот способ есть - шестнадцатеричная система счисления. ШЕСТНАДЦАТЕРИЧНАЯ СИСТЕМА СЧИСЛЕНИЯ Как следует из названия, основание этой системы счисления равно 16, в её алфавите 1 6 цифр. Давайте их перечислим: 0, 1,2, 3, 4, 5, 6, 7, 8, 9, _ А что же дальше? Десять цифр нам знакомы, но откуда взять остальные? Вспомните, что такое цифра. Это символ, который используется для записи числа. Поэтому мы вправе придумать любые шесть обозначений оставшихся цифр. Традиционно они обозначаются первыми шестью буквами латинского алфавита: A, B, С, D, E, F. Итак, алфавит готов. Теперь настало время расширить таблицу соответствия десятичных и двоичных чисел, добавив в неё шестнадцатеричные числа (рис. 1.4). Десятичная с. с. Двоичная с. с. Шестнадцатеричная с. с. 0 0000 0 1 0001 1 2 0010 2 3 0011 3 4 0100 4 5 0101 5 6 0110 6 7 0111 7 8 1000 8 9 1001 9 10 1010 A 11 1011 B 12 1100 C 13 1101 D 14 1110 E 15 1111 F Рис. 1.4 Посмотрите, что изменилось в этой таблице, кроме того, что мы добавили ещё один столбец. В столбце двоичных чисел мы дописали к каждому числу незначащие нули слева так, чтобы число всегда состояло из четырёх разрядов. Откуда взялось это «магическое» число 4? Дело в том, что при переводе числа из шестнадцатеричной системы счисления в двоичную удобно использовать следующее правило. Любую 50 Модуль 1. Алгоритмизация и программирование шестнадцатеричную цифру можно заменить четырёхразрядной двоичной комбинацией. Правило работает и в обратную сторону: при переводе из двоичной системы в шестнадцатеричную четвёрка двоичных цифр представляется шестнадцатеричной цифрой. Проверим эти утверждения на примере. Возьмём десятичное число 16 и переведём его в двоичную систему счисления. Для этого достаточно посмотреть на нашу таблицу и прибавить 1 к числу 1111. Получим 100002. Можно также было воспользоваться для этого стандартным правилом перевода чисел из десятичной системы счисления в двоичную. Теперь разобьём полученное число на «четвёрки^ - они называются тетрадами. Делать мы это будем, начиная справа, а если не будет хватать разрядов, то допишем слева нули. Получим: 0001 |00002. Поставив в соответствие каждой тетраде шестнадцатеричную цифру из нашей таблицы, получим 1016. Проверим этот ответ следующим образом: прибавим единицу к шестнадцатеричному числу F. F - это старшее одноразрядное шестнадцатеричное число. Когда мы к нему прибавляем 1, мы должны перенести единицу в следующий разряд, а в текущий занести 0. Получается 10. Итак, всё верно: 1610 = 100 002 = 1016. Проведём эксперимент в обратную сторону. Возьмём шестнадцатеричное число 1116. Переведём его в десятичную систему, рассуждая так: поскольку 1016 = 1610, то (10 + 1)16 = (16 + 1)10 = 1710. Теперь переведём 1710 в двоич- 16 10 ную систему по рассмотренному в § 2 алгоритму. Результат: 100012. Воспользуемся нашим способом: заменим каждую цифру числа 11 на тетраду из таблицы и удалим стоящие слева незначащие нули. 1116 ^ ^ 0001|00012 = 100012. И опять результаты вычислений совпали. Примеры 10101111012=0010 10101012 = 0101 2CF2916 = 0010 10116 = 0001 11100 0000 1011 |11012 = 2BD16 01012 = 5516 1111 |0010|10012 = 1011001111001010012 00012=1000000012 Обратите внимание, что шестнадцатеричная цифра всегда заменяется на тетраду двоичных цифр, даже если в этой тетраде есть незначащие нули. Вы заметили, насколько короче становится запись числа в шестнадцатеричной системе счисления по сравнению с двоичной? ПЕРЕВОД ЧИСЕЛ ИЗ ШЕСТНАДЦАТЕРИЧНОЙ СИСТЕМЫ СЧИСЛЕНИЯ В ДЕСЯТИЧНУЮ И ОБРАТНО Алгоритм перевода чисел из шестнадцатеричной системы счисления в десятичную практически ничем не отличается от алгоритма по переводу чисел из двоичной системы в десятичную. § 6. Шестнадцатеричная система счисления 51 Правило перевода: 1. Пронумеровать разряды числа справа налево, начиная с нуля. 2. Представить число в виде суммы произведений цифр числа на веса соответствующих разрядов - получить развёрнутую форму записи шестнадцатеричного числа. (Надо помнить, что в шестнадцатеричной системе счисления вес разряда определяется степенью числа 16 - основания системы счисления.) Цифры от A до F заменить при этом на десятичные числа из диапазона от 10 до 16. 3. Вычислить значение полученного выражения в десятичной системе счисления. Результат - число, записанное в десятичной системе счисления. Переведём число A1016 в десятичную систему счисления. 2 1 A 1 А1016 = 10^162 + 1^161 + 0^160 = 10^256 + 16 + 0 = 2560 + 16 = 257610. • Вы видите, что запись числа в шестнадцатеричной системе счисления короче, чем в десятичной, а в десятичной — короче, чем в двоичной. Какую общую закономерность можно отметить? Перевод числа из десятичной системы счисления в шестнадцатеричную аналогичен переводу числа из десятичной в двоичную. Необходимо делить исходное число на 16 до того момента, пока мы не получим в качестве частного 0; остатки от деления записать в обратном порядке - это и будет искомое шестнадцатеричное число. Следует помнить, что в данном случае остаток от деления на 16 может быть больше 9, поэтому такие остатки мы будем записывать шестнадцатеричными цифрами из диапазона от A до F. Переведём число 121010 в шестнадцатеричную систему счисления. 12 10 1 6 12 0 0 7 5 1 6 1 0 6 4 4 1 6 A 1 1 0 0 Итак, 121010 = 4BA16 52 Модуль 1. Алгоритмизация и программирование КАК ИСПОЛЬЗОВАТЬ ШЕСТНАДЦАТЕРИЧНУЮ СИСТЕМУ СЧИСЛЕНИЯ В ПРОГРАММИРОВАНИИ? Поскольку шестнадцатеричная система счисления такая удобная, то наверняка должен существовать способ её прямого использования в языках программирования. Так оно и есть. В языках программирования есть возможность использовать шестнадцатеричные числа наравне с десятичными. В языке Паскаль для того, чтобы указать, что число написано в шестнадцатеричной системе, перед ним ставят знак «$». program hex; var a: integer; begin a := $5F; writeln(a); end. В переменную a заносится шестнадцатеричное число 5F. А на экран будет выведено десятичное число 95. • Проверьте, верно ли это? Программу мы не случайно назвали hex. Это сокращение английского слова hexadecimal (шестнадцатеричная). В вычислительной технике и программировании всё, что тем или иным образом связано с шестнадцатеричной системой счисления, обозначают этим словом (рис. 1.5). т x Dump: EinsExtra, MPEG2 Video 8 9 A B C D E Г SavO 1 Apply I Рис. 1.5 Справа на рис. 1.5 изображён шестнадцатеричный редактор. Число в каждой клетке занимает ровно 1 байт памяти. А один байт - это 8 двоичных разрядов, поэтому содержимое байта удобно и коротко записывается двухразрядным шестнадцатеричным числом. 0^ В 0P § 6. Шестнадцатеричная система счисления 53 ОБОБЩЕНИЕ НОВЫХ ЗНАНИЙ Шестнадцатеричная система счисления применяется повсеместно в вычислительной технике и программировании, поскольку она позволяет существенно упростить запись двоичных чисел. Правила перевода из шестнадцатеричной системы счисления в двоичную и обратно просты и основаны на представлении одноразрядной шестнадцатеричной цифры двоичной тетрадой. Алгоритмы перевода из шестнадцатеричной системы счисления в десятичную и обратно аналогичны алгоритмам перевода для двоичной системы. В языке программирования Паскаль есть возможность явно указывать шестнадцатеричные числа. Для этого перед числом ставится символ «$». ПРИМЕНЕНИЕ ЗНАНИЙ 1. Как шестнадцатеричная система счисления «упрощает» жизнь программистам для записи двоичных чисел? 2. • Что нужно делать, если в некоторой системе счисления нам не будет хватать символов для записи чисел? 3. Переведите из шестнадцатеричной системы счисления в двоичную числа: а) 30С1д; б) 180816; в) 5116. 4. Переведите из двоичной системы счисления в шестнадцатеричную числа: а) 10011012; б) 10111011000012; в) 1000000012. 5. • Что выведет на экран следующая программа на языке Паскаль? program hex1; var a, b: integer; begin a := $2E; b := $13; writeln(a + b - 1); end. Переведите ответ в шестнадцатеричную систему счисления. 54 Модуль 1. Алгоритмизация и программирование § 7. Двумерные массивы (матрицы) ПОСТАНОВКА ПРОБЛЕМЫ УРОКА Учитель предложил ребятам написать программу-игру «Морской бой». Они с энтузиазмом взялись за дело, прочитали правила, разделили обязанности. Но вдруг возник вопрос: «А как моделировать игровое поле?» Ведь, по своей сути, игровое поле — это таблица, в которой каждая клетка имеет две координаты. Какая проблема возникла у ребят? Сформулируйте основной вопрос урока. Сравните свой вариант с авторским (с. 1 91 учебника). НЕОБХОДИМЫЕ БАЗОВЫЕ ЗНАНИЯ Вспомните типы данных и основные конструкции языка Паскаль. (Учебники для 7-го и 8-го классов, модули «Алгоритмизация и программирование».) Что такое подпрограммы и как они используются? (Учебник для 8 класса, часть 2, модуль 1.) Вспомните свой опыт работы в интегрированной среде разработки программ. (Учебники для 7-го и 8-го классов, модули «Алгоритмизация и программирование».) РЕШЕНИЕ ПРОБЛЕМЫ ОДНОМЕРНЫЕ И МНОГОМЕРНЫЕ ПРОСТРАНСТВА 10 9 8 7 6 5 ■ A B C D E F G H I J Рис. 1.6 Поможем ребятам разобраться с их проблемой. Взглянем на игровое поле. Оно представляет собой квадратную таблицу, где в каждой ячейке может находиться или не находиться корабль (рис. 1.6). Обычно в игру вводятся ограничения, регулирующие правила размещения кораблей. В процессе игры ваш соперник называет клетку (с помощью буквы и числа), а вы отвечаете, что произошло: ваш корабль «ранен», потоплен или противник промахнулся. Упростим задачу - рассмотрим поле игры, которую мы назвали «Речной бой» (рис. 1.7). На этом поле всего одна линия клеток, и на этой линии вам и вашему противнику надо расставить свои корабли (представьте, что они располагаются в русле реки). Игра идёт по тем же правилам, что и «Морской бой». 4 3 2 1 § 7. Двумерные массивы (матрицы) 55 РЕЧНОЙ БОЙ ABCDEFGH IJKLMNOPQR Рис. 1.7 • Ответьте на два вопроса: 1) Что вам напоминает рисунок 1.7? 2) С помощью каких типов данных языка Паскаль можно смоделировать и запрограммировать игровое поле? Конечно же, игровое поле «Речного боя» проще всего моделировать массивом целых чисел, причём каждое число будет обозначать какое-либо состояние. Например, пусть 0 - это пустая клетка, 1 - клетка, в которой стоит корабль или его часть, 2 - клетка, в которую попал противник, и т. д. Такой процесс можно назвать кодированием игровой ситуации. Почему мы легко можем смоделировать игровое поле обычным массивом? Потому что в случае «Речного боя» поле представляет собой одномерное пространство. Это означает, что любая клетка определяется только одной координатой. В нашем случае это буква. Массивы, с которыми мы с вами работали до сих пор (в 7-м и 8-м классах), представляли собой тоже одномерные структуры. Для доступа к элементу нам нужно указать только его индекс. Поэтому для создания игрового поля «Речного боя» на языке Паскаль нужно написать следующий код: var field: array of integer,- Если противник попал в ваш корабль, расположенный в клетке 'B', то в коде нужно указать: field['B'] := 2 - Вернёмся к «Морскому бою». В отличие от одномерного случая, здесь для определения клетки на игровом поле потребуется уже не одна, а две координаты. Такое пространство называется двумерным. Существуют пространства, размерность которых превышает число 2. Например, мы с вами живём в трёхмерном пространстве, в котором каждая точка имеет три координаты. А если учесть ещё и время, то можно говорить и о четырёхмерном пространстве. В математике есть раздел, который изучает пространства более высоких порядков, их все можно назвать одним термином - многомерные пространства. 1 56 Модуль 1. Алгоритмизация и программирование Одномерным массивом многомерные пространства уже не смоделировать. Как же быть? Нам поможет ещё один тип данных, который называется многомерным массивом. МНОГОМЕРНЫЕ МАССИВЫ (МАТРИЦЫ) Вспомним, что массив - это совокупность однотипных элементов. Обратите внимание на слово «однотипных». В Паскале элементами массива в том числе могут быть элементы типа «массив» - другие массивы: type TMatr = array [1..100] of array [1..200] of integer; var Matr: TMatr; В этом примере мы описали тип TMatr как массив из 100 элементов, где эти элементы сами есть массивы целых чисел из 200 элементов. По сути, мы создали таблицу, в которой 100 строк, а в каждой строке хранится 200 чисел. Запись array [1..100] of array [1..200] of integer не очень удобная, поэтому разработчики языка позволили её немного упростить: type TMatr = array [1..100, 1..200] of integer; Так описываются двумерные массивы в языке Паскаль. Такие объекты называются по-другому матрицами. Для описания трёхмерного массива необходимо добавить «третье измерение»: type TMatr3 = array [1..100, 1..200, 1..300] of integer; РАБОТА С ДВУМЕРНЫМИ МАССИВАМИ Мы научились создавать двумерные массивы (матрицы). Но как с ними работать? Нам же надо написать игру «Морской бой»! Рассмотрим ряд примеров, которые объяснят суть вопроса. Пример 1 Требуется ввести «красиво» вывести матрицу целых чисел. § 7. Двумерные массивы (матрицы) 57 Код программы Вывод program m1; const MAX = 100; type TMatr = array [1..MAX, 1..MAX] of integer; var M: TMatr; // Матрица Mn, Mm: integer; // Размеры матрицы procedure Read^atr(var A: TMatr; n, m: Введите кол-во integer); строк в матрице: // процедура вводит матрицу Введите кол-во // A - матрица столбцов в // n - количество строк, m - количество матрице: 4 // столбцов Ввод матрицы var M[1, 1]=1 i, j: integer; M[1, 2]=2 begin M[1, 3]=3 for i := 1 to n do M[1, 4]=4 for j := 1 to m do M[2, 1]=5 begin M[2, 2]=6 write('M[', i, ', ', j, ']='); M[2, 3]=7 readln(A[i, j]); M[2, 4]=8 end; M[3, 1]=9 end; M[3, 2]=10 procedure WriteMatr(A: TMatr; n, m: integer); M[3, 3]=11 // процедура выводит матрицу таблицей на экран M[3, 4]=12 // A - матрица Вывод матрицы // n - количество строк, m - количество 1 2 3 4 // столбцов 5 6 7 8 var 9 10 11 12 i, j: integer; begin for i := 1 to n do begin for j := 1 to m do write(A[i, j]:4); writeln; end; end; begin write('Введите кол-во строк в матрице: '); readln(Mn); write('Введите кол-во столбцов в матрице: '); readln(Mm); writeln('Ввод матрицы'); ReadMatr(M, Mn, Mm); writeln('Вывод матрицы'); WriteMatr(M, Mn, Mm); end. 58 Модуль 1. Алгоритмизация и программирование Обратите внимание, что в этой программе для обращения к элементу матрицы применяется конструкция вида A[i, j], где i и j - координаты ячейки таблицы и, для того чтобы «обойти» все элементы матрицы, необходимо использовать вложенные циклы. И ещё один момент: так же как и для одномерных массивов, в описании типа-матрицы [TMstr] мы должны задавать её размеры с запасом, что и сделано в примере с использованием механизма констант. Пример 2 С клавиатуры вводится квадратная матрица. Нужно определить суммы значений элементов её главной и побочной диагонали. Поясним ряд понятий, приведённых в условии задачи. Квадратная матрица - это матрица, у которой количество строк и столбцов совпадает. Гпавная диагональ - это элементы квадратной матрицы, имеющие координаты вида [i, i]: то есть [1, 1]; [2, 2], _, [5, 5] и т. д. Это диагональ, идущая из верхнего левого в правый нижний угол матрицы. Побочная диагональ - это диагональ, идущая из левого нижнего в правый верхний угол матрицы. Код программы Вывод [1..MAX, 1..MAX] of integer; // Матрица // Размер матрицы n: integer) program m2; const MAX = 100; type TMatr = array var M: TMatr; n: integer; procedure Read^atr(var A: TMatr // процедура вводит матрицу // A - матрица // n - размер матрицы var i, j: integer; begin for i := 1 to n do for j := 1 to n do begin write('M[', i, j, readln(A[i, j]); end; end; function CalcMain(A: TMatr; var i, sum: integer; Введите размер матрицы: 3 Ввод матрицы M[1, M[1, 1]=1 2]=2 M[1, 3]=1 1]=6 2] =5 3] =4 1]=2 2]=3 integer): integer; . 3]=4 Сумма элементов главной диагонали: 10 Сумма элементов побочной диагонали: 8 § 7. Двумерные массивы (матрицы) 59 Код программы Вывод begin sum := 0; for i := 1 to n do sum := sum + A[i, i]; CalcMain := sum; end; function CalcSecond(A: TMatr; n: integer): integer; var i, sum: integer; begin sum := 0; for i := 1 to n do sum := sum + A[n - i + 1, i] CalcSecond := sum; end; begin write('Введите размер матрицы: '); readln(n); writeln('Ввод матрицы '); ReadMatr(M, n); writeln('Сумма элементов главной диагонали: ', CalcMain(M, n)); writeln('Сумма элементов побочной диагонали: ' CalcSecond(M, n)); end. В этой задаче для вычисления нужной суммы не требуются вложенные циклы. Для получения координат необходимых элементов матрицы нам нужна только одна переменная i. Элементы главной диагонали элементы имеют вид A[i, i], а элементы побочной - A[n - i +1, i]. • Проверьте правильность последней формулы. Пример 3 С клавиатуры вводятся размеры матрицы n и т. Необходимо заполнить её натуральными числами «змейкой» по горизонтали. Например, если n = 3, а т = 4, то матрица должна выглядеть так: 1 2 3 4 5 6 7 8 9 10 11 12 60 Модуль 1. Алгоритмизация и программирование Код программы Вывод [1..MAX, 1..MAX] of integer; // Матрица // Размеры матрицы n, m: integer) m количество столбцов to n do 1 to m do j] := k; program m3; const MAX = 100; type TMatr = array var M: TMatr; Mn, Mm: integer; procedure FillMatr(var A: TMatr; // процедура заполняет матрицу // A - матрица // n - количество строк, var i, j, k: integer; begin k := 1; for i := 1 for j := begin A[i, k := k + 1; end; end; procedure WriteMatr(A: TMatr; n, m: integer); // процедура выводит матрицу таблицей на экран // A - матрица // n - количество строк, m - количество столбцов var i, j: integer; begin for i := 1 to n do begin for j := 1 to m do write(A[i, j]:4); writeln; end; end; begin write('Введите кол-во строк в матрице: '); readln(Mn); write('Введите кол-во столбцов в матрице: '); readln(Mm); FillMatr(M, Mn, Mm); writeln('Вывод матрицы'); WriteMatr(M, Mn, Mm); end. Введите кол-во строк в матрице: 6 Введите кол-во столбцов в матрице: 4 Вывод матрицы 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 § 7. Двумерные массивы (матрицы) 61 ОБОБЩЕНИЕ НОВЫХ ЗНАНИЙ Очень часто для моделирования задачи одномерных типов данных бывает недостаточно. Многомерные пространства - это пространства, в которых для описания объекта необходимо указать несколько координат. Элементами массива могут быть другие массивы. Эта возможность позволяет описывать многомерные объекты на языке программирования с помощью многомерных массивов (матриц). Описание матриц в языке Паскаль очень похоже на описание одномерных массивов. Отличие заключается в том, что мы должны указать в описании несколько измерений: array [1..100, 1..200] of char Для доступа к элементу матрицы в квадратных скобках нужно указать не одну, а несколько координат. Для «обхода» матриц используются вложенные циклы. ПРИМЕНЕНИЕ ЗНАНИЙ 1. С клавиатуры последовательно вводятся размеры матрицы и сама матрица целых чисел. Выведите матрицу. Замените все элементы второго столбца на 5. Выведите изменённую матрицу. 2. С клавиатуры последовательно вводятся размеры матрицы и сама матрица целых чисел. Выведите матрицу. Замените все элементы третьей строки на 4. Выведите изменённую матрицу. 3. С клавиатуры последовательно вводятся размер квадратной матрицы и сама матрица целых чисел. Выведите матрицу. Замените все элементы главной диагонали на противоположные числа. Выведите изменённую матрицу. 62 Модуль 1. Алгоритмизация и программирование § 8.Рекурсия ПОСТАНОВКА ПРОБЛЕМЫ УРОКА На урок информатики учитель принёс веточку дерева с набухшими почками и сказал: «Посмотрите на ветку дерева. Весной на ней появляются почки, из которых со временем образуются новые ветки, на которых опять появляются почки, и процесс продолжается, пока дерево живёт. Выходит, что каждая ветка дерева, в свою очередь, состоит из меньших веток. Ветка — самоподобный объект, то есть форма ветки повторяет форму её частей». • В чём заключается закономерность, которую заметил учитель? Как вы считаете, существуют ли самоподобные структуры в программировании? Сформулируйте основной вопрос урока. Сравните свой вариант с авторским (с. 191 учебника). НЕОБХОДИМЫЕ БАЗОВЫЕ ЗНАНИЯ Вспомните типы данных и основные конструкции языка Паскаль. (Учебники для 7-го и 8-го классов, модули «Алгоритмизация и программирование».) Что такое подпрограммы и как они используются? (Учебник для 8 класса, часть 2, модуль 1.) Вспомните свой опыт работы в интегрированной среде разработки программ. (Учебники для 7-го и 8-го классов, модули «Алгоритмизация и программирование».) РЕШЕНИЕ ПРОБЛЕМЫ ЧТО ТАКОЕ РЕКУРСИЯ Рекурсия - это способ описания объекта через самого себя. Рекурсивный метод применяется во многих сферах человеческой деятельности, включая точные науки и искусство. Объекты, которые можно описать рекурсивно, всегда обладают свойством самоподобия. Это означает, что для описания объекта целиком необходимо описать некоторую составляющую его часть, которая является мини-копией самого объекта. Например, для n > 0 n! = 1 • 2 • 3 • _ • (n - 1) • n. Если внимательно посмотреть на эту запись, то можно увидеть: в определение факториала числа n входит определение факториала числа n - 1. Эта часть выделена цветом. В результате мы можем дать рекурсивное определение факториала: § 8. Рекурсия 63 1, при n = 0; n • (n - 1)!, при n > 0. Другой пример самоподобных объектов - числа Фибоначчи. Вспомним, как мы их определяли ранее: 1) два первых числа последовательности равны единице; 2) остальные числа последовательности, начиная с третьего, вычисляются как сумма двух предыдущих чисел. Получается, что для вычисления элемента последовательности Фибоначчи (начиная с третьего) нам необходимо вычислить и сложить два предшествующих ему элемента, для вычисления которых, в свою очередь, нужно получить и суммировать пары предшествующих им и т.д. Таким образом, мы приходим к следующему рекурсивному определению элементов последовательности Фибоначчи: 1, при n = 1; 1, при n = 2; fib + fib , при n ^ 3. n-^ n-2 ^ В математике на рекурсивный метод очень похож метод математической индукции, в котором сложная задача по шагам сводится к простой, решение которой известно. В геометрии рекурсивными свойствами обладают объекты, называемые фракталами, - бесконечные самоподобные структуры. Один из самых известных таких объектов называется кривой Коха. Давайте его рассмотрим. Задача заключается в построении кривой, вид которой зависит от некоторого параметра n. Если n = 1, то кривая имеет вид отрезка: При n = 2 кривая приобретает следующий вид: Для n = 3 получим следующую картинку: 64 Модуль 1. Алгоритмизация и программирование А для n = 4 - такую: И так далее. Вы увидели, где в этих рисунках «спрятана» рекурсия? На новом шаге мы на каждом отрезке строим одну и ту же фигуру, поэтому, для того чтобы построить фигуру для n = 4, мы должны построить её же, только для n = 3, а для этого надо построить фигуру для n = 2 и т. д. Посмотрите, какие виртуальные «картины» можно строить с помощью рекурсии (рис. 1.8). Рис. 1.8 РЕКУРСИЯ В ПРОГРАММИРОВАНИИ Рекурсивные определения применяются в программировании повсеместно. Это связано с тем, что очень часто дать рекурсивное определение объекта гораздо проще, нежели указать шаги (итерации) для решения задачи. Но надо помнить, что не всякое рекурсивное решение будет оптимальным. Любой программист должен знать основные правила создания рекурсивных алгоритмов (описаний). 1. По сути, вы описываете не содержание способа достижения результата (последовательность шагов), а даёте определение понятия. Например, если для вычисления факториала итеративным методом (с помощью циклов) мы задаём конкретные шаги, позволяющие получить результат, § 8. Рекурсия 65 то с помощью рекурсии мы даём определение понятия факториала, которое само по себе и есть алгоритм его вычисления. 2. Любой рекурсивный алгоритм (рекурсивное определение) должен иметь в своём составе точку выхода. В примере с факториалом это случай для n = 0. Давайте представим, что получится, если мы не укажем это условие. Рассмотрим вычисление 3!. 1) По определению факториала 3! = 3 • 2! 2) 2! = 2 • 1! 3) 1! = 1 • 0! 4) 0!=0 • (-1)! 5) (-1)! = -1 • (-2)! и т. д. Наше вычисление никогда не закончится, поскольку мы «ушли» в отрицательную область и не сможем из неё выбраться. Программа не сможет остановиться. Точка выхода - самая важная часть рекурсивного алгоритма. 3. Рекурсивный алгоритм должен содержать вызов самого себя. В противном случае он просто вырождается. Носителями рекурсии в программе являются подпрограммы. Сейчас мы рассмотрим их примеры и сравним их с итеративными аналогами. ПРИМЕРЫ РЕКУРСИВНЫХ ЗАДАЧ Пример 1 Нужно написать и сравнить функции factr и facti, вычисляющие факториал соответственно рекурсивным и итеративным способом. Рекурсивный способ Итеративный способ function facti(n: integer): function factr(n: integer): integer; integer; begin var if (n = 0) then factr := 1 s, i: integer; else factr := n * factr(n - 1); begin end; s := 1; for i := 1 to n do s := s * i; facti := s; end; Обратите внимание, что в функции facti мы описали две переменные s, i и создали цикл, в котором в переменной s накапливается значение факториала числа n. Для работы функции factr никаких переменных не требуется. Мы чётко перекладываем на язык программирования рекурсивное описание понятия «факториал». А именно: 66 Модуль 1. Алгоритмизация и программирование 1) если n = 0, то функция возвращает 1; 2) в противном случае функция возвращает результат, равный произведению числа n и результата вычисления факториала от n - 1. Посмотрите, насколько рекурсивная запись получилась лаконичнее! Пример 2 Требуется написать и сравнить функции fibr и последовательности Фибоначчи соответственно ным способом. fibi, вычисляющие элемент рекурсивным и итератив- Рекурсивный способ Итеративный способ function fibr(n: begin if ((n = 1) or else fibr := end ; integer): integer; (n = 2)) then fibr := 1 fibr(n - 1) + fibr(n - 2) function fibi(n: integer): integer; var a, b, i, t: intege begin a := 1 ; b := 1 ; for i := 3 to n do begin t := b; b := a + b; a := t; end; fibi end; = b; В этом примере лаконичность, простота и «красота» рекурсивного определения видны ещё чётче. Пример 3 Нужно перевести десятичное число в двоичную систему счисления. Сложность этой задачи заключается в том, что остатки от последовательного деления числа на 2 должны быть записаны в обратном порядке. Давайте дадим определение процесса перевода: 1) если n < 2, то выведем n; 2) в противном случае переведём в двоичную систему счисления число n div 2 (целую часть), после этого выведем n mod 2 (остаток). Для примера возьмём число 6 и рассмотрим, что будет происходить. 1) 6 > 2, поэтому будем переводить число 6 div 2, то есть 3. 2) 3 тоже больше, чем 2, поэтому будем переводить число 3 div 2, то есть 1. 3) 1 < 2. Выводим 1, затем выводим 3 mod 2, то есть 1. Итого вывели 11. 4) Число 3 перевели, теперь можем вывести 6 mod 2. Итого получилось 110. § 8. Рекурсия 67 procedure conv10to2(n: integer); begin if (n < 2) then write(n) else begin conv10to2(n div 2); write(n mod 2); end; end; Перевод оформлен в виде процедуры, поскольку мы только выводим результат, а не возвращаем его. • Переведите число 6 из десятичной системы счисления в двоичную стандартным способом и посмотрите на целые части и остатки. ОБОБЩЕНИЕ НОВЫХ ЗНАНИЙ Рекурсия - это способ описания объекта через самого себя. Рекурсия присутствует вокруг нас как в живой природе, так и в искусственных объектах и компьютерных моделях. Создавая рекурсивный алгоритм (рекурсивное описание), человек фактически даёт определение искомого объекта, а не описывает пошаговый процесс его получения. В программировании рекурсивным объектом является подпрограмма. Чтобы не происходило её «зависание», необходимо помнить о точке выхода - условии, при котором из рекурсии можно выйти. ПРИМЕНЕНИЕЗНАНИЙ 1. • Расскажите, как вы понимаете термин «самоподобие». 2. • Назовите самые главные вещи, которые программист всегда должен помнить, если решает задачу рекурсивно. 3. Переделайте процедуру из примера 3 в функцию так, чтобы она возвращала результат перевода, а не выводила его. 4. • Сформулируйте рекурсивное определение алгоритма Евклида по вычислению НОД двух чисел. 5. • Сформулируйте рекурсивное определение процесса переворачивания строки. 68 Модуль 1. Алгоритмизация и программирование § 9. Файлы и работа с ними ПОСТАНОВКА ПРОБЛЕМЫ УРОКА До текущего момента вы работали с файлами исключительно как пользователи персонального компьютера. Но вы не зря учитесь программировать. Вы развиваетесь, получаете новые знания и теперь готовы взглянуть на файл с несколько другого угла. • Как вы считаете, программисты и пользователи одинаково работают с файлами? Сформулируйте основной вопрос урока. Сравните свой вариант с авторским (с. 191 учебника). НЕОБХОДИМЫЕ БАЗОВЫЕ ЗНАНИЯ Вспомните типы данных и основные конструкции языка Паскаль. (Учебники для 7-го и 8-го классов, модули «Алгоритмизация и программирование».) Что такое подпрограммы и как они используются? (Учебник для 8-го класса, часть 2, модуль 1.) Вспомните свой опыт работы в интегрированной среде разработки программ. (Учебники для 7-го и 8-го классов, модули «Алгоритмизация и программирование».) РЕШЕНИЕ ПРОБЛЕМЫ ЧТО ТАКОЕ ФАЙЛ С ТОЧКИ ЗРЕНИЯ ПРОГРАММИСТА Понятие «файл» для программиста и для обычного пользователя компьютера существенно различается. Корректнее говорить, что понятие «файл» для программиста более ёмкое, нежели для пользователя. Почему так происходит? Дело в том, что для пользователя файл - это документ, в котором записана та или иная информация. Например, документ Microsoft Word или Microsoft Excel, графический документ в формате JPEG, видеоматериалы и т. д. Простому пользователю не нужна информация о том, каким образом этот файл создан, что за данные внутри него находятся, как они устроены и т. д. Программисту же для работы подобная информация чрезвычайно важна. Если программисту необходимо написать программу, обрабатывающую графические файлы, то он должен или разобраться в устройстве необходимых файлов, или воспользоваться уже созданными подпрограммами по работе с ними. В любом случае для программиста файл - это в первую очередь «контейнер» с цифровыми данными, а во вторую - документ. В дальнейшем в этом параграфе мы будем рассматривать файлы именно с точки зрения программиста. § 9. Файлы и работа с ними 69 ВИДЫ ФАЙЛОВ Обычно файлы с точки зрения программиста делятся на две большие группы: бинарные (двоичные) и текстовые. Бинарные файлы - это файлы, в которых может храниться любая двоичная информация, сохранённая в соответствии с определённым форматом, то есть правилом. Для работы с такой информацией программист должен знать нужный формат. Без этого знания файл представляет собой бесполезный набор байтов. Когда человек смотрит на содержимое бинарного файла, он видит просто последовательность двоичных чисел. К бинарным файлам можно отнести: 1) графические файлы (jpeg, bmp, gif, png); 2) видеофайлы (avi, mp4, wmv); 3) музыкальные файлы (wav, mp3); 4) архивы (zip, rar, ice); 5) исполняемые файлы; 6) файлы баз данных и т. д. • Попробуйте запустить любой файловый менеджер (например, Far manager) и открыть на просмотр любой бинарный файл (клавиша F3). Вы увидите примерно такую картину (рис. 1.9). - Hex-Ed - HN_Hex-Ed.exe [81.920 bytes] File Edit Search Help В Q I 000000 000010 000020 000030 000050 000050 000060 000070 000080 000090 0000A0 0000B0 0000C0 0000D0 0000E0 0000F0 000100 000110 000120 000130 000140 000150 000160 000170 4D 5A 90 B8 00 00 00 00 00 00 00 00 0E 1F BA 69 73 20 74 20 62 6D 6F 64 50 75 E5 7B 0B 80 7B 0B 81 76 0B 98 12 37 81 D3 12 8D 00 00 00 50 45 00 00 00 00 00 A0 00 00 C0 90 04 00 00 00 60 01 00 00 10 00 00 00 58 CE 00 00 03 00 00 00 00 00 00 00 00 00 00 0E 00 B4 50 52 4F 65 20 72 65 2E 0D 5D 14 14 0E 15 14 0E 45 14 0E 1D 14 0E 16 14 0E 15 14 00 00 00 00 4C 01 00 E0 00 00 00 00 00 00 00 00 00 00 00 00 10 00 00 10 00 10 00 00 78 00 00 00 04 00 00 00 40 00 00 00 00 00 00 00 00 00 09 CD 21 B8 47 52 41 4D 75 6E 20 69 0D 0A 24 00 8B 0E 14 14 8B 0E 97 08 8B 0E 14 14 8B DE 14 14 8B 0E FC 08 88 0E 52 69 00 00 00 00 04 00 3C F5 0F 01 0B 01 00 00 FC 48 00 00 04 10 00 00 04 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 04 40 00 00 00 00 00 00 00 00 01 4C 20 63 6E 20 00 00 8B 0E 85 0E 8B 0E 8A 0E 81 0E 63 68 00 00 FB 3F 06 00 00 00 00 00 00 00 00 00 10 00 00 00 01 00 FF FF 00 00 00 00 F0 00 CD 21 61 6E 44 4F 00 00 14 14 02 14 10 14 66 14 15 14 14 14 00 00 00 00 00 B0 00 10 00 10 00 00 02 00 00 10 00 00 E8 15 00 00 00 00 00 00 00 00 54 68 6E 6F 53 20 00 00 8B 0E 8B 0E 8B 0E 8B 0E 8B 0E 8B 0E 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 Cunrent position: 90 / 00005A M2................ ■ ........@........ . . i . . ! Th is PROGRAM canno t be run in DOS node.. . $........ Pu . .]........... {................. { . . . E......... v............f . . . . . 7............... .........Rich..... PE'. V. '< '? . . . . . . . . . . . . H . . . . . . . ......@........... X . . . x.@....... ASCII Рис. 1.9 На рисунке 1.9 видно, что бинарный файл состоит из последовательности байтов, а каждый байт представлен двумя шестнадцатеричными цифрами. Текстовые файлы хранят текстовые данные. Здесь очень важно не перепутать текстовые файлы и текстовые документы. Например, документ 70 Модуль 1. Алгоритмизация и программирование Microsoft Word - это не текстовый файл, а бинарный, хоть мы и храним в нём созданные печатные произведения. Если открыть текстовый файл в любом редакторе, то мы увидим обычный текст, который сможем понять (рис. 1.10). RCP Text Editor ий */home/tei/work/Inter... /home/tel/work/Update.. RCP Text Edidng

RCP is great

(U Рис. 1.10 Текстовыми файлами являются: 1) программы на языках программирования; 2) содержание описания разметки web-страниц на языке HTML; 3) XML-документы; 4) конфигурационные файлы операционных систем; 5) файлы журналов (log-файлы) и т. д. Строго говоря, любой текстовый файл является бинарным, поскольку символ - это число, поэтому, в принципе, с текстовыми файлами можно работать так же, как и с бинарными. Однако для текстовых файлов были придуманы свои, более удобные технологии, которые мы сейчас и рассмотрим. Работу с бинарными файлами мы оставляем на факультативное изучение для самых любознательных. РАБОТА С ТЕКСТОВЫМИ ФАЙЛАМИ С текстовыми файлами можно производить всего лишь две операции: чтение и запись. В языке Паскаль для этого существует специальный файловый тип данных: Text. В качестве примера приведём описание файловой переменной T : Var T: Text; § 9. Файлы и работа с ними 71 Примечание. В некоторых компиляторах этот тип может называться TextFile. С точки зрения программиста, текстовый файл представляет собой набор символов, который делится на строки. Разделителями являются символы перевода строки. Поэтому работа с файлом сводится к чтению и записи строк в файле. Но перед тем как начинать работать со строками файла, необходимо связать файловую переменную с реальным файлом на диске. В компиляторе PascalABC.NET это делается с помощью процедур Assign или AssignFile. Две процедуры введены для того, чтобы поддержать работу программ, которые были созданы в других системах программирования. Вы вправе пользоваться любой из приведённых процедур, но для определённости в дальнейшем мы будем использовать процедуру AssignFile. Процедура AssignFile имеет два параметра: файловую переменную и строку, в которой указывается имя реального файла на диске. Имя файла может содержать полный путь к файлу, например: ' c: \mydocs\files\ filel. txt'. В этом случае месторасположение файла определяется точно. Имя может быть кратким, например: ' file2 . txt'. Эта ситуация предполагает, что файл находится в том же каталоге, что и сама программа. После связывания необходимо выполнить открытие файла. Файл можно открыть тремя способами: для чтения, для записи и для дополнения. Каждый способ использует свою процедуру: 1) Procedure Reset (f: Text) - открывает текстовый файл f для чтения; 2) Procedure Rewrite(f: Text) - открывает текстовый файл fдля записи, если файл существовал, то он будет очищен; 3) Procedure Append (f: Text) - открывает текстовый файл f для дополнения. Чтение и запись в файл производится с использованием знакомых нам процедур readln и writeln, только в них добавляется первый параметр -файловая переменная. По окончании работы с файлом его нужно закрыть с помощью процедуры CloseFile(f: Text). Резюмируем методику работы с текстовым файлом в виде последовательности шагов. 1. Связывание файловой переменной и реального файла. 2. Открытие файла одним из трёх способов. 3. Чтение или запись в файл. 4. Закрытие файла. Рассмотрим несколько примеров, в которых приведём варианты работы с файлами. 72 Модуль 1. Алгоритмизация и программирование Пример 1 С клавиатуры вводится число N. Создать файл fib.txt и записать в него значения чисел Фибоначчи от 1 до N по одному в каждой строке. program fibfile; var F: Text; i, n: integer; function fib(n: integer): integer; begin if (n < 3) then fib := 1 else fib := fib(n - 1) + fib(n - 2); end; begin write('Введите число N: '); readln(n); // Связываем файловую переменную с файлом fib.txt AssignFile(F, 'fib.txt'); // Открываем файл на запись ReWrite(F); // Пишем в файл данные for i := 1 to n do writeln(F, fib(i)); // Закрываем файл CloseFile(F); end. Много раз встречавшаяся нам функция fib рекурсивно вычисляет значения числа Фибоначчи. В основной программе мы сначала связываем файловую переменную F с файлом fib.txt. Поскольку имя файла указано без пути, то файл должен находиться в том же каталоге, что и основная программа. Далее мы открываем файл для записи. При этом вся информация, ранее содержавшаяся в файле fib.txt, будет уничтожена. После этого в цикле, который повторяется n раз, в файл записываются значения чисел Фибоначчи: каждое в свою строку. В конце файл закрывается. Посмотрите на содержание созданного нами файла и убедитесь, что это действительно последовательность Фибоначчи (рис. 1.11). Пример 2 Дан текстовый файл. Требуется подсчитать количество строк в нём. Общий принцип решения подобных задач следующий: надо читать строки из файла до тех пор, пока не будет достигнут конец файла. Но как это опре- § 9. Файлы и работа с ними 73 делить? В арсенале программиста есть функция Eof (от английского End of File). У этой функции всего один параметр - файловая переменная, а возвращает она значение типа Boolean: true («истина»), если достигнут конец файла, и false («ложь»), если не достигнут. Код программы Вывод program countfile; var F: Text; count: integer; s, s1: string; begin write('Введите имя текстового файла: '); readln(s); // Связываем файловую переменную с файлом AssignFile(F, s); // Открываем файл на чтение reset(F); count := 0; // читаем данные while (not (eof(F))) do begin readln(F, s1); count := count + 1; end; // Закрываем файл CloseFile(F); writeln('В файле ' + s + ' ', count, ' строк'); end. Введите имя текстового файла: fib.txt В файле fib.txt 5 строк 74 Модуль 1. Алгоритмизация и программирование В качестве имени файла мы ввели fib.txt - этот файл был сформирован в предыдущем примере, затем мы связали файловую переменную F с введённым файлом и обнулили переменную count. После этого, пока мы не достигнем конца файла, будем читать из файла строку и увеличивать значение переменной count. В результате файл закрывается, а на экран выдаётся значение переменной count. Пример 3 Дан текстовый файл. Нужно скопировать его содержимое в другой файл. Для решения этой задачи мы один файл открываем для чтения, а другой -для записи. Код программы Вывод program copyfile; var F1, F2: Text; s: string; begin write('Введите имя источника: '); readln(s); // Связываем файловую переменную AssignFile(F1, s); write('Введите имя приемника: '); readln(s); AssignFile(F2, s); // Открываем файл F1 на чтение, а F2 - на // запись reset(Fl); rewrite(F2); // читаем данные из F1 и пишем в F2 while (not (eof(F1))) do begin readln(F1, s); writeln(F2, s); end; // Закрываем файлы CloseFile(F1); CloseFile(F2); end. Введите имя источника: fib.txt Введите имя приемника: fib1.txt § 9. Файлы и работа с ними 75 ОБОБЩЕНИЕ НОВЫХ ЗНАНИЙ Понятия «файл» для пользователя и программиста существенно различаются. Если для первого это документ определённого вида, то для второго - «контейнер» с данными, которые нужно ещё и интерпретировать. С точки зрения программиста, файлы делятся на два вида: бинарные и текстовые. Для каждого типа существуют свои методы работы. Для работы с текстовыми файлами существует специальный файловый тип Text. Работа с текстовыми файлами состоит из четырёх этапов. 1. Связывание файловой переменной с реальным файлом (процедура AssignFile). 2. Открытие файла на чтение, запись или дополнение (процедуры Reset, Rewrite, Append). 3. Чтение и запись в файл, которые происходят по строкам (процедуры ReadLn, WrteLn). 4. Закрытие файла (процедура CloseFile). ПРИМЕНЕНИЕ ЗНАНИЙ 1. • Объясните различие понимания термина «файл» пользователем компьютера и программистом. 2. Расскажите об основных этапах по работе с текстовыми файлами на языке Паскаль. 3. С клавиатуры вводится имя файла. Создайте текстовый файл с введённым именем и запишите в него фразу «Hello, world!» 4. Откройте созданный в предыдущем задании файл и допишите в него фразу «World, hello!» 5. В файле input.txt записано целое число, не превосходящее 10. Прочитайте его, вычислите факториал этого числа, результат запишите в файл output.txt. 76 Модуль 1. Алгоритмизация и программирование § 10. Случайные числа ПОСТАНОВКА ПРОБЛЕМЫ УРОКА Мир полон случайностей. Предположим, вы подбрасываете монету, или кидаете игральный кубик, или стреляете в мишень. Каков будет результат? А если повторить ваши действия несколько раз? Люди всегда хотели научиться предвидеть результаты своих действий. Эти желания превратились в науку — теорию вероятностей. Компьютер призван помочь нам в автоматизации процесса изучения случайностей, но для этого должны поработать программисты, чтобы его этому научить. • Какой важный вопрос здесь поднят? Сформулируйте тему урока в виде вопроса. Сравните свой вариант с авторским (с. 1 91 учебника). НЕОБХОДИМЫЕ БАЗОВЫЕ ЗНАНИЯ Вспомните типы данных и основные конструкции языка Паскаль. (Учебники для 7-го и 8-го классов, модули «Алгоритмизация и программирование».) Что такое подпрограммы и как они используются? (Учебник для 8-го класса, часть 2, модуль 1.) Вспомните свой опыт работы в интегрированной среде разработки программ. (Учебники для 7-го и 8-го классов, модули «Алгоритмизация и программирование».) РЕШЕНИЕ ПРОБЛЕМЫ ЧТО ТАКОЕ СЛУЧАЙНЫЕ ЧИСЛА Случайные числа находят применение во многих прикладных науках, например в физике, вычислительной математике, статистике, криптографии и т. д. Однако понятие «случайное число» не такое простое, каким кажется. Ещё сложнее получить настоящие случайные числа. Получение одного случайного числа не имеет прикладного смысла, поэтому всегда говорят о последовательности случайных чисел или величин. В последовательности настоящих случайных чисел каждый элемент никаким образом не зависит от других членов этой же последовательности. Источников случайных чисел в природе не так уж много, и все они не компьютерного происхождения. Поэтому в ситуациях, когда требуется повышенное качество последовательностей случайных чисел, к компьютеру подключают специальное устройство, которое может получать данные из окружающего мира. Что же делать в остальных ситуациях? Любой компьютер работает по алгоритму. Поэтому были придуманы специальные алгоритмы, которые получили название генераторов псевдослучайных чисел. Эти алгоритмы умеют § 10. Случайные числа 77 производить последовательности чисел, элементы которых практически не зависят друг от друга. Но генератор необходимо запускать. Обычно запуском является задание первого числа последовательности. Далее, отталкиваясь от первого числа, алгоритм начинает генерировать остальные. Как вы думаете, что получится, если такому алгоритму каждый раз давать для запуска одинаковое число? Конечно, последовательности получатся одинаковыми. Поэтому за стартом генератора всегда нужно очень внимательно следить. В качестве стартового числа часто используется текущее время компьютера. В языках программирования существуют средства для работы с псевдослучайными числами. Язык Паскаль не является исключением. СЛУЧАЙНЫЕ ЧИСЛА В ЯЗЫКЕ ПАСКАЛЬ Итак, для того чтобы работать с генератором псевдослучайных чисел, его нужно запустить. В языке Паскаль есть процедура, которая этим занимается. Она называется randomize. Эта процедура может быть вызвана как без параметров (в этом случае стартовое число будет выбрано автоматически), так и со стартовым параметром. Если стартовые параметры будут одинаковыми, то и последовательности получатся одинаковыми. Система PascalABC.NET имеет в своём составе три функции получения случайных чисел. Все они называются random и различаются только количеством и типами параметров. Рассмотрим их: Функция Описание function Random(maxValue: integer): integer; Возвращает случайное целое число в диапазоне от 0 до maxValue - 1 function Random(a, b: integer): integer; Возвращает случайное целое число в диапазоне от a до b function Random: real; Возвращает случайное вещественное число в диапазоне [0..1) Пример 1 Представьте, что вы подбрасываете монетку. Результат её падения или «орёл», или «решка». Смоделируем этот процесс. Поскольку при бросании у нас есть всего два варианта исхода, то в последовательность псевдослучайных чисел должны входить только два числа: 0 и 1. Под нулём мы будем понимать «орла», а под единицей - «решку». program coin; var i, n, s: integer; 78 Модуль 1. Алгоритмизация и программирование begin randomize; write('Введите кол-во бросаний: '); readln(n); write('Результаты бросаний: '); for i := 1 to n do begin // получим результат броска s := random(2); if (s = 0) then write('орел ') else write('решка ') end; writeln; end. Сначала мы запустим генератор псевдослучайных чисел и введём число n - количество бросаний. Затем в цикле в переменной s будем получать случайное целое число из диапазона [0..1]. Если получим 0, то выведем слово «орёл», а при получении 1 - «решка». Пример 2 С клавиатуры вводится целое число n - количество элементов в массиве и вещественное число A. Заполним массив псевдослучайными вещественными числами из диапазона [0..A). В нашем арсенале нет функции, которая получает псевдослучайное вещественное число из диапазона [0..A), но мы можем её создать, умножая на А псевдослучайное число из диапазона [0..1). Тогда решение будет выглядеть следующим образом: Код программы Вывод program randarray; var i, n: integer; M: array [1..100] of real; A: real; begin randomize; write('Введите кол-во элементов массива: readln(n); write('Введите максимальный элемент массива: readln(A); for i := 1 to n do M[i] := A * random; write('Заполненный массив: '); for i := 1 to n do write(M[i]:6:2, ' '); writeln; end. ); ); Введите кол-во элементов массива: 5 Введите максимальный элемент массива: 102.5 Заполненный массив: 56.33 26.12 57.23 51.97 11.96 § 10. Случайные числа 79 ОБОБЩЕНИЕ НОВЫХ ЗНАНИЙ Случайные числа применяются для решения широкого круга прикладных задач в физике, статистике, криптографии и т. д. Получить настоящие случайные числа очень сложно, и для этого требуется специальная аппаратура. В цифровой вычислительной технике используются генераторы псевдослучайных чисел. Генератор псевдослучайных чисел - это алгоритм, результатом работы которого является последовательность практически независимых друг от друга чисел. Любой генератор необходимо запускать, то есть задавать начальное значение, поскольку в противном случае всегда будут получаться одинаковые последовательности. ПРИМЕНЕНИЕ ЗНАНИЙ 1. • Что такое случайные процессы? Возможно ли смоделировать истинно случайный процесс с помощью компьютера? Если вы считаете, что возможно, приведите пример. 2. Какими средствами обладает программист, пишущий на языке Паскаль, для работы со случайными величинами? 3. Зачем необходимо запускать генератор псевдослучайных чисел? 4. Напишите программу, которая с помощью генератора псевдослучайных чисел получает и выводит на экран 10 целых чисел из диапазона [1 ..25]. 5. Смоделируйте бросание игрального кубика. Напомним, что у игрального кубика 6 граней. 80 Проверь себя Задание 1 Переведите из шестнадцатеричной системы счисления в двоичную и десятичную числа: AB16, 201 Задание 2 C клавиатуры вводится число n - размер квадратной матрицы. Создайте единичную матрицу (матрицу, у которой значения элементов главной диагонали равны 1, а значения всех остальных элементов равны 0) введённого размера. Задание 3 Доработайте программу coin из § 10, чтобы результаты «бросков» записывались в файл coin.txt. 81 ПРИМЕНЕНИЕ ЗНАНИЙ [необходимый уровень) Задание 1 С клавиатуры вводится строка. Проверьте, может ли эта строка быть записью шестнадцатеричного числа. Задание 2 С клавиатуры вводятся размеры двумерного массива, а после них - сам массив. Найдите и выведите на экран сумму значений элементов, расположенных в левом верхнем и правом нижнем углах. Задание 3 Заполните квадратную матрицу случайными числами. Задание 4 Напишите программу, имеющую в своём составе рекурсивную функцию по вычислению НОД двух чисел. Задание 5 В текстовом файле в двух строках записаны два целых числа. Прочитайте их и вычислите с помощью функции из задания 4 НОД этих чисел. Задание 6 Имеется текстовый файл test.txt, содержащий одну строку: ' Привет всем '. Допишите в конце строки восклицательный знак. ПРИМЕНЕНИЕ ЗНАНИЙ [повышенный уровень] Задание 1 Двумерный массив (матрица) целых чисел заполняется случайными числами. Найдите среднее арифметическое значений элементов матрицы. Задание 2 С клавиатуры вводится последовательность целых чисел до нуля. Посчитайте и выведите на экран НОД всех этих чисел. Задание 3 Напишите программу, которая переворачивает строку. Задание 4 С клавиатуры вводится число n - размер квадратной матрицы. Заполните её последовательно квадратами целых чисел. Задание 5 В двумерном массиве хранятся данные об оценках учеников класса. В первой строке - данные об оценках первого ученика, во второй - второго и т. д. Узнайте средний балл всего класса. C клавиатуры вводится инфор- 82 мация о количестве учеников и количестве предметов. Заполните матрицу с помощью генератора псевдослучайных целых чисел из интервала [2..5]. В качестве ответа выведите матрицу и средний балл в формате: 10 знаков, из них 3 под дробную часть. Задание 6 В файле записаны элементы вещественного массива, каждое число в новой строке. Создайте новый файл, в котором элементы массива идут в обратном порядке. ПРИМЕНЕНИЕ ЗНАНИЙ (максимальный уровень] Задание 1 Составьте программу, на вход которой поступает двоичное число в виде строки и которая переводит это число в шестнадцатеричную систему счисления. Задание 2 Составьте программу, которая меняет местами два произвольных элемента матрицы. На вход программе поступает матрица, заполненная случайными целыми числами, а также координаты двух элементов матрицы. Выводите матрицу после заполнения и после выполнения замены. Задание 3 Напишите программу, которая проверяет, является ли строка палиндромом. (Палиндром - это строка, которая слева направо и справа налево читается одинаково.) Задание 4 В первой строке файла input.txt записано количество строк целочисленной матрицы, во второй строке - количество столбцов, в третьей через пробел идут элементы матрицы по строкам. Заполните матрицу из файла и напишите функцию, которая определяет, есть ли в матрице хотя бы две строки с одинаковой суммой значений элементов. Задание 5 С клавиатуры вводится имя текстового файла и целое число n - номер строки. Необходимо удалить из файла строку с номером n. Новый файл не создавать. Задание 6 С клавиатуры вводится число n - количество бросаний кубика. Посчитайте, сколько раз появляется каждое из чисел 1 ..6. Подсказка: используйте массив из шести элементов. 83 Итоговая проверочная работа Задание 1 а) В текстовом файле input.txt записаны два числа, по одному в каждой строке. Найдите среди них максимальное и выведите на экран. б) С клавиатуры вводятся целые числа m и n - размеры матрицы. Заполните столбцы с чётными номерами нулями, а с нечётными - единицами. После этого выведите матрицу. Задание 2 а) C клавиатуры вводится целое число n - размерность квадратной матрицы. Заполните главную диагональ нулями, все элементы выше главной диагонали - единицами, а все элементы ниже главной диагонали - двойками. Выведите получившуюся матрицу. б) C клавиатуры вводится три целых числа п, a и b (a < b). Запишите в первую строку файла random.txt через пробел п случайных целых чисел из диапазона [a..b]. Задание 3 а) Последовательность, заданная формулой Кат(п) = 0, 1, при n = 0; Кат(п - 1) 2 f2n - 1) n + 1 , при n > 0, называется последовательностью Каталана. Напишите рекурсивную функцию, вычисляющую числа Каталана. б) В файле input.txt в двух строках через пробел записаны координаты двух ферзей на шахматном поле размером 8^8. Определить, бьют ли ферзи друг друга. Пример файла: 3 8 4 2 84 т Решаем жизненные задачи и работаем над проектами Жизненная задача 1. Биоритмы Ваша роль. Программист. Описание. Биологические ритмы (биоритмы) - периодически повторяющиеся изменения характера человека, а также колебания мощности его биологических процессов и явлений. Их изучением занимается раздел биологии, который называется хронобиологией. Существует теория, что в момент рождения человека с различной периодичностью запускаются три ритма, определяющие эмоциональный (период 28 дней), интеллектуальный (период 33 дня) и физический (23 дня) уровни его активности. Стоит отметить, что научного подтверждения эта теория не получила. Графическими изображениями этих ритмов являются синусоиды, соответственно, интересны те дни, когда каждая синусоида достигает максимума или минимума или обращается в ноль. Ваши друзья очень хотели бы узнать эти дни. Задание. Пользователь с клавиатуры вводит дату своего рождения. Кроме того, он указывает месяц и год, на который он хотел бы получить информацию. Ваша задача: 1) организовать интерфейс пользователя для ввода данных пользователем; 2) произвести расчёт указанных выше дней на введённый месяц. Для этого вспомните операции с целыми числами и то, как найти «ноль» синусоиды, если известен её период; 3) вывести информацию о том, на какие даты приходятся указанные дни. 85 Жизненная задача 2. Записная книга Ваша роль. Программист. Описание. Человек придумал записные книги, чтобы не запоминать большое количество информации, а иметь возможность в нужный момент её быстро найти. Представьте, что вашей маме понадобилась электронная записная книга, в которую она смогла бы записывать телефоны всех своих друзей и знакомых. Она хотела пойти в магазин и купить цифровое устройство, но вы, поскольку уже знаете достаточно в области программирования, остановили её и сказали, что сделаете ей такую книгу сами. Задание. Напишите следующую программу. Запустив программу, пользователь видит меню, состоящее из следующих пунктов: Добавить запись Найти запись Выход Если он выбирает первый пункт, то ему необходимо ввести фамилию и имя человека, а затем его телефон. Информация должна храниться в текстовом файле, каждая строка которого - это данные о человеке. Вид строки следующий: Фамилия Имя Телефон. Разделитель - символ «пробел». Если пользователь вводит данные, но при этом и имя, и фамилия, и телефон уже присутствуют в файле, то ему выдаётся сообщение о том, что такие данные уже были введены ранее. В случае, когда пользователь выбирает второй пункт, он может ввести слово без пробелов. Программа должна попытаться найти это слово. Оно может являться фамилией, именем или телефоном. На экран должны быть выведены все строки файла, в которых произошло совпадение при поиске. При выборе третьего пункта меню программы закрывается. После выполнения первой или второй операции пользователю опять показывается меню. 86 Проект 1. Рецептурная книга В рамках данного проекта вам предлагается создать программу, автоматизирующую рецептурную книгу, в которой вы, ваши друзья или родственники смогли бы хранить свои кулинарные рецепты. Определите, какую информацию должна хранить книга, какие важные составляющие есть у рецепта и по каким критериям организовать по ней поиск. Ваша программа должна предлагать пользователю удобный интерфейс. Данные должны храниться в текстовом файле. Структуру файла выберите сами. Проект 2. Метод Монте-Карло В этом проекте вам предлагается научиться с помощью случайных величин вычислять площади фигур. Посмотрите на рисунок. Там нарисована фигура. Для вычисления её площади мы ограничим фигуру прямоугольником (его площадь мы знаем) и будем случайно «кидать точки» в этот прямоугольник. Какие-то из точек попадут в нашу фигуру, а какие-то нет. В математике доказано, что площадь фигуры, ограниченной кривой, будет равна: N S = S . попадании ^ф ^прям ■ N ’ Nвсего Создайте программу, которая будет вычислять площади фигур, ограниченных параболой, полуокружностью и любой кривой на ваше усмотрение. 87 О профессиях Дорогие ребята! Три года мы с вами на уроках учились и пытались постепенно овладеть навыками по созданию программ для персональных компьютеров. Профессия программиста многогранна и разнообразна. Одни специалисты создают программы для цифровых устройств, другие пишут операционные системы, третьи генерируют базы данных и приложения для них, четвёртые производят программные системы для сети Интернет - web-приложения, пятые конструируют сложные многопроцессорные системы, шестые разрабатывают компьютерные игры и программы для мобильных устройств и коммуникаторов и т. д. Любой хороший программист может построить отличную карьеру и стать руководителем группы разработчиков программного обеспечения, а затем, возможно, и управляющим целого направления. В последнее время в мире всё больше и больше приобретают важное место специалисты, которых называют фрилансерами, от английского слова freelancer - вольный художник. Это люди, которые через сеть Интернет или любым другим способом выполняют определённую работу на заказ. Среди программистов рынок фриланс-услуг широко развит. Ведь для создания программы не обязательно находиться в офисе заказчика. Разработчик может выполнять заказ у себя дома. Главное - выполнить работу качественно и в срок. Если фриланс - прерогатива частных разработчиков, то компании, не оставаясь в стороне, занимаются оффшорным программированием, то есть разработкой программ для удалённых (в основном иностранных) заказчиков. Наша страна не является лидером в оффшорном программировании, уступая первые места Ирландии и Индии. В любом случае, профессия программиста в век цифровых технологий остаётся популярной, востребованной и престижной. Вместе с тем, тысячи людей находят в программировании и информационных технологиях место для хобби и приятного времяпрепровождения. Интернет полон сайтами программистов-любителей, предлагающих на всеобщее обозрение свои творения. Одним словом, занимайтесь программированием! Это весело и полезно! Удачи вам! 88 Модуль 2. Знакомство с математической логикой 89 Этот модуль поможет вам: • узнать о древней науке логике и её применении в компьютере; • узнать способ упрощения логической формулы, не требующий равносильных преобразований; • познакомиться с именами выдающих учёных, предложивших использовать методы математической логики для упрощения сложных электрических схем, узнать, как графически представляется логическая функция с помощью логических схем; • познакомиться с важными логическими элементами компьютера -сумматором и триггером. Для этого вам надо научиться: • применять понятия, лежащие в основе логики; • составлять логические формулы и решать с их помощью задачи; • научиться пользоваться картами Карно для упрощения логической функции; • упрощать релейно-контактные схемы; • составлять схемы из логических элементов. 90 Модуль 2. Знакомство с математической логикой Введение Слово «логика» происходит от латинского слова logos - разум и знакомо каждому. «Он поступает нелогично», «логично было бы предположить», «где тут логика?» - все эти фразы вы слышали и понимаете, что они означают. Вы спросите: «При чём тут информатика? Как знание логики поможет нам в изучении компьютера или в программировании?» Часто бывает, что понятия, которые мы используем в быту, имеют гораздо более широкое толкование, чем то, к которому мы привыкли. Так и с логикой. Логика является одной из древнейших наук. Как стройная система знаний она сформировалась в IV веке до нашей эры в трудах выдающегося древнегреческого мыслителя Аристотеля. В то время бурно развивались науки: физика, математика, астрономия, медицина - и нужен был инструмент для того, чтобы осмыслить, что представляет собой процесс познания и вообще умственная деятельность. Нужно было ответить на вопрос: насколько рассуждения и выводы учёных правильно отражают действительность, можно ли, рассуждая, получить «истинное знание»? В этом модуле вы познакомитесь с азами этой древней, но в то же время и молодой науки. Среди многочисленных применений логики нас будет интересовать, конечно, в первую очередь её связь с информатикой, с компьютером. С другими, не менее интересными направлениями науки логики вы можете познакомиться на уроках истории, обществознания. § 1. Что такое математическая логика? Высказывания 91 § 1. Что такое математическая логика? Высказывания ПОСТАНОВКА ПРОБЛЕМЫ УРОКА Почему именно на уроках информатики мы изучаем основы логики? При решении задач и в быту, и в учебной деятельности вам приходится оперировать различными понятиями, выстраивать цепочки рассуждений и доказательств, записывать условия, решения и ответы, то есть заниматься логическими построениями. Всегда ли убедительно они выглядят? Как вы считаете, в чём состоит важность науки логики? Сформулируйте основной вопрос урока. Сравните свою формулировку с авторской (с. 1 91 учебника). РЕШЕНИЕ ПРОБЛЕМЫ Как развивалась логика? Древнегреческий учёный Аристотель (384 - 322 до н. э.) заложил основы формальной логики. Формальная логика изучает мышление. Есть и другие науки, изучающие мышление: философия, психология, кибернетика, физиология высшей нервной деятельности. Каждая из этих наук отличается методами изучения. Формальная логика изучает мышление с точки зрения «взаимодействия» логических форм и действия формально-логических законов. Основными формами мышления являются понятие, суждение, умозаключение. Понятие - это мысленное отражение существенных признаков объекта или класса объектов в их взаимосвязи. Например, понятие «кошка» определяется так: «Кошка - это млекопитающее, относящееся к роду felis, к виду домашняя кошка». • Приведите ещё примеры понятий. Отдельными понятиями люди никогда не мыслят. Суждение - это форма мышления, в которой что-то утверждается или отрицается об объектах, их свойствах или взаимоотношениях. С помощью суждений выражают соотношение между различными понятиями, связывают их. Пример суждения: «Птицы - это теплокровные животные». • Приведите ещё примеры суждений. С помощью умозаключения из одного или нескольких суждений, называемых посылками, по определённым правилам вывода получаются новые суждения - заключения. 92 Модуль 2. Знакомство с математической логикой Умозаключение, представляющее собой переход от посылок 1,2 к заключению, является правильным, если между посылками и заключением имеется отношение логического следования, то есть заключение является логическим следствием посылок. В противном случае - если между посылками и заключением нет такого отношения - умозаключение неправильно. Если нарушить правила вывода, то умозаключение станет неверным. Пример 1 - правильное умозаключение: Посылка 1: «Все люди смертны» Посылка 2: «Сократ - человек» Заключение: «Сократ смертен» Пример 2 - неправильное умозаключение: Посылка 1: «Стекло прозрачно» Посылка 2: «Алмаз не стекло» Заключение: «Алмаз непрозрачен» Естественная логика человека позволяет интуитивно использовать логические законы. Формальная логика - мощное орудие познания, позволяющее работать более эффективно во всех сферах человеческой деятельности, - была создана на основе естественной логики. Формальная логика применяется: • в научной (учебной) деятельности. Каждая наука связана с переработкой, систематизацией понятий, для чего и необходимо знание логических правил; • в области философии; • в научных спорах; • для выражения мысли в устной и письменной речи. Первым, кто выдвинул идею об описании построений формальной логики с помощью математических символов, был немецкий математик Готфрид Вильгельм Лейбниц (1646-1716). Он считал, что если обозначить особыми знаками понятия и отношения между ними, то любое умозаключение можно преобразовать и вычислить. Это сделает процесс получения умозаключения подобным процессу точного вычисления, что приведёт к исчезновению споров между учёными и облегчит процесс мышления. Только в XIX веке английский учёный Джордж Буль (181 5-1 864) реализовал идею Лейбница. Он создал алгебру (её называют булевой алгеброй, алгеброй высказываний, алгеброй логики), в которой высказывания (суждения) обозначены буквами и определены операции над ними. Введение символических обозначений в логику было таким же значимым, как и введение символьных обозначений в математику. Именно это сделало возможным появление нового направления в логике - математической (символической) логики. Математическая логика применяется в математике, кибернетике, биологии, лингвистике, философии, социологии, педагогике. § 1. Что такое математическая логика? Высказывания 93 Высказывание. Простое и сложное высказывание. Логические операции В математической логике суждения называют высказываниями. Высказывание - это повествовательное предложение, относительно которого можно сказать, истинно оно или ложно. Вопросительные и побудительные предложения высказываниями не являются. Примеры высказываний: • «Москва - большой город»; • «Щуки не рыбы». Первое из этих высказываний истинно, второе - ложно. Истинность или ложность называют логическими, или истинностными, значениями (значениями истинности) высказывания. Логические значения удобно кодировать в двоичной системе счисления: истина - 1; ложь - 0. Слова: «не», «и», «или», «либо ... либо», «влечёт», «тождественно» и их синонимы называют логическими связками. Логические связки служат для обозначения логических операций над высказываниями. Высказывания, не содержащие логических связок, называют простыми или элементарными. Примеры простых высказываний: • «Аристотель - воспитатель Александра Македонского»; • «Аристотель старше Александра Македонского»; • «5 > 7»; • «5 - чётное число». Высказывания, содержащие логические связки, называются сложными. Примеры сложных высказываний: • «Если Аристотель - воспитатель Александра Македонского, то Аристотель старше Александра Македонского»; • « 5 > 7 или 5 - чётное число». Как было сказано выше, высказывания в алгебре логики обозначают латинскими буквами. Например: a = «Аристотель - воспитатель Александра Македонского». Буквы, обозначающие логические высказывания, называют логическими переменными. Логические операции над высказываниями удобно описывать таблицей истинности, в которой для каждого из вариантов соотношений значений истинности простых высказываний, входящих в состав сложного, указывается результат логической операции - значение сложного высказывания. 94 Модуль 2. Знакомство с математической логикой Таблицы истинности основных логических операций Инверсия (отрицание) - унарная логическая операция (применяется к одному высказыванию-операнду). Обозначается: -а, а, НЕ а. Результат операции отрицания - изменение значения логической переменной на противоположное. На рисунках, расположенных рядом с таблицами истинности (рис. 2.1 -2.6), с помощью кругов дана графическая интерпретация действия логических связок - обозначены области, соответствующие различным комбинациям значений переменных а и b (0, 0; 0, 1; 1,0; 1, 1). Комбинации значений, при которых данное высказывание истинно, выделены красным цветом, значению «ложь» (0) соответствует чёрный цвет. Вы уже познакомились с этой графической интерпретацией, когда изучали множества в курсе математики. Конъюнкция (логическое умножение) - бинарная логическая операция (применяется к двум операндам). Обозначается: адЬ, алЬ, а* b, a И b. Конъюнкция двух операндов принимает значение «истина» (1) тогда и только тогда, когда истинны (1) оба операнда, и «ложь» (0) в противном случае. Рис. 2.2 § 1. Что такое математическая логика? Высказывания 95 Дизъюнкция (логическое сложение) - бинарная логическая операция. Обозначается a / b, a + b, a ИЛИ b. Дизъюнкция двух операндов принимает значение «ложь» (0) тогда и только тогда, когда ложны (0) оба операнда. a b a V b 0 0 0 0 1 1 1 0 1 1 1 1 Рис. 2.3 Импликация (следование) - бинарная логическая операция. Обозначается a ^ b. Часть формулы до импликации называют основанием условного высказывания, а часть, расположенную за ней, - следствием. Эти две части нельзя менять местами во избежание искажения смысла высказывания. Импликация ложна только в том случае, когда значение первого операнда 1, а второго - 0 (из «истины» следует «ложь»). a b a ^ b 0 0 1 0 1 1 1 0 0 1 1 1 Рис. 2.4 Эквиваленция - бинарная логическая операция. Обозначается a о b. Истинное значение этой операции означает совпадение значений операндов и наоборот. 96 Модуль 2. Знакомство с математической логикой a b a ^ b 0 0 1 0 1 0 1 0 0 1 1 1 Рис. 2.5 Строгая дизъюнкция (исключающее ИЛИ) - бинарная логическая операция. Обозначается a v b, a © b. Смысл истинности строгой дизъюнкции: истинно либо одно, либо другое высказывание, причём обязательно одно из них. a b a V b 0 0 0 0 1 1 1 0 1 1 1 0 Рис. 2.6 В отличие от разговорного языка, в математической логике простые высказывания a и b, входящие в сложное высказывание, могут быть не связаны друг с другом по смыслу. Например, пусть даны два высказывания: a = «Если Лондон - столица Франции» и b = «2 • 2 = 5». Тогда правомерно высказывание «Если Лондон - столица Франции, то 2 • 2 = 5» (a ^ b). § 1. Что такое математическая логика? Высказывания 97 ОБОБЩЕНИЕ НОВЫХ ЗНАНИЙ Математическая логика использует для описания формальнологических построений математические обозначения. В математической логике производятся операции над высказываниями (аналог переменной в математике). Для обозначения высказываний используются буквы латинского алфавита. Логические связки связывают одно или несколько простых высказываний в сложное. Таблица истинности отображает значение сложного высказывания в зависимости от распределения значений истинности простых высказываний, входящих в него. ПРИМЕНЕНИЕ ЗНАНИЙ 1. • Приведите примеры простых высказываний. 2. • Приведите примеры сложных высказываний. 3. • Определите, какие из примеров являются высказываниями, а какие нет. а) «Сегодня четверг»; б) «Собирайся в школу»; в) «Все киты - рыбы»; г) «Сколько будет к трём прибавить два?»; д) «2 • 3 = 8»; е) «2 + 3»; ж) «5 > 8». 98 Модуль 2. Знакомство с математической логикой § 2. Таблица истинности логической формулы ПОСТАНОВКА ПРОБЛЕМЫ УРОКА Сложное высказывание получается из простых высказываний, соединённых логическими связками. До сих пор мы рассматривали высказывания, в которых была всего одна логическая операция, и знаем, как будет выглядеть таблица истинности в зависимости от вида логической связки. Вы знаете, что в естественном языке не встречаются случаи, когда в сложном предложении более чем два простых предложения. Или в сложном высказывании не одна логическая связка? • Как вы считаете, может ли сложное высказывание состоять из трёх и более простых высказываний? А если может, то вправе ли мы использовать в сложном высказывании разные логические связки? Сформулируйте основной вопрос урока. Сравните свою формулировку с авторской (с. 191 учебника). РЕШЕНИЕ ПРОБЛЕМЫ Логическая формула строится по следующим правилам: • всякая логическая переменная (элементарное высказывание) - формула; • если a и b - формулы, то и -а, a л b, a v b, a ^ b, a о b, ab - формулы. Как в алгебраическом выражении может быть несколько операций, так и в сложном высказывании (логической формуле) может быть несколько логических операций. Каждая логическая операция имеет свой приоритет (порядок) выполнения, так же как операции в алгебраическом выражении. Порядок действий в логических формулах В логических формулах, не содержащих скобки, действия выполняются в следующем порядке: 1) инверсия (-); 2) конъюнкция (л); 3) дизъюнкция (v); 4) импликация (^); 5) эквиваленция (о); 6) исключающая дизъюнкция (V). Одноимённые операции производятся по очереди слева направо. Скобки (как и в математике) служат для изменения или обозначения порядка логических операций. Теперь у нас есть необходимые знания, чтобы ответить на основной вопрос урока: как составить логическую таблицу формулы, состоящей из про- § 2. Таблица истинности логической формулы 99 извольного количества высказываний и произвольного количества логических связок? Порядок составления таблицы истинности для формулы 1. Переписать формулу. 2. Расставить все возможныe (в зависимости от количества переменных) варианты распределения значений истинности (0 и 1) входящих в неё переменных. Если одинаковых переменных в формуле несколько, то они должны иметь одинаковые распределения значений. 3. Над знаками логических операций обозначить порядок их выполнения с учётом приоритета операций и скобок. 4. Под знаками операций написать результат их выполнения, согласно таблицам истинности для логических операций. 5. Столбец, соответствующий последней операции, содержит значения формулы. Выделить его. Пример Порядок действий в формуле 4 6 1 7 2 5 ((р V q) о -q) (-Г -р) 0 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 1 0 1 01 1 1 0 0 1 1 0 01 1 1 0 1 1 0 0 1 1 0 01 1 01 1 1 0 1 1 0 1 1 0 0 1 0 0 01 1 1 0 1 1 0 1 01 1 01 1 1 1 0 01 1 1 0 0 01 1 1 1 0 01 1 01 1 01 Замечание. Столбцы, в которых находятся отрицания (-q, -г, -р), удобно сразу заполнять инверсными по отношению к q, г, р значениями. 100 Модуль 2. Знакомство с математической логикой Если опустить теперь промежуточные операции, то таблица истинности примет вид: p q r ((p V q) o-q) ^(-r^-p) 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 Формула, правый столбец таблицы истинности которой содержит только единицы, называется тавтологией, или тождественно истинной формулой. Она истинна независимо от значений входящих в неё переменных. Формула, логическая таблица которой содержит только нули, называется противоречием, или тождественно ложной формулой. Она ложна независимо от значений входящих в неё переменных. Заметим, что существует связь между количеством переменных, входящих в формулу, и количеством комбинаций значений логических переменных (и, соответственно, количеством строк таблицы истинности). Как вы видели в § 1, для двух переменных существует четыре сочетания их значений 0 и 1. Для трёх переменных таких сочетаний восемь, как видно из приведённого примера. • В общем случае для n логических переменных существует 2n комбинаций их значений. Попробуйте показать это. Теперь посмотрите внимательно на первые три столбца полученной таблицы истинности. Что представляют собой комбинации значений переменных? Их можно рассматривать как все последовательные двоичные трёхразрядные числа (от 000 до 111), эти числа фактически являются номерами комбинаций (от 0-й до 7-й). Это позволяет автоматически заполнять распределение значений истинности переменных в таблицах истинности. § 2. Таблица истинности логической формулы 101 ОБОБЩЕНИЕ НОВЫХ ЗНАНИЙ Порядок составления таблицы истинности для произвольной логической формулы: 1. Переписать формулу. 2. Расставить все возможныe (в зависимости от количества переменных) варианты распределения значений истинности (0 и 1) входящих в неё переменных. Если одинаковых переменных в формуле несколько, то они должны иметь одинаковые распределения значений. 3. Над знаками логических операций обозначить порядок их выполнения с учётом приоритета операций и скобок. 4. Под знаками операций написать результат их выполнения, согласно таблицам истинности для логических операций. 5. Столбец, соответствующий последней операции, содержит значения формулы. Выделить его. ПРИМЕНЕНИЕ ЗНАНИЙ Постройте таблицы истинности для следующих формул: а) ((-q ^ р) V q) о р; б) -(q ^ р) V q ^ р; в) -q ^ р V q о р; г) (b л -а) ^ с V -b; д) c ^ -с л a V b; е) a л b л с (а V с о a). 102 Модуль 2. Знакомство с математической логикой § 3. Равносильные преобразования. Законы алгебры логики. Нормальная форма логической формулы ПОСТАНОВКА ПРОБЛЕМЫ УРОКА Вы заметили, что у логической формулы и алгебраического выражения есть общее. Закономерно предположить, что при более глубоком изучении обнаружится и более глубокое сходство. Во всяком случае, было бы легче, если перед тем как строить логические таблицы для заданий предыдущего параграфа, формулы удалось бы упростить. В математике для упрощения выражения вы прибегаете к равносильным (тождественным) преобразованиям — только в этом случае вы получаете выражение, равносильное данному. Правила для преобразования алгебраических выражений вы знаете. • Как вы считаете, можно ли подвергнуть тождественным преобразованиям логическую формулу? Сформулируйте основной вопрос урока. Сравните свой вариант с авторским (с. 191 учебника). РЕШЕНИЕ ПРОБЛЕМЫ Равносильные формулы Формулы, которые принимают одинаковые значения на всех наборах значений входящих в них переменных (имеют одинаковые таблицы истинности), называются равносильными. Пример (а b) 0 1 0 0 0 1 1 0 0 1 1 1 равносильно (-а V b)) 1 1 0 1 0 1 0 0 0 0 1 1 Замечание. Равносильными могут быть и формулы, содержащие разные наборы переменных. Замена формулы другой, ей равносильной, называется равносильным (тождественным) преобразованием данной формулы. Для того чтобы подвергнуть логическую формулу равносильным преобразованиям, надо знать, какие преобразования оставят значения формулы неизменными. § 3. Равносильные преобразования. Законы алгебры логики 103 Равносильные (тождественные) преобразования используются для упрощения логической формулы. Законы алгебры логики Получить равносильную формулу можно, используя тождественные преобразования при помощи основных законов алгебры логики. Перечислим их. Примечание. Символ «=» заменяет слово «равносильно». 1) 2) X л X ^ X X V X ^ X 3) X л 1 ^ X 4) X V 1 ^ 1 5) X л 0 ^ 0 6) X V 0 = X 7) X л -X ^ 0 8) X V -X ^ 1 9) -(-X) ^ X 10) X л (у V X) ^ X 11) X V (у л X) ^ X 12) (X л у) V (X л -у) ^ X 13) (X л z) V (у л -z) V (x л у) ^ X л z V у л -z 14) X ^ у = (X ^ у) л (у ^ X) 15) х^ у = -X V у 16) - (X л у) ^ -X V -у; 17) - (X V у) ^ -X л -у 18) X л у = -(-X V -у) 19) X V у = - (-X л -у) законы идемпотентности законы исключения констант закон противоречия закон исключённого третьего закон снятия двойного отрицания правила поглощения правило исключения (склеивания) правило обобщённого склеивания законы, выражающие одни логические операции через другие Из этой группы законов следует, что любую логическую операцию можно выразить через конъюнкцию и отрицание или через дизъюнкцию и отрицание. Дальнейшее исключение логических операций невозможно. Однако существует операция, через которую выражаются все основные логические операции. Эта операция называется штрих Шеффера. Она обозначается символом «|» и определяется следующей таблицей истинности: 104 Модуль 2. Знакомство с математической логикой х у х|у 0 0 1 0 1 1 1 0 1 1 1 0 Из определения этой операции следует, что -х ^ х | х; х л у = (х | у) | (х | у). 20) х л у = у л х 21) х V у = х V у 22) х л (у л z) = (х л у) л z 23) х V (у V z) ^ (х V у) V z 24) х л (у V z) ^ (х л у) V (х л z) 25) х V (у л z) ^ (х V у) л (х V z) коммуникативность конъюнкции коммуникативность дизъюнкции ассоциативность конъюнкции ассоциативность дизъюнкции дистрибутивность конъюнкции относительно дизъюнкции дистрибутивность дизъюнкции относительно конъюнкции Примечание. Если в формулах 20-25 заменить знак «л» на знак умножения «•», знак «V» - на знак сложения «+», знак «=» - на знак равенства «=», то можно заметить, что первые пять законов - это известные нам законы алгебры чисел, а шестой закон приводит к равенству, которое не справедливо в алгебре чисел. • Можно ли сказать, что -(ab) равносильно -а -b? Ответ обоснуйте с помощью таблиц истинности. Тождественные преобразования. Нормальная форма логической формулы Формула алгебры логики имеет нормальную форму, если она: • не содержит знаков, отличных от -, л, V (содержит только базовые логические связки); • знаки отрицания стоят в ней только при переменных. Вся логика вычислительной машины представлена в нормальной форме. • Формула (а V -b) л (-d л -с) имеет нормальную форму, а формула -(b л а) V (-d л с) — нет. Объясните почему. § 3. Равносильные преобразования. Законы алгебры логики 105 Теорема. Любую формулу, не представленную в нормальной форме, можно за конечное число преобразований перевести в нормальную форму, равносильную данной. Доказать эту теорему мы сейчас не сможем, но примем к сведению и будем ею пользоваться. Замечание 1. Равносильные преобразования осуществляются согласно порядку выполнения операций в логической формуле. Замечание 2. Для сокращения затрат времени при записи этапов упрощения формулы часто используют следующие соглашения: • знак конъюнкции (логического умножения) - «л» заменяют на «•» или опускают (так же, как и в алгебраическом выражении). Например, a л b заменяют на ab; • знак дизъюнкции (логического сложения) - «V» заменяют на «+». Например, a V b заменяют на a + b; • знак инверсии «-» заменяют на черту над формулой. Например, -a заменяют на а, а -(ac + b) заменяют на ac + b; • знак «=» (равносильно) заменяют на «=»; • знак «V» заменяют на «©». Пример Требуется упростить логическую формулу: a л b л c л( a v c о a). 1. Перепишем формулу: a л b л c л ( a v c о a) = abc(a + c о a). 2. Определим порядок действий (можно обозначить скобками): abc((a + c) о a). 3. Выполним тождественные преобразования: abc((a + c) о a) = abc(((a + + c) ^ a)(a ^ (a + c))) = abc(((a + c) + a)(a+ (a + c)) = abc((a c + a)((¥ + a) + c)) = = abc, так как во второй скобке получается 1, а после умножения abc и (a c + a) остаётся abc. Ответ: abc((a + c) о a) = abc. Замечание. Преобразования были бы менее громоздкими, если бы мы заметили, что a о b = ab + a b. Построение логической формулы по таблице истинности Зная логическую формулу, мы можем построить для неё таблицу истинности. А можно ли, имея таблицу истинности, найти логическую формулу, соответствующую таблице? Можно. Для того чтобы получить логическую формулу, необходимо: 1) для каждого набора значений логических переменных (строки таблицы истинности), на котором формула имеет значение 1 (1 в правом столбце), выписать конъюнкцию логических переменных, где переменные с нулевыми значениями записать с отрицаниями; 106 Модуль 2. Знакомство с математической логикой 2) записать дизъюнкцию полученных конъюнкций. Пример 1 a b c F 0 0 0 1 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 0 1 1 1 1 c &• Ь^ c а^Ь^ c а^Ь^ c а^Ь^ c а^Ь^ c а^ Ь^ c a^b^c Ответ: a^b^c + a^b^c + a^b^ c + a^b^c + a^b^ c. Пример 2 Дана логическая формула (x ^ y + z • y ^ x). Построим таблицу истинности. Порядок действий обозначим скобками. ((X (у + (z • у))) X) 0 1 0 0 0 0 1 1 1 0 1 0 1 1 1 1 1 1 0 1 1 1 0 0 0 1 1 0 1 1 1 1 0 0 1 1 1 0 0 0 0 0 1 1 0 1 1 0 1 1 1 1 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 X у z F 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 0 Применив правило построения логической формулы по таблице истинности, получим: X^y^Z + X^y^z + x^y^z + X^y^z + x^y^^ • Как убедиться, что мы получили формулу, равносильную исходной? • Как изменилась формула? В какой форме она записана? § 3. Равносильные преобразования. Законы алгебры логики 107 • Эту формулу можно упростить. Попробуйте. Получится x + y^z, но может быть, какая-нибудь другая формула, но с такой же таблицей истинности. ОБОБЩЕНИЕ НОВЫХ ЗНАНИЙ Изменить логическую формулу с целью упрощения или приведения к нормальной форме можно с помощью тождественных преобразований. Равносильные преобразования осуществляются согласно порядку операций в логической формуле. Чтобы записать логическую формулу по её таблице истинности, необходимо записать дизъюнкцию конъюнкций переменных, записанных на наборах значений переменных, где формула имеет значение 1. Причём, если значение переменной - 0, в конъюнкцию входит её отрицание. ПРИМЕНЕНИЕ ЗНАНИЙ 1. Заполнив таблицы истинности двух формул, покажите, что следующие формулы равносильны: а) (- (р л q]] и (-Р V -q); б) (- (р V q)) и (-р^л -q); в) (-(р q)) и (р V q); г) (- (р V q) и (-р о -q); д) (- (р ^ q) и (р л -q). 2. Запишите формулы в нормальной форме: а) a ^ b; б) a о b; в) a V b; г) -(a о -b); д) (-р V q)^ р; е) - (р о q) л р; ж) -(a ^ b) V b; з) ((-q ^ р ) V q) о р; и) -(q ^ р ) V q ^ р; к) -q ^ р V q о р; л) (b л -а ) ^ с V -b; м) c ^ -с л a V b. 108 Модуль 2. Знакомство с математической логикой § 4-5. Решение логических задач ПОСТАНОВКА ПРОБЛЕМЫ УРОКА Вы, конечно, решали логические задачи и можете привести много примеров. Вспомните, была ли необходимость для решения этих задач выражать условие задачи в виде логической формулы? Почему? Да, верно, эти задачи не требовали для своего решения таких действий. Вы решали их, пользуясь построениями естественной логики. • Как вы считаете, могут ли знания, полученные вами в области алгебры логики, помочь вам в решении логических задач? Сформулируйте основной вопрос урока. Сравните свой вариант с авторским (с. 191 учебника). НЕОБХОДИМЫЕ БАЗОВЫЕ ЗНАНИЯ Что такое логическая формула? (§ 2) Как можно упростить логическую формулу? (§ 3) РЕШЕНИЕ ПРОБЛЕМЫ Обилие типов логических задач и, следовательно, способов их решения не позволяет в учебнике рассказать обо всём. Остановимся на некоторых типах - это: • задачи, решаемые методом составления и анализа логической формулы; • задачи, решаемые составлением таблиц, связывающих условие задачи; с последующим анализом таблиц; • задачи, решаемые с помощью рассуждений. Следуя логике изучаемого материала, остановимся на решении задач методами алгебры логики. Решение логических задач с помощью алгебры логики заключается в записи условия задачи в виде логической формулы и дальнейшем анализе этой формулы. В простейшем случае решение находится непосредственно из исходной формулы, в других случаях, когда не всё так очевидно, формулу необходимо подвергнуть равносильным преобразованиям. Иногда для верной записи условия полезны рисунки, схемы. Необходимо знать, как в естественном языке представлены логические связки, чтобы перевести условие задачи в логическую формулу и затем рассмотреть её значения. В этом вам поможет таблица, в которой выражениям естественного языка поставлены в соответствие логические связки (табл. 2.1). § 4-5. Решение логических задач 109 Таблица 2.1 Логическая операция Логическая формула Союзы в естественном языке Примеры Конъюнкция A л B а; и; но; да; хотя; который; зато; однако; не только^, но и^; как^,так и^ B, несмотря на A; как А, так и В; А вместе с В; А в то время, как В Дизъюнкция A v B или А или В Разделительная дизъюнкция A V B либо; то ли^, то ли^; или (в смысле «либо») либо А, либо В Импликация A ^ B если^, то^; коль скоро^,то^ в случае А имеет место В; для В достаточно А; для А необходимо В; А влечёт В; А только если В; В, если А Эквиваленция A о B тождественно, эквивалентно А, если и только если В; если А, то и В и обратно; А, если В, и В, если А; для А необходимо и достаточно В; А тогда и только тогда, когда В Рассмотрим перевод фразы естественного языка на язык математической логики на примере. А B C «Он молчит, а Варенька поёт ему “виют витры”, или глядит на него задумчиво D своими тёмными глазами, или вдруг зальётся “ха-ха-ха”». (А. П. Чехов.) Для перевода фразы необходимо: 1. Выявить все простые высказывания и обозначить их логическими переменными: А = «Он молчит». В = «Варенька поёт ему “виют витры”». C = «(Варенька) глядит на него задумчиво своими тёмными глазами». D = «(Варенька) вдруг зальётся “ха-ха-ха”». 2. Определить логические союзы (по смыслу): «а» - конъюнкция первое «или» - дизъюнкция второе «или» - исключающая дизъюнкция (одновременно нельзя глядеть задумчиво и смеяться, также нельзя одновременно петь и смеяться). 3. Записать переведённую фразу: A л (B v C v D). 110 Модуль 2. Знакомство с математической логикой Пример 1. Задача, требующая анализа формулы Живут четыре друга. Их зовут Алексей, Борис, Сергей и Дмитрий. Фамилии их: Алексеев, Борисов, Сергеев и Дмитриев. Ни у одного мальчика первая буква фамилии не совпадает с первой буквой имени, кроме того, фамилия Сергея - не Алексеев. Определите фамилию и имя каждого мальчика, если известно, что от имени мальчика, фамилия которого Дмитриев, образована фамилия того мальчика, от имени которого образована фамилия Бориса. Решение 1. Введём обозначения. Обозначим имя и фамилию каждого мальчика двумя буквами (имя - прописной буквой, фамилию - строчной: A, B, C, D; а, b, c, d). 2. Переведём условие задачи на язык алгебры логики. В условии задачи говорится, что не существует мальчика, инициалы которого одинаковы, то есть следующие конъюнкции равны 0: А^ а = B^b = C^ c = = d = 0. Кроме того, по условию, C^ а = 0. Ещё известно, что существует такой мальчик, что выполняется условие: X^d = = B^y = 1. 3. Определим X и У. Проанализируем формулу: относительно У: если У = D, то существуют мальчики с одинаковой фамилией: X^d = 1 и B^d = 1, что противоречит условию задачи. Если У = B, то существует мальчик B^b = 1, что также неверно. Значит,Уф D; Уф B; относительно X: если X = B, то существуют мальчики B^d = 1 и B^y = 1, что противоречит условию задачи. Если X = D, то существует мальчик D^d = 1, чего тоже не может быть. Значит, X ф D, Xф B. Следовательно, остаются случаи: 1) У = C; X = А; 2) X = C; У = А. Предположим, что У = C, тогда X = А, что невозможно, так как тогда У^х = = C^a = 1, а по условию C^a = 0. Значит, У = А, X = C. Т о есть C^d = А^с = B^a = 1, отсюда D^b = 1. Ответ: Сергей Дмитриев, Алексей Сергеев, Борис Алексеев, Дмитрий Борисов. § 4-5. Решение логических задач 111 Пример 2. Задача, требующая произвести тождественные преобразования с целью минимизации формулы Пытаясь вспомнить победителей прошлого турнира, пятеро заявили, что по их мнению: 1) Антон был вторым, Борис - пятым; 2) Виктор был вторым, Денис - третьим; 3) Антон был третьим, Евгений - шестым; 4) Григорий был первым, Борис - третьим; 5) Виктор был третьим, Евгений - четвёртым. Оказалось, что каждый, высказывая своё мнение, ошибся один раз. Каково было истинное распределение мест, если ни одно из мест не было занято двумя участниками турнира? Решение Обозначим имя участника и позицию, занимаемую им в турнирной таблице, буквой и цифрой и запишем каждое высказывание в виде дизъюнкции его составляющих при равной нулю конъюнкции. • Обоснуйте этот шаг решения. Л2 + Б5 = 1, В2 + Д3 = 1, Л3 + Е6 = 1, Г1 + БЗ = 1; В3 + Е4 = 1, Л2 В2 Л3 Г1 В3^ Б5 = 0; Д3 = 0; Е6 = 0; БЗ = 0; Е4 = 0. Так как эти дизъюнкции тождественно истинны, то и их конъюнкция тождественно истинна, то есть: (Л2 + Б5) • (В2 + ДЗ) • (ЛЗ + Е6) • ( ^1 + БЗ) • (ВЗ + Е4) = 1. Значит, подвергнув эту формулу тождественным преобразованиям, конечный результат мы получим в виде тождественно истинной формулы. Анализируя условия, замечаем, что формулы вида (Ха • Xb) и (Ха • Ya) равны 0, так как один и тот же участник не может занимать разные места и одно и то же место не разделили между собой разные участники. В результате несложных преобразований получим: ^1 -В2-Л3-Е4-Б5 = 1. Ответ: Григорий занял первое место, Виктор - второе, Антон - третье, Евгений - четвёртое, Борис - пятое. Решение этой задачи сводилось к упрощению исходной формулы. Мы получили ответ, не используя условия о равенстве нулю конъюнкций. 112 Модуль 2. Знакомство с математической логикой Пример 3 Трое приятелей рассказали о машине, которую они видели на соревнованиях: 1) Это была Toyota стального цвета. 2) Это была чёрная Honda. 3) Это была машина другой марки, и цвет был не чёрный. Каждый из приятелей ошибся в одном из двух утверждений. Какого цвета и какой марки была машина? Решение Обозначим простые высказывания: T = «Это была Toyota»; s = «Цвет стальной» (steel); H = «Это была Honda»; b = «Цвет чёрный» (black); X = «Это была машина другой марки». Высказывание первого: T*s. Высказывание второго: H^b_ Высказывание третьего: Х^ b. Так как по условию каждый ошибся в одном из двух утверждений, для того, чтобы записать тождественно истинную формулу, поступим следующим образом: (7"*s + T*s]*(/-/*b + H*b]*(X 'b + X'b] - 1. Выполним логическое умножение, помня о том, что ощно^вре_менно машина не может быть разных марок и разного цвета, получим: ТXHsb = 1. Ответ: это была Honda стального цвета. ПРИМЕНЕНИЕ ЗНАНИИ 1. • Переведите на язык логики следующие высказывания: а) «Андрей идёт в кино только в том случае, когда там показывают комедию»; б) «Если в следующее воскресенье не будет дождя и я буду здоров, то я пойду в лес и буду собирать грибы»; в) «Спортсмен подлежит дисквалификации, если он некорректен по отношению к судье или сопернику или принимает запрещённые препараты». 2. Решите задачи: а) • В зале суда. § 4-5. Решение логических задач 113 Обвинитель. «Если подследственный совершил преступление, то он не мог это сделать один». Адвокат. «Это неправда!» Почему своим возгласом он сильно навредил подзащитному? б) • На вопрос. «Кто из учащихся изучал математическую логику?» получен верный ответ. «Если изучал Александр, то изучал и Пётр, но неверно, что если изучал Михаил, то изучал и Пётр». Кто изучал математическую логику? в) • Даны два десятичных числа X и Y. Их перевели в двоичную систему счисления и определили, что в числе X из шести разрядов три единицы, а в числе Y из четырёх разрядов две единицы. Логическое произведение этих чисел равно Ю02, а логическая сумма - 111 Ю02. Определите эти числа в десятичной системе счисления. г) • На вопрос мамы «Какой бы ты хотел пирог?» Серёжа ответил. - «Если начинка будет фруктовая без взбитых сливок, то тесто должно быть песочным»; - «Если не будет песочного теста, то пусть начинка будет не фруктовой»; - «Не надо сливок, если будет фруктовая начинка»; - «Пусть будут фрукты без взбитых сливок». Подумав, Серёжа понял, что его высказывания сводятся к трём простым. Сформулируйте их, решив задачу с помощью логических операций. РЕШЕНИЕ ПРОБЛЕМЫ Следующий тип задач требует анализа таблицы истинности, так как логическая формула, полученная при записи условий задачи, не является тождественно истинной. Пример 4. Задача, требующая анализа таблицы истинности По подозрению в разорении клумбы с редкими цветами задержали Бориса, Дмитрия и Степана. Один из них был студентом, другой - клоуном цирка шапито, третий - известным в городе воришкой. В процессе следствия студент всегда говорил правду, воришка всегда лгал, клоун мог сказать правду, а мог и приврать. Вот, что они утверждали. 1) Борис. «Я совершил это, Дмитрий не виноват»; 2) Дмитрий. «Борис не виноват, клумбу разорил Степан»; 3) Степан. «Я не трогал цветы, это Борис сорвал цветы для девушки». Кто совершил преступление? Кто из них был студентом, кто - клоуном, а кто - воришкой, если известно, что цветы рвал один человек? 114 Модуль 2. Знакомство с математической логикой Решение Обозначим буквами Б, Д и С высказывания «Борис виноват», «Дмитрий виноват», «Степан виноват». Тогда высказывания задержанных можно представить в виде конъюнкций: Борис. Б *Д; Дмитрий: Б_* С; Степан: Б-С. По условию задачи при правильном наборе значений истинности переменных Б, Д и С две конъюнкции ложны, а однна истинна. Поэтому истинна будет их дизъюнкция: L = [Б-Д] + [Б - С] + [Б-С]. Эта формула не является тождественно истинной, поэтому для решения задачи необходимо анализировать таблицу истинности: Б Д С Б-Д Б - С Б-с L 0 0 0 0 0 О 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 1 1 0 1 0 1 1 0 0 1 0 1 1 1 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 Видно, что функция истинна в пяти случаях из восьми. Случай 5 исключаем сразу: по условию не могут быть истинны сразу две конъюнкции. В случаях 4, 6, 7 виновными являются по два человека, что тоже противоречит условию задачи. Остаётся случай 2, то есть Борис не рвал цветы, клумбу разрушил Степан. Ответ: тот, кто произнёс данное утверждение (Дмитрий), - студент, Степан - воришка, а Борис - клоун. Существуют задачи, в которых части высказываний могут иметь разные значения истинности или значение истинности высказывания, описывающего условие задачи, не определено однозначно. Пример 5 На школьных соревнованиях по лыжным гонкам трое друзей спорили о том, кто победит: 1) Вот увидите, победит Сергей, - сказал Пётр. - У Бориса нет шансов. 2) Что ты говоришь? Победит Борис, а вот у кого нет шансов, так это у Ивана, - парировал Илья. 3) Сергей не победит, у Ивана - самые лучшие лыжи! - высказался Николай. § 4-5. Решение логических задач 115 Когда соревнования закончились, оказалось, что оба предположения двух друзей были правильными, а третий ошибся. Кто победил в соревнованиях? Решение Обозначим: С = «Победит Сергей»; Б = «Победит Борис»; И = «Победит Иван». Обозначим высказывания каждого из друзей: С-Б Б* И С Для того чтобы получить тождественно истинную формулу, учитывая то, что оба предположения двух друзей были правильными, а третий ошибся, запишем сумму конъюнкций, отражающих условие задачи: [С-Б]-[Б-И]-С + [С-Б]-[Б-И].С + [С-Б] • [Б-И]-С = 1. Упростим её: [С + Б] •Б*И*С = Б*И*С = 1. Ответ: победил Борис. ОБОБЩЕНИЕ НОВЫХ ЗНАНИЙ Для решения задачи с помощью составления логической формулы необходимо: 1) определить в условии задачи простые высказывания и обозначить их буквами; 2) записать каждое условие в виде логической формулы, связав простые высказывания с помощью логических связок, подходящих по смыслу; 3) собрать полученные формулы в общую формулу и, если возможно, упростить её; 4) проверить адекватность полученной формулы условию задачи; 5) подвергнуть формулу анализу или построить логическую таблицу и найти решение задачи; 6) записать ответ в том виде, который оговорен в условии задачи. 116 Проверь себя Задание 1 Упростите формулу: а) a о b + S‘b; б) X ^ ух + Z'x ^ z; в) a + b ^ a* с + b^ a. Задание 2 Составьте таблицу истинности формулы: а) X + y о X; б) X о y ^ X; в) X«z ^ X + у. Задание 3 Переведите на язык алгебры логики фразу: а) «Он не только хороший математик, но и хорошо знает английский язык»; б) «Если завтра будет хорошая погода и у меня будет время, пойду в лес и буду собирать грибы». Задание 4 Запишите формулу в нормальной форме: а] а + Ь; б] а ^ Ь. 117 ПРИМЕНЕНИЕ ЗНАНИЙ [необходимый уровень) Задание 1 Является ли формула тавтологией? Является ли она противоречием? а) Л о (Л + Л); б) (Л ^ В)^((В ^ С) ^ (Л ^ С)); в] [£Л^В]В]^Л; г] Л ^ Л • В. Задание 2 Упростите формулу: а) x-y+ x + y^ Х; б) а + b + с ^ с; в) x-y ^ x + y ^ х; г) x + у о X. Задание 3 Постройте таблицу истинности формулы: а) x-y+ x + у^ Х; б) а + b + с ^ с; в) x-y ^ x + у ^ Х. Задание 4 Запишите высказывание в виде логической формулы: а) «Для того чтобы х было нечётным числом, достаточно, чтобы х было простым числом»; б) «Если х положительно, то х2 положительно»; в) Необходимое и достаточное условие счастья для Иванушки-дурачка состоит в том, чтобы ездить на печи, играть на дудочке и жениться на Царевне. Задание 5 Решите логическую задачу. Обсуждая результаты соревнования, друзья спорили: 1) «Первой была синяя Honda», - сказал первый. 2) «Нет, это был жёлтый Renault», - возразил второй. 3) «Вы оба не правы: это была машина другой марки и не синяя», - вмешался в спор третий. Результаты фотофиниша показали, что каждый ошибся либо в марке машины, либо неправильно назвал её цвет. Какая машина пришла первой? Задачу решите методом составления логической формулы. 118 ПРИМЕНЕНИЕ ЗНАНИЙ [повышенный уровень) Задание 1 Постройте логическую таблицу и определите, является ли формула тавтологией. Является ли она противоречием? а] [а ^ Ь] о- [Ь ^ а]; б) a*b* (с + a + d) • b; Задание 2 Упростите формулу: в] а-Ь<г^[а + Ь]. в] э ^ Ь ^ а + аЬ. а] [а ^ Ь] ^ Ь + а ^ а', б) а* b ^ (с + a + d) • b; Формула в упрощённом виде должна содержать не более трёх базовых логических операций. Задание 3 Требуется, чтобы выключение света в комнате осуществлялось с помощью трёх различных выключателей таким образом, чтобы нажатие на любой из них приводило к включению света, если он перед этим был выключен, и к его выключению, если он был включен. Постройте логическую формулу, отвечающую условиям. Задание 4 Исключите возможно большее число скобок в формулах: а] [[Во[[С] + [О.Л]]]о[В^В]]; б] [[[Л- [В]]- С] + В]. Задание 5 Запишите высказывание в виде логической формулы: 1) «Или Семён пойдёт на вечеринку, и Михаил останется дома, или Семён не пойдёт на вечеринку, а Михаил отлично проведёт время с друзьями»; 2) «Дорожки, по которым дети переходят из здания в здание, содержатся в идеальной чистоте, а если в ненастную погоду они бывают мокрыми от дождя, то ученик несёт на ногах только влагу, но не грязь и не пыль» (В. А. Сухомлинский. «О воспитании»). Задание 6 Даны два десятичных числа Х и Y. Их перевели в двоичную систему счисления и определили, что в числе Х из шести разрядов четыре единицы и в числе Y из четырёх разрядов три единицы. Логическое произведение этих чисел равно 1102, а логическая сумма - число 1011112. Определите эти числа в десятичной системе счисления. ПРИМЕНЕНИЕ ЗНАНИЙ [максимальный уровень] Задание 1 ______ Упростите формулу: а^Ь + с ^ [Ь ^ а]. Формула в упрощённом виде должна содержать не более трёх базовых логических операций. 119 Задание 2 Упростите формулу: (х ^ y)^(yz ^ x^z], В упрощённом виде формула должна быть записана в нормальной форме и содержать только отрицание и две дизъюнкции, Задание 3 Решите логическую задачу. По обвинению в ограблении перед судом предстали Первый, Bторой и Третий. Установлено следующее: - Если Первый не виновен или Bторой виновен, то Третий виновен. - Если Первый не виновен, то и Третий не виновен. Кто из них преступник, если виновен только один человек? Задание 4 Выясните, являются ли следующие рассуждения логически правильными. Для этого представьте каждое предположение в виде логической формулы и проверьте, является ли заключение логическим следствием конъюнкции посылок: если импликация конъюнкции посылок и следствия окажется тождественно истинной, то рассуждения логически правильны. «Если D не видел днём в кино C, то либо C - прогульщик, либо D лжёт. Если C не прогульщик, то D не встречал C днём в кино, и сеанс был вечерним. Если сеанс был вечерним, то либо C - заядлый прогульщик, либо D лжёт. Следовательно, C - прогульщик». Задание 5 Определите, сколько корней имеет уравнение: ((^х ^ у) ^ (z л t л и)) л (^ (^х д^у) ^ - (z л t л и)) л (-z^x) = 1. Совет. С целью экономии времени при выполнении тождественных преобразований можно воспользоваться приведёнными в § 3 соглашениями и записать выражение, опустив знаки конъюнкции и заменив знак «-» чертой над высказыванием. Задание 6 Решите логическую задачу. Семья, где пятеро детей (Л, В - сыновья; C, D, E - дочери), купила телевизор. Условились, что в первый вечер будут смотреть передачи в таком порядке: - когда Л смотрит передачу, его брат В делает то же; - сёстры D и E, обе или одна из них, смотрят передачу; - из двух членов семьи - брата В и сестры С - смотрит передачу один и только один; - сёстры C и D или обе смотрят, или обе не смотрят; - если Е смотрит передачу, то её брат Л и сестра D делают то же. Кто из членов семьи в этот вечер смотрит передачу? 120 Итоговая проверочная работа Задание 1 а) Постройте логическую таблицу функции: X ^ у + x о x^y. б) Упростите формулу: X + у ^ z + x^y. в) Решите логическую задачу с помощью составления логической формулы. Начинающие ботаники увидели в саду незнакомое растение и принялись спорить: - Это флокс и, когда вырастет, зацветёт розовыми цветами, у нас в саду точно такой же, - сказала Катя. - Нет. Это колокольчик, он будет цвести лиловыми цветами, - возразила Настя. - Это сорняк у вас, и цветы у него точно не розовые, - сказал Дима. Определите, не дожидаясь цветения, что это за растение и как будет цвести, если мама Насти, слушая спорщиков, заметила, что в своих предположениях каждый ошибся наполовину. Задание 2 а) Упростите формулу до одной логической операции: X ^ у + X о Х^у + x^z + X. б) Пусть каждый из трёх членов комитета голосует «за», нажимая на кнопку. Решение считается принятым, если «за» проголосовало не менее двух человек. Запишите логическую функцию, соответствующую условию задачи. в) Выясните, являются ли следующие рассуждения логически правильными. Для этого представьте каждое предположение в виде логической формулы и проверьте, является ли заключение логическим следствием их конъюнкции. «Если Фёдор - лыжник, то он обладает отменным здоровьем. Фёдор -лыжник. Следовательно, Фёдор обладает отменным здоровьем». Задание 3 а) Упростите формулу до двух логических операций: Л*(Л^Б)*(ЛоС*Б)*(Л + B + C^A*B). б) Найдите наименьшее натуральное значение x, при котором ложно высказывание: (x^x > 60) ^ ((x + 1)^(x + 1) < 60). в) Укажите значения переменных, при которых данное высказывание (у + x) ^ (z + t + x) ложно. § 6. Способ упрощения логической функции с помощью карт Карно 121 § 6. Способ упрощения логической функции с помощью карт Карно ПОСТАНОВКА ПРОБЛЕМЫ УРОКА Представьте себе критическую ситуацию: задание в контрольной работе (или на экзамене, или при написании сложного условия в программе) требует от вас упростить логическое выражение, а вы не помните формул, по которым нужно произвести тождественные преобразования. • Какую проблему вы видите в этой ситуации? Сформулируйте основной вопрос урока. Сравните свой вариант с авторским (с. 1 91 учебника). НЕОБХОДИМЫЕ БАЗОВЫЕ ЗНАНИЯ Вспомните, как выглядят таблицы истинности основных логических операций. (§ 1) Как определяется порядок действий в логическом выражении? (§ 2) Вспомните правила склеивания (исключения) и поглощения. (§ 3) Вспомните, как строится логическая формула по таблице истинности. (§ 3) РЕШЕНИЕ ПРОБЛЕМЫ Так как значение формулы алгебры логики полностью зависит от значений входящих в эту формулу переменных, то формула алгебры логики является функцией входящих в неё переменных. Логической функцией n переменных у = f(x1, x2, _, xn) называется такая функция, у которой все переменные и сама функция могут принимать только два значения: 0 и 1. Вспомните, что переменными в логической функции обозначаются высказывания. Пример Требуется упростить логическую функцию, имеющую вид: L(x, у, z) = x л у л z V -x л у л z V x л-у л z + x л у л -Z. Перепишем её, как мы делали это раньше, в более компактной форме (знак конъюнкции при этом опустим): L(x, у, z) = xyz + Xyz + xyz + xyZ. Сначала упростим эту формулу путём равносильных преобразований, используя известные соотношения: добавим с помощью дизъюнкции ещё две 122 Модуль 2. Знакомство с математической логикой конъюнкции xyz (используем закон идемпотентности: x + x = x) и скомпонуем слагаемые: L = (xyz + Xyz) + (xyz + xyz) + (xyz + xyZ), L = z (xy + xy) + x (yz + yz) + y (xz + xz). Используя закон склеивания (xy + xy = x), получим: L = yz + xz + xy, или (1) L = z (x + y) + xy. (2) Основными действиями для преобразований, приводящих к упрощению, являются склеивание (исключение) и поглощение. После проведённого конечного числа преобразований мы получаем функцию, не поддающуюся дальнейшему упрощению (минимизации). Такую форму функции называют тупиковой. Логическая функция может иметь несколько тупиковых форм (например, формы (1) и (2) - тупиковые). Этот способ минимизации функций алгебры логики требует определённого навыка и часто больших усилий. • Подумайте, как доказать, что различные тупиковые формы, являющиеся результатом минимизации функции алгебры логики, равносильны. В ситуации, когда не стоит вопрос о демонстрации умения проводить равносильные преобразования; в условиях теста; при решении логических задач, где часто перед анализом логической функции, составленной по условию задачи, требуется её упростить, - во многих случаях есть желание облегчить процесс нахождения склеивающихся наборов переменных. Существуют методы, облегчающие процесс минимизации функций алгебры логики, автоматизирующие этот процесс. Среди них графический метод минимизации с помощью карт Карно представляется наиболее простым. Он основан на автоматизации нахождения склеивающихся наборов. Рассмотрим пример функции трёх логических переменных: f (а, b, с). Составим для наборов значений логических переменных конъюнкции переменных, как мы это делали раньше: a b c 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 а b с аЬс аЬс аЬс аЬс аЬс аЬс аЬс § 6. Способ упрощения логической функции с помощью карт Карно 123 • Вспомните, по какому принципу образованы конъюнкции для каждого набора значений переменных. Карта Карно - это таблица, имеющая ячейки для всех возможных конъюнкций переменных логической функции. Комбинации значений переменных расположены в заголовках строк и столбцов таблицы. Обратите внимание, что стоящие в соседних строках или столбцах комбинации значений истинности должны отличаться друг от друга только одной позицией: 0 0, 0 1, 1 1, 1 0. Карта Карно для функции трёх переменных строится следующим образом. Рассмотрим таблицу: b 0 0 0 1 1 1 1 0 c 0 abc abc abc abc 1 abc abc abc abc Видно, что в каждой ячейке таблицы записана конъюнкция переменных, соответствующих значениям в заголовках строки и столбца. В карту Карно вместо конъюнкций записываются значения функции на соответствующих наборах значений переменных. • Вы заметили, что для переменных a и Ъ нарушен порядок перебора их значений истинности, принятый для таблиц истинности? Какое правило построения карт Карно будет нарушено, если порядок перебора значений будет такой, к которому вы привыкли: 0 0, 0 1, 1 0, 1 1? Склеивание осуществляется между конъюнкциями, для которых функция имеет значение 1, записанными в соседние ячейки карты. 1. «Склеить» означает объединить ячейки. Фигура, которая получается при объединении, - прямоугольник или квадрат. 2. «Склеиваться» (объединяться) могут ячейки в количестве, кратном 2^-*, где i = 1,2,_, n - 1 (n - количество переменных в формуле). Причём при склеивании двух ячеек исключается одна переменная, при склеивании четырёх - две и т. д. Теперь, когда мы знаем правила, попробуем «склеить» наборы переменных. 124 Модуль 2. Знакомство с математической логикой Пример Функция f (x, y, z) задана следующей таблицей истинности: x у z fix, у, z) 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 Соответствующая ей карта Карно: x у z 0 0 0 1 1 1 1 0 0 0 ; 1 1 1 0 1 ; 1 ; 1 1 ; 1; Объединяем прямоугольниками соседние ячейки таблицы, содержащие 1 (прямоугольники могут перекрываться). Для каждой фигуры определяем неизменяющиеся в пределах данной комбинации переменные и записываем их конъюнкцию. Для всех ячеек квадрата это у, для всех единиц прямоугольника - z. Если неизменяющееся значение - это 1, то переменная входит в конъюнкцию без отрицания, иначе - с отрицанием. Результирующая функция представляет собой дизъюнкцию этих конъюнкций. Для нашего примера: f (x, у, z) = у + z. Соседними считаются также ячейки верхнего и нижнего рядов, крайние слева и справа (примеры 1-3). Пример 1 \ x у z 0 0 0 1 1 1 1 0 0 1 : 0 0 1 1 ^ 1 : 0 0 1 f(x, у, z) = у § 6. Способ упрощения логической функции с помощью карт Карно 125 Пример 2 у z t 0 0 0 1 1 1 1 0 0 0 ' ' 1 : 0 0 1 1 0 1 0 0 0 0 1 1 0 0 0 0 1 0 " л С •. 1 i ■ 0 0 ! 1 f(x, у, z, t) = y t Пример 3 X у z t 0 0 к к 0 1 1 1 к к 1 0 0 0 А А 11 1 0 л А 1 1 1 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 i 1 1 0 : 1 ! 0 f(x, y, z, t) = x y t + x y t Примечание. В данном случае получилась форма, которая может быть улучшена: f(x, у, z, t) = t (x y + xy). Порядок минимизации функции с помощью карт Карно: 1. Получить таблицу истинности функции. 2. Нарисовать карту Карно с пустыми ячейками. 3. Следуя таблице истинности, заполнить карту значениями функции. Так как нас интересуют только значения функции, равные 1, нули можно не писать, чтобы не перегружать таблицу. 4. Определить прямоугольники, объединяющие ячейки, содержащие 1. 5. Для каждой фигуры определить переменные, которые не меняют своих значений внутри неё, и записать их конъюнкцию (без отрицания или с отрицанием переменных в зависимости от их значений). 6. Результирующая функция получается после логического сложения (дизъюнкции) найденных конъюнкций. • Почему важно, чтобы в одну фигуру было объединено возможно большее количество единиц? 126 Модуль 2. Знакомство с математической логикой Рассмотрим два примера нахождения по готовой карте Карно логической функции по следующему правилу: 1. Найти все объединения единиц (на рисунках в примерах 4 и 5 они обозначены фигурами разного цвета). 2. Найти конъюнкции неизменяющихся в пределах каждого объединения переменных (без отрицания или с отрицанием) и записать их логическую сумму. Пример 4 f[x, у, z) = ху + XZ + zy Пример 5 X y z t 0 0 0 1 1 1 1 0 0 0 hi 1 (1l 0 1 1 1 1 1 1 1 1 0 1 (1 Цвет заливки Переменные, не меняющиеся в пределах фигуры Конъюнкция переменных y, t ~yt x, y, t x y t x, y, z x y z 1 x, y, z x y z Полученная с помощью карты Карно функция имеет следующий вид: f (x, y, z, t) = xyz + xyz + yt + xyt. § 6. Способ упрощения логической функции с помощью карт Карно 127 На примере видно, что минимизация функции четырёх переменных принципиально ничем не отличается от подробно рассмотренной минимизации функции трёх переменных. Следует заметить, что при определении фигур, содержащих 1, нужно стремиться, чтобы площадь каждой фигуры была максимальной (от этого зависит степень упрощения функции). ОБОБЩЕНИЕ НОВЫХ ЗНАНИЙ Карта Карно - это таблица, имеющая ячейки для всех возможных конъюнкций переменных логической функции. Комбинации значений переменных расположены в заголовках строк и столбцов таблицы. В ячейках расположены значения функции. Стоящие в соседних строках или столбцах комбинации значений истинности должны отличаться друг от друга только одной позицией: 0 0, 0 1, 1 1, 1 0. Графический метод минимизации функций алгебры логики с помощью карт Карно основан на автоматизации нахождения склеивающихся наборов. Операции по минимизации функции с помощью карт Карно: объединение прямоугольниками соседних ячеек таблицы, содержащих 1; определение для каждой фигуры неизменяющихся в пределах данной комбинации переменных (без отрицания или с отрицанием) и запись их конъюнкции: запись дизъюнкции этих конъюнкций. При склеивании двух ячеек исключается одна переменная, при склеивании четырёх - две и т. д. ПРИМЕНЕНИЕЗНАНИЙ 1. Упростите функцию алгебры логики с помощью карты Карно: а) a( a ^ b)(a о cb)(a + b + c ^ ab), причём упрощённый вид должен содержать не более трёх логических операций; б) xy ^ (z + x); в) (x y)(y ^ z); г) a о b + c ^ ab + a. 2. Найдите тупиковые формы функций f1(a, b, c,), f2(a, b, c,), f3(a, b, c) по таблицам истинности: a b c 0 0 0 0 1 0 0 0 1 1 1 1 0 1 0 1 0 1 0 1 1 0 0 1 1 0 0 0 1 0 1 0 1 1 1 0 1 1 0 1 0 1 1 1 1 0 1 1 128 Модуль 2. Знакомство с математической логикой § 7. Представление логической формулы в виде релейно-контактной схемы ПОСТАНОВКА ПРОБЛЕМЫ УРОКА В электротехнических устройствах применяют электрические релейно-контактные схемы, содержащие большое количество переключателей. Релейно-контактные схемы широко используются в технике автоматического управления и в вычислительной технике. Эти схемы называются также переключательными. Каждый переключатель может находиться в одном из двух состояний: при одном переключатель проводит ток, при другом — нет. Поэтому одному состоянию переключателя можно поставить в соответствие 1, а другому — 0. • Как вы считаете, на что по своему «поведению» похожи переключатели? Можно ли применить полученные вами знания по алгебре логики для ответа на этот вопрос? Сформулируйте основной вопрос урока. Сравните свой вариант с авторским (с. 1 9l учебника). РЕШЕНИЕ ПРОБЛЕМЫ Релейно-контактные схемы (переключательные схемы) широко используются в электронно-вычислительной технике. Под переключательной схемой понимают некоторое устройство, в состав которого могут входить следующие элементы: • переключатели (различные реле, полупроводниковые приборы, выключатели и т. п.); • проводники, их соединяющие; • входы (вход) в схему и выход из неё. Это полюса схемы. В начале XX века релейно-контактные схемы, широко применяющиеся в системах автоматики и связи, становятся настолько сложными, что требуют для конструирования новых подходов. Таким новым, очень важным для развития и науки, и техники стал подход соединения логики и техники. В 1910 году физик Павел Сигизмундович Эренфест (Пауль Эренфест, 1880-1933) указал на возможность описания релейно-контактных схем с помощью алгебры логики. По прошествии почти тридцати лет после работ Эренфеста сначала Виктор Иванович Шестаков (1907-1987) и чуть позже Клод Элвуд Шеннон (1916-2001) разработали метод расчёта сложных электрических сетей с применением аппарата алгебры логики. Каждой схеме можно поставить в соответствие некоторую формулу алгебры логики, описывающую эту схему. Упростив логическую формулу, мы получим решение для упрощения релейно-контактной схемы. § 7. Представление логической формулы в виде релейно-контактной схемы 129 Рассмотрим представление в виде релейно-контактных схем основных логических операций. Вы знаете, что все логические связки могут быть представлены с помощью трёх базовых связок (конъюнкции, дизъюнкции и инверсии). Пусть X и Y - некие переключатели (реле). Сопоставим в логической формуле этим переключателям переменные х и у. A и B - полюса схемы: Операция f[x, у) Релейно-контактная схема Инверсия х Если переключатель X замкнут, то через него ток идёт (логическая переменная х = 1), и если разомкнут, то тока нет ( логическая переменная х = 0). Существует и такой переключатель X, который разомкнут, когда замкнут переключатель X, и наоборот Конъюнкция х & у Л О X Y О В Дизъюнкция х V у — X — Тождественно истинная формула 1 qb Ток в цепи всегда есть Тождественно ложная формула 0 ^ Ключ разомкнут. ^ Ов Разрыв цепи. Тока нет • Если в схеме последовательно расположены два выключателя, каково условие существования тока в этой цепи? Поясните, почему конъюнкция выражается последовательно соединёнными переключателями. • Как надо соединить лампочки в цепь, чтобы при порче одной лампочки остальные продолжали гореть? Поясните, почему дизъюнкция выражается параллельно соединёнными переключателями. Применив полученные схемы к логической формуле, записанной в нормальной форме, согласно приоритету операций, можно изобразить эту формулу графически в виде релейно-контактной схемы. Часто бывает необходимо минимизировать релейно-контактную схему, то есть уменьшить количество элементов в ней или количество связей. Для этого надо представить релейно-контактную схему в виде логической формулы, минимизировать логическую формулу, тем самым упростить схему. 130 Модуль 2. Знакомство с математической логикой Пример 1 Требуется построить релейно-контактную схему для следующих функций. 1. f[x, у, z) = x + y ^ (z + y). Переведём функцию в нормальную форму: f (x, у, z) = у + z. Построим для неё схему: — У - A B 2. f(x, у, z) = (x^y) (y^z). Переведём функцию в нормальную форму: f (x, y, z) = x y + xz + yz = x (y + z) + yz. Построим схему: - y --------- z - Ai y B — z — Пример 2 Задача: построить по возможности наиболее простую релейно-контактную схему для голосования трёх членов жюри, через которую ток будет проходить тогда и только тогда, когда не менее двух членов жюри нажимают кнопку (голосуют «за»). Определим вид логической функции, которая удовлетворяет условию задачи, для этого построим таблицу истинности и карту Карно. Затем построим по функции переключательную схему. a b c f 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 \a b c 0 0 0 1 1 1 1 0 0 } 1 j 1 -JiiL 1 i f(a, b, с) = ab + bc + ac = a(b + c) + bc — b ----------------------------- c - A> b B x a c § 7. Представление логической формулы в виде релейно-контактной схемы 131 Пример 3. По виду релейно-контактной схемы определить вид логической функции. b ^ —OB b —‘ Определим все возможные пути от полюса А к полюсу В и запишем дизъюнкцию этих конъюнкций: f (а, b, с) = ab + bb + abc. Упростив, получим: f (а, b, с) = b (а + с). ОБОБЩЕНИЕ НОВЫХ ЗНАНИЙ Релейно-контактные схемы (переключательные схемы) широко используются в электронно-вычислительной технике. Каждой схеме можно поставить в соответствие некоторую формулу алгебры логики, описывающую эту схему. Упростив логическую формулу, мы получим решение для упрощения релейно-контактной схемы. ПРИМЕНЕНИЕ ЗНАНИЙ 1. Постройте релейно-контактную схему для сети, в которой два различных выключателя независимо друг от друга способны изменять состояние сети (проще говоря, включать и выключать одну лампочку). 2. Упростите функцию f (а, b, с) = а (а ^ b)(a о с b)(a + b + с ^ а b). Постройте для упрощённой функции релейно-контактную схему. 3. Постройте релейно-контактную схему для функции: f (x, у, z) = (x ^ y о z + x) y + z ^ x. a b 132 Модуль 2. Знакомство с математической логикой 4. Постройте релейно-контактную схему для функции, заданной таблицей истинности. x у z f 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 0 1 1 1 1 5. Упростите релейно-контактную схему. § 8. Логические элементы в компьютере. Логический базис 133 § 8. Логические элементы в компьютере. Логический базис ПОСТАНОВКА ПРОБЛЕМЫ УРОКА На прошлом уроке вы познакомились с применением математической логики для конструирования, упрощения и анализа работы электрических сетей, состоящих из реле (переключателей). Основные логические операции конъюнкция, дизъюнкция, отрицание в таких схемах изображались с помощью последовательного (конъюнкция) или параллельного (дизъюнкция) соединения переключателей. Теперь пришла очередь познакомиться, как реализуются в компьютере логические операции. • Как вы считаете, можно ли с помощью основных логических операций описать работу устройств компьютера? Сформулируйте основной вопрос урока. Сравните свой вариант с авторским (с. 1 92 учебника). НЕОБХОДИМЫЕ БАЗОВЫЕ ЗНАНИЯ Вспомните законы алгебры логики. Вспомните, в каком порядке выполняются логические операции. РЕШЕНИЕ ПРОБЛЕМЫ Логический элемент - это устройство, предназначенное для обработки информации в цифровой форме. Логический элемент компьютера - это часть электронной схемы, которая реализует элементарную логическую операцию, например конъюнкцию, дизъюнкцию, инверсию. Логическими элементами компьютера являются электронные схемы И, ИЛИ, НЕ, И-НЕ, ИЛИ-НЕ и другие, называемые также вентилями. С помощью этих схем, соединённых в определённом для данной функции порядке, можно реализовать любую логическую функцию, описывающую работу устройства. Обычно у вентилей бывает от двух до восьми входов и один или два выхода. Нулю и единице на входах и выходах вентилей соответствуют разные уровни напряжения. Более высокий обычно соответствует 1, более низкий - 0. На схеме каждый логический элемент представляется графически, в виде прямоугольника с соответствующей маркировкой, без указания электронной схемы, которая реализует обозначенную им функцию. Представьте, что эта схема спрятана в «коробочке», на которой стоит соответствующая ей маркировка. 134 Модуль 2. Знакомство с математической логикой Так обозначаются логические элементы: Схема И [конъюнкция] Схема ИЛИ [дизъюнкция] Схема НЕ [инверсия] Набор логических функций, позволяющий реализовать любую функцию, называется логическим базисом. Так логические функции НЕ, И, ИЛИ являются базисом. Этот базис называется стандартным. Пусть X и у - переменные логической функции, принимающие значения 0 и 1, которыми кодируют низкий и высокий уровни напряжения. Эти сигналы [импульсы] подаются на входы схемы. Количество входов логической схемы равно количеству переменных логической функции. На выходе получается результат работы логической функции. Чтобы построить логическую схему, необходимо: 1 ] если функция не записана в нормальной форме, перевести функцию в нормальную форму; 2] следуя приоритету логических операций, соединить логические элементы согласно формуле. Пример Требуется построить логическую схему функции f [x, у] = x ^ у. Совершив равносильные преобразования, получим функцию в нормальной форме: f[x, у] = X + у. Сначала выполняется операция инверсии, а потом - дизъюнкции. Y X Y 0- X X + Y Функции НЕ, И, ИЛИ не являются минимальными, так как сами могут быть выражены через другие функции. • Какую логическую функцию, через которую могут быть выражены функции НЕ, И, ИЛИ, вы знаете? 1 § 8. Логические элементы в компьютере. Логический базис 135 Кроме функции штрих Шеффера, реализующей операцию И-НЕ, существует ещё одна функция - стрелка Пирса, тоже являющаяся минимальной: через неё могут быть выражены основные логические операции, следовательно, и все другие. Штрих Шеффера (|] Стрелка Пирса (^] a b f a b f 0 0 1 0 0 1 0 1 1 0 1 0 1 0 1 1 0 0 1 1 0 1 1 0 • Подумайте, как основные логические операции можно реализовать через стрелку Пирса. Базисы И-НЕ, ИЛИ-НЕ Оказывается, что можно представить функции НЕ, И, ИЛИ в базисах И-НЕ и ИЛИ-НЕ, которые являются минимальными, значит, в этих базисах можно реализовать любую логическую функцию. Покажем это. Базис «И-НЕ» Логический элемент И-НЕ изображается так: И Y = Y-X^ Y-X X Y ИЛИ X + Y = X • X • Y • Y X- Y О 136 Модуль 2. Знакомство с математической логикой Базис «ИЛИ-НЕ» Вид логического элемента ИЛИ-НЕ: Итак, мы показали, что возможно представить функции И, НЕ, ИЛИ в базисах, которые являются минимальными (И-НЕ, ИЛИ-НЕ), а значит, и любую другую логическую функцию мы можем представить в минимальном базисе. • Какое преимущество имеет логическая схема, реализованная в базисах И-НЕ, ИЛИ-НЕ, по сравнению с представлением в стандартном базисе? • Какой недостаток у представления логической функции в базисах И-НЕ, ИЛИ-НЕ? § 8. Логические элементы в компьютере. Логический базис 137 ОБОБЩЕНИЕ НОВЫХ ЗНАНИЙ Логический элемент компьютера - это часть электронной схемы, которая реализует элементарную логическую операцию, например конъюнкцию, дизъюнкцию, инверсию. С помощью этих схем можно реализовать любую логическую функцию, описывающую работу устройства. Набор логических функций, позволяющий реализовать любую функцию, называется логическим базисом. Базис НЕ, И, ИЛИ называется стандартным. Минимальные базисы: И-НЕ, ИЛИ-НЕ. ПРИМЕНЕНИЕ ЗНАНИЙ 1. Представьте функцию f[x, у, z) = yz + x ^ zx: а) в стандартном базисе; б) в базисе И-НЕ; в) в базисе ИЛИ-НЕ. 2. Нарисуйте логическую схему функции в стандартном базисе: а) f[x, у, z) = [x ^ у о z + X)y + z ^ X - x; б) f[x, у, z) = yz + x ^ zx; в) f[x, y, z) = x ^ у ^ z + xy. 138 Модуль 2. Знакомство с математической логикой § 9-10. Логические элементы в компьютере. Сумматор. Триггер ПОСТАНОВКА ПРОБЛЕМЫ УРОКА В состав компьютера входит множество элементов, реализующих различные функции. Арифметико-логическое устройство (АЛУ) (англ. Arithmetic Logic Unit, ALU) - блок процессора, который служит для выполнения арифметических и логических преобразований. Важной частью этого блока служит сумматор - устройство, в котором происходит поразрядное суммирование двоичных чисел. Память — важная часть компьютера. Поскольку единица измерения информации -1 бит, необходимо устройство, способное хранить 1 бит информации. Это устройство — триггер. Триггер — электронная схема, применяемая в регистрах компьютера для запоминания одного разряда двоичного кода. Вы знаете, что можно построить логическую функцию, которая будет «выполнять все желания» — давать нужный результат в зависимости от значений входящих в неё переменных. • Как вы считаете, можно ли с помощью основных логических операций описать работу устройств компьютера? Сформулируйте основной вопрос урока. Сравните свой вариант с авторским (с. 1 92 учебника). НЕОБХОДИМЫЕ БАЗОВЫЕ ЗНАНИЯ Вспомните таблицы истинности и обозначения на логической схеме функций НЕ, И, ИЛИ, И-НЕ, ИЛИ-НЕ. РЕШЕНИЕ ПРОБЛЕМЫ Какие арифметические действия можно заменить суммированием? Сумматор Сумматор - это электронная логическая схема, выполняющая суммирование двоичных чисел. Сумматор - центральный узел арифметико-логического устройства (АЛУ) компьютера, находит применение и в других устройствах компьютера. Многоразрядный сумматор, предназначенный для сложения многоразрядных двоичных чисел, состоит из одноразрядных сумматоров. Суммирование чисел происходит поразрядно с учётом единицы переноса из предыдущего разряда. § 9-10. Логические элементы в компьютере. Сумматор. Триггер 139 На схеме сумматор изображается так: pi -1 Bi А рвых S Ь. i В 1 Обозначения: A, B - складываемые числа, S - сумма, - цифра числа А в разряде /; - цифра числа B в разряде i; - цифра переноса в следующий разряд, р- ^ - цифра переноса из разряда i - 1 в разряд i; з- - цифра, получающаяся в разряде i после сложения. Работа одноразрядного сумматора может быть описана следующей таблицей истинности: входы выходы b Р;-1 Р; 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 1 0 1 0 0 0 1 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 Логическая схема сумматора, реализующая таблицу истинности: Р 140 Модуль 2. Знакомство с математической логикой • Назовите типы логических элементов на схеме. • В каком базисе реализована схема? • Для различных наборов таблицы проверьте работу логической схемы. При сложении двоичных чисел длиной более одного бита используют последовательное соединение таких сумматоров, причём выход переноса предыдущего сумматора (р-) является входом для следующего (p^+^J- I i+i Триггер Триггер (англ. trigger) - это устройство, способное длительное время находиться в одном из двух состояний. В одном состоянии на выходе триггера - 0, в другом - 1. Триггер запоминает эти значения. Если на один из входов триггера подать цифровой сигнал 1, что соответствует высокому напряжению, то состояние триггера практически мгновенно может измениться и до следующего сигнала он будет хранить это значение. Рассмотрим самый простой триггер - RS-триггер (reset-set), построенный на двух вентилях ИЛИ-НЕ: вход S вход R Q выход Q Примечание. Хотя выходов два: Q и Q, сигнал получает на выходе Q. Какие случаи могут возникнуть при работе устройства? 1. Начальное состояние Q = 0. Подаётся сигнал на вход S : S = 1, а R = 0. § 9-10. Логические элементы в компьютере. Сумматор. Триггер 141 вход S=1 С вход R =0 Q выход Q = 0 ^ Q = 1: установка 1 2. Начальное состояние Q = 1. Подаётся сигнал на вход S: S = 1; а R = 0. вход S=1 вход R =0 Q выход Q = 1: состояние не меняется; запись 1 3. Начальное состояние Q = 0. Подаётся сигнал на вход R: R = 1, а S = 0. вход S = 0 0 вход R = 1 Q выход Q = 0: состояние не меняется; запись 0 4. Начальное состояние Q = 1. Подаётся сигнал на вход R: R = 1, а S = 0. вход S = 0 0 вход R = 1 Q выход Q = 0: установка 0 142 Модуль 2. Знакомство с математической логикой Одновременная подача сигнала на оба входа этого триггера: S = 1 и R = 1 запрещена, так как возникает неопределенность; триггер может принять любое из устойчивых состояний. Кратко рассмотренные случаи могут быть описаны в таблице: Входы Выход Q R S до подачи сигнала после подачи сигнала 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 0 1 1 - - 1 1 - - Пояснение Хранение информации, значение Q не меняется Состояние Q меняется: установка 1 Состояние Q не меняется: запись 1 Состояние Q не меняется: запись 0 Состояние Q меняется: установка 0 Запрещено ОБОБЩЕНИЕ НОВЫХ ЗНАНИЙ Триггер - устройство, способное длительное время находиться в одном из двух устойчивых состояний 0 и 1. Триггер хранит эти значения. Сумматор - это электронная логическая схема, выполняющая суммирование двоичных чисел. Многоразрядный сумматор, предназначенный для сложения многоразрядных двоичных чисел, состоит из одноразрядных сумматоров. ПРИМЕНЕНИЕ ЗНАНИЙ 1. Сложите числа А = 112 и В = 1012. Сколько одноразрядных сумматоров потребуется для сложения? Нарисуйте, используя изображение сумматора и принятые обозначения, схему этого сложения. 2. Сколько триггеров необходимо для запоминания 1 байта? Посчитайте, сколько триггеров нужно для запоминания мегабайта. 143 Проверь себя Задание 1 Упростите функцию с помощью карты Карно: f (а, b, с) = bC + ab c + abc. Задание 2 Упростите релейно-контактную схему: Л — b ^b — Задание 3 Постройте логическую схему функции f (а, b) = (а ^ b +а) ^ b: а) в стандартном базисе; б) в базисе И-НЕ. -^08 а b а 144 ПРИМЕНЕНИЕ ЗНАНИЙ [необходимый уровень) Задание 1 Упростите функцию с помощью карты Карно: а) (х + xy); б) х^ (Х ^ (у ^ ху)); в) у о (Х ^ ху); г) х ^ у о х ^ ху; д) х ^ у + х о ху. Задание 2 Найдите тупиковую форму функции: a) a b f 0 0 1 0 1 1 1 0 0 1 1 1 б) a b f 0 0 1 0 1 0 1 0 1 1 1 1 Задание 3 Упростите релейно-контактную схему: a) __a____ б) А a — b -b —О B А О -OB А —x — у — г) x 1 —у— -OB ^^x — L у —x — — у — x 1 — ^—OB Задание 4 Постройте логическую схему функции в стандартном базисе: а) a ^ b; б) a о b; в) a © b; г) х о х + у ^ ху. b a a a 145 ПРИМЕНЕНИЕ ЗНАНИЙ [повышенный уровень) Задание 1 Упростите функцию с помощью карты Карно: а) (а ^ b) + (ас) о ас; б) xy о (х + у ^ xy); в) Х ^ у о х + у ^ ху; г) xyz + ху + z + Хуz + Xyz. Задание 2 Упростите релейно-контактную схему: a) — а — О б) B а------b b — a - b — B -О в) Or b — — с —1 — а — — а — B -О --- b О Задание 3 Определите, верный ли сделан вывод из приведённых суждений. Для этого нужно проверить, является ли вывод логическим следствием конъюнкции высказываний. «Прямые а и b или параллельны, или пересекаются, или скрещиваются. Если прямые а и b лежат в одной плоскости, то они не скрещиваются. Прямые а и b лежат в одной плоскости и не пересекаются, следовательно, они параллельны». Задание 4 Постройте логическую схему функции f(a, b, c) = (а о b + c) (а + b ^ с): а) в стандартном базисе; б) в базисе И-НЕ; в) в базисе ИЛИ-НЕ. b b а а а а с 146 Модуль 2. Знакомство с математической логикой ПРИМЕНЕНИЕ ЗНАНИЙ [максимальный уровень) Задание 1 Упростите функцию с помощью карты Карно: а) X + yzо x + yz; б) X + ('yZ + Z) X; в) X о (у + X ^ z) ^ Задание 2 Упростите релейно-контактную схему: a) Z Z у — ---Z -о B -у- б) — a — b — c — — ^ — b — c — ^ ^ —OB — a — b — с — — a — b — c — в) AO- b OB Задание 3 Упростите функцию f(a, b, c) = a ^ bc о bc ^ a. Постройте логическую схему: а) в стандартном базисе; б) в базисе И-НЕ; в) в базисе ИЛИ-НЕ. a c a с b c Задание 4 Равносильны ли переключательные схемы? э] — a — b - О- -c ----a b ---с ■О б] О—b - 147 О- b a —1 — b — -о о—b - — a —^ — c — в] О- a--b — с — — b — b-- с О О- b --- с -О с a b c с 148 Модуль 2. Знакомство с математической логикой Итоговая проверочная работа Задание 1 а) Представьте функцию в нормальной форме, используя карту Карно: f(x, у) = x + у ^ xy ^ x + у. б) Упростите переключательную схему. — a ---- b — СУ -О в) Поотройте логическую схему функции в стандартном базисе: f (x, у) = xy ^ xy ^ x + у. Задание 2 а) Представьте функцию в нормальной форме, используя карту Карно: f (x, у) = x + у о xy ^ x ^ у. б) Упростите переключательную схему. ---b -b — b —c — -О в) Поотройте логическую схему функции в базисе И-НЕ: f (x, у) = x + у ^ x о у. с a b с a c 149 Задание 3 а) Представьте функцию в нормальной форме, используя карту Карно: f (x, у, z) = x ^ y ^ z ^ xz + y. б) Постройте переключательную схему для мажоритарной функции (функции голосования), следуя условиям: решение считается принятым, если за него проголосовали три человека из четырёх. в) Постройте логическую схему в базисе ИЛИ-НЕ: f (x, у) = Xy ^ x + у ^ Ху. г) Нарисуйте схему для сложения двоичных чисел: A = 111 и B = 111 и обозначьте значения на входах/выходах. д) Запишите логическую функцию, соответствующую схеме: a b 150 151 Модуль 3. Web-конструирование. Основы мастерства Этот модуль поможет вам: • научиться использовать слои для размещения данных на web-страницах; • познакомиться с возможностями оформления web-страниц с помощью скриптов; • публиковать web-страницы в Интернете и превращать их в chm-файлы. Для этого вам надо научиться: • пользоваться блоками
и описывать их оформление с помощью CSS; • вставлять на web-страницу готовые скрипты и отлаживать их работоспособность; • регистрироваться на бесплатном хостинге и публиковать файлы с помощью Менеджера сайтов в составе редактора Nvu; Л попиопосэтипа попсэи'тппплл l—ll-mC^nhm 152 Модуль 3. Web-конструирование. Основы мастерства Введение Количество web-страниц сегодня измеряется миллиардами, поэтому просто опубликовать свой сайт и ждать, пока его начнут посещать пользователи Интернета, достаточно наивно: этого просто может не произойти. За каждое посещение нужно бороться. Именно этим и занимаются многочисленные специалисты в области интернет-технологий. Тот, с кого начинается работа над новым интернет-проектом, - это заказчик: один человек, или группа заинтересованных людей, или фирма. Заказчику нужен сайт, и он обращается в web-студию - специальную компанию, занимающуюся разработкой сайтов. На основании требований заказчика составляется техническое задание и студия приступает к работе. Первым за дело берётся дизайнер. Его стихия - графические программы; с их помощью дизайнер создаёт эскизы будущих web-страниц. Как только эскизы готовы, их показывают заказчику и ждут утверждения. Следующим в работу включается верстальщик - человек, который превращает «картинку» в html-код. Следующий этап после вёрстки - внедрение системы управления. Ведь далеко не все, кому придётся редактировать данные на сайте, владеют HTML и CSS. Web-программисты создают специальную базу данных, в которой будет храниться вся информация (тексты, картинки, новости, рекламные объявления и пр.), а затем заставляют её транслироваться в нужных фрагментах web-страниц. Они же добавляют и некоторые интерактивные элементы: всплывающие подсказки, высвечивающиеся при наведении указателя мыши границы и т. п. Современные сайты уже давно перестали представлять собой совокупность статичных web-страниц, содержащих только текст, картинки и ссылки. Сплошь и рядом мы наблюдаем выпадающие меню, всплывающие подсказки, красочные рекламные объявления и т. п. Далее следует наполнение сайта, то есть занесение в базу данных всего, что необходимо. Этим могут заниматься уже те сотрудники, которые далеки от интернет-технологий, поскольку им будет помогать система управления - простая и интуитивно понятная. Процесс наполнения сайта и редактирования его содержимого называется также контент-менеджментом, а системы управления нередко упоминаются под аббревиатурой CMS (content management system - система управления контентом). На этом создание сайта завершается, о чём заказчик и web-студия подписывают соответствующий акт. После этого в игру вступают специалисты по раскрутке сайта, то есть привлечению посетителей. Среди методов раскрутки наиболее популярна реклама, а также поисковая оптимизация - редактирование текстов, размещённых на странице, в результате чего эта страница появляется в первых строках результатов поисковых запросов. В предыдущих модулях мы знакомились в основном с работой верстальщика: изучали HTML и CSS. Этот модуль также немного касается вёрстки, но затрагивает и вопросы web-программирования, и публикации своих проектов. § 1. Вёрстка с помощью блоков 153 § 1. Вёрстка с помощью блоков ПОСТАНОВКА ПРОБЛЕМЫ УРОКА 'ЩгЪ-д'изайнгр: Чтобы страница была действительно удобной и красивой, я буду размещать элементы (картинки, текст, ссылки) там, где считаю нужным, без привязки к таблицам. Например, мне нужно разместить картинку ровно посередине таблицы. Aenean felis ipsum, malesuada eget dictum eu placerat ut dolor. Nulla venenatis tellus vitae leo iaculis eu laoreet quam sollicitudin. Ut tempor semper mi in interdum. Mauris rhoncus, leo sed varius facilisis, mauris justo cursus purus, vitae accumsan libero velit sed tellus. Suspendisse ligula leo, blandit vel adipiscing ac, dapibus a eros. Vivamus erat sem, condimentum non hendrit at, rutrum vel eros. Phasellus elit diam, convallis ut ultricies sed, portittor in purus. Nullam interdum tincidunt leo, ac mattis orci sollicitudin id. Nullam sed nulla a purus porttitor elementum. In hac habitasse platea dictumst. Nullam egestas neque sed odio dignissim vitae gravida libero rutrum. Integer pulvinar varius volutpat. Ut blandit luctus magna, quis consectetur urna pretium luctus Vestibulum at suscipit turpis. Duis tempor tellus et lectus luctus dignissum. Nullam imperdiet magna sit amet velit placerat vitae molestie magna sodales. Phasellus aliquam molestie ornare. Fusce volutpat porta dui, eget ultrices tellus dignissim id. Etiam ornare risus et lacus tincidunt tempus. Donec neque neque, ornare ut placerat sed, ultricies in mi. Mauris nec turpis diam. Quisque et tellus sed libero egestas laoreet. Sed elementum adipiscing nisl. Donec tincidunt, felis at commodo scelerisque, augue lorem imperdiet mauris, pretium tempus ipsum diam et est. Vivamus porta, orci id auctor luctus, augue neque malesuada libero, at condimentum nisi ligula id nunc. Phasellus cursus moleste orci. Maecenas nisl nibh, auctor eu ultricies sed, pulvinar quis eros. Morbi elementum hendrerit dolor id scelerisque. Curabitur malesuada iaculis eros, non ultrices tortor tempus non. Верстальщик: Но ведь таблицы — это инструмент, который позволяет превратить созданный вами дизайн в html-документ, и без таблиц не обойтись! • Как вы считаете, кто из участников спора прав в большей степени? Почему? Возможен ли в такой ситуации компромисс? Сформулируйте основной вопрос урока. Сравните свою формулировку с авторской (с. 1 92 учебника). НЕОБХОДИМЫЕ БАЗОВЫЕ ЗНАНИЯ Как осуществлять вёрстку с помощью таблиц? (Учебник для 9-го класса, книга 1, модуль 1.) Что такое атрибут тега? Какие атрибуты вам известны? (Учебник для 9-го класса, книга 1, модуль 1.) Что такое внешние и внутренние стили? Как описывать внешние стили в css-файле? (Учебник для 9-го класса, книга 1, модуль 1.) РЕШЕНИЕ ПРОБЛЕМЫ Использование таблиц для верстки web-страниц имеет ряд неоспоримых преимуществ, среди которых: • простота; • наглядность структуры: есть «большая», главная таблица, есть более мелкие таблицы, размещённые в ячейках «большой» (см. учебник для 9-го класса, книга 1, модуль 1, § 3); 154 Модуль 3. Web-конструирование. Основы мастерства • наследование принципов оформления: если в стиле «большой» таблицы указать, например, определённое начертание шрифта, оно будет распространяться и на всё более мелкие таблицы, и его не нужно указывать заново. Однако у табличной вёрстки есть и недостатки: • большой объём html-кода (слишком много тегов , , и пр.); • зависимость позиционирования более младших таблиц от более старших: например, если уменьшить ширину ячейки «большой» таблицы, автоматически уменьшатся и все таблицы, расположенные внутри данной ячейки; • невозможность «наложения» одних элементов web-страницы на другие: закончилась одна ячейка, началась другая, и никак по-другому. Последний недостаток ощущается особенно остро в тех случаях, когда необходимо использовать много маленьких блоков (текстовых или графических) в разных местах страницы. Посмотрите на одну из страниц сайта «Естествознание» (рис. 3.1). Рис. 3.1. Страница сайта «Естествознание» § 1. Вёрстка с помощью блоков 155 Мы видим множество картинок, которые являются основой оформления этой страницы. Те, которые расположены слева (два сосуда), можно разместить в ячейках «большой» таблицы. Но для тех, которые справа, это проблематично: некоторые из них слишком далеко, некоторые - слишком близко. Введение для каждой из них новой таблицы значительно увеличило бы код и усложнило структуру html-документа. Кроме того, некоторые изображения должны «заползать» за границы ячеек таблицы, в которых расположен текст (рис. 3.2). Статьи, видеоу^оки и подкасты / "Естествозчэние" -Windows Ir^ernet Explorer • ' ! ♦! I ,1. ' 1 funm ^ Избранное ^ Яндекс Q Почт^ ^ Карт^ ^ Маркез ^ Новости ^ Сповар^^ Виде^ ^ Музыка ^ Дис^ ^ °мендуем“е у * Коллек и. -б- ф,Г.,„ • Q . « • Страни а Еезопа^о^^ Сервис ' Поиск простейшей формулы по массовым долям элементов Решаем две задачи на вывод формулы вещества, если известны массовые доли образующих его химических элементов Моль: простой и удобный Количество вещества и его единица - моль. Для чего нужны м^ 1? Как перевести моли в граммы? Серия "Элементы и соединения" Из чего состоят атомы Какие частицы находятся внутри атома? Как они расположены? Что такое химический элемент? Что Несколько слов о химических связях Ш Неорганические соединения. Оксиды Какими бывают неорганические соединения? Кто придумывает для них названия? Что такое оксиды? Как правильно называть оксиды и, наоборот, составлять формулы по названиям? ^ Основания и кислоты Какие вещества называются основаниями, а какие кислотами? Как строятся их названия? \ зли? По каким правилам их нужно называть? ^44 Соли Какие вещества называются солями? Что такое средние, кислые и основн Серия "Растворы и прочие смеси" Какими бывают смеси Что такое диспенсерная система? Какие диспенсерные системы встречаю называются коллоидными? Что такое истинный раствор? Вычисляем концентрации Как можно выражать концентрацию растворенного вещества? Какими бывают доли? Что такое молярность? Как пересчитывать одни концентрации в другие? Картинка «заползает» за границу таблицы нике? Какие системы 4100% » ^ Рис. 3.2. Особенности позиционирования некоторых картинок • Вспомните, как решается подобная проблема в печатных изданиях. Как можно добавить надпись или картинку в любое место печатного документа в редакторе Microsoft Word? На помощь приходят слои. Оказывается, мы можем размещать данные на web-страницах не на одном слое, а на нескольких: что-то ближе, а что-то дальше (рис. 3.3). В этом случае проблема с «заползанием» одних блоков на другие решается сама собой: необходимо просто размещать эти блоки на разных слоях. Почему атомы соединяются друг с другом, образуя молекулы? Как изменяются при этом их свойства? Что такое валентность? 156 Модуль 3. Web-конструирование. Основы мастерства Рис. 3.3. Слои • Где ещё вам встречалось разбиение данных по слоям? В языке HTML имеется специальный тег, отвечающий за самостоятельный блок данных:
. Если его использовать без атрибутов, он будет выполнять роль обычного абзаца, то есть тега
, например:
Солнце стояло высоко и светило ярко
С помощью css-стилей этому тегу можно придавать любое оформление:
Солнце стояло высоко и светило ярко
Однако наибольший интерес он вызывает как раз тогда, когда речь заходит о слоях. В этом случае для тега
можно создать обычный css-стиль, а можно поступить и по-другому: присвоить ему атрибут id (от англ. identification - идентификация), который будет подчёркивать, что данный тег особенный и к нему необходимо применять особые правила оформления:
Солнце стояло высоко и светило ярко
Далее в css-файле (если стили внешние) или в подразделе