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

Федеральный государственный образовательный стандарт Образовательная система «Школа 2100» А.В. Горячев, В.Г. Герасимова, Л.А. Макарина, А.В. Паволоцкий, А.А. Семёнов, Т.Л. Чернышёва ИНФОРМАТИКА 8 класс • Часть- 2 Москва ь/mjz 2015 УДК 373.167.1:004+004(075.3) ББК 32.81я721 Г67 Федеральный государственный образовательный стандарт Образовательная система «Школа 2100» ^ Совет координаторов предметных линий Образовательной системы «Школа 2100» — лауреат премии Правительства РФ в области образования за теоретическую разработку основ образовательной системы нового поколения и её практическую реализацию в учебниках На учебник получены положительные заключения по результатам научной экспертизы (заключение РАН от 14.10.2011 № 10106-5215/448), педагогической экспертизы (заключение РАН от 24.01.2014 № 000383) и общественной экспертизы (заключение НП «Лига образования» от 30.01.2014 № 176) Руководитель издательской программы -чл.-корр. РАО, доктор пед. наук, проф. Р.Н. Бунеев Авторский коллектив: А.В. Гиглавый - научный редактор, А.В. Горячев - автор концепции курса, научный руководитель, В.Г. Герасимова (часть 1: модуль «Выступление с компьютерным сопровождением»), Л.А. Макарина (часть 1: модуль «Поиск информации»), С.Л. Островский (часть 1: модуль «Управление личными проектами»), А.В. Паволоцкий (часть 2: модуль «Алгоритмизация и программирование»), А.А. Семёнов, А.Г. Юдина (часть 1: модуль «Принятие решений»), Т.Л. Чернышёва (часть 2: модуль «Системы счисления») Данный учебник в целом и никакая его часть не могут быть скопированы без разрешения владельца авторских прав ISBN 978-5-85939-993-2 ISBN 978-5-85939-940-6 (ч. 2) © Горячев А.В., Герасимова В.Г., Макарина Л.А., Паволоцкий А.В., Семёнов А.А., Чернышёва Т.Л., 2012 © ООО «Баласс», 2012 Дорогие ребята! Профессии, связанные с развитием компьютерной техники и компьютерных программ, пользуются большим спросом в разных странах мира. Иногда такие специалисты живут в одном городе, а работают в другом или даже в другой стране. Теоретические основы для овладения этими профессиями называются компьютерными науками (Computer Science). Чтобы стать профессионалом, надо не жалеть сил и времени на их изучение. Во второй книге учебника мы разместили учебные модули, с помощью которых вы сможете изучить теоретические основы информатики, сквозную линию модулей с 7-го по 9-й класс, нацеленную на обучение программированию, а также модули профессиональной ориентации, с помощью которых можно научиться основам профессий, опирающихся на применение компьютера. Во второй книге учебника для 8-го класса, которую держите в руках, в модуле «Алгоритмизация и программирование» вы сможете продолжить обучение программированию на языке Паскаль. Модуль «Системы счисления» относится к теоретическим модулям, с его помощью можно узнать о разных системах счисления, научиться переводить числа из одной системы счисления в другую и выполнять над ними арифметические действия в разных системах счисления. Как работать с учебником Просмотрите Содержание, перелистайте учебник. Вы заметите, что он разделён на модули. Вы будете изучать их в том порядке, который предложит учитель. Практически в каждом модуле мы предусмотрели пять основных параграфов. Изучив их, вы напишете проверочную работу, по итогам которой узнаете, как вы освоили новый материал: ниже необходимого уровня, на необходимом или повышенном уровне. Далее вы будете работать самостоятельно, выполняя по указанию учителя задания того уровня, которого вы пока не достигли. Если проверочная работа покажет, что освоен и повышенный уровень, то вы будете выполнять задания самого высокого -максимального уровня. Учитель в любой момент может предложить вам перейти на выполнение заданий более высокого уровня. По окончании выполнения заданий учебника учитель проведёт итоговую проверочную работу. Далее в модуле расположены дополнительные параграфы, задания к ним и проверочные работы. Основные параграфы выделены в учебнике зелёной полосой вверху страницы, дополнительные - розовой полосой. Дополнительный материал, который не будет изучен на уроках, вы сможете использовать на факультативах и кружках. На уроках информатики вы освоите умения, которые помогут вам более эффективно использовать компьютеры и компьютерные сети для решения возникающих в вашей жизни задач. Кроме того, учитель может решить, что вам надо овладеть умениями, которые помогут заниматься разработкой новых компьютерных программ или заложат основы профессиональной деятельности, тесно связанной с применением компьютерной техники. Кроме того, наш учебник, как и все учебники Образовательной системы «Школа 2100», поможет вам в развитии универсальных учебных действий. В нём вам могут встретиться задания, обозначенные кружками и фоном разного цвета, - это условные знаки. Каждый цвет соответствует определённой группе умений: • - организовывать свои действия: ставить цель, планировать работу, действовать по плану, оценивать результат; • - работать с информацией: самостоятельно находить, осмысливать и использовать её; 4 ' 1^ - общаться и взаимодействовать с другими людьми, владеть устной и письменной речью, понимать других, договариваться, сотрудничать; ' I - развивать качества своей личности, оценивать свои и чужие слова и поступки; .0. так обозначены задания, где нужно применить разные группы умений, мы называем их жизненными задачами и проектами. Для успешного изучения информатики и овладения универсальными учебными действиями на уроках используется проблемно-диалогическая образовательная технология. Поэтому структура параграфа, где вводится новый материал, имеет в учебнике следующий вид. ПОСТАНОВКА ПРОБЛЕМЫ УРОКА Это подведение к теме (вопросу, цели) урока: вы обсуждаете проблему в предложенном материале и формулируете главный вопрос урока (всем классом, в группе или в паре). Сравните свой вариант вопроса с авторским. Авторские вопросы к параграфам расположены в «Содержании» под названиями параграфов и выделены курсивом. НЕОБХОДИМЫЕ БАЗОВЫЕ ЗНАНИЯ Так обозначены вопросы и задания по изученному материалу, который вам необходим для открытия нового знания. РЕШЕНИЕ ПРОБЛЕМЫ Вы в группе, в паре или совместно с учителем, ведя диалог, осуществляете поиск решения проблемы. Для решения проблемы вы работаете с текстом. ОБОБЩЕНИЕ НОВЫХ ЗНАНИЙ На этом этапе вы формулируете вывод и проверяете свои предположения, сравнивая их с авторским решением проблемы - научными формулировками правил или определений. ПРИМЕНЕНИЕ ЗНАНИЙ Так обозначены задания на применение новых знаний. ОПЕРАЦИИ Раздел «Операции» позволит вам научиться выполнять действия с компьютерными программами, необходимые для решения учебных задач. В конце модуля вы найдёте раздел «Решаем жизненные задачи и работаем над проектами». Задачи и проекты могут выполняться как на уроках, так и на факультативах и кружках. Там же находится очень важный раздел «О профессиях». Прочитайте его и подумайте, какие профессии вам больше по душе. Что такое жизненные задачи? Это проблемы, с которыми вы можете столкнуться в жизни и для решения которых вам понадобятся разные знания и умения. Они оформлены следующим образом: Название задачи Ваша роль: человек, в роли которого вы должны себя представить, решая проблему. Описание. Условия, в которых возникла проблема. Задание. То, что нужно сделать и получить в итоге. Что такое проект? Это любое самостоятельное дело, которое предполагает: 1) оригинальный замысел (цель); 2) выполнение работы за определённый отрезок времени; 3) конкретный результат, представленный в итоге. Что можно считать результатом проекта? • Предметы, сделанные своими руками: макеты, модели или вещи для практического использования. • Мероприятия: спектакли, фотовыставки, викторины, конференции, праздники и тому подобное - при условии, что они подготовлены самими учениками. • Информационные продукты: газеты, книжки, плакаты, карты, стихотворения, рассказы, доклады, отчёты об исследованиях и т. д. • Решение конкретных проблем: изменение, улучшение конкретной ситуации, например уборка мусора на школьном дворе. 6 Правила проектной деятельности 1. Каждый может начать собственный проект. 2. Каждый может объединиться с другими в ходе работы над проектом. 3. Каждый может выйти из проекта при условии, что он не подводит других. 4. Каждый может не участвовать ни в одном проекте. Как оценить свои учебные достижения? Для этого надо освоить алгоритм самооценки: 1. Какова была цель задания (что нужно было получить в результате)? 2. Вы выполнили задание (получен ли результат)? 3. Вы выполнили задание верно или с ошибкой? 4. Вы выполнили задание самостоятельно или с чьей-то помощью? 5. Вспомните, как вы ставите отметки. Определите свою отметку. Модуль 1. Алгоритмизация и программирование 8 Модуль 1. Алгоритмизация и программирование Этот модуль поможет вам: • ознакомиться с основами математической логики; • изучить методы поиска информации; • исследовать новые алгоритмы и технологии; • разобраться в новых возможностях языка Паскаль. Для этого вам надо научиться: • составлять программу на языке Паскаль; • использовать основные конструкции и типы данных языка Паскаль; • работать в интегрированной среде разработки программ; • искать ошибки в программах - отлаживать их. 9 10 Модуль 1. Алгоритмизация и программирование Введение Дорогие друзья! В 7-м классе мы с вами немного погрузились в мир программирования, научились писать программы на языке Паскаль, начали работать в интегрированной среде разработки программ, узнали некоторые важные алгоритмы. В этом году вам предстоит развивать свои знания о программировании и об устройстве компьютера. Кроме того, мы продолжим знакомить вас с программированием на языке Паскаль и различными алгоритмами. Помните: единственный способ стать хорошим программистом - это практика, практика и ещё раз практика. Удачи вам! § 1. Знакомство с математической логикой 11 § 1. Знакомство с математической логикой ПОСТАНОВКА ПРОБЛЕМЫ УРОКА Вы читали книгу «Алиса в Стране чудес» Льюиса Кэрролла? А знаете ли вы, что Льюис Кэрролл — известный английский математик? Прочитайте его высказывание относительно темы, которую мы будем рассматривать далее: «Методы эти позволяют Вам обрести ясность мысли, способность находить собственное оригинальное решение трудных задач, вырабатывают у Вас привычку к систематическому мышлению и, что особенно ценно, умение обнаруживать логические ошибки, изъяны и пробелы тех, кто не пытался овладеть привлекательным искусством логики. Попытайтесь. Вот всё, о чём я прошу Вас». Как вы считаете, о методах какой науки говорит Льюис Кэрролл? Сформулируйте тему урока в виде вопроса. Сравните свою формулировку с авторской (с. 141 учебника). НЕОБХОДИМЫЕ БАЗОВЫЕ ЗНАНИЯ Вспомните свои умения программирования на языке Паскаль. (Учебник для 7-го класса, книга 2, модуль 1.) Вспомните свой опыт работы в интегрированной среде разработки программ. (Учебник для 7-го класса, книга 2, модуль 1.) РЕШЕНИЕ ПРОБЛЕМЫ ЧТО ТАКОЕ ЛОГИКА? Ещё в древние времена логикой называли умение строго и чётко строить рассуждения, доказывать свои убеждения, выигрывать споры и соревнования. Основу логики как науки заложил великий древнегреческий учёный Аристотель. Рассуждая, люди выражают свои мысли с помощью высказываний. Что такое высказывание? Рассмотрим повествовательное предложение: «Сейчас идёт дождь». Выглянув на улицу, вы точно можете определить, идёт сейчас дождь или нет, то есть однозначно сказать, истинно или ложно это предложение. Есть всего два варианта: либо дождь идёт, либо нет. Задав вопрос: «Сейчас идёт дождь?» - вы получите один из двух ответов: «да» или «нет». Третьего не дано. Повествовательное предложение, относительно которого можно сказать, истинно оно или ложно, в логике называется высказыванием. 12 Модуль 1. Алгоритмизация и программирование Вот примеры высказываний: «Волга впадает в Каспийское море». «Дважды два равно пять». «Медведи не летают». Первое и третье из этих высказываний истинны, а второе - ложно. Вопросительные и побудительные предложения высказываниями не являются. Итак, любое высказывание является истинным или ложным. Значения «истина» и «ложь» называются логическими значениями. Высказывания могут быть заданы как словесно, так и формально - с помощью букв. Например, можно обозначить буквой А высказывание «Волга впадает в Каспийское море». Кроме того, высказывания можно задать и на языке программирования. Например, выражение a = b - это высказывание, значение которого может быть или «истина», или «ложь», в зависимости от значений переменных а и b. Формальную запись высказывания в языке программирования называют логическим выражением. Раздел математики, изучающий рассуждения, доказательства с помощью математических методов, называется математической логикой. Рассуждения в математической логике изучаются с точки зрения формы, а не смысла. Одним из основателей математической логики считается известный английский математик и логик Джордж Буль. Алгебра логики (алгебра высказываний) - это раздел математической логики, изучающий высказывания и операции над ними. Алгебру логики ещё называют булевой алгеброй - по имени Дж. Буля. Джордж Буль [1815-1864] Аппарат алгебры логики применяется при разработке и описании функционирования электронных схем элементов компьютера, работа которых основана на двух устойчивых состояниях переключателей: «включено» (ток идёт)/«выключено» (тока нет), «да»/«нет», «истина»/«ложь», 0/1. Как вы знаете, данные в компьютере представлены последовательностями двух значений - 0 и 1. ЛОГИЧЕСКИЙ ТИП И ЛОГИЧЕСКИЕ ПЕРЕМЕННЫЕ В ПАСКАЛЕ Логические значения надо как-то хранить в памяти компьютера. Вы уже знакомы с языком Паскаль и знаете, что для хранения значений необходимы переменные, а переменные всегда должны иметь какой-то определённый тип. § 1. Знакомство с математической логикой 13 Для хранения логических значений в языке Паскаль существует тип, который называется boolean (по имени Дж. Буля). Соответственно, имея тип, мы можем описывать переменные этого типа в разделе var нашей программы: var f: boolean,- Переменная f, которую мы описали, может принимать всего два значения: «истина» и «ложь». Эти значения представлены в языке Паскаль английскими словами true (истина) и false (ложь). Таким образом, возможны операции: f := true-f := false- if (f = true) then a := 5-while (f = false) do begin end; Вспомните, что при выполнении условного оператора if или оператора цикла с предусловием while^do проверяется, является ли значение условия истинным. Поэтому выражение f = true можно не писать, а вместо него оставить только f, так как здесь переменная f и является условием, проверяется её логическое значение: if f then a := 5 Основное назначение логических переменных - принимать и хранить значения логических выражений. Например, после выполнения оператора f := (1 = 2) в переменной f окажется значение false, поскольку 1 не равно 2. А после выполнения оператора f := (1 < 2) переменная f примет значение true, поскольку 1 меньше 2. Конечно же, вместо чисел в выражениях могут стоять переменные. Например: f := (a = b) Логические переменные можно сравнивать, но к ним неприменимы арифметические операции. Сравнение логических переменных основано на том соглашении, что false меньше true. Значения логических переменных можно выводить с помощью процедуры writeln. При этом будет выведено словесное значение переменной: True или False. Кроме того, к логическим переменным применимы логические операции, которые мы сейчас с вами и рассмотрим. 14 Модуль 1. Алгоритмизация и программирование ЛОГИЧЕСКИЕ ОПЕРАЦИИ До этого момента мы рассматривали простые высказывания. Сложные высказывания составляются из нескольких простых. Например, высказывание «Я сегодня вечером пойду в кино или пойду в театр» состоит из двух простых: 1) «Я сегодня вечером пойду в кино»; 2) «Я сегодня вечером пойду в театр» и специальной связки - союза «или». Таким связкам соответствуют логические операции. Рассмотрим три наиболее важные операции, которые присутствуют в языке Паскаль. ОПЕРАЦИЯ НЕ Первая логическая операция называется НЕ. В языке Паскаль она обозначается английским словом not. Дадим определение операции НЕ. Определение. Если применить операцию НЕ к высказыванию, то его значение изменится на противоположное. Если оно было истинным, то станет ложным, а если было ложным, то превратится в истинное. Вспомните рассмотренный выше фрагмент программы: там можно оператор цикла с предусловием while (f = false) do заменить на while (not f) do Здесь проверяется значение условия not f: если оно истинно (то есть значение f ложно), то цикл продолжает выполняться. Операция НЕ - унарная (от латинского слова unus - единственный), то есть она применяется к одному высказыванию. Объект, над которым совершается операция, называется операндом. Рассмотрим простую программу. § 1. Знакомство с математической логикой 15 Код программы Вывод program logicl; var f: boolean; begin f := false; writeln('До операции not: ', f); f := not false; writeln('После операции not: ', f); end. До операции not: False После операции not: True Как видно из примера, значение переменной f после выполнения операции not изменилось с false на true. ОПЕРАЦИЯ И Следующая логическая операция называется И. В языке Паскаль она обозначается английским словом and. Этой операции соответствует связка «и» или «а». Примеры высказываний: «Сейчас холодно и идёт снег»; «На дворе ветер, а всё равно тепло». Определение. Значение операции И - «истина» тогда и только тогда, когда оба простых высказывания, которые она объединяет, истинны. Примеры: 1) Логическое выражение (2 > 1) and (5 = 10 div 2) истинно, поскольку 2 > 1, а 5 равно 10, делённому нацело на 2. 2) Логическое выражение (1 = 2) and (5 > 0) ложно, поскольку хотя 5 больше нуля, но 1 не равно 2. Операция И называется бинарной - она применяется к двум операндам. Давайте напишем программу, которая будет выводить все возможные комбинации значений операции И. Код программы Вывод program logic2; var a, b: boolean; a b a И b begin writeln(' a | ', ' b | ', ' a И b'); False False False writeln ( ' ' ) ; False True False for a := false to true do True False False for b := false to true do writeln(a:7, b:7, (a and b):7); end. True True True В нашем примере операнды - это a и b. 16 Модуль 1. Алгоритмизация и программирование Как мы видим, существует всего четыре варианта. Кроме того, пример показывает нам, что логические переменные можно использовать в цикле (поскольку false всегда меньше true), а также логические переменные можно форматировать при выводе. Таблица, которую мы с вами получили в итоге, называется таблицей истинности логической операции. Посмотрите на неё внимательно. Когда операция И истинна? Когда и а, и b истинны, и только в этом случае. • Сравните полученный результат с определением операции И. ОПЕРАЦИЯ ИЛИ Третья логическая операция, которую мы с вами рассмотрим, называется ИЛИ. Её обозначение в языке Паскаль - or. Определение. Значение операции ИЛИ - «истина» в том случае, когда хотя бы одно из высказываний, входящих в её состав, истинно, и «ложь» - в противном случае. Примеры: 1) Логическое выражение (1 = 2) or (5 < 10) истинно, поскольку хотя 1 не равно 2, но 5 меньше 10. 2) Сложное логическое выражение (1 = 2) or (5 < 0) ложно, поскольку оба простых логических выражения ложны. Операция ИЛИ, так же как и операция И, является бинарной, поскольку у неё есть два операнда. Давайте получим таблицу истинности операции ИЛИ. Код программы Вывод program logic3; var a, b: boolean; a | b | a ИЛИ b begin writeln(' a |', ' b |', ' a ИЛИ b'); False False False writeln ( ' ' ) ; False True True for a := false to true do True False True for b := false to true do writeln(a:7, b:7, (a or b):7); end. True True True Как мы видим, операция ИЛИ ложна только в том случае, когда оба её операнда ложны, во всех остальных случаях операция истинна. § 1. Знакомство с математической логикой 17 ПРИОРИТЕТЫ ЛОГИЧЕСКИХ ОПЕРАЦИЙ Как и в случае с арифметическими операциями, логические операции имеют приоритеты по выполнению. Рассмотрим логическое выражение: a or not b and c. Никаких скобок в нём нет, какая же операция будет выполняться первой, а какая - второй? Самым высшим приоритетом, то есть операцией, которая будет выполняться первой, обладает операция НЕ, затем идёт операция И, а самый низкий приоритет имеет операция ИЛИ. Таким образом, в нашем примере сначала будет вычислено not b, затем not b and c, а потом к результату будет применена операция or. ПРИМЕНЕНИЕ ЛОГИЧЕСКИХ ОПЕРАЦИЙ Рассмотрим задачу, в которой продемонстрируем применение логических операций. Задача. Последовательность чисел вводится с клавиатуры до нулевого значения. Необходимо определить, является ли она возрастающей, то есть верно ли утверждение, что каждое следующее число больше предыдущего. Ноль учитывать не надо. Пример возрастающей последовательности: 1,3, 5, 7, 8, 10. Пример невозрастающей последовательности: 1,2, 3, 3, 2, 1. program logic4; var a, b: integer; f: boolean; begin writeln('Вводите числа до нуля'); // Предположим, что последовательность // изначально возрастающая f := true; readln(a); // будем продолжать цикл, пока а не ноль while (a <> 0) do begin // Введём новое число b readln(b); // Проверим, не нарушилось ли возрастание // с учётом предыдущих значений. // Поскольку 0 учитывать не надо, проверим b на равенство нулю if (b <> 0) then f := f and (b > a); 18 Модуль 1. Алгоритмизация и программирование // сохраним b в a a := b; end; // Если f = true, то возрастание не нарушилось if f then writeln('Последовательность возрастающая') else writeln('Последовательность невозрастающая'); end. Комментарии, указанные в тексте программы, объясняют её работу. Обратите внимание на выделенные фрагменты. Логическая переменная f является признаком того, какая последовательность была ранее, до текущего момента - момента проверки. Мы предположили, что наша последовательность возрастающая, и занесли в f начальное значение true. Затем, каждый раз (в цикле), вводя b, мы выполняем операцию присваивания f := f and (b > a). Если значение f было равно false, то в каком бы отношении ни находились переменные a и b, f своё значение в дальнейшем не поменяет (вспомните операцию И). Это означает, что если в последовательности попался хотя бы один элемент, нарушающий её возрастание, то она так и останется невозрастающей, независимо от того, какие элементы к ней добавятся. Если же значение f было равно true, и на текущем шаге b станет меньше или равным а, то f изменит своё значение на false (нашёлся элемент, нарушающий возрастание). Как вы думаете, что бы вы получили, если бы не использовали операцию И, а написали бы просто f := (b > a) ? В f остался бы результат последнего сравнения. А нам этого мало, поскольку мы должны проанализировать всю последовательность. ОБОБЩЕНИЕ НОВЫХ ЗНАНИЙ Раздел математики, изучающий рассуждения, доказательства с помощью математических методов, называется математической логикой. Алгебра логики (алгебра высказываний) - это раздел математической логики, изучающий высказывания и операции над ними. Высказывание - это повествовательное предложение, относительно которого можно сказать, истинно оно или ложно. Высказывания бывают простыми и сложными. Значения «истина» и «ложь» называются логическими значениями. Формальную запись высказывания в языке программирования называют логическим выражением. Для описания логических значений в языке Паскаль имеется тип boolean. Логические значения записываются как true и false. Логические переменные можно сравнивать, но к ним не применимы арифметические операции. Сложные высказывания получаются из простых с помощью логических операций: И, ИЛИ, НЕ. В языке Паскаль им соответствуют операторы and, or, not. § 1. Знакомство с математической логикой 19 ПРИМЕНЕНИЕ ЗНАНИИ 1. Найдите значение логической переменной. а) f := (5 mod 2 = 0) б) f := (9 div 3 > 2) and (15 mod 2 = 0) в) f := not (5 div 2 = 0) or (2 > 0) and (48 > 9 6 div 2) 2. Из приведённых предложений выделите высказывания. Объясните свой выбор. а) Который сейчас час? б) Сегодня жаркая погода, а вчера было холодно. в) Моему другу Васе 13 лет. г) Собирайся в школу! д) Мы в школе изучаем информатику. 3. C клавиатуры вводятся три действительных числа А, В и С. Удвойте эти числа, если А > В> С, и замените их противоположными значениями, если это не так. 4. Напишите программу, которая для натурального числа k (от 1 до 99), введённого вами, выводит фразу «Мне k лет». При этом в нужных случаях слово «лет» нужно заменить на слово «год» или «года». Например, при k = 70 должна быть выведена фраза «Мне 70 лет», при k = 15 - фраза «Мне 15 лет», при k = 23 - фраза «Мне 23 года», при k = 21 - фраза «Мне 21 год». 20 Модуль 1. Алгоритмизация и программирование § 2. Поиск в массиве ПОСТАНОВКА ПРОБЛЕМЫ УРОКА Учитель биологии разложил на столе перед учениками карточки с изображениями различных зверей картинками вниз, так что ребята самих изображений не видели. - Найдите, пожалуйста, среди этих карточек ту, на которой изображён заяц, - сказал учитель. - Но ведь мы не видим, что изображено на карточках, - ответила Маша, — и не знаем, есть ли вообще там нужная картинка! Как можно помочь Маше? Сформулируйте основной вопрос урока. Сравните свой вариант с авторским (с. 141 учебника). НЕОБХОДИМЫЕ БАЗОВЫЕ ЗНАНИЯ Какие существуют способы записи алгоритмов? (Учебник для 7-го класса, книга 2, модуль 1, § 2.) Вспомните свои навыки работы с массивами. (Учебник для 7-го класса, книга 2, модуль 1, § 8-9.) Вспомните свой опыт работы в интегрированной среде разработки программ. (Учебник для 7-го класса, книга 2, модуль 1.) Что такое отладка программ и как она выполняется? (Учебник для 7-го класса, книга 2, модуль 1, § 7.) РЕШЕНИЕ ПРОБЛЕМЫ Вы уже научились заносить данные в массив, обрабатывать их, выводить на экран, одним словом, работать с содержимым массива. Продолжим изучать алгоритмы работы с массивами - попробуем решить задачу поиска элемента в массиве. Будем рассматривать алгоритмы поиска на примере целочисленных массивов. ПРОСТОЙ ЛИНЕЙНЫЙ ПОИСК Представьте, что у вас есть непрозрачный мешок, в котором лежат пронумерованные шарики. И вы хотите вытащить из этого мешка шарик с номером 5, причём вы не знаете, есть там такой шарик или нет. Как вы поступите? Скорее всего, вы будете по одному вытаскивать шарики из мешка и смотреть на их номера. Если вы вытащите шарик с желаемым номером 5, то ваша § 2. Поиск в массиве 21 задача будет решена и поиск можно будет считать завершившимся удачно. Однако может случиться и так, что вы вытащите все шарики, а нужного среди них не окажется. Эта ситуация говорит о том, что шарика с номером 5 в мешке не было. Давайте попробуем решить нашу задачу с помощью компьютера. Мешок с шариками представим в виде массива целых чисел. Формулировка задачи поиска будет звучать следующим образом: найти в массиве элемент с требуемым значением; если его там нет, вывести сообщение об этом. Запишем алгоритм в виде блок-схемы (рис. 1.1) и на языке программирования Паскаль. Рис. 1.1 program searchl; var A: array [1..100] of integer; x, n, i: integer; 22 Модуль 1. Алгоритмизация и программирование begin writeln('Поиск числа в массиве'); // Ввод массива write('Введите количество элементов в массиве: '); readln(n); for i := 1 to n do begin write('A[', i, ']='); readln(A[i]); end; // Конец ввода массива // Ввод искомого числа write('Введите искомое число: '); readln(x); // Поиск i := 1; while ((i <= n) if (i > n) then writeln' else writeln' end. and (x <> A[i] 'Число 'Число x, x, do i := i + 1; в массиве не найдено' в массиве найдено'); В начале алгоритма происходит ввод количества элементов массива - n и заполнение массива А. Заполнение происходит с помощью цикла с параметром for. Затем вводится искомое число х. Поиск выполняется с помощью цикла с предусловием. Мы начинаем просматривать массив с первого элемента (i := 1). Условием продолжения цикла является логическое выражение ((i <= n) and (x <> A[i])). Цикл можно описать так: пока i не превысило n (то есть пока мы не перебрали все элементы массива) и искомое число X не равно текущему элементу массива A[i], будем увеличивать i. У нас только два варианта прекращения этого цикла: 1) мы просмотрим все элементы (i станет больше n); 2) мы найдём искомое число в массиве (A[/] станет равным x). Проверим это в последнем условном операторе. Если мы просмотрели все элементы, то искомого числа в массиве нет, в противном случае число в массиве присутствует. Приведённый поиск называется линейным, поскольку его суть состоит в последовательном (линейном) переборе всех элементов массива до момента принятия решения о наличии или отсутствии в нём искомого числа. Если оно находится на первом месте в массиве, то алгоритм отработает очень быстро, а вот если оно находится в конце массива или отсутствует, то, пока мы не просмотрим весь массив, ответить на вопрос мы не сможем. § 2. Поиск в массиве В этой тонкости заключается основной недостаток линейного поиска - непредсказуемость времени его работы, но для осуществления поиска в массиве, о структуре которого мы ничего не знаем, у нас нет других вариантов. Стоит отметить также, что в нашем случае мы искали элемент строго по одному условию - равенству х его значения. Мы можем усложнить критерий поиска. Например, узнать, есть ли в массиве элемент, значение которого равно х, а индекс кратен 5. • Как надо модифицировать алгоритм, чтобы вы могли получить информацию об индексе искомого элемента массива? • Представьте, что искомый элемент встречается в массиве дважды. Какой индекс найдёт модифицированный алгоритм? ЛИНЕЙНЫЙ ПОИСК С БАРЬЕРОМ Предыдущий алгоритм в своей работе использовал сложное логическое выражение в качестве условия продолжения цикла поиска. Сейчас мы рассмотрим механизм, который позволит нам избавиться от этого сложного условия. Назовём барьером элемент массива, равный искомому и добавленный в массив после самого последнего элемента. Таким образом, исходный массив увеличится на 1 элемент, а элемент-барьер будет иметь индекс n + 1. Примеры: 1) Массив: 1,2, 3, 4, 5. Ищем число 3. Массив с барьером: 1,2, 3, 4, 5, 3. 2) Массив: 3, 2. Ищем число 1. Массив с барьером: 3, 2, 1. Теперь вы будете искать число не в исходном массиве, а в массиве с барьером. И что самое важное - вы этот элемент всегда найдёте! Вы же его сами добавили в конец массива. Как в этом случае понять, нашли вы элемент или нет? Вам поможет барьер. Если при поиске элемента вы получили номер n + 1, то в исходном массиве искомого числа нет, в противном случае оно есть. Посмотрите, как изменилась блок-схема алгоритма (рис. 1.2). При реализации этого алгоритма на языке программирования нужно не забыть увеличить размер массива на 1, чтобы было где разместить барьерный элемент. Линейный поиск с барьером обладает тем же недостатком, что и простой линейный поиск, - невозможностью предсказания времени работы алгоритма. Для того чтобы эффективно искать информацию в массивах данных, необходимо приводить массивы к такому виду, при котором становятся известны закономерности размещения в них элементов. Такие алгоритмы называются упорядочением массива по некоторому признаку. Их мы рассмотрим в следующем параграфе. 23 Рис. 1.2 ОБОБЩЕНИЕ НОВЫХ ЗНАНИЙ Чтобы проверить массив на наличие в нём некоторого элемента, необходимо применить алгоритмы поиска элементов. Алгоритмы линейного поиска (простого и с барьером) позволяют искать данные в произвольном массиве, последовательно перебирая все его элементы. ПРИМЕНЕНИЕ ЗНАНИЙ 1. По блок-схеме, приведённой в параграфе, напишите на языке Паскаль программу, осуществляющую линейный поиск в целочисленном массиве с барьером. 2. С клавиатуры вводится число n, а за ним - массив из n целых чисел. Найдите номер первого по счёту элемента массива с нечётным значением. 3. С клавиатуры вводится число n, за ним массив из n целых чисел и число X. Найдите количество элементов массива, равных х. § 3. Упорядочение массивов § 3. Упорядочение массивов ПОСТАНОВКА ПРОБЛЕМЫ УРОКА Перед началом урока физкультуры ученики построились в спортивном зале. Но учителю построение не понравилось. - Ну-ка, постройтесь по росту! - скомандовал он. — А как? По возрастанию или по убыванию? — спросил Вася. Что не понравилось учителю? О каких правилах построения говорит Вася? Сформулируйте основной вопрос урока. Сравните свой вариант с авторским (с. 141 учебника). НЕОБХОДИМЫЕ БАЗОВЫЕ ЗНАНИЯ Вспомните свои навыки работы с массивами. (Учебник для 7-го класса, книга 2, модуль 1, § 8-9.) Вспомните свой опыт работы в интегрированной среде разработки программ. (Учебник для 7-го класса, книга 2, модуль 1.) 25 РЕШЕНИЕ ПРОБЛЕМЫ УПОРЯДОЧЕНИЕ Порядок - это расположение вещей, людей и любых других объектов, удовлетворяющее заранее определённому правилу. Например, расположение книг в библиотеке подчиняется правилу алфавитного каталога. Это означает, что книги так расставляются в шкафах, что фамилии их авторов расположены по алфавиту: Петров после Иванова, Иванов после Батюшкова, а Батюшков после Абрикосова. Представьте, как долго вы занимались бы поиском в большой библиотеке, если бы книги там были расставлены случайным образом. Про информацию, организованную в соответствии с некоторым порядком, говорят, что она упорядочена. В упорядоченной информации гораздо проще искать нужные сведения. В компьютере информация закодирована в виде данных. Поиск в больших массивах данных значительно облегчается при их упорядочении и становится эффективнее. Давайте научимся приводить имеющиеся у нас в компьютере данные к упорядоченному виду. Упорядочение массивов часто называют сортировкой. Алгоритмов сортировки очень много, причём существуют как универсальные алгоритмы, так и алгоритмы, которые применяются в уникальных ситуациях. Мы рассмотрим два алгоритма: сортировку выбором и сортировку обменом. 26 Модуль 1. Алгоритмизация и программирование СОРТИРОВКА ВЫБОРОМ Пусть у нас имеется произвольный массив целых чисел. Его можно отсортировать по возрастанию. Это означает, что каждый следующий элемент массива должен быть строго больше предыдущего. При сортировке по убыванию, напротив, каждый следующий элемент массива должен быть строго меньше предыдущего. Если в массиве имеются одинаковые элементы, то его сортируют по неубыванию (следующий элемент больше или равен предыдущему) или по невозрастанию (следующий элемент меньше или равен предыдущему). Например, массив 1 3 5 5 8 9 118 335 отсортирован по неубыванию, а массив 1 3 5 3 5 2 9 10 - нет. Рассмотрим сортировку по неубыванию. Пусть исходный массив выглядит так: 3 8 -1 5 2 15 10 Найдём в этом массиве минимальный элемент - это будет -1. Поменяем местами первый элемент массива и найденный нами минимальный. Получим вот такую картину (элементы, которые мы поменяли местами, выделены красным цветом): -1 8 3 5 2 15 10 Теперь мы точно знаем, что на первом месте в массиве стоит самое маленькое число. С этим числом мы больше работать не будем - оно заняло своё место (выделим его на рисунке синим цветом). Вновь поищем в массиве, но уже без первого элемента, самое маленькое число. Мы найдём число 2. Поменяем местами второй элемент массива и найденное число 2. Получим такой массив: -1 | 2 3 5 8 15 10 Два самых маленьких числа встали в начало массива: -1 и 2. Их больше не рассматриваем. Будем дальше повторять наши действия. Начиная с третьего элемента (числа 3), будем искать минимальный элемент в массиве. Но третий элемент и есть наименьший, поэтому никакого обмена производить не будем. Получим: -1 2 | 3 5 8 15 10 Будем продолжать и остановимся в тот момент, когда дойдём до последнего элемента массива: § 3. Упорядочение массивов 27 -1 2 3 | 5 8 15 Ю -1 2 3 5 | 8 15 10 -1 2 3 5 8 |10 15 -1 2 3 5 8 10 | 15 -1 2 3 5 8 10 15 В результате, как только мы дойдём до последнего элемента массива, мы получим отсортированный массив. Посмотрите на блок-схему нашего алгоритма (рис 1.3). Синей пунктирной рамкой отмечен фрагмент, в котором происходит поиск минимального элемента, красной - фрагмент, в котором происходит обмен. Г Начало j Рис. 1.3 В переменной i хранится номер текущего элемента массива. Часть массива до i-го номера уже отсортирована. Первоначально в переменную i мы заносим значение 1. 28 Модуль 1. Алгоритмизация и программирование Если внимательно проанализировать приведённую блок-схему, то можно увидеть, что она содержит два цикла, один из которых находится внутри другого. Такие циклы называются вложенными. Обратите внимание на условие продолжения первого (внешнего) цикла: i < n. Оно говорит нам о том, что последний элемент массива мы не будем рассматривать. Почему? Потому, что массив из одного элемента всегда является отсортированным, и никаких действий для упорядочения применять не надо. Как только мы доберёмся до последнего элемента массива, мы его выводим. На этом алгоритм заканчивается. Задачу поиска минимального элемента в массиве мы с вами разбирали в 7-м классе. Посмотрите на блок-схему и вспомните её. После выполнения вложенного (внутреннего) цикла в переменной min будет находиться номер минимального элемента. Теперь рассмотрим красный блок. Если номер минимального элемента отличается от i, то необходимо произвести обмен. Для обмена нам понадобится ещё одна переменная - temp. СОРТИРОВКА ОБМЕНОМ Рассмотрим тот же исходный массив: 3 8 -1 5 2 15 Ю Сравним первые два элемента (выделены красным). Если первый больше второго, то поменяем их местами. В нашем случае это не так (3 меньше 8), поэтому оставим элементы без изменений и сравним второй и третий элементы: 3 8 -1 5 2 15 10 8 больше -1, поэтому произведём обмен. Получим такой массив (обмен выделен синим): 3 -1 8 5 2 15 10 Сравним третий и четвёртый элементы (8 и 5). Поскольку 8 больше 5, то произведём обмен: 3 -1 5 8 2 15 10 Сравним четвёртый и пятый элементы (8 и 2). Снова производится обмен: 3 -1 5 2 8 15 10 § 3. Упорядочение массивов Подошла очередь пятого и шестого элементов (8 и 1 5). В этом случае обмена нет, массив остаётся без изменений: 3 -1 5 2 8 15 Ю Последнее сравнение - шестого и седьмого элементов (15 и 10) - снова вызовет обмен. В результате мы получим вот такой массив: 3 -1 5 2 8 10 15 Что мы получили? Благодаря нашим обменам, самое большое число (15) «всплыло» в конец массива, как пузырёк с воздухом всплывает в водоёме. Поэтому данный алгоритм ещё называют методом пузырька. Поскольку самый большой элемент оказался на своём, последнем месте, то в дальнейшем его рассматривать не нужно. Поэтому продолжим производить сравнения с первого элемента до предпоследнего. Посмотрим, какие значения будут принимать элементы массива при следующем проходе массива. (Обмен, как и раньше, будем выделять синим цветом.) 29 -1 3 5 2 8 10 15 -1 3 5 2 8 10 15 -1 3 2 5 8 10 15 -1 3 2 5 8 10 15 -1 3 2 5 8 10 15 -1 3 2 5 8 | 10 15 Сколько раз мы будем повторять проход по массиву? Вы заметили, что у нас всё время увеличивается упорядоченная часть в конце массива? Когда эта упорядоченная часть будет состоять из всех элементов, кроме первого (вспомните, что массив из одного элемента всегда упорядочен), то мы сможем сказать, что массив отсортирован. Это означает, что мы должны сделать N - 1 проход, где N - длина массива. В алгоритме полезно учесть следующее: если, совершая очередной проход по массиву, мы не сделали ни одного обмена, то это означает, что массив уже упорядочен и дальнейшие проходы не требуются. Составим блок-схему этого алгоритма (рис 1.4). Обратите внимание на появление логической переменной flag. Если значение этой переменной равно true, то это означает, что в процессе прохода были обмены, если false, то обменов не было. Если происходит обмен (A[j] > Л[/+1]), то переменная flag принимает значение true. Кроме того, в неё нужно занести значение true в самом начале, чтобы мы смогли попасть в цикл. 30 Модуль 1. Алгоритмизация и программирование Посмотрим на условие продолжения внешнего цикла: (/ < п]and flag. Оно будет ложным в случае, когда либо i станет большим или равным п, либо flag станет равным false. То есть цикл закончится тогда, когда либо мы сделаем п - 1 проходов, либо в процессе последнего прохода не будет сделано ни одного обмена. Поскольку после каждого прохода в конце массива образуется упорядоченная часть, то в следующий раз эту часть рассматривать не надо. Для реализации данного условия во вложенном цикле переменная j изменяется до значения п - i. ( Начало) Рис. 1.4 Приведём программу, которая сортирует массив методом пузырька § 3. Упорядочение массивов 31 program obmen; var i, j, n, temp: integer; flag: boolean; A: array [1..100] of integer; begin // Ввод массива write('Введите количество элементов в массиве: '); readln(n); for i := 1 to n do begin write('A[', i, ']='); readln(A[i]); end; // Конец ввода массива // Сортировка пузырьком flag := true; i := 1; while (i < n) and flag do begin flag := false; for j := 1 to n - i do if (A[j] >= A[j+1]) then begin temp := A[j]; A[j] := A[j+1]; A[j+1] := temp; flag := true; end; i := i + 1; end; // Конец сортировки // Вывод отсортированного массива write('Отсортированный массив: '); for i := 1 to n do write(A[i], ' '); writeln; // Конец вывода массива end. 32 Модуль 1. Алгоритмизация и программирование Отметим, что условие продолжения внешнего цикла (i < n) and flag можно сократить и записать просто: flag Это возможно, так как на некотором шаге обязательно не будет сделано ни одного обмена и внешний цикл закончится. Мы рассмотрели два способа сортировки массивов. Оба этих метода используют вложенные циклы для своей работы. Алгоритм сортировки пузырьком является самым простым в реализации, но в то же время он самый неэффективный. Поэтому применять его можно только на небольших массивах. Алгоритм выбором эффективен по количеству обменов значений местами и неэффективен по количеству сравнений элементов между собой. Для упорядочивания больших объёмов данных используются более совершенные методы, но и они в общем случае используют несколько проходов массива. В наших примерах мы сортировали массивы по неубыванию. Однако критерии упорядочения бывают весьма и весьма разнообразными. ОБОБЩЕНИЕ НОВЫХ ЗНАНИЙ Упорядочение (сортировка) массива - это процесс расстановки элементов массива в порядке, определяемом некоторым правилом. Примеры сортировок: по неубыванию, по невозрастанию. Существует множество алгоритмов сортировки, как универсальных, так и рассчитанных на конкретные ситуации. Мы рассмотрели два алгоритма сортировки: выбором и обменом (пузырьком). Первый из них использует в своём составе алгоритм поиска минимального числа. Сортировка пузырьком самая неэффективная, но в то же время самая простая в реализации. ПРИМЕНЕНИЕ ЗНАНИЙ 1. • Можно ли изменить алгоритм сортировки выбором так, чтобы мы ис- кали не минимум, а максимум? 2. • Как изменить алгоритм сортировки пузырьком, чтобы массив сортиро- вался по невозрастанию? 3. С помощью блок-схемы на рис. 1.3 реализуйте на языке Паскаль алгоритм сортировки массива выбором. 4. С клавиатуры вводится число n, а за ним массив из n элементов. Проверьте его на упорядоченность по неубыванию. § 4. Структурирование программ. Подпрограммы 33 § 4. Структурирование программ. Подпрограммы ПОСТАНОВКА ПРОБЛЕМЫ УРОКА Представьте, что две фабрики выпускают однотипный мебельный гарнитур. В гарнитур входят 6 стульев, обеденный стол и комод. Естественно, что каждая фабрика обязана предоставить инструкцию по сборке. У первой фабрики инструкция занимает 8 листов: 6 — на каждый из стульев и по одному для стола и комода. А вторая фабрика выпустила инструкцию только на 3 листах. • Как, по вашему мнению, второй фабрике удалось так сократить инструкцию? Сформулируйте основной вопрос урока. Сравните свой вариант с авторским (с. 141 учебника). НЕОБХОДИМЫЕ БАЗОВЫЕ ЗНАНИЯ Вспомните свои умения программирования на языке Паскаль (Учебник для 7-го класса, книга 2, модуль 1.) Как в языке программирования используются циклические конструкции? (Учебник для 7-го класса, книга 2, модуль 1, § 5-6.) Вспомните свой опыт работы в интегрированной среде разработки программ. (Учебник для 7-го класса, книга 2, модуль 1.) РЕШЕНИЕ ПРОБЛЕМЫ ВСПОМОГАТЕЛЬНЫЕ АЛГОРИТМЫ Очень часто встречается такая ситуация, когда для решения поставленной задачи приходится использовать ранее созданные алгоритмы. Представьте, например, что вы проектируете систему, которая предназначена для рисования геометрических фигур. Допустим, вы хотите рисовать квадраты и окружности. Но любые два квадрата различаются длиной сторон, а окружности - размером радиусов. Получается, что нужно придумать разные алгоритмы для рисования каждого квадрата и каждой окружности? Конечно, нет. Достаточно создать вспомогательный алгоритм, в который вы будете передавать параметр - длину стороны квадрата или радиус окружности. Этот вспомогательный алгоритм сможет строить нужную вам фигуру, а в основном алгоритме вы будете только вызывать вспомогательный с необходимым вам значением параметра. Для оформления вспомогательных алгоритмов в программировании применяются подпрограммы. 34 Модуль 1. Алгоритмизация и программирование ПОДПРОГРАММЫ В языке Паскаль подпрограммы делятся на процедуры и функции. И в процедуру, и в функцию мы можем из основной программы передавать параметры. Функция - это подпрограмма, которая возвращает результат - некоторое значение. Например, вы можете написать функцию, в которую будете передавать число, а она будет возвращать квадрат этого числа. Или, например, функцией является подпрограмма, которая вычисляет площадь параллелограмма по заданным длинам его сторон. • Какие ещё примеры функций вы можете привести? Процедура - это подпрограмма, которая, в отличие от функции, не возвращает значение. Пример процедуры - подпрограмма, которая по переданному ей числу n выводит n звёздочек. Подпрограммы бывают встроенными и определёнными программистом. Встроенные подпрограммы являются частью какой-либо компьютерной системы (встроены в неё). Их написали другие программисты, но вы можете ими пользоваться. Оказывается, вы уже неоднократно встречались со встроенными подпрограммами. Например, это процедуры ввода (read, readln) и вывода (write, writeln) в Паскале. Кроме того, язык Паскаль обладает большим количеством встроенных функций. Приведём некоторые из них. Функция Описание sqr(a) Возводит число a в квадрат sqrt(a) Возвращает квадратный корень из a abs(a) Возвращает модуль числа a Теперь вы можете использовать эти функции в своих программах. А как создавать свои функции и процедуры? ФУНКЦИИ В языке Паскаль функции описываются в программе в разделе var . В качестве первого примера разберём структуру встроенной функции sqr, написав свою функцию с именем square. program f1; var a, s: integer; function square(x: integer): integer; begin square := x * x; end; § 4. Структурирование программ. Подпрограммы 35 begin write('Введите число: '); readln(a); s := square(a); writeln('Квадрат числа end. a, равен Как вы видите, структура подпрограммы (в данном случае функции) очень похожа на структуру самой программы: у неё тоже есть заголовок и содержимое. Давайте обратим внимание на заголовок функции: function square(x: integer): integer; Описание функции начинается с ключевого слова function, за ним следует имя функции - square, в скобках идут параметры - данные, которые функция принимает (в нашу функцию передаётся значение типа integer), а в конце после символа «:» указывается тип значения, которое функция возвращает (здесь мы хотим вернуть значение типа integer). Давайте будем представлять себе функцию как «чёрный ящик». Так инженеры и программисты называют объект, об устройстве которого они ничего не знают (но очень хотят узнать), однако имеют информацию о том, какие входные параметры объект принимает и какие выходные параметры выдаёт (рис. 1.5). Объявив нашу функцию, мы сообщили компилятору (вспомните, что такое компилятор), что: 1) мы хотим создать функцию; 2) мы даём ей имя square; 3) функция будет принимать один целочисленный параметр - х; 4) функция будет возвращать целое число. Этими действиями мы создали «чёрный ящик». Теперь мы должны сделать его «прозрачным», то есть написать содержимое (тело) функции: begin square := x * x; end; 36 Модуль 1. Алгоритмизация и программирование В строке square := x * x; мы говорим следующее: функция square возвращает значение квадрата числа х. Функция square написана, нам осталось её вызвать, то есть использовать. Делаем мы это в основной программе в строке: s := square(a); Эта строка означает следующее: передать в функцию square значение переменной а, выполнить функцию и занести в переменную s результат её работы. Обратите внимание: в описании функции параметр обозначен как х, а в её вызове - как а. Это означает, что мы передаём функции значение переменной a: в функции это будет значение переменной х. Й Параметры в описании функции называются формальными (в нашем примере X - формальный параметр], а в обращениях (вызовах] к ней - фактическими (в нашем примере а - фактический параметр]. Фактические параметры - это переменные как раз с теми значениями, которые мы хотим передать функции. В нашей функции значение переменной а передаётся соответственно переменной х. Рассмотрим пример более сложной функции - power, которая будет возводить вещественное число а в степень n. Напомним, что ап = а • а а n раз. У этой функции уже два параметра, так как мы должны сообщить ей и число, которое нужно возвести в степень, и саму степень. Возвращать эта функция будет вещественное число. Заголовок функции: function power(base: real; p: integer): real; Нам понадобятся дополнительные переменные r и i, мы должны описать их в разделе var функции. var i: integer; r: real; Переменные, которые описываются внутри подпрограммы (у нас это переменные i, r), называются локальными. Локальные переменные доступны только в подпрограмме, где они описаны. Параметры в подпрограмме тоже являются локальными переменными для этой подпрограммы. В отличие от локальных, глобальные переменные описываются в основной программе, их можно использовать и в ней, и во всех подпрограммах. Об использовании глобальных переменных мы поговорим в следующем параграфе. § 4. Структурирование программ. Подпрограммы 37 program f2; var n: integer; a, res: real; function power(base: real; p: integer): real; var i: integer; r: real; begin r := 1; for i power end; begin write 1 to p do r := r * base; r; 'Введите число а: '); readln(a); write('Введите степень: '); readln(n); res := power(a, n); writeln('Результат - ', res); end. Обратите внимание на тот факт, что если в функцию передаются несколько параметров, то в заголовке они перечисляются через символ «;». При вызове функции порядок следования параметров важен. Они должны идти в той же последовательности, в которой соответствующие им параметры описаны в подпрограмме. В нашем примере в функцию power сначала поступает основание степени -base, а потом показатель степени - р. function power(base: real; p: integer): real; Поэтому и в вызове функции сначала должна идти переменная а, содержащая значение, равное основанию степени, а потом - переменная n, содержащая показатель степени. res := power(a, n) ПРОЦЕДУРЫ Процедуры в языке Паскаль описываются в том же месте, что и функции, — в разделе описания переменных van. Описания процедур и функций можно чередовать. 38 Модуль 1. Алгоритмизация и программирование Одна подпрограмма может вызывать другую. Программист сам принимает такое решение, руководствуясь только одним правилом: если подпрограмма А вызывает подпрограмму B, то подпрограмма B должна быть описана раньше подпрограммы А. Мы уже говорили о том, что процедура, в отличие от функции, не возвращает значение. Рассмотрим пример процедуры. program p1; var n, k: integer; procedure print(m: integer); var i: integer; begin for i := 1 to m do write('*'); writeln; end; begin write('Введите n: '); readln(n); for k := 1 to n do print(k); end. Заголовок процедуры начинается с ключевого слова procedure, далее следует её имя, а затем в скобках список параметров. Процедура ничего не возвращает, поэтому указывать тип (как у функции) не нужно. Можно рассматривать процедуру как «чёрный ящик» (рис. 1.6). В нашем случае, написав следующий заголовок: procedure print(m: integer); мы сообщили компилятору, что: 1) мы хотим создать процедуру; 2) мы даём ей имя print, 3) процедура будет принимать один целочисленный параметр - т. Нам понадобилась локальная переменная i, с её помощью мы в теле процедуры т раз выводим символ «*», после чего переводим курсор на новую строку с помощью вызова процедуры writeln без параметров. В этом месте как раз происходит вызов одной процедуры из другой. § 4. Структурирование программ. Подпрограммы 39 В основной программе мы вводим n и n раз вызываем процедуру print. for k := 1 to n do print(k); Результат работы процедуры print для разных значений n показан на рис. 1.7. n = 1 n = 3 n = 5 n = 10 * * * * ** * * ★ ★ ★ * ** * ★ ★ ★ ★ * ** ★ ★ ★ * ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ * ★ ★★★★★ ★ ★ ★ ★ ★ * ★ ★★★★★★ * ★ ★★★★★★★ * ★ ★★★★★★★★ Рис. 1.7 ОБОБЩЕНИЕ НОВЫХ ЗНАНИЙ В программировании удобно использовать подпрограммы, которые можно неоднократно вызывать из основной программы. В языке Паскаль подпрограммы бывают встроенными и определяемыми программистом. По своей структуре подпрограммы похожи на программу и имеют аналогичные разделы. Подпрограммы делятся на функции (возвращают значение) и процедуры (не возвращают значение). Переменные, которые программист определяет в подпрограммах, называются локальными переменными. ПРИМЕНЕНИЕЗНАНИЙ 1. Перечислите встроенные процедуры и функции, которые вы знаете. 2. • Найдите ошибку в подпрограмме и исправьте её. function f1(x: integer): integer; begin f1 := (sqr(x) + x) / 2; end; 3. Напишите программу, вычисляющую числа Фибоначчи с помощью функции. 4. С использованием функции power вычислите сумму: 1 + х2 + _ + xn, где х - вещественное число (х < 10), n - целое число. Числа вводятся с клавиатуры. Подумайте, возможно ли решить эту задачу без функции power. 40 Модуль 1. Алгоритмизация и программирование § 5. Передача параметров в подпрограммы ПОСТАНОВКА ПРОБЛЕМЫ УРОКА На прошлом занятии вы узнали, что такое подпрограммы, и как они устроены. А вы можете привести пример подпрограммы, которая возвращает несколько значений? Получается? Если не получается, то в чём затруднение? Каких знаний или умений не хватает? Сформулируйте основной вопрос урока. Сравните свой вариант с авторским (с. 141 учебника). НЕОБХОДИМЫЕ БАЗОВЫЕ ЗНАНИЯ Что такое подпрограммы? (§ 4) Вспомните всё, что вы узнали о переменных в программировании. (Учебник для 7-го класса, книга 2, модуль 1 и § 1-4 этого учебника.) Вспомните свой опыт работы в интегрированной среде разработки программ. (Учебник для 7-го класса, книга 2, модуль 1.) РЕШЕНИЕ ПРОБЛЕМЫ В предыдущем параграфе мы с вами рассмотрели принципы работы с подпрограммами, разобрались, что они собой представляют, и лишь немного поговорили о том, как основная программа передаёт данные в подпрограммы и как получает от них ответ. Давайте рассмотрим правила взаимодействия основной программы и подпрограмм подробнее. ПЕРЕДАЧА ПАРАМЕТРОВ ПО ЗНАЧЕНИЮ Когда мы с вами обсуждали подпрограммы, мы представляли их как «чёрные ящики», то есть объекты, в которые из основной программы передаются данные с помощью параметров. Рассмотрим пример. § 5. Передача параметров в подпрограммы 41 Код программы Вывод program paraml; var a: integer; procedure p1(b: integer); begin writeln('b=', b); b := b * b; writeln('b=', b); end; begin readln(a); writeln('a=', a); writeln('вызов процедуры'); p1(a); writeln('после вызова процедуры' writeln('a=', a); end. a = 5 вызов процедуры b=5 b=25 после вызова процедуры a=5 Мы вводим значение в переменную а, выводим его, затем передаём это значение в процедуру р1. При вызове процедуры значение переменной а копируется в переменную b. Внутри процедуры мы уже работаем только с переменной b - изменяем её значение и выводим исходное и новое значения. Мы видим, что значение переменной a не меняется во время работы процедуры. Такой способ передачи параметров называется передачей по значению. ИСПОЛЬЗОВАНИЕ ГЛОБАЛЬНЫХ ПЕРЕМЕННЫХ Посмотрите на следующий пример. Код программы Вывод program param2; var a: integer; procedure p2(b: begin writeln('b=', b := b * b; writeln('b=', integer) b) writeln('внутри процедуры' writeln('a=', a); a := a + 5; end; begin readln(a); writeln('a=', a); writeln('вызов процедуры') a=5 вызов процедуры b=5 b=25 внутри процедуры a=5 после вызова процедуры a = 10 42 Модуль 1. Алгоритмизация и программирование Код программы Вывод p2(a); writeln('после вызова процедуры'); writeln('a=', a); end. В этом примере мы выводим значение переменной а в процедуре p2. Кроме того, внутри процедуры мы изменяем значение переменной а. Всё это можно сделать, поскольку переменная а является глобальной по отношению к данной процедуре. Как мы говорили в предыдущем параграфе, глобальные переменные (в данном случае переменная а) описываются в основной программе, они доступны и в ней, и в подпрограмме. Обратите внимание, что после выполнения процедуры и возврата в основную программу переменная а имеет изменённое значение. Может получиться так, что программист в качестве имени локальной переменной в подпрограмме будет использовать имя, совпадающее с именем глобальной переменной. В этом случае при обращении к переменной приоритет будет иметь локальная переменная. В следующем примере в процедуре производится работа с локальной переменной а, значение глобальной переменной а не меняется во время работы процедуры. Код программы Вывод program param3; var a: integer; procedure p3(b: integer); var a: integer; begin a := 10; a=5 writeln('b=', b); вызов процедуры b := b * b; b=5 writeln('b=', b); b=25 writeln('внутри процедуры'); внутри процедуры writeln('a=', a); a=10 end; после процедуры begin a=5 readln(a); writeln('a=', a); writeln('вызов процедуры'); p1(a); writeln('после процедуры'); writeln('a=', a); end. § 5. Передача параметров в подпрограммы 43 ПЕРЕДАЧА ПАРАМЕТРОВ ПО ССЫЛКЕ Рассмотрим пример. Код программы Вывод program param4; var a: integer; procedure p4(var b: integer) begin writeln('b=', b); b := b * b; writeln('b=', b); writeln('внутри процедуры' writeln('a=', a); end; begin readln(a); writeln('a=', a); writeln('вызов процедуры') p4(a); writeln('после процедуры') writeln('a=', a); end. a = 5 вызов процедуры b=5 b=25 внутри процедуры a = 2 5 после процедуры a = 2 5 Посмотрите, какая интересная картина получается! Во-первых, у нас появилось слово var перед переменной b в описании параметров процедуры. Во-вторых, каким-то образом внутри процедуры глобальная переменная a получила то же значение, что и локальная b. И после завершения работы процедуры переменная a своё новое значение сохранила. Что же произошло? Ключевое слово var перед параметром b означает, что при вызове процедуры p4(a) подпрограмме будет передано не значение переменной а, а её адрес (ссылка на неё). Подпрограмма будет производить действия с глобальной переменной a. Переменная b в этом случае как бы прикрепляется, связывается с переменной а. Теперь эти переменные неотделимы друг от друга. Если меняется а, то меняется и b, а если меняется b, то своё значение изменит и а. Такой способ передачи параметров называется передачей по ссылке. Фактически при передаче параметра по значению в подпрограмму передаётся копия переменной, а при передаче по ссылке - сама переменная. У вас может возникнуть вопрос: зачем нужен такой сложный способ передачи параметров? Давайте рассмотрим следующую задачу: написать функцию, в которую передаются два целых числа а и b и которая возвращает одновременно остаток от деления а на b и целую часть этого же деления. Как же такое сделать? Ведь функция возвращает только одно значение. Здесь нам как раз поможет способ передачи параметров по ссылке. 44 Модуль 1. Алгоритмизация и программирование Код программы Вывод program param5; var a, b, div_, mod_: integer; function super(a, b: integer; var d: integer): integer; begin d := a div b; super := a mod b; end; begin writeln('Введите целые числа a и b' write('a='); readln(a); write('b='); readln(b); mod_ := super(a, b, div_); writeln('a div b = ', div_); writeln('a mod b = ', mod_); End. Введите целые числа a и b a=5 b=2 a div b = 2 a mod b = 1 Мы описали четыре глобальные переменные: a и b - для хранения вводимых чисел, div_ и mod_ - для хранения результата. Также мы создали функцию super со следующим заголовком: function super(a, b: integer; var d: integer): integer,- В эту функцию мы будем передавать наши числа a и b, а также ещё и параметр d, в котором будем получать целую часть от деления a на b. А функция будет возвращать остаток от деления a на b. Вызывается функция super следующим образом: mod_ := super(a, b, div_)- Таким образом, после вызова функции в переменной mod_ появится результат (значение) работы функции, а в переменной div_ - значение, которое приобрела переменная d внутри функции, поскольку она передавалась по ссылке. Итак, нам удалось получить два значения: одно - возвращённое функцией, второе - в глобальной переменной. Посмотрите и проанализируйте результат работы программы. Такой метод очень часто применяется в программировании. § 5. Передача параметров в подпрограммы 45 ОБОБЩЕНИЕ НОВЫХ ЗНАНИЙ В языке Паскаль существуют разные способы передачи параметров в подпрограммы. Первый способ - передача параметров по значению. В подпрограмму передаётся значение глобальной переменной, сама глобальная переменная при этом не изменяется. Второй способ - использование глобальных переменных. В подпрограммах можно использовать любые глобальные переменные, описанные в основной программе. Замечание: старайтесь использовать этот метод как можно реже. Третий способ - передача параметров по ссылке. В подпрограмму передаётся адрес глобальной переменной. Параметр связывается с передаваемой глобальной переменной. Работа в подпрограмме производится с глобальной переменной, и она изменяется. ПРИМЕНЕНИЕ ЗНАНИЙ 1. Какие способы передачи параметров в подпрограммы вы узнали? 2. • Разберите предлагаемую программу по шагам и ответьте, что будет выведено на экран. program question,-var a, b, c: integer- procedure p(var x, y: integer- z: integer), var a: integer-begin a := 5- c := 4- y := x + y-end- procedure q(var x, y, z: integer)-var a: integer-begin a := 5- c := 4- y := x + y-end- procedure r(x: integer- var y, z: integer)- 46 Модуль 1. Алгоритмизация и программирование var a: integer,-begin a := 5- c := 4- y := x + y-end-begin a := 2- b := 5- c := -2- p(a, b, c)- writeln('a=', a, '- b=', b, '- c=', c)- a := 1- b := 10- c := -2- q(a, b, c)- writeln ( ' a=' , a, '- b=', b, '- c=', c)- a := 1- b := 5- c := -2- r(a, b, c)- writeln('a=', a, '- b=', b, '- c=', c)-end. Проверь себя Задание 1 Напишите следующую программу на языке Паскаль. Даны целые числа А, В и С. Если А < В < С, то все числа замените их квадратами, если А > B> C, то каждое число замените наибольшим из них, в противном случае смените знак каждого числа. Задание 2 С клавиатуры вводится число n, а за ним - массив из n элементов. Найдите номер последнего по счёту положительного элемента массива. Задание 3 С клавиатуры вводится число n. Напишите программу с функцией вычисления факториала, которая вычисляет сумму: 1+2!+3!+4!+5!+6!+7!+ ... . 48 ПРИМЕНЕНИЕ ЗНАНИЙ [необходимый уровень) Задание 1 Напишите программу, которая строит таблицу истинности для логического выражения (not а) or (not b). Решить эту задачу вам помогут примеры, приведённые в § 1. Задание 2 С клавиатуры вводится число n, за ним - массив из n целых чисел и число х. Найдите количество элементов массива, значения которых равны х ■ х. Задание 3 Массив целых вводится с клавиатуры до нуля. Ноль при этом не учитывается. Посчитайте количество отрицательных чисел в массиве. Задание 4 Массив действительных чисел вводится с клавиатуры до нуля, при этом ноль не учитывается. Напишите функцию, которая будет возвращать среднее значение элементов массива. В основной программе выведите это число. Подсказка: опишите массив как глобальную переменную. Задание 5 Напишите программу, в состав которой входит процедура print, выводящая следующую картинку: Задание 6 С клавиатуры вводится число n - количество строк в треугольнике. Затем оно передаётся в процедуру print, которая должна вывести на экран, например при n = 4, следующую картинку: 2 2 3 2 3 I 49 ПРИМЕНЕНИЕ ЗНАНИЙ [повышенный уровень) Задание 1 Напишите программу, которая строит таблицу истинности для логической формулы (not а) or (not b) or c. Решить эту задачу вам помогут примеры, приведённые в § 1. Подумайте, сколько вложенных циклов вам понадобится. Задание 2 С клавиатуры вводится число n, а за ним - массив из n элементов. Найдите и выведите на экран произведение всех положительных элементов массива с чётными индексами. Задание 3 Целые числа вводятся до тех пор, пока не будет введён ноль. Верно ли, что все числа равны? Подсказка: массив в этой задаче использовать не надо, а вот логические переменные вам помогут. Задание 4 Напишите программу, содержащую функцию, вычисляющую квадрат натурального числа, используя следующую закономерность: 12 = 1; 22 = 1 + 3; 32 = 1 + 3 + 5; 42 = 1 + 3 + 5 + 7. Задание 5 С клавиатуры вводится натуральное число n, а за ним - массив действительных чисел из n элементов. Напишите функцию, которая вычисляет разность между максимальным и минимальным элементами массива. Подсказка: опишите массив как глобальную переменную. Постарайтесь для поиска максимума и минимума использовать один цикл. Задание 6 С клавиатуры вводится число n - число строк в треугольнике. Затем оно передаётся в процедуру print, которая должна вывести на экран, например при n = 4, следующую картинку: 4 3 4 2 3 1 2 4 3 ПРИМЕНЕНИЕ ЗНАНИЙ [максимальный уровень) Задание 1 Напишите программу, которая строит таблицу истинности для логического выражения: (а or (not b)) and (с or (not d)) and (not a). Задание 2 С клавиатуры вводится натуральное число, не превышающее Ю 000, - номер года. Напишите функцию, которая определяет, является ли данный год високосным. Напомним, что високосными являются года, номера которых кратны 4, но не кратны 100, а также года, номера которых кратны 400. Например, 2000 год - високосный, поскольку 2000 делится на 400, а 1 900 год - не високосный, поскольку 1900 делится на 4, но делится и на 100 тоже. Функция должна возвращать значение либо «истина», либо «ложь». Задание 3 Напишите программу, в которой вводится натуральное число n. Затем это число передаётся в функцию test, в которой последовательно с клавиатуры вводятся n натуральных чисел. Функция должна вернуть значение «истина», если все введённые числа являются полными квадратами каких-либо других чисел, и значение «ложь», если это не так. Например, для последовательности 1,4, 81,16 должно быть возвращено значение «истина», а для 1, 6, 25 - «ложь». Задание 4 С клавиатуры вводится число n, а за ним - массив целых чисел из n элементов. Напишите процедуру, которая ищет и выводит два самых больших числа в массиве, при условии, что в массиве есть как минимум два различных элемента. Например, в массиве 1,3, 9, 5, 7 два самых больших числа - это 9 и 7, а в массиве 1, 3, 3, 3 - это 1 и 3. Подсказка: объявите массив как глобальную переменную. Задание 5 С клавиатуры вводится число n, а за ним - массив из n чисел. Упорядочите любым способом левую половину массива по возрастанию, а правую - по убыванию. Если в массиве нечётное количество элементов, то центральный элемент отнесите к правой части. Выведите итоговый массив. Задание 6 С клавиатуры вводится число n. Напишите программу с функцией вычисле- .X. ,111111 ния факториала, которая вычисляет сумму: 1+2!-3!+4!-'5!+"B!-?"! + .. . В этой сумме знаки слагаемых чередуются. Вычисление факториала должно быть оформлено отдельной функцией. Итоговая проверочная работа Задание 1 а) Что будет выведено на экран в результате работы программы? program d; var a, b: integer; procedure s1; var a, c: real; begin a := 2.5; b := 5; c := 0; write(a, ' b, ' c); end; begin a := 2; b := 7; write(b, ' '); s1; writeln(' ', a); end. б) Напишите функцию sum вида function sum(n: integer) : real, которая вычисляет и возвращает следующую сумму: 1 + 1/2 + 1/3 + ... + 1/n. в) С клавиатуры вводятся три числа. Напишите программу, которая проверяет, могут ли эти числа быть длинами сторон прямоугольного треугольника. Выведите «да», если могут, и «нет» в противном случае. Задание 2 а) Что будет выведено на экран в результате работы программы? program d; var a, c: integer; procedure s2 (var b: integer); var d, c: real; begin d := a / 5; c := d + 3; write(a, ' '); b := 5; write(d); end; 52 begin a := 7; c := a mod 2; s2(a); writeln(' a); end. б) Напишите функцию perfect вида function perfect(n: integer): boolean, которая возвращает значение «истина», если число n является совершенным, то есть равным сумме всех своих делителей. Например, числа 6 = 1 + 2 + 3 и 28 = 1 + 2 + 4 + 7 + + 14 - совершенные. в) C клавиатуры вводятся действительные числа a и b. Если a и b отрицательны, то каждое значение замените его модулем (вам поможет встроенная функция abs); если отрицательно только одно из них, то удвойте оба значения; если оба значения неотрицательны и ни одно из них не принадлежит отрезку [0,5; 2,0], то уменьшите оба значения в 10 раз; в остальных случаях оставьте числа без изменения. Выведите результат. Задание 3 а) Найдите ошибки в функции и исправьте их. function error (a: real); var z: integer; begin z := a mod 4; write(z); a := z; end; б) Напишите функцию friend вида function friend (a, b: integer): boolean; Функция должна определять, являются ли данные числа дружественными. (Подсказка: Два натуральных числа называются дружественными, если каждое из них равно сумме всех натуральных делителей другого. При этом само число в качестве делителя не рассматривается.) в) С клавиатуры вводятся вещественные положительные числа а, b, c, d. Выясните, можно ли прямоугольник с длинами сторон а и b уместить внутри прямоугольника с длинами сторон c и dтак, чтобы каждая из сторон одного прямоугольника была параллельна или перпендикулярна каждой стороне второго прямоугольника. § 6. Знакомство с математической логикой: продолжение § 6. Знакомство с математической логикой: продолжение ПОСТАНОВКА ПРОБЛЕМЫ УРОКА Вы читали детективные романы, не так ли? Про Шерлока Холмса, Эркюля Пуаро, комиссара Мегрэ? А вы никогда не задумывались, каким же образом этим детективам удавалось распутывать сложные ситуации так же просто и эффектно, как клубок ниток? Им всегда помогал логический способ доказательств их предположений. Представьте, что вам известны некоторые факты. Возможно ли на их основании чётко построить логическое доказательство? Или их мало? Или эти факты противоречат друг другу? Как вы думаете, существуют ли правила решения логических задач? Сформулируйте основной вопрос урока. Сравните свой вариант с авторским (с. 141 учебника). НЕОБХОДИМЫЕ БАЗОВЫЕ ЗНАНИЯ Что вы уже знаете о математической логике? (§ 1) РЕШЕНИЕ ПРОБЛЕМЫ В § 1, посвящённом первому знакомству с математической логикой, мы рассмотрели три основные логические операции: И, ИЛИ, НЕ. С помощью этих операций можно записать любое высказывание. (Вспомните, что такое высказывание.) Однако часто бывает удобнее использовать и другие логические операции. Рассмотрим их. ОПЕРАЦИЯ «СЛЕДОВАНИЕ» Рассмотрим высказывание: «Если завтра будет солнце, то я поеду за город». Оно состоит из двух простых высказываний: «Завтра будет солнце» и «Я поеду за город», которые связаны между собой связкой «Если _, то». Этой связке соответствует логическая операция «следование». Если мы обозначим первое простое высказывание буквой а, а второе - буквой b, то на языке математической логики наше сложное высказывание будет выглядеть так: a ^ b и читаться: «из a следует b». Дадим определение операции «следование». Определение. Значение операции a ^ b - «ложь» в том случае, когда a истинно, а b ложно, и «истина» - в противном случае. Как записать на языке математической логики следующее высказывание: «Если завтра не будет светить солнце, то Вася не пойдёт гулять»? 53 54 Модуль 1. Алгоритмизация и программирование 1) Обозначим латинскими буквами простые высказывания: a - «Завтра будет светить солнце»; b - «Вася пойдёт гулять». Заметьте, что простым высказыванием является именно «Завтра будет светить солнце», а не «Завтра не будет светить солнце», поскольку второе высказывание - это применение к первому логической операции (НЕ), следовательно, оно уже не простое. 2) Запишем наше сложное высказывание с помощью логических операций: (НЕ а) ^ (НЕ b). Построим таблицу истинности операции «следование». a b a ^ b ложь ложь истина ложь истина истина истина ложь ложь истина истина истина Мы уже сказали, что с помощью логических операций И, ИЛИ, НЕ можно записать любое высказывание. Это означает, что и операцию «следование» можно выразить через них. Давайте попробуем это сделать. Рассмотрим логическое выражение (НЕ a) ИЛИ b и построим для него таблицу истинности. Сколько у нас в выражении переменных? Две. Значит, строк в нашей таблице будет столько же, сколько и в таблице любой бинарной операции - 4. Но столбцов будет немного больше. Сначала мы вычислим значение операции НЕ а, а потом выполним операцию ИЛИ над значениями в столбцах «НЕ а» и «b». a b НЕ a (НЕ а) ИЛИ b ложь ложь истина истина ложь истина истина истина истина ложь ложь ложь истина истина ложь истина Сравните получившийся столбец-результат со столбцом-результатом операции «следование». Они совпадают на одинаковых наборах (a, b). Таким образом, мы с вами получили важнейший результат: для того чтобы доказать, что логические выражения равны, необходимо построить их таблицы истинности и сравнить итоговые результаты. Итак, a ^ b = (НЕ а) ИЛИ b. § 6. Знакомство с математической логикой: продолжение 55 ОПЕРАЦИЯ «ЭКВИВАЛЕНЦИЯ» Рассмотрим высказывание: «Снег в России выпадает тогда, когда наступает зима^. Это высказывание состоит из двух простых высказываний: «Снег в России выпадает» и «Наступает зима», а также связки «тогда, когда» (связка может формулироваться ещё и так: «тогда и только тогда, когда»). Логическая операция, соответствующая этой связке, называется «экви-валенция». На языке математической логики она обозначается так: a ~ b и читается: «a эквивалентно b». Определение. Значение операции a ~ b - «истина» в том случае, когда a и b имеют одинаковые значения, и «ложь» - в противном случае. Построим таблицу истинности для операции «эквиваленция». a b a ~ b ложь ложь истина ложь истина ложь истина ложь ложь истина истина истина Выразим операцию «эквиваленция» через операции И, ИЛИ, НЕ: a ~ b = (a И b) ИЛИ ((НЕ a) ИЛИ (НЕ b)). ОПЕРАЦИЯ «ИСКЛЮЧАЮЩЕЕ ИЛИ» Рассмотрим высказывание: «Я съем либо апельсин, либо яблоко». В отличие от операции ИЛИ, в случае применения которой оба исхода могут случиться одновременно, в данном случае может произойти либо первый вариант, либо второй, но не два одновременно. Логическая операция, соответствующая связке «либо _, либо» («или_, или»), называется «исключающее ИЛИ» («строгое ИЛИ») и на языке математической логики обозначается ©. Определение. Значение операции a © b - «истина» в том случае, когда a и b имеют разные значения, и «ложь» - в противном случае. Построим таблицу истинности для операции «исключающее ИЛИ». a b a © b ложь ложь ложь ложь истина истина истина ложь истина истина истина ложь Выразим операцию «исключающее ИЛИ» через операции И, ИЛИ, НЕ: a © b = (a И (НЕ b)) ИЛИ ((НЕ a) И b). 56 Модуль 1. Алгоритмизация и программирование ОБОЗНАЧЕНИЯ ОСНОВНЫХ ЛОГИЧЕСКИХ ОПЕРАЦИЙ Обратите внимание, что для обозначения рассмотренных в этом параграфе операций мы применяли специальные значки. Для основных операций И, ИЛИ, НЕ тоже существуют обозначения: Операция Обозначение И a & b ИЛИ a / b НЕ a Примечание. Операцию ИЛИ обозначают также «+». Тогда зависимости рассмотренных в параграфе логических операций от основных операций будут выглядеть следующим образом: a=а/b a ~ b = a&b / а &Ь а © b = a&b / b&a ПОИГРАЕМ В ШЕРЛОКА ХОЛМСА Давайте немного поиграем в Шерлока Холмса и попробуем применить математическую логику для решения логических задач. Задача 1. На вопрос сыщика, кто из троих задержанных преступников взломал сейф, был получен ответ: «Если взломал первый, то взламывал и второй, но неверно, что если взломал третий, то взламывал и второй». Кто из преступников взломал сейф? Любые логические задачи надо решать не спеша и последовательно. Сначала выделим из нашего исходного высказывания два поменьше: 1) «Если сейф взломал первый, то взламывал и второй»; 2) «Неверно, что если сейф взламывал третий, то взламывал и второй». Теперь обозначим буквами простые высказывания, из которых состоят эти два сложных: 1) a - «Сейф взломал первый преступник»; 2) b - «Сейф взломал второй преступник»; 3) с - «Сейф взломал третий преступник». Давайте запишем на языке математической логики известные нам высказывания. 1) Если сейф взломал первый, то взламывал и второй: a ^ b. 2) Неверно, что если сейф взламывал третий, то взламывал и второй: c ^ b. Второе высказывание состоит из отрицания к операции «следование». Нам известно, что оба наших высказывания выполняются одновременно. § 6. Знакомство с математической логикой: продолжение 57 Это значит, что если мы применим к этим высказываниям операцию И, то её результат должен быть истинным. Поэтому нам остаётся проверить, при каких же значениях а, b и c значение выражения (а ^ b) & c ^b будет равно «истина». Для этого построим таблицу истинности для указанного логического выражения. В этой таблице истинности будет 8 строк, поскольку у нас 3 переменные. (Вспомните, сколько будет строк в таблице истинности для логического выражения, содержащего 2 переменные.) Для краткости будем обозначать в таблице значения «истина» и «ложь» как «И» и «Л» (рис. 1.8). a b c a ^ b c ^ b c^b (а^ b) & c^b Л Л Л И И Л Л Л Л И И Л И И Л И Л И И Л Л Л И И И И Л Л И Л Л Л И Л Л И Л И Л Л И Л И И Л И И Л Л И И И И И Л Л Рис. 1.8 Как вы видите, итоговое логическое выражение принимает значение «истина» только в одной строке (в таблице она выделена синим цветом). Посмотрим, какая из наших переменных истинна в этом случае. Это переменная с. Поэтому сыщик будет абсолютно точно уверен, что сейф взломал третий преступник, и остальных надо пока отпустить. Задача 2. По обвинению в ограблении банка перед судом предстали Джон, Билл и Марк. Следствием установлено, что: 1) если Джон не виновен или Билл виновен, то Марк виновен; 2) если Джон не виновен, то Марк не виновен. Судья никак не мог рассудить это дело и обратился к Холмсу. Тот подумал немного и сказал: «Могу сказать точно: Джон виновен!» Как же он это сделал? Обозначим буквами простые высказывания, из которых состоят сложные: 1) d - «Джон виновен»; 2) b - «Билл виновен»; 3) m - «Марк виновен». Запишем на языке математической логики данные задачи: 1) (d / b) ^m; 2) d ^m. Рассмотрим операцию И над нашими условиями: [(d/ b) ^m] & (d -^m). 58 Модуль 1. Алгоритмизация и программирование Построим для полученного логического выражения таблицу истинности и обратим внимание на строки, где его значение истинно (рис. 1.9). d b m d m d + b (d + b) ^m d ^m [(d + b) ^m] & (d ^m] Л Л Л И И И Л И Л Л Л И И Л И И Л Л Л И Л И И И Л И Л Л И И И Л И И Л Л И Л Л Л И Л И И И И Л И Л Л Л И И И И И Л Л И И Л И Л И И И Л Л И Л И Л Рис. 1.9 В обеих строках, где значение итогового выражения истинно, переменная d принимает значение «истина», переменная b - значение «ложь», а m принимает оба значения. Это означает, что Джон точно виновен, а Билл невиновен. А вот про Марка, к сожалению, ничего точно сказать нельзя. Для этого нам не хватает данных. ОБОБЩЕНИЕ НОВЫХ ЗНАНИЙ В § 1 вы изучили три основные логические операции: И, ИЛИ, НЕ. В этом параграфе вы познакомились с логическими операциями «следование», «эквиваленция», «исключающее ИЛИ». Все логические операции можно выразить через три основные. Для решения логических задач необходимо: 1. Обозначить буквами все простые высказывания, из которых состоят сложные, приведённые в условии. 2. Записать на языке математической логики сложные высказывания. 3. Применить операцию И ко всем высказываниям из условия. 4. Построить для полученной формулы таблицу истинности и проанализировать результат. ПРИМЕНЕНИЕ ЗНАНИЙ 1. Перечислите логические операции, которые вы знаете. 2. • Докажите правильность равенств, выражающих операции «исключаю- щее ИЛИ» и «эквиваленция» через три основные логические операции. 3. • Решите ещё одну логическую задачу про Шерлока Холмса. § 6. Знакомство с математической логикой: продолжение 59 Вернувшись домой, Холмс позвонил доктору Ватсону. - Говорит Холмс. Есть новости? - Да. Поступили сообщения от инспекторов Скотленд-Ярда: 1) Джонс установил, что если Смит был пьян, то Джек убийца, или Смит лжёт. 2) Гаррисон считает, что Джек убийца, или Смит не был пьян, и убийство произошло после полуночи. 3) Инспектор Лейстрейд просил передать Вам, что если убийство произошло после полуночи, то Джек убийца, или Смит лжёт. 4) Затем звонил^ - Всё. Спасибо. Этого достаточно. Шерлок Холмс положил трубку. Он знал, что трезвый Смит никогда не лжёт. Теперь он знал всё. Что же знал Холмс? 60 Модуль 1. Алгоритмизация и программирование § 7. Использование констант и собственных типов ПОСТАНОВКА ПРОБЛЕМЫ УРОКА Скажите, вам больше нравятся удобные или неудобные вещи? Возьмем, например, обувь. Согласитесь, что в удобной обуви ходить гораздо приятнее. Вопрос удобства можно рассматривать и по отношению к программам. Они могут быть написаны так, что любая работа с ними программиста может быть удобной, может быть не очень удобной, а может быть совсем неудобной. Заметьте, что мы всё время говорим о хорошем стиле программирования. • Какая важная проблема здесь поставлена? Сформулируйте основной вопрос урока. Сравните свой вариант с авторским (с. 141 учебника). НЕОБХОДИМЫЕ БАЗОВЫЕ ЗНАНИЯ Вспомните свои умения программирования на языке Паскаль. Что понимается под хорошим стилем программирования? (Учебник для 7-го класса, книга 2, модуль 1, § 2.) Вспомните свой опыт работы в интегрированной среде разработки программ. (Учебник для 7-го класса, книга 2, модуль 1.) Что такое отладка программ и как она выполняется? (Учебник для 7-го класса, книга 2, модуль 1, § 7.) РЕШЕНИЕ ПРОБЛЕМЫ КОНСТАНТЫ Константа - это такой объект, который никогда не меняет своего значения. Само слово «константа» происходит от латинского constanta, что означает «постоянная, неизменная». Где же в программировании применяются константы? Представьте себе такую ситуацию: вы пишете программу, которая анализирует температуру за окном, постоянно сравнивает её с эталоном и сообщает об отклонениях. Допустим, вам сказали, что эталон - это 20°С, и вы написали программу, в тексте которой много раз присутствует сравнение значения текущей температуры с 20. И тут в момент, когда вы уже закончили работу, заказчик вам говорит: «Теперь у нас эталон - 22°С». И вам не остаётся ничего иного, как исправлять везде числа с 20 на 22. А если таких исправлений сотни? Неудобно, правда? Но не расстраивайтесь! Из этой ситуации есть выход. § 7. Использование констант и собственных типов Мы можем описать константу, у неё есть имя и значение. Константа очень похожа на переменную, её можно использовать в операциях языка. Единственное ограничение заключается в том, что константу изменять нельзя. Константы описываются в разделе const, который располагается после ключевого слова program. Этот раздел не является обязательным - может отсутствовать в программах. Начинается он с ключевого слова const. Затем следуют описания констант в формате: <Имя_константы> = <Значение_константы> const MAX = 5; MIN = 2; Etalon = 20; Рассмотрим фрагмент программы анализа температуры, использующей константы. program c1; const etalon = 20; begin for i := 1 to n do if A[i]<>etalon then writeln('Внимание! Несоответствие эталону!') 61 end. Обратите внимание на то, как константы похожи на переменные. Что мы теперь будем делать в ситуации, когда заказчик попросит нас изменить значение эталона? Мы просто поменяем значение константы etalon в разделе const. Очень часто константы используются в описаниях массивов для указания индексных границ. Выглядит это следующим образом: const MAX = 100; var a: array [1..MAX] of integer; Такой способ описания массивов относится к хорошему стилю программирования. 62 Модуль 1. Алгоритмизация и программирование КАК ПЕРЕДАТЬ В ПОДПРОГРАММУ МАССИВ? Давайте попробуем передать в подпрограмму массив таким же образом, как мы передавали в неё переменные. procedure test(a: array [1..100] of integer); begin end; При запуске такой программы вы получите ошибку: Program1.pas(4): Тип параметра или возвращаемого значения не может быть описанием записи или описанием массива с границами Дело в том, что для передачи массивов в подпрограмму мы должны назвать тип массива по-другому, одним словом. Это делается в специальном разделе программы, который называется type. РАЗДЕЛ TYPE В разделе type находятся описания собственных типов, то есть типов, которые создает сам программист. Раздел type располагается сразу после раздела const, если он есть в программе, а при отсутствии описания констант - после ключевого слова program. Этот раздел необязателен, как и раздел const, но при использовании массивов в программах хорошим стилем является его наличие. Начинается раздел ключевым словом type. Затем следуют описания типов в формате: <имя типа> = <описание типа> После такого описания вновь созданный тип можно использовать наравне со встроенными типами языка, такими как integer и real. Рассмотрим пример программы. program t1; type my_array = array [1..100] of integer; var a: my_array ; i, n: integer; procedure print(b: my_array ; n: integer); var i: integer; § 7. Использование констант и собственных типов begin for i := 1 to n do write(b[i], ' '); writeln; end; begin write('Введите количество элементов в массиве: '); readln(n); for i := 1 to n do begin write('a[', i, ']='); readln(a[i]); end; print(a, n); end. В разделе type мы описали новый тип, который назвали my_array. Правила именования типов такие же, как и правила именования переменных. (Вспомните их.) Тем самым мы сообщили программе, что теперь под типом my_array нужно понимать массив из 100 целых чисел. • Проанализируйте приведённую программу. Что она делает? Теперь мы можем использовать это имя в любых местах программы, где описываются переменные, в том числе и в описании параметров подпрограмм. Массивы можно передавать в подпрограммы и по ссылке. Принцип остаётся таким же, что и для обычных переменных. При изменении массива, описанного в подпрограмме, будет изменяться и глобальный массив. 63 ОБОБЩЕНИЕ НОВЫХ ЗНАНИЙ Для упрощения модернизации программ, а также для того, чтобы программы легко читались, применяются константы. Константы описываются в разделе const, который располагается после ключевого слова program. Использование констант не является обязательным. Работа с константами очень похожа на работу с переменными. Отличие заключается в том, что константу нельзя изменять. Использование констант в описании массивов относится к хорошему стилю программирования. Программист может создавать свои собственные типы, описания которых размещается в разделе type, который находится после раздела const. Использование собственных типов не является обязательным, кроме случая передачи массивов в подпрограммы. 64 Модуль 1. Алгоритмизация и программирование ПРИМЕНЕНИЕ ЗНАНИИ 1. Зачем нужны константы в программе на языке Паскаль? 2. • Посмотрите на фрагмент программы. Что делает процедура р? program p1; const MAX = 100; type my_array = array [1..MAX] of integer; var A: my_array; l: integer; procedure p(var M: my_array; n: integer); var i: integer; begin for i := 1 to n do if (M[i] mod 2 <> 0) then M[i] := 0; end; 3. Напишите программу на языке Паскаль с функцией f, в которую передается массив вещественных чисел и которая вычисляет сумму значений элементов этого массива. § 8. Работа с упорядоченными массивами 65 § 8. Работа с упорядоченными массивами ПОСТАНОВКА ПРОБЛЕМЫ УРОКА Вообразите, что вы пришли в библиотеку и перед вами находится большой алфавитный каталог. Этот каталог можно представить в виде массива, элементы которого упорядочены по алфавиту. Но даже если бы это было не так, вы уже умеете упорядочивать массивы и смогли бы исправить эту оплошность. И вы знаете, что в упорядоченном массиве искать нужные данные гораздо эффективнее. А почему эффективнее? Как вы думаете, какие именно алгоритмы поиска позволяет выполнять упорядоченный массив? Много ли их? Сформулируйте основной вопрос урока. Сравните свой вариант с авторским (с. 141 учебника). НЕОБХОДИМЫЕ БАЗОВЫЕ ЗНАНИЯ Вспомните свои навыки работы с массивами. (§ 2-3 и учебник для 7-го класса, книга 2, модуль 1, § 8-9.) Вспомните свой опыт работы в интегрированной среде разработки программ. (Учебник для 7-го класса, книга 2, модуль 1.) РЕШЕНИЕ ПРОБЛЕМЫ ЭФФЕКТИВНЫЙ АЛГОРИТМ ПОИСКА Мы уже говорили, что упорядочивание массивов даёт нам большие преимущества при работе с данными. Давайте посмотрим, как осуществить поиск в отсортированном по неубыванию массиве. Итак, представьте, что перед вами на столе лежат N пронумерованных от 1 до N шариков, причём номера расположены по неубыванию. И ваш друг загадал число от 1 до N. Ваша задача - найти тот шарик, номер которого загадал друг, или сказать, что такого шарика у вас нет. Как же это сделать? Для определённости положим, что шарики пронумерованы от 1 до 20. Поделите общее количество шариков пополам и посмотрите на «центральный» шарик. Он будет иметь номер 10. Спросите вашего друга: «Ты загадал номер 10?». Если он ответит положительно, то это означает, что вы нашли то, что искали. Если ответ отрицательный, то спросите: «Загаданный номер больше 10?» Если он ответит «да», то вы будете искать нужный шарик справа от центрального, если «нет» (номер меньше 10), то слева. Этот принцип применим только в случае упорядоченного массива, поскольку если загаданное число больше центрального, то находиться оно может 66 Модуль 1. Алгоритмизация и программирование только справа от него. Ведь все элементы, расположенные левее центра, заведомо его меньше. Допустим, ваш друг сказал, что загаданный шарик имеет номер больше 10, поэтому вам нужно рассматривать часть массива от 11 до 20. Опять посмотрите на центральный шарик. Он будет иметь номер 15. Снова задайте вопрос другу: «Я нашёл твоё загаданное число?» «Нет, - ответит друг, - оно меньше 15». Не беда. Значит, это число находится левее 1 5. Рассмотрите часть массива от 11 до 14. Возьмите центральный шарик - с номером 12. «Да! - ответит ваш друг. - Ты угадал!» Описанный способ поиска называется двоичным (бинарным), поскольку мы всё время делим массив на две части. Причём эти две части могут быть неравными. Например, ничего не помешает нам разделить массив не пополам, а в отношении один к трём. От способа деления зависит только скорость поиска. В нашем алгоритме мы будем придерживаться деления пополам, и делать это будем так: сложим номер левой границы и номер правой границы и разделим сумму нацело на два. (1 + 20) div 2 = 10, (11 + 20) div 2 = 15, (11 + 14) div 2 = 12. Сравните получившиеся числа с номерами центральных шаров из примера. Когда мы понимаем, что нам надо рассмотреть начальную («левую») часть массива, то объявляем в качестве новой правой границы уменьшенный на 1 номер центрального элемента, в случае перехода к «правой» части массива новой левой границей становится увеличенный на 1 номер центрального элемента (центр - 10, следовательно, новая левая граница - 11; центр - 15, следовательно, новая правая граница - 14). Алгоритм останавливается, если на некотором шаге центральный элемент оказывается равным искомому или в какой-то момент левая граница становится больше правой. В таком случае искомого элемента в массиве нет. Рассмотрим ещё один пример. Пусть задан массив: 1,3, 5, 6, 8, 10, 15, 25. Он упорядочен по неубыванию. Необходимо найти индекс элемента со значением 5. Алгоритм поиска будет следующим: 1. В массиве 8 элементов, поэтому изначально левая граница будет равна 1, а правая - 8. 2. Анализируем центральный элемент. Его номер = (1 + 8) div 2 = 4. Проверяем, равен ли он 5. Нет, не равен: его значение - 6. Поскольку 5 < 6, то дальше будем искать слева от него. 3. Левая граница останется прежней - 1, а правая изменится и станет на 1 меньше, чем значение центрального элемента, то есть 4 - 1 = 3. Левая граница не превысила правую, поэтому мы можем продолжать поиск. § 8. Работа с упорядоченными массивами 67 4. Снова анализируем центральный элемент. Его номер = (1 + 3) div 2 = 2. Его значение - 3. 5 > 3, следовательно, будем искать в правой части. 5. Теперь изменяется левая граница. Она будет на единицу больше 2, то есть станет равной 3. Правая же останется без изменения - 3. Левая граница пока не превысила правую. Продолжаем поиск. 6. Ищем центр - (3 + 3) div 2 = 3. Третий элемент массива имеет значение 5. Ура! Мы нашли искомый элемент. Он имеет индекс 3. Нарисуем блок-схему этого алгоритма (рис. 1.10). Рис. 1.10 68 Модуль 1. Алгоритмизация и программирование В данной блок-схеме переменная l хранит левую границу, а переменная r -правую. Выход из основного цикла (Л[с] # х) and (l< r) возможен или в случае, когда мы нашли элемент (ложно первое логическое выражение), или когда левая граница превысила правую (ложно второе логическое выражение). Итак, мы рассмотрели эффективный алгоритм поиска элемента в упорядоченном массиве. Этот алгоритм не производит полного перебора, как это делает линейный поиск, однако всё же существуют случаи, когда линейный поиск работает быстрее. • Как вы думаете, в каких ситуациях линейный поиск работает быстрее, чем бинарный? Эффективность поиска оценивают в среднем. Это означает, что берут множество вариантов заполнения массивов, множество искомых чисел и в каждом случае замеряют время работы алгоритма. Затем берут среднее значение всех вычисленных значений времени, и это значение считается средним значением эффективности алгоритма. После этого остаётся сравнить средние значения различных методов и сделать вывод. В наших примерах мы рассматривали массивы, упорядоченные по неубыванию. Однако сортировка может происходить по любому критерию. Алгоритм в этом случае, конечно, претерпит изменение, но суть его (деление на части и дальнейший поиск в одной из частей) при этом не меняется. СЛИЯНИЕ МАССИВОВ Очень часто встречаются задачи, в которых нужно объединить уже имеющиеся данные из нескольких массивов в один итоговый. Такие задачи называются слиянием данных. В случае неупорядоченных массивов у нас нет никаких вариантов для манёвров. Необходимо добавить элементы второго массива в конец первого и отсортировать результат. Рассмотрим слияние двух упорядоченных массивов. Пускай у нас есть два упорядоченных массива: A = {1,3, 4, 8, 9, 10} и B = {2, 4, 6, 7}. Как вы видите, они упорядочены по неубыванию. Нам нужно сформировать массив С, в котором окажутся все элементы массивов А и В и который будет также упорядочен по неубыванию. Будем хранить в переменной т1 индекс текущего элемента первого массива, в переменной m2 - индекс текущего элемента второго массива, а в переменной m3 — индекс текущего элемента третьего, формируемого, массива. В начале и m1, и m2, и m3 равны 1. Сравним A[m1] и B [m2]. Если A[m1 ] < B [m2], то в С [m3] мы занесём A[m1 ] и ml увеличим на 1, в противном случае в С [m3] мы занесём B [m2] и m2 увеличим на 1. Увеличим m3 на 1. В нашем примере в первый элемент массива C запишется число 1. Будем повторять такое сравнение и запись до тех пор, пока один из массивов не закончится. § 8. Работа с упорядоченными массивами 69 При этом массив С будет последовательно заполняться так: 1 1,2 1.2, 3 1.2, 3, 4 1.2, 3, 4, 4 1.2, 3, 4, 4, 6 1.2, 3, 4, 4, 6, 7 Оставшиеся же элементы из другого массива просто добавим в конец массива C. В результате массив С будет выглядеть так: {1,2, 3, 4, 4, 6, 7, 8, 9, 10}. Главное преимущество этого алгоритма заключается в том, что заполнение массива C происходит за один проход. Здесь нет вложенных циклов, которые присутствуют в алгоритмах сортировки. Подобное преимущество возможно только потому, что массивы, которые мы объединяем в один, уже являются упорядоченными. Поэтому данный алгоритм выполняется очень быстро. Рассмотрим его блок-схему (рис. 1.11). 70 Модуль 1. Алгоритмизация и программирование ОБОБЩЕНИЕ НОВЫХ ЗНАНИЙ Когда массивы данных отсортированы (упорядочены), то алгоритмы поиска и работы с информацией становятся гораздо эффективнее. Бинарный поиск позволяет быстрее, чем линейный, находить элементы в массиве за счёт того, что он делит массив на две части и продолжает при необходимости поиск только в одной из них, в зависимости от критерия поиска. Алгоритм слияния двух массивов позволяет без использования вложенных циклов объединить в один массив данные из двух упорядоченных массивов. ПРИМЕНЕНИЕ ЗНАНИЙ 1. Какие преимущества имеет поиск в упорядоченном массиве по отношению к поиску в неупорядоченном? 2. Что мы подразумеваем, когда говорим про один алгоритм, что он в среднем эффективнее другого? 3. Как надо изменить блок-схему алгоритма бинарного поиска, если известно, что массив упорядочен по невозрастанию? 4. Напишите на языке Паскаль программу, содержащую функцию, которая реализует двоичный поиск элемента в массиве. Функция должна принимать 3 параметра: количество элементов в массиве, сам массив и искомый элемент. Возвращать функция должна номер элемента, если этот элемент в массиве присутствует, или 0, если элемента в массиве нет. Ввод и вывод реализуйте в основной программе. § 9-10. Поговорим об эффективности 71 § 9-10. Поговорим об эффективности ПОСТАНОВКА ПРОБЛЕМЫ УРОКА Ребята на уроке создавали программу, которая помогала рассчитать, как перевезти груз, состоящий из множества коробок, с помощью одной грузовой машины. Когда учитель посмотрел на их решения, то он сказал: «Ваше решение нельзя назвать неверным. Но если бы мне нужно было перевозить вещи, то я обратился бы в другую транспортную компанию. Ваш вариант переезда был бы для меня слишком дорогим». Как вы думаете, почему у учителя могло сформироваться такое мнение? Сформулируйте основной вопрос урока. Сравните свой вариант с авторским (с. 141 учебника). НЕОБХОДИМЫЕ БАЗОВЫЕ ЗНАНИЯ Какова структура программы в языке Паскаль? Как в языке программирования используются циклические конструкции? (§ 3 и учебник для 7-го класса, книга 2, модуль 1, § 5-6.) Вспомните свой опыт работы в интегрированной среде разработки программ. (Учебник для 7-го класса, книга 2, модуль 1.) Вспомните свои навыки работы с массивами. (§ 2, 3, 8 и учебник для 7-го класса, книга 2, модуль 1, § 8-9.) РЕШЕНИЕ ПРОБЛЕМЫ ЭФФЕКТИВНОСТЬ АЛГОРИТМОВ Когда мы начинали разговор о программировании (в 7-м классе), мы говорили о том, что алгоритмов решения одной и той же задачи может быть много. Программист должен выбирать тот способ решения задачи, который в данном случае наиболее эффективен. Понятие эффективности сложное. Часто случается так, что самое простое решение задачи - то, которое первым приходит в голову, бывает самым неэффективным. Задание программисту на разработку алгоритма включает критерии эффективности. Они могут быть такими: 1) программа должна работать быстро; 2) программа должна использовать определённые алгоритмы; 3) программа должна занимать мало ресурсов (памяти или процессора); 4) программа должна содержать определённые синтаксические конструкции и т. д. 72 Модуль 1. Алгоритмизация и программирование При этом часто один критерий противоречит другому. Выбор критерия эффективности алгоритма сродни выбору условий поездки. Представьте, что вы хотите поехать из Москвы в Санкт-Петербург. И тут возникают вопросы: 1) Какое время вы хотите потратить на поездку? Если вам надо попасть в город на Неве за 4 часа, то надо ехать на поезде «Сапсан» или лететь на самолёте. 2) Если вам абсолютно неважно время, затраченное на путь, но вы хотите потратить минимум средств, то ваш выбор однозначен - ночной поезд и плацкартное купе. 3) А если вы едете втроём или вчетвером, то вам выгоден автомобиль. И таких вариантов может быть очень много. Выбирайте. ПОИСК ПРОСТЫХ ЧИСЕЛ В качестве примера поиска эффективного алгоритма рассмотрим следующую задачу: вводится натуральное число a > 2. Необходимо вывести все простые числа на интервале от 1 до а. Как вы думаете, какое первое решение приходит в голову? Вот такое: 1. Начало. 2. Положить X равным 2. 3. Проверить, является ли x простым числом. 4. Если X - простое число, то вывести его. 5. Увеличить x на 1. 6. Если X стало больше, чем а, то закончить выполнение программы (перейти на шаг № 7), иначе перейти на шаг № 3. 7. Конец. А как проверить число x на простоту? Будем проверять его делимость на все числа из интервала [2; x - 1]. Если оно разделится хотя бы на какое-то из чисел данного интервала, значит, оно составное, а если не разделится, то простое. Вот как будет выглядеть эта программа: program simplel; var a, x, y: integer; begin write('Введите натуральное число a >= 2: '); readln(a); x := 2; while (x <= a) do § 9-10. Поговорим об эффективности 73 begin У := 2; // Пока x не делится на у, // будем увеличивать у while (x mod y <> 0) do y := y + 1; // Если x = y, то число простое, // и мы его выводим if (x = у) then write(x, ' '); x := x + 1; end; writeln; end. Вывод программы: Введите натуральное число a >= 2: 100 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 Программа получилась очень компактной, но давайте задумаемся, эффективна ли она? Возьмём, например, число 4. Мы выяснили, что оно составное, поскольку делится на 2. Значит, все числа, которые делятся на 4 (8, 12, 16 и так далее) заведомо составные. А мы их заново проверяем. Получается, что наша программа неэффективна. Но, конечно, только с точки зрения (критерия) быстроты работы. С точки зрения лаконичности кода она нас устраивает. Как же нам улучшить программу? Воспользуемся алгоритмом, который называется решетом Эратосфена: 1. Начало. 2. Выписать подряд все целые числа от 2 до a (2, 3, 4, _, a). 3. Занести в х значение 2 - первое простое число. 4. Вычеркнуть из списка все числа, делящиеся на х, то есть числа 2х, 3х, 4х и т. д. На первом шаге это будут все чётные числа. 5. Найти первое незачёркнутое число, большее х, и занести его в х. В первый раз это будет число 3. 6. Повторить шаги № 4 и 5 до тех пор, пока х не станет больше, чем a div 2. 7. Все оставшиеся невычеркнутыми числа в списке - простые. Вывести их. 8. Конец. Приведём текст программы, реализующий этот алгоритм. program simple2; var x, a, y: integer; M: array [2..200] of integer; 74 Модуль 1. Алгоритмизация и программирование begin write('Введите натуральное число a >= 2: '); readln(a); // заполним массив единицами, то есть // предположим, что все числа - простые for x := 2 to a do M[x] := 1; // начинаем с x = 2 for x := 2 to (a div 2) do if M[x] <> 0 then begin // 'Зачёркиваем' все числа, кратные x, // то есть заносим 0 в массив на кратные х места y := 2 * x; while (y <= a) do begin M[y] := 0; y := y + x; end; end; // выводим из итогового массива // только индексы, которым //соответствуют ненулевые элементы for x := 2 to a do if (M[x] <> 0) then write(x, ' '); writeln; end. Как вы видите, в этой программе нам пришлось использовать массив, в котором индекс равен числу, а значение элемента с этим индексом говорит о том, простое это число или составное. Если i-й элемент массива равен 1, то число простое, а если он равен нулю, то число составное. Изначально мы занесли в массив все единицы, предполагая, что все числа простые. Далее мы перебираем числа х, начиная от 2 и заканчивая a div2. • Подумайте, почему нас устраивает этот диапазон и не надо перебирать числа до а. Если текущее значение M [х] не равно нулю (то есть если х - простое), мы будем «зачёркивать числа», то есть присваивать ноль всем элементам, индексы которых кратны х. В результате мы выведем все индексы отличных от нуля элементов массива. Это и будут простые числа. § 9-10. Поговорим об эффективности 75 Мы хотим ещё раз обратить ваше внимание на тот факт, что программа с точки зрения объёма кода получилась больше, чем предыдущая, но с точки зрения эффективности по времени она на порядок лучше. ВЫЧИСЛЕНИЕ ФАКТОРИАЛОВ Рассмотрим задачу вычисления суммы S [п] = 1 | + 2 ! + 3 ! 1 I = 7ГТ + 2 3 + -^г + п п! Для её решения мы должны каждый раз вычислять факториал нового числа. Но можно ли этого не делать? Давайте посмотрим, как соотносятся числа, стоящие в знаменателях дробей этой суммы. Сначала мы должны посчитать 1!, затем 2!, затем 3! и т. д. А как связан 3! с 2!? Вот так: 3! = 2! ■ 3, 4! = 3! ^4 и т. д. п! = n ■ (n - 1)! Таким образом, зная (п - 1)!, вычислить п! просто. Надо только умножить известное значение на п. Но чтобы начать вычисление последовательности факториалов, нужно знать значение 1!. А оно нам известно. В результате эффективная программа, вычисляющая заданную сумму, будет выглядеть так: program summa; var n, i, fact: integer; s: real; begin // Ввод n write('Введите n: '); readln(n); // Изначально 1! = 1, а сумма = 0 // Занесём эти значения в fact и s fact := 1; s := 0; // Считаем сумму for i := 1 to n do begin fact := fact * i; s := s + i / fact; end; writeln('Сумма равна: ', s); end. + 76 Модуль 1. Алгоритмизация и программирование ОБОБЩЕНИЕ НОВЫХ ЗНАНИЙ Для решения задачи могут быть найдены различные алгоритмы. Выбор конкретного алгоритма определяется критерием эффективности. Хороший программист всегда должен искать эффективное решение своей задачи. РЕШЕНИЕ ПРОБЛЕМЫ ВЫЧИСЛЕНИЕ НАИБОЛЬШЕГО ОБЩЕГО ДЕЛИТЕЛЯ Вычисление наибольшего общего делителя (НОД) двух чисел - задача, которая очень часто встречается, например, при решении задач, связанных с шифрованием. Напомним, что НОД двух чисел а и b (обозначается НОД(а, b)) - это наибольшее число, на которое делятся оба числа. Обычно вычисление НОД реализуется функцией, в которую поступают два числа а и b и которая возвращает их НОД. Понятно, что если оба числа не равны нулю, то их НОД не может превышать меньшее из них. Поэтому мы можем составить такой алгоритм: 1. Начало. 2. Если какое-либо из чисел а и b равно нулю, то НОД - это другое из них. Закончить выполнение программы (перейти на пункт № 6). 3. Положить m = min (а, b). 4. Проверить делимость а на m и b на m. Если оба числа делятся на m, то m и есть НОД(а, b). Если хотя бы одно из чисел не делится нацело на m, то уменьшить m на 1. 5. Если m Ф 1, то перейти на пункт № 4. В противном случае НОД(а, b) = 1. 6. Конец. Вроде бы всё хорошо. Мы получили простой алгоритм. Однако вглядитесь в него. Мы всё время вычитаем из числа m единицу. А если это число очень большое, например порядка 1010? В этом случае алгоритм будет работать очень долго, даже на современных мощных компьютерах. Выходом является использование современной модификации алгоритма Евклида. Пусть у нас есть два целых неотрицательных числа а и b, а < b. Тогда а можно представить в виде: а = b-q + к. Допустим, число с является НОД(а, b). Это означает, что и а делится на с, и b делится на с. Следовательно, к тоже делится на с. Поэтому мы можем записать: НОД(а, b) = НОД(Ь, к). Таким образом, мы § 9-10. Поговорим об эффективности 77 уменьшили значения чисел, НОД которых мы ищем, ведь к - это остаток от деления a на b, а он заведомо меньше b. У какой пары чисел мы всегда знаем НОД? НОД(а, 0) = а. Последовательная замена чисел приведёт к тому, что в конце концов второе число обратится в 0. Таким образом, первое число из пары и будет НОД. Общий алгоритм будет выглядеть так: Га, при Ь = 0; Н0Д[а, Ь] I^Q а Рассмотрим несколько примеров вычисления НОД по алгоритму Евклида. 1) НОД(5, 0) = 0; 2) НОД(24, 16) = НОД(16, 8) = НОД(8, 0) = 8; 3) НОД(9, 12) = НОД(12, 9) = НОД(9, 3) = НОД(3, 0) = 3; 4) НОД(11,7) = НОД(7, 4) = НОД(4, 3) = НОД (3, 1) = НОД(1,0) = 1. Обратите внимание на третий пример. В нём первое число меньше второго. Чтобы можно было применить алгоритм Евклида, потребовалось поменять их местами. Это сделать можно, так как НОД(а, b) = НОД(Ь, а). При а < b алгоритм будет работать неверно. Давайте разделим нацело 9 на 12: 9 = 0'12 + 9. Целая часть от деления 9 на 12 - это 0, а остаток - 9. В последнем примере НОД двух чисел стал равным единице. Такие числа называются взаимно простыми. Приведём текст функций, одна из которых реализует первый рассмотренный алгоритм вычисления НОД, а вторая - алгоритм Евклида. function simple_nod(a, b: integer): integer,- var m: integer- begin if (a * b = 0) then m := a + b else begin if (a > b) then m := b else m := awhile (m > 1) and ((a mod m <> 0) or (b mod m <> 0)) do m := m - 1- end; simple_nod := m; end; function evklid_nod(a, b: integer): integer; var m: integer; 78 Модуль 1. Алгоритмизация и программирование begin while (b<>0! do begin m : = b; b : = a mod b; a : = m; end; evklid_nod := a; end; Когда a и b одновременно равны нулю, их НОД не определён. Функции выдают в этом случае 0. БЫСТРОЕ УМНОЖЕНИЕ ЦЕЛЫХ ЧИСЕЛ Алгоритм, о котором мы сейчас хотим рассказать, используется для того, чтобы «научить» компьютер умножать. Согласитесь, звучит странно, но давайте разбираться! Что означает умножение a на b? Это означает, что надо сложить a само с собой b раз. Но что делать, если числа a и b большие? Простой алгоритм теряет свою эффективность. Значит, надо придумать что-то иное, более эффективное. Давайте рассмотрим метод умножения двух целых неотрицательных чисел, который хоть и называется «русским», но был известен ещё в Древнем Египте. Возьмём два числа: a = 53, b = 36. Будем составлять таблицу: в первом столбце будем хранить преобразованное число а, во втором - преобразованное число b, в третьем ставить флажок, если b нечётное (рис. 1.12). Правила преобразования следующие: на каждом шаге мы будем a умножать на 2, а b целочисленно делить на 2. a b Флажок 53 36 106 18 212 9 424 4 848 2 1696 1 Рис. 1.12 § 9-10. Поговорим об эффективности После заполнения таблицы сложим те значения а, для которых соответствующее значение b нечётно: S = 212 + 1696 = 1908. Приведём блок-схему этого алгоритма (рис. 1.13). 79 Рис. 1.13 В приведённом алгоритме мы используем умножение на 2 и деление на 2? Но операции умножения на 2 и деления на 2 выполняются процессором очень быстро, так же как сложение и вычитание, это связано с тем, что любые данные в компьютере хранятся в двоичной системе счисления. Но о системах счисления мы с вами поговорим в следующем модуле. ОБОБЩЕНИЕ НОВЫХ ЗНАНИЙ Алгоритм нахождения НОД двух целых чисел часто применяется в шифровании. Самые быстрые операции с вещественными числами - сложение, вычитание, умножение на 2 и деление на 2. ПРИМЕНЕНИЕ ЗНАНИЙ 1. Почему поиск простых чисел методом перебора неэффективен? 2. Напишите программу на языке Паскаль, в состав которой входит функция, реализующая «русский» метод умножения целых чисел. Проверь себя Задание 1 Выразите через основные логические операции логическое выражение: a ^ b. Задание 2 Напишите функцию, в которую поступает массив А и количество элементов в нём. Функция должна вернуть количество положительных элементов массива. Задание 3 Вариант алгоритма Евклида для натуральных чисел выглядит так: а, при а = Ь; НОД [а, Ь] = • НОД [а - Ь, Ь], при а> Ь; НО Д(а,Ь- а], при Ь> а. Напишите функцию, реализующую этот алгоритм. ПРИМЕНЕНИЕ ЗНАНИЙ [необходимый уровень) Задание 1 Напишите программу, которая выводит таблицу истинности для логического выражения (а ^ b) © (а ~ с). Вспомните, как логические операции из этого выражения представляются через основные логические операции. Сделайте вывод красивым. Вспомните также, каким образом форматируется вывод целых и логических переменных в языке Паскаль. Задание 2 С клавиатуры вводится натуральное число N. Узнайте, сколько натуральных делителей имеет это число. Помните об эффективности и попробуйте понять, какой диапазон чисел нужно проверять. Задание 3 С клавиатуры вводятся натуральные числа а и b. Напишите функцию, которая вычисляет их наименьшее общее кратное (НОК). НОК можно вычислить по формуле: НОК(а.И-нотаТБ) Задание 4 Напишите на языке Паскаль программу, в которой есть процедура, обеспечивающая слияние двух упорядоченных по неубыванию массивов. Сами массивы и количество элементов в них опишите, как глобальные переменные. Ввод и вывод реализуйте в основной программе. Подсказка: воспользуйтесь блок-схемой из § 8. Задание 5 С клавиатуры вводятся натуральные числа а и b (а < b < 100). Найдите и выведите все простые числа на отрезке [а; b]. ПРИМЕНЕНИЕ ЗНАНИЙ (повышенный уровень] Задание 1 Решите логическую задачу. В нарушении технологического процесса по изготовлению микросхем подозреваются четыре технолога - Алексеев, Бантиков, Воропаев и Гудков. Известно, что: 1) если Алексеев нарушил процесс, то и Бантиков тоже нарушил; 2) если Бантиков нарушил, то Воропаев нарушил или Алексеев не нарушил; 3) если Гудков не нарушил, то Алексеев нарушил, а Воропаев не нарушил; 4) если Гудков нарушил, то и Алексеев нарушил. Кто из подозреваемых нарушил правила? Для решения этой задачи напишите программу, которая построит таблицу истинности для логического выражения, получившегося в процессе решения. Подсказка: в этой задаче должны быть 4 логических переменных. Задание 2 С клавиатуры вводится натуральное число N. Заполните массив всеми натуральными делителями этого числа в порядке убывания. Само число в качестве делителя учитывать не надо. Выведите массив. Заполнение массива организуйте в отдельной процедуре, вывод - по вашему усмотрению. Помните об эффективности решения. Задание 3 С клавиатуры вводятся целое число a и натуральное число b. Сократите дробь а/b и, если возможно, выделите целую часть. Например, если a = -5 и b = Ю, то в качестве ответа надо вывести -1/2. Если а = Ю и b = 8, то вывод должен быть: 1 1/4. Задание 4 Напишите программу на языке Паскаль, в которой есть эффективная функция summa, имеющая заголовок function summa (n: integer):real; вычисляющая следующее выражение: 2 22 2З 24 С = 2 2 + 2- 2 + + (- цп+1, ^ 1! 2! + 3! 4! +... ( 1 ^ 2п ПГ' Ввод n и вывод ответа необходимо реализовать в основной программе. Под вывод выделите 10 знаков, из них 4 - под дробную часть. Задание 5 С клавиатуры вводятся натуральные числа а и b. Напишите функцию, которая определяет, являются ли они близнецами (функция должна возвращать тип boolean]. Близнецами называются простые числа, отличающиеся на 2. Близнецами являются, например, числа 5 и 7, 11 и 13, 17 и 19. Подсказка: в этой программе нужно написать две функции: одну основную проверочную и вторую, вспомогательную, проверяющую число на простоту. ПРИМЕНЕНИЕ ЗНАНИЙ (максимальный уровень] Задание 1 Решите логическую задачу. Наступила осень. Школа собиралась на туристический слёт. Но встал вопрос: какая же будет погода на выходные? Ребята стали искать прогноз в Интернете. Но, к сожалению, все сайты говорили загадками. Вот что удалось выведать: 1) «Если не будет ветра, то будет пасмурно и без дождя»; 2) «Если будет пасмурно, то обязательно пройдёт дождь, но ветра совсем не будет»; 3) «Если будет дождь, то будет пасмурно и без ветра». Помогите ребятам определить погоду. Для решения задачи напишите программу, которая построит таблицу истинности для необходимого логического выражения. Подсказка: вспомните про то, как выражаются разные логические операции через основные. Задание 2 С клавиатуры вводятся два натуральных числа a и b. Напишите функцию, которая определяет, являются ли эти числа дружественными. Два натуральных числа называются дружественными, если каждое из них равно сумме всех натуральных делителей другого (само число в качестве делителя не рассматривается). Задание 3 С клавиатуры вводится натуральное число п, а за ним n натуральных чисел. Найдите их НОД. Постарайтесь не использовать в этой задаче массивы. Подсказка: НОД(а, b, с) = НОД(НОД(а, b), с). Задание 4 Известно, что: Ао~1’ 1 А = к' А 1+ —, где к = 1,2, ... к к-1 к С клавиатуры вводится натуральное число п. Напишите процедуру, которая вычисляет числа Л0,_, и заполняет ими массив. Ввод п и вывод массива организуйте в основной программе. Массив должен быть передан в функцию в качестве параметра. Задание 5 С клавиатуры вводится натуральное число п. Напишите процедуру, которая раскладывает его на простые множители и выводит это разложение. Ответ надо вывести в виде п = x*y*^*z. Например, 12 = 2*2*3, 15 = 3*5, 100 = 2*2*5*5, 7 = 7. Подсказка: для решения этой задачи посмотрите внимательно на приведённые в параграфе примеры. Итоговая проверочная работа Задание 1 _ а) Докажите, что a ^ b = a + b. б) Напишите процедуру, в которую поступает натуральное число n и которая выводит на экран все натуральные делители числа п, меньшие его. Задание 2 а) Докажите, что a © b © b = a. б) Напишите функцию, в которую передаётся число п и которая вы- 1 1 1 числяет выражение: [2^] • [2^] • [2^] •... 12 6 Задание 3 _ а) Постройте таблицу истинности для выражения a&(a ^ b)&(a ^ b) и докажите, что оно всегда ложно. б) Напишите процедуру, в которую поступает массив A, число элементов в нём п и число X. Необходимо вернуть массив, из которого надо удалить все вхождения числа х. Подсказка: • можно использовать вспомогательный массив; • подумайте, каким способом надо передать параметры в процедуру; • учтите, что после удаления количество элементов в массиве может измениться. 87 Модуль 2. Системы счисления Этот модуль поможет вам: • понять и узнать ещё кое-что о компьютере и о числах; • изучать числа в позиционных системах счисления, узнать, как записывается число в общем виде в любой системе счисления, как производятся умножение и деление в любой системе счисления и вычисления не только с целыми числами, но и с дробями; • понять, зачем нужны двоичная, восьмеричная, шестнадцатеричная системы счисления; • узнать, как представлены в памяти компьютера целые и дробные (вещественные) числа, как осуществляется операция сложения в ячейках памяти. Для этого вам надо научиться: • получать целое число, следующее за данным целым числом в любой позиционной системе счисления; • переводить целые числа в любую систему счисления; • складывать и вычитать в любых системах счисления; • переводить в произвольную систему счисления правильную десятичную дробь; • умножать и делить числа, записанные в любой системе счисления; • разбираться, как происходит сложение двоичных чисел в ячейках памяти. 88 Модуль 2. Системы счисления Введение Дорогие друзья! Вы уже много знаете о компьютере, пользуетесь его помощью для написания рефератов, обработки фотографий, слушаете музыку, общаетесь с друзьями. Нелегко перечислить всё, что заставляет вас обратиться к нему. Но как компьютер работает со всей перечисленной информацией? Любая информация, вводимая в компьютер, сначала должна быть представлена в виде, доступном для обработки компьютером, — закодирована. В этом модуле мы будем говорить о кодировании чисел. Вы уже знакомы с одним из способов кодирования — десятичной системой счисления. Кроме десятичной системы счисления, существуют и другие способы представления чисел. В этом разделе вы ознакомитесь с различными системами счисления, в том числе с двоичной системой счисления, в которой кодируются числа в компьютере. § 1. Что такое системы счисления § 1. Что такое системы счисления 89 ПОСТАНОВКА ПРОБЛЕМЫ УРОКА Вам уже встречались различные способы записи чисел: пункты плана в сочинении, главы в книге часто нумеруются посредством римских чисел, а для вычислений вы пользуетесь десятичными числами. Но вы знаете, что Х — это 10, а I — это 1, и уже привыкли к этому. Вы знаете, что римское число III (I + I + I) отличается по значению от десятичного числа 111 (1^100 + 1^10 + 1), хотя в записи каждого из них используются три единицы. А десятичное число 20 и римское число XX оба означают два десятка, а устроены по-разному. • Что здесь для вас новое, а о чём вы хотите спросить? Сформулируйте основной вопрос урока. Сравните свою формулировку с авторской (с. 141 учебника). НЕБХОДИМЫЕ БАЗОВЫЕ ЗНАНИЯ Вспомните, что вы знаете о разных способах записи чисел. РЕШЕНИЕ ПРОБЛЕМЫ • Прочитайте рассказ о различных способах записи чисел и попробуйте объяснить, что такое система счисления. Люди научились считать предметы очень давно и придумали способы записи результатов счёта - в виде чисел. Самым древним способом записи чисел была унарная система (от латинского слова unus - единственный). В ней для записи чисел использовался всего один какой-нибудь знак. Количество предметов обозначалось соответствующим количеством одинаковых знаков (например, число 20 можно было изобразить с помощью двадцати одинаковых подряд идущих вертикальных палочек). В славянской системе нумерации для записи чисел использовались все буквы алфавита (правда, с нарушением алфавитного порядка), над которыми ставился знак ~ (титло). Эти знаки являлись цифрами славянской системы. Каждая буква-цифра обозначала количество единиц, десятков или сотен: Л [аз] - 1; ^ [веди] - 2; ^ [глаголь] - 3; ^ [добро] - 4; ^ [еоть] - 5; $ [зело] - 6; 3 [земля]-?; И [иже] - 8; Д [фита] - 9; I [и] -10; *РГ [како]-20; ^ [люди] - 30 и т. д. В римской системе записи чисел используется следующий набор знаков-цифр, обозначающих числа: I - 1; V - 5; X - 10; L - 50; C - 100; D - 500; M - 1000. 90 Модуль 2. Системы счисления Все другие числа строятся как комбинации цифр в соответствии со следующими правилами: • если цифра с меньшим значением стоит справа от большей цифры, то их значения суммируются; если слева, то меньшее значение вычитается из большего; • несколько подряд идущих одинаковых цифр суммируются; • цифры I, X, C и M могут следовать подряд не более трёх раз каждая; • цифры V, L и D могут использоваться в записи числа не более одного раза. Рассмотренные способы (системы) записи чисел называются системами счисления. Под системой счисления понимается способ представления чисел с помощью некоторого алфавита знаков - цифр. Существуют позиционные и непозиционные системы счисления. В непозиционных системах счисления значение цифры в числе не зависит от её позиции в числе. Например, в числе ХХХ (30) каждая из цифр означает 10 единиц, независимо от позиции цифры. Поэтому римская система счисления является непозиционной. Непозиционные системы счисления были и у греков и египтян. Непозиционные системы счисления обладали рядом недостатков. Для записи чисел нужно было использовать много знаков. В непозиционных системах трудно было производить арифметические действия. По мере развития науки у людей возникла потребность в большем количестве вычислений, что подтолкнуло древних математиков к созданию более удобных способов записи чисел. Появились системы счисления, в которых значение цифры в числе зависело от её позиции в числе. Они были придуманы почти одновременно в Вавилоне, Индии, у древних майя. Привычная нам позиционная десятичная система счисления зародилась не позднее V века нашей эры в Индии и через арабские страны пришла в Европу. • Вы догадались, почему такие системы счисления называются позиционными? Назовите отличие позиционной системы счисления от непозиционной. В позиционной системе счисления значение цифры в числе определяется её позицией (разрядом) в числе. Например, запись числа N = 222 в десятичной системе счисления означает, что в первой позиции (единицы) - 2 единицы, во второй позиции (десятки) -2 десятка, то есть 2^10 = 20 единиц, в третьей позиции (сотни) - 2 сотни, то есть 2^100 = 200 единиц. Важной характеристикой системы счисления является её основание. Основание позиционной системы счисления - это количество цифр в алфавите этой системы. § 1. Что такое системы счисления Основание обычно обозначается латинской буквой «р». Например, десятичная система счисления - позиционная, с основанием 10 (р =10). Цифры, принятые для записи чисел (алфавит), - 0, 1,2, 3, 4, 5, 6, 7, 8, 9. У систем счисления с основаниями, меньшими 10, в качестве знаков-цифр используются привычные нам цифры десятичной системы, например, в пятеричной системе цифрами являются 0, 1,2, 3, 4. В двоичной системе счисления это цифры 0, 1. Двоичная система счисления используется для представления чисел в компьютере. Значение основания приписывают в виде нижнего индекса после последней цифры числа: 2510, 4325, 1012 и т. д. Число в десятичной системе счисления можно представить в виде суммы, где каждое слагаемое - это цифра числа, умноженная на основание (р = 10) в степени, определяемой разрядом этой цифры. Например, десятичное число 123,6710 можно представить в виде: 123,67510 = 1^102 + 2^101 + 3^10° + 6^10-1 + 7^10-2 + 5^10-3. Точно так же можно записать число в любой позиционной системе счисления. Например: 23,015 = 2^51 + 3^5° + 0^5-1 + 1^5-2. Такая запись называется развёрнутой формой записи числа. 91 Пример 1 N = 371,3310 Степени основания: 2 10 Цифры числа: 3 7 1 , N = 3^102 + 7^101 + 1^10° + 3^10-1 + 3^10-2 -1 -2 33 Пример 2 N = 371,338 Степени основания: 2 1 0 Цифры числа: 3 7 1 N = 3^82 + 7^81 + 1^8° + 3^8-1 + 3^8-2 -1 -2 33 Какое основание у этой системы счисления? Какие цифры используются для записи чисел в этой системе счисления? 92 Модуль 2. Системы счисления Последовательность чисел, составленная из представленных в развёрнутой форме сомножителей р', где p - основание системы счисления, i - степень основания, определяемая разрядом, представляет собой базис системы счисления. Базис является второй характеристикой позиционной системы счисления. Базис задаёт значение цифры числа в соответствующем разряде, как ещё говорят, - вес разряда. Базисы некоторых систем счисления Степень основания Основание 10 2 3 8 -к 10-к 2-к 3-к 8-к -3 10-3=0,001 2-3=1/8 3-3=1/27 8-3=1/512 -2 10-2=0,01 2-2=1/4 3-2=1/9 8-2=1/64 -1 10-1=0,1 2-1=1/2 3-1=1/3 8-1=1/8 0 100=1 20=1 30=1 80=1 1 101=10 21=2 31=3 81=8 2 102=100 22=4 32=9 82=64 3 103=1000 23=8 33=27 83=512 n 10n 2n 3n 8n Но что делать, если основание системы счисления больше Ю? Например, широко используется шестнадцатеричная система счисления - её основание равно 16. Значит, и цифр в её алфавите должно быть 16! Выход нашёлся: первые 10 взяли из десятичной системы счисления: 0, 1,2, 3, 4, 5, 6, 7, 8, 9, а остальные шесть стали обозначать буквами латинского алфавита: A, B, C, D, E, F. Все позиционные системы счисления «устроены» одинаково. Правила, по которым получаются числа в позиционных системах, тоже одинаковые для всех позиционных систем счисления. Давайте разберёмся, как получается целое число, следующее за данным числом. • Расскажите, как это происходит в десятичной системе счисления. Конечно, вы правы. Чтобы получить следующее целое число, надо к предыдущему прибавить 1. Но не забудьте, что мы ещё не научились складывать числа в произвольной системе счисления. Поэтому воспользуемся следующим правилом. Чтобы получить число, следующее за данным, нужно заменить крайнюю правую (младшую) цифру этого числа на следующую за ней в алфавите § 1. Что такое системы счисления 93 системы счисления, причём старшая цифра в алфавите меняется на 0. Если цифра числа стала равной нулю, то следует заменить вторую справа цифру на следующую и т. д. Если нулём стала крайняя правая (старшая) цифра числа, то нужно приписать к числу слева единицу. ОБОБЩЕНИЕ НОВЫХ ЗНАНИЙ Существуют позиционные и непозиционные системы счисления. Мы пользуемся позиционными системами счисления, потому что они позволяют записать число в компактном виде и производить над числами все арифметические операции. ПРИМЕНЕНИЕ ЗНАНИЙ 1. Получите числа, следующие за числами: а) 99916, б) AAFF16, в) 9AEF16. 2. Составьте и заполните следующую таблицу: впишите в каждый столбец по порядку числа системы счисления с основанием р. p = 10 p = 8 P = 5 P = 3 P = 2 p = 16 0 0 0 0 0 0 1 1 1 1 1 1 17 3. Какие минимальные основания должны иметь системы счисления, в которых могут быть записаны числа 28; 123; 1022; 1 89; AC12? Ответ запишите в виде цепочки чисел, разделённых символом «;». 4. Какие числа во всех системах счисления выглядят одинаково? 5. Запишите в развёрнутой форме число N = 202, 334. 94 Модуль 2. Системы счисления § 2. Перевод числа из произвольной системы счисления в десятичную. Перевод целого числа из десятичной системы счисления в произвольную ПОСТАНОВКА ПРОБЛЕМЫ УРОКА В задании к § 1 вы заполнили таблицу чисел в некоторых системах счисления. Она позволяет легко найти соответствие между числами в этих системах. Как вы думаете, может ли эта таблица оказаться полезной для вас? • Есть ли здесь проблема? Сформулируйте основной вопрос урока. Сравните свою формулировку с авторской (с. 141 учебника). РЕШЕНИЕ ПРОБЛЕМЫ Теперь вы знаете, как представляются числа в разных системах счисления. Но как установить соответствие между этими числами? Посмотрите на составленную вами таблицу чисел в нескольких системах счисления. В ряде частных случаев она вам поможет. Но невозможно создать таблицу, в которой бы было любое интересующее вас число в любой системе счисления! Поэтому надо научиться переводить любое число из одной системы счисления в другую. ПЕРЕВОД ЧИСЛА ИЗ ПРОИЗВОЛЬНОЙ СИСТЕМЫ СЧИСЛЕНИЯ В ДЕСЯТИЧНУЮ СИСТЕМУ СЧИСЛЕНИЯ Правило перевода: 1. Число, записанное в системе счисления с основанием р, представить в развёрнутой форме. 2. Заменить цифры числа в данной системе на цифры в десятичной системе. 3. Вычислить значение полученного выражения в десятичной системе счисления. Результат - число, записанное в десятичной системе счисления. Примеры 2025 = 2^52 + О^б1 + 2^ 50 = 25 + 0 + 2 = 52 11, = 1^161 + 1^16° = 16 + 1 = 17 10 ' 16 10’ 3A16 = 3^161 + A^160 = 3^161 + 10^160 = 48 + 10 = 5810; 11012 = 1^23 + 1^22 + 0^21 + !• 20 = 8 + 4 + 0 + 1 = 1310 ; 22,67 = 2^71 + 2^70 + 6^7-1 = 14 + 2 + 6/7 * 16,8610. § 2. Перевод числа из произвольной системы счисления в десятичную ПЕРЕВОД ЦЕЛОГО ЧИСЛА ИЗ ДЕСЯТИЧНОЙ СИСТЕМЫ СЧИСЛЕНИЯ В ПРОИЗВОЛЬНУЮ СИСТЕМУ СЧИСЛЕНИЯ Правило перевода: 1. Найти максимальную степень к основания р новой системы счисления, для которой рк меньше данного десятичного числа. 2. Определить, сколько раз (n) рк «укладывается» в данном десятичном числе. 3. Записать п*рк в качестве очередного слагаемого развёрнутой формы записи числа в новой системе счисления. 4. Получить разность данного десятичного числа и п*рк. 5. Для полученной разности повторять пункты № 1-4 до тех пор, пока разность не станет меньше основания р новой системы. 6. Записать последнее слагаемое как произведение полученной разности на р0. 7. Выписать коэффициенты при рк в качестве цифр числа в новой системе так, чтобы их разряды соответствовали коэффициентам к. В разряды, соответствующие пропущенным к, записать нули. Пример. Перевод в четверичную систему счисления числа 14010. 1 4 0^ = 2-43 + 3-41 + 0-40 = 2030. 95 М0 — 1 2 8 2 2 0 Когда вы будете выполнять примеры, рассказывайте себе этот алгоритм. Рассуждайте (для приведённого примера) приблизительно так: «Основание новой системы счисления - 4. Мне надо найти максимальную степень к этого основания, для которой 4к «умещается» в десятичном числе 140. 43 = 64 меньше 140, а 44 = 256 уже больше 140. Значит, это степень к = 3. Теперь посмотрю, сколько раз 43 «укладывается» в числе 140: 2 раза. Запишу произведение 2^43 как первое слагаемое. Найду произведение 2*43 = 128. Вычту 128 из данного числа 140. Разность равна 12. Она не меньше основания новой системы, значит, мне надо повторить предыдущие действия ещё раз - для числа 1 2. Теперь максимальная степень основания равна 1,41 в числе 12 «укладывается» 3 раза. Запишу в качестве второго слагаемого 3^41. Далее из 12 я вычту 3*41 = 12. Разность 0 меньше 4, значит, далее поиск степени и вычисления производить не буду. Запишу последнюю разность 0 на своё место: при 40. Теперь запишу коэффициенты на соответствующие места в числе. Замечу, что пропущен коэффициент при степени основания 2, в соответствующий разряд запишу 0». 96 Модуль 2. Системы счисления А как следует поступить, если вы хотите перевести число из произвольной системы счисления в произвольную? Для этого можно использовать десятичную систему как «переводчика»: сначала перевести число из первой системы счисления в десятичную, а затем полученное десятичное число - во вторую систему. ОБОБЩЕНИЕ НОВЫХ ЗНАНИЙ Есть два алгоритма, которые позволяют перевести число из произвольной системы счисления в десятичную и целое число из десятичной системы в произвольную. Применяя их, можно переводить целые числа из любой системы счисления в любую, а «переводчиком» будет работать десятичная система счисления. ПРИМЕНЕНИЕ ЗНАНИЙ 1. Укажите, какие целые числа следуют за числами: а) 1010112; в) 5678; д) AABF16; б) 289; г) 1011112; е) 1222123; з) 5556 ж) 1334; 2. Какой цифрой заканчивается чётное двоичное число? Нечётное двоичное число? Какой цифрой может заканчиваться чётное троичное число? 3. Переведите в шестнадцатеричную систему счисления число 21610. Сверьте своё решение с ответом: 21610 = 13^161 + 8^160 = D816. 4. Переведите числа: а) 101112 в шестеричную систему счисления; б) A0116 в десятичную систему счисления; в) 13334 в пятеричную систему счисления; г) 5128 в двоичную систему счисления; д) 51210 в двоичную систему счисления. § 3. Переход между системами счисления, основания которых - степени двойки § 3. Переход между системами счисления, основания которых - степени двойки ПОСТАНОВКА ПРОБЛЕМЫ УРОКА На прошлом уроке вы научились переводить числа из одной системы счисления в другую и обнаружили, что посредником между системами счисления при переводе является десятичная система счисления. Но среди систем счисления есть такие, основания которых — степень двойки. Это объединяет их в особый класс. Они — «близкие родственники». Но в чём же проявляется «родство» этих систем и как оно нам может помочь? Если такие системы «ближе» друг к другу, чем к десятичной системе, то нужна ли она им как «посредник»? • Как вы считаете, существуют ли особые приёмы перевода для данного случая? Сформулируйте проблему урока. Сравните свой вариант с авторским (с. 141 учебника). РЕШЕНИЕ ПРОБЛЕМЫ • Назовите системы счисления, основания которых — степень двойки. Для чего мы прибегаем к помощи систем счисления с такими основаниями? Как вы знаете, для кодирования информации в компьютере применяется двоичная система счисления. Это обусловлено тем, что удобно использовать технические элементы, способные находиться в одном из двух состояний (есть ток - 1, нет тока - 0; низкое напряжение - 0, более высокое - 1 и т. д.). Но для человека громоздкие двоичные числа неудобны и непривычны в использовании, поэтому для записи адресов ячеек памяти используют восьмеричные и шестнадцатеричные числа. Перевод чисел из одной системы счисления с основанием, равным степени числа 2, в другую такую систему, конечно, можно осуществлять через десятичную систему счисления. Но для таких систем счисления существует и другой, свой «посредник». Это двоичная система счисления. Давайте познакомимся со способом такого перевода. Он может показаться вам необычным, поскольку, в отличие от алгоритмов, приведённых в § 2, здесь ничего не придётся вычислять. ПЕРЕВОД ВОСЬМЕРИЧНЫХ ЧИСЕЛ В ДВОИЧНУЮ СИСТЕМУ СЧИСЛЕНИЯ Правило перевода: Для перевода восьмеричного числа в двоичную систему счисления надо каждую восьмеричную цифру представить отдельно в двоичной системе в виде трёх двоичных цифр (триады). 97 98 011 111 101 3 7 58 010 101 001 2 5 1 Почему верен такой Модуль 2. Системы счисления Примечание. Незначащие нули (перед первой единицей в целой части и после последней единицы в дробной части) можно опускать. Примеры = 11111101, 0 68 = 10101001,0010001102 ство двоичных знаков, необходимое для представления любой восьмеричной цифры в двоичном коде, - три, поэтому для перевода мы записываем каждую восьмеричную цифру тремя двоичными. Пусть надо перевести в двоичную систему счисления число 638. По предложенному правилу у нас должно получиться число 110 011. Представим наше восьмеричное число в развёрнутой форме и воспользуемся равенством 23 = 8: 638 = 6^81 + 3^80 = 6^(23)1 + 3^(23)0 = 6^23 + 3^20. Переведём, как нам указывает наше правило, отдельно каждую восьмеричную цифру в двоичную систему, представим каждое получившееся двоичное число в развёрнутой форме и раскроем скобки: 638 = 6^81 + 3^80 = 6^(23)1 + 3^(23)0 = 6^23 + 3^20 = (110)^23 + (011)^20 = = (1^22 + 1^21 + 0-2°) ^23 + (0^22 + 1^21 + 1^2°)^20 = 1^25 + 1^24 + 0^23 + + 0^22 + 1^21 + 1^2°. Но что мы получили? Это же развёрнутая форма двоичного числа! Значение этого двоичного числа равно значению числа 638. Выпишем двоичное число по его развёрнутой форме: 110011. Оно совпадает с полученным по правилу перевода. Приведём таблицу соответствия восьмеричных цифр и двоичных чисел. Восьмеричная цифра 0 1 2 3 4 5 6 7 Двоичное число 000 001 010 011 100 101 110 111 § 3. Переход между системами счисления, основания которых - степени двойки ПЕРЕВОД ДВОИЧНЫХ ЧИСЕЛ В ВОСЬМЕРИЧНУЮ СИСТЕМУ СЧИСЛЕНИЯ Правило перевода: Для перевода двоичного числа в восьмеричную систему счисления надо двоичное число разделить на триады и каждую триаду заменить на соответствующую ей восьмеричную цифру. Примечание. Целая часть делится на триады справа налево, а дробная -слева направо. Если при делении целой части на триады окажется, что в последней (левой) выделяемой группе меньше трёх цифр, никаких дополнительных действий не требуется. Если не хватает цифр при выделении триад в дробной части, необходимо дописать в конец дроби столько нулей, сколько цифр не хватает. 99 Пример Направления деления на триады целой части дробной части ◄------- ------------► 10101,0Ю012 = ЮЮ1 ,0100102 = 25,228 Выделен 0, который мы добавили до триады в конце дроби. ПЕРЕВОД ШЕСТНАДЦАТЕРИЧНЫХ ЧИСЕЛ В ДВОИЧНУЮ СИСТЕМУ СЧИСЛЕНИЯ Правило перевода: Для перевода шестнадцатеричного числа в двоичную систему счисления надо каждую шестнадцатеричную цифру представить соответствующей ей четвёркой двоичных цифр - тетрадой. Примечание. Незначащие нули (перед первой единицей в целой части и после последней единицы в дробной части) можно опускать. Это правило основано на том, что минимальное одинаковое количество двоичных знаков, необходимое для представления любой шестнадцатеричной цифры в двоичном коде, - четыре, поэтому для перевода мы записываем каждую шестнадцатеричную цифру четырьмя двоичными. Примеры 0011 0010 0101 3 2 ^ =1100100101. 0010 0001 21 0001 1 0010 2,= = 100001,000100102 100 Модуль 2. Системы счисления • Покажите на примере, аналогично тому, как это сделано выше для восьмеричной системы счисления, почему это правило верное. Приведём таблицу соответствия шестнадцатеричных цифр и двоичных чисел. Шестнадцатеричная цифра 0 1 2 3 4 5 6 7 Двоичное число 0000 0001 0010 0011 0100 0101 0110 0111 Шестнадцатеричная цифра 8 9 A B C D E F Двоичное число 1000 1001 1010 1011 1100 1101 1110 1111 ПЕРЕВОД ДВОИЧНЫХ ЧИСЕЛ В ШЕСТНАДЦАТЕРИЧНУЮ СИСТЕМУ СЧИСЛЕНИЯ Правило перевода: Для перевода двоичного числа в шестнадцатеричную систему счисления надо разделить двоичное число на тетрады и каждую тетраду заменить на соответствующую ей шестнадцатеричную цифру. Примечание. Целая часть делится на тетрады справа налево, а дробная -слева направо. Если при делении целой части на тетрады окажется, что в последней (левой) выделяемой группе меньше четырёх цифр, никаких дополнительных действий не требуется. Если не хватает цифр при выделении тетрад в дробной части, необходимо дописать в конец дроби столько нулей, сколько цифр не хватает. Пример 1 B 1 1011 B 1011 B 1011 8 1000, = 1BB,B81 Заметим, что приписывание 0 справа к двоичному числу увеличивает его в 2 раза, так же как приписывание к десятичному - в 10 раз, к шестнадцатеричному - в 16 раз и т. п. Это можно использовать для определения шестнадцатеричного выражения комбинаций двоичных цифр. Двоичное число Действия Десятичное число Шестнадцатеричная цифра 1 0010 4^2 + 0 8 8 100; 1 4^2 + 1 9 9 1010 5^2 + 0 10 A 10111 5^2 + 1 11 B 110 0 6^2 + 0 12 C 11011 6^2 + 1 13 D 1110 7^2 + 0 14 E 11111 7^2 + 1 15 F § 3. Переход между системами счисления, основания которых - степени двойки ОБОБЩЕНИЕ НОВЫХ ЗНАНИЙ Вы узнали, что переводить числа между системами счисления, основания которых - степени двойки, можно, используя в качестве «посредника» двоичную систему счисления. 101 ПРИМЕНЕНИЕ ЗНАНИЙ 4. Переведите числа в восьмеричную систему счисления: а) 123,1316; б) 1111,1114; в) EDA,DA16. Переведите числа в шестнадцатеричную систему счисления: а) 123,1234; б) 1515,218; в) 400, 0348. Переведите числа в четверичную систему счисления: а) ABC,0116; б) 111,0018; в) 111,00116. Предложите правило перевода чисел из четверичной в восьмеричную систему счисления. 1 2 3 102 Модуль 2. Системы счисления § 4. Сложение и вычитание чисел в произвольных системах счисления ПОСТАНОВКА ПРОБЛЕМЫ УРОКА Итак, мы с вами «путешествуем» по миру чисел. Вы узнали много нового о числах и умеете переводить целые числа из одной позиционной системы счисления в другую. Мир чисел велик, числа окружают нас повсюду, без них очень сложно обходиться. Но зачем нам нужны числа? Правильно, чтобы производить расчёты. В десятичной системе вы давно научились этому. А что происходит в других системах? Существуют ли там свои правила? Чем арифметические действия в произвольной системе отличаются от действий в десятичной системе? • Как вы считаете, какая проблема в этой ситуации? Сформулируйте её. Сравните свой вариант с авторским (с. 142 учебника). НЕБХОДИМЫЕ БАЗОВЫЕ ЗНАНИЯ Вспомните из курса математики, как производится сложение и вычитание десятичных чисел. РЕШЕНИЕ ПРОБЛЕМЫ Давайте расширим умения обращения с числами в разных системах счисления и добавим к ним опыт сложения и вычитания целых чисел в произвольной системе счисления. Арифметические действия во всех позиционных системах счисления выполняются по одним и тем же правилам. С этими правилами вы давно знакомы по десятичной системе счисления. Это хорошая новость: никаких новых правил! Но при этом следует помнить о том, что в других позиционных системах другие основания, к которым вы ещё не привыкли. Если в десятичной системе число 10 следует за числом 9, то, например, в пятеричной системе 10 идёт после 4, а в двоичной - после 1. От этого зависит, например, сколько единиц мы переносим в следующий разряд при сложении чисел. Следует быть внимательными при выполнении операций над числами, помнить, какое основание у данной системы. Отметим важный момент: перед тем, как произвести любую арифметическую операцию, числа надо записать в одной и той же системе счисления. СЛОЖЕНИЕ Правила сложения чисел в произвольной системе счисления аналогичны правилам сложения чисел в десятичной системе счисления. Это означает, что, во-первых, сложение чисел в некотором разряде производится согласно таблице сложения в данной системе счисления § 4. Сложение и вычитание чисел в произвольных системах счисления (с основанием p). Во-вторых, если при сложении цифр в некотором разряде получается значение, большее старшей цифры в данной системе счисления, в соответствующий разряд результата надо записать разность между этим значением и значением 10р в данной системе. Образовавшуюся цифру переноса нужно учитывать при сложении в следующем разряде. Таблицу сложения в десятичной системе вы знаете. Приведём таблицы сложения в двоичной (рис. 2.1) и восьмеричной (рис. 2.2) системах. Цифры-слагаемые находятся в строках и столбцах, результаты сложения - на их пересечении: в ячейках таблицы. Таблица сложения в двоичной системе счисления 103 + 0 1 0 0 1 1 1 10 Рис. 2.1 Таблица сложения в восьмеричной системе счисления + 0 1 2 3 4 5 6 7 0 0 1 2 3 4 5 6 7 1 1 2 3 4 5 6 7 10 2 2 3 4 5 6 7 10 11 3 3 4 5 6 7 10 11 12 4 4 5 6 7 10 11 12 13 5 5 6 7 10 11 12 13 14 6 6 7 10 11 12 13 14 15 7 7 10 11 12 13 14 15 16 Рис. 2.2 • Какую закономерность вы видите в таблицах сложения? Аналогично строятся таблицы сложения для других систем счисления. Рассмотрим правило сложения на примерах. Пример 1 Сложение целых двоичных чисел: Пример 2 Сложение дробных двоичных чисел: 110 0 1 110 1 1 1, 1, 10 0 1 1 0 10 111, 0 1 1 + + 104 Модуль 2. Системы счисления Пример 3 Сложение целых восьмеричных чисел 1 7 7 1 1 2 Точки обозначают перенос единицы в следующий разряд. Обратите внимание на пример сложения восьмеричных чисел. Сложение в младшем разряде в восьмеричной системе цифр 3 и 7 здесь даёт не 10, как в десятичной системе, а 1 28. Из этого числа вычитается 108. Поэтому цифрой результата будет 2. При этом переносится единица в старший разряд. Для двоичной системы (см. примеры 1 и 2) сложение 1 и 1 даёт 102, поэтому цифрой результата будет 0, при этом в старший разряд переносится единица. Можно пользоваться следующим приёмом сложения. Цифры в разряде складываются в десятичной системе, а результат сложения затем переводится в нужную систему счисления. Вычислять в десятичной системе нам привычнее. В рассмотренном примере 3 сложим числа 7 и 3 в десятичной системе: получим 10 в десятичной системе. Переведём 10 в восьмеричную систему: получим 128. Теперь, зная, как суммируются числа в двоичной системе счисления, можно воспользоваться одним полезным алгоритмом для перевода в десятичную систему счисления больших двоичных чисел, в записи которых много единиц и мало нулей, например числа 1111101012. Если делать так, как вы научились, то придётся произвести следующие действия: 1111101012 = 1^28 + !• 27+ + 1^26 + 1^25 + 1^24 + 1^22 + 1^2°. Шансов ошибиться, производя эти действия, много. И времени вы потратите много. Сделаем лучше так. Представьте себе, что перед вами лист тетради в клетку (таблица, рис. 2.3). Запишем данное число, поставив над каждым разрядом степень двойки. Получим из данного числа новое заменой 0 на 1, а 1 на 0. Такую операцию называют инвертированием. Сложим данное и инвертированное числа. В результате получим число, состоящее из одних единиц. Прибавим к сумме 1. В результате все единицы заменятся на нули, при этом появится ещё один старший разряд с единицей. Для нашего примера 9-разрядного числа получим 29 = 512. Теперь будем считать, поднимаясь вверх по таблице (см. рис. 2.3). В верхней строчке получим ответ: 501. + § 4. Сложение и вычитание чисел в произвольных системах счисления 105 9 8 7 6 5 4 3 2 1 0 + 1 1 1 1 1 0 1 0 1 0 0 0 0 0 1 0 1 0 + 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 511-10 = 501 Ж 23 + 21 = 10 512 - 1 = 511 512 Рис. 2.3 Замечание. Отметим, что рассмотренные на рис. 2.3 операции инвертирования и прибавления единицы используются для представления отрицательных чисел в компьютере. С ними вы сможете подробно познакомиться в § 8. Обратим особое внимание на сложение шестнадцатеричных чисел. Оно не сложнее других, просто складывать буквы как-то непривычно. Складывают, конечно, не буквы, а их численные значения: A - 10; B - 11; C - 12; D - 13; E - 14; F - 15. Складывать будем в десятичной системе, а результат записывать в шестнадцатеричной. Пример 4 2 E 2 1-й разряд (160): (2 + 4)16; (2 + 4)10 = 610 = 616; A 5 4 2-й разряд (161): (Е + 5)16; (14 + 5)10 = 1910 = 1316; D 6 пишем 3, а 1 переносим в 3-й разряд: (2 + A + 1)16; (2 + 10 + 1)10 = 1З10 = D16. • Выполните примеры 5, 6, 7 самостоятельно и сверьте полученный результат с ответом. Пример 5 Сложение пятеричных чисел: Пример 6 Сложение шестнадцатеричных чисел: 1 1 1 1 1 1 1 1 1 + 4 4 2 3 4 + E D A, 9 8 3 3 3 3 F 1, A B 1 0 3 1 2 2 1 0 C C, 4 3 106 Модуль 2. Системы счисления Пример 7 Сложение восьмеричных чисел: 1 1 1 + 5 7, 5 7 3, 6 1 5 3, 3 ВЫЧИТАНИЕ Вычитание чисел в любых позиционных системах счисления выполняется по тем же правилам, что и в десятичной системе счисления. Рассмотрим это на примере вычитания 16-разрядных чисел. Пример 8 ■ 6 9 2 А Из 2-го разряда (его вес - 161) занимаем 1 (то есть 161 = 1016); в 1-м разряде получается: (9 + 10 - А)16 = (9 + 16 - 10)10 = 1510 = F16. Производим действия во 2-м разряде: (5 - 2)16 = 316. Рассмотрим теперь подробно схему вычитания чисел для общего случая, когда требуется занимать из старших разрядов. • Вспомните, как вы производите заёмы при вычитании в десятичной системе счисления. Схема основана на том, что любую степень основания pn в любой системе счисления можно представить как сумму младших степеней основания, где коэффициент при любой степени, кроме самой младшей из используемых, всегда на единицу меньше основания, а коэффициент при самой младшей степени равен основанию. Пример 9 В двоичной системе: 24 = 2^23 24 = 1^23 + 2 ^22 24 = 1^23 + 1^22 + 2^21 24 = 1^23 + 1^22 +1^21 + 2^20 В семеричной системе: 75 = 6^74 + 6^73 + 7^72 § 4. Сложение и вычитание чисел в произвольных системах счисления 107 Пример 10 3 1 2 0 1 0 1 0 10002 - 112 = 1012 0 0 Мы видим, что в разрядах с 1-го по 3-й невозможно произвести вычитание - надо занять единицу в 4-м разряде (то есть 23). Поэтому разложим 23 до 20: 23 = 1 ^22 + + 1^21 + 2^2° (распределим единицу в 4-м разряде, то есть 23, по младшим разрядам). Коэффициенты в этом разложении будем учитывать при вычитании в соответствующих разрядах. В 1-м разряде произведём действия: (2 + 0) - 1 = 1 - пишем 1 в числе-результате. Во 2-м разряде: (1 + 0) - 1 = 0 -пишем 0. В 3-м разряде: 1 + 0 = 1 - пишем 1. В 4-м разряде была одна единица, но мы её заняли, и там ничего не осталось. Пример 11 2 1 0 -1 -2 -3 10 0, 0 0 12 1, 1 1 12 1 0, 0 1 02 Занимаем двойку во второй степени; раскладываем до 2-2: 22 = 1^21 + 1^20 + +1 ^2-1 + 2^2-2; учитываем коэффициенты при вычитании. 100,0012 - 1,1112 = 10,01, Пример 12 2 7 1 0 0 б8 5 7„ 6 2 7„ Занимаем 82, раскладываем до 80: 82 = 7 • 81 + 8 • 80 , в 1-м разряде (80) учитываем коэффициент 8: 8 + 6 = 14; после вычитания остаётся 14 - 7 = 7. Во 2-м разряде: (7 + 0) - 5 = 2. В 3-м разряде после заёма остаётся 6. 7068 - 578 = 6278 Вспомните, как вы занимаете при вычитании в десятичной системе счисления: вы, на самом деле, применяете рассмотренный приём, но делаете это уже автоматически. Таким же автоматическим станет для вас процесс вычитания в произвольной системе счисления после приобретения некоторого опыта. Вы уже не будете задумываться о каждом конкретном шаге схемы, рассмотренной здесь так подробно. 108 Модуль 2. Системы счисления • Подумайте, для решения каких ещё задач вам может пригодиться возможность рассмотренного представления степени числа. ОБОБЩЕНИЕ НОВЫХ ЗНАНИЙ Арифметические действия производятся по одинаковым правилам во всех позиционных системах счисления. При выполнении арифметических действий необходимо помнить, каково основание системы, в которой они производятся, и учитывать это. Сложение и вычитание нужно выполнять над числами, представленными в одной и той же системе счисления. ПРИМЕНЕНИЕ ЗНАНИЙ 1. Выполните сложение. а) 7548 + 3418; б) 12A,8B16 + BBA, 4516; в) 467д + 1 2316. Результат представьте в шестнадцатеричной системе счисления. 2. Выполните вычитание. а) 101001012 - 1111112; б) 1011101,0114 - 2 2 2, 234; в) ABC,DE16 - 1 534,58. Результат представьте в восьмеричной системе счисления. § 5. Перевод правильной десятичной дроби в произвольную систему счисления § 5. Перевод правильной десятичной дроби в произвольную систему счисления ПОСТАНОВКА ПРОБЛЕМЫ УРОКА Как перевести из десятичной системы счисления в произвольную целое число, вы теперь знаете. Но мир чисел не ограничивается только целыми числами. Как вы думаете, «секреты» работы с какими числами вы сейчас узнаете? Сформулируйте основной вопрос урока. Сравните свою формулировку с авторской (с. 142 учебника). НЕБХОДИМЫЕ БАЗОВЫЕ ЗНАНИЯ Вспомните из курса математики, какая десятичная дробь называется правильной. 109 РЕШЕНИЕ ПРОБЛЕМЫ Правило перевода дроби: 1. Нарисовать вертикальную черту. 2. Расположить переводимое число так, чтобы 0 с запятой были слева от вертикальной черты, а дробная часть - справа. 3. Умножить только дробную часть на основание р системы счисления. Полученную целую часть записать слева от черты, дробную - справа. 4. Выполнять пункт № 3 до тех пор, пока часть, записываемая справа от черты, не станет равной 0. Справа от черты при этом будут появляться цифры от 0 до р - 1. Может так случиться, что в правой части 0 никогда не получится. В этом случае умножение продолжать до необходимой степени точности или до появления периодической дроби. 5. Выписать цифры, написанные сверху вниз, расположенные слева от черты (в примере ниже выделены красным), в одну строчку, первое из них -ноль, отделить запятой. Помните: умножайте только числа, записанные справа от черты, а в результат записывайте цифры, получающиеся слева от черты. 110 Модуль 2. Системы счисления Примеры Перевод в двоичную систему счисления дроби 0,12510: 0, 125 X 2 0 250 X 2 0 500 X 2 1 000 0,12510 = 0,0012 Перевод в троичную систему счисления дроби 0,12510: 0, 125 X 3 0 375 X 3 1 125 X 3 0 375 X 3 1 125 X 3 0,12510 = 0,01(01)з - получили периодическую дробь. Отметим, что в случае перевода правильной десятичной дроби в шестнадцатеричную систему счисления дробная часть каждый раз умножается на двузначное число (1 6), по правилу умножения на двузначное число; то есть очередная дробная часть умножается на 6 и на 1, результаты умножения записываются со сдвигом и складываются. Целая часть результата сложения представляет собой очередную цифру искомой шестнадцатеричной дроби. Не забывайте цифры целой части, большие 9, записывать в виде букв A-F шестнадцатеричной системы счисления. Напоминание: умножайте только числа, записанные справа от черты (в примере ниже выделены красным), а в результат записывайте цифры, получающиеся слева от черты. Пример Перевод десятичной дроби 0,124 в шестнадцатеричную систему счисления: § 5. Перевод правильной десятичной дроби в произвольную систему счисления 0, 1 2 4 1 6 + 7 4 4 1 2 4 1 9 8 4 1 6 +5 9 0 4 9 8 4 F 7 4 4 1 6 +4 4 6 4 7 4 4 B 9 0 4 111 0,1241О » 0.1FB, Правило перевода смешанного числа: Чтобы перевести из десятичной системы счисления в произвольную смешанное десятичное число, необходимо отдельно перевести в новую систему счисления целую и дробную части и затем сложить их. ОБОБЩЕНИЕ НОВЫХ ЗНАНИЙ Алгоритм перевода правильной десятичной дроби в произвольную систему счисления отличается от алгоритма перевода целого числа. При переводе в шестнадцатеричную систему счисления необходимо следовать правилу умножения на двузначное число и помнить, что, если целая часть результата сложения превышает 9, она записывается в виде соответствующей буквы (A-F). В смешанном числе отдельно переводятся целая и дробная части. Для получения окончательного ответа результаты перевода целой части и правильной десятичной дроби суммируются. ПРИМЕНЕНИЕ ЗНАНИЙ 1. Переведите правильную десятичную дробь 0,125 в следующие системы счисления: а) пятеричную; в)восьмеричную; б) четверичную; г) шестнадцатеричную. 2. Переведите число 1 22,55 из десятичной системы счисления в следующие системы счисления: а) пятеричную; в)восьмеричную; б) четверичную; г) шестнадцатеричную. 112 Модуль 2. Системы счисления Проверь себя Задание 1 Определите, какое число следует за числом 3778. Задание 2 Переведите число 12334 в шестеричную систему счисления. Задание 3 Переведите из восьмеричной системы счисления в шестнадцатеричную систему счисления число 735,12. Задание 4 Выполните сложение двоичных чисел: 100111,1 + 111011,011. Задание 5 Выполните вычитание двоичных чисел: 10010101101 - 1110011111. Задание 6 Выполните вычитание восьмеричных чисел: 213 - 67. Задание 7 Переведите из десятичной системы счисления правильную десятичную дробь 0,75 в шестеричную систему счисления. ПРИМЕНЕНИЕ ЗНАНИЙ [необходимый уровень) Задание 1 Запишите целое число, следующее за данным: а) ABF16; б) 12334; в) 1001112. Задание 2 Переведите: а) в десятичную систему счисления числа 255,56; 101112; б) из десятичной системы счисления в шестеричную и в шестнадцатеричную системы счисления число 117; в) из восьмеричной системы счисления в шестнадцатеричную систему счисления число 456. Задание 3 Найдите сумму двоичных чисел 110110,11 и 11101,111. Задание 4 Найдите разность двоичных чисел 1110011 и 111101. Задание 5 Переведите число 111,2233 из четверичной системы счисления в шестнадцатеричную систему счисления. Задание 6 Выпишите целые числа от 212 до 1000 в троичной системе счисления. Задание 7 Какие целые числа предшествуют числам: 2008; 10002; 7708; 4005? Задание 8 Переведите в шестеричную систему счисления десятичную дробь 0,25. ПРИМЕНЕНИЕ ЗНАНИЙ [повышенный уровень) Задание 1 Переведите число 3256 в пятеричную систему счисления. Задание 2 Найдите сумму чисел 2134 и 1118. Результат запишите в четверичной системе счисления. 114 Задание 3 Найдите разность чисел 111001Ю12 и 5009. Результат запишите в восьмеричной системе счисления. Задание 4 Найдите сумму чисел 17516 системе счисления. и 11616. Ответ запишите в восьмеричной Задание 5 Переведите число 665д из восьмеричной системы счисления в троичную систему счисления. Задание 6 Какое наибольшее десятичное число можно записать двумя цифрами в: а) двоичной; б) восьмеричной; в) шестнадцатеричной системах счисления? Задание 7 Составьте таблицы сложения однозначных чисел в троичной и четверичной системах счисления. Задание 8 Дед, Бабка, Внучка и Жучка собирали в саду яблоки. Когда Мышка спросила, кто сколько собрал, каждый дал ответ в своей системе счисления. Дед назвал число 55, Бабка - 44, Внучка - 22, а Жучка - 11. Когда Дед добавил, что если бы каждый положил в свою корзину ещё только одно яблоко, то число яблок в каждой корзине можно было бы записать как 100, для Мышки уже не было секретом, сколько всего яблок собрала дружная семейка. Какое количество яблок насчитала Мышка? Задание 9 Переведите в восьмеричную систему счисления числа 34,1 2510 и 11 8,2510 и затем сложите их. Ответ запишите в шестнадцатеричной системе счисления. ПРИМЕНЕНИЕ ЗНАНИЙ (максимальный уровень) Задание 1 В некоторой системе счисления десятичное число 74 записывается как 202. Чему равно основание этой системы счисления? Задание 2 В спортивной секции плаванием занимаются 210 детей. Среди них 120 мальчиков и 50 девочек. В какой системе счисления записаны данные? 5 115 Задание 3 Даны три числа в шестнадцатеричной системе счисления А11016 и В1 Найдите их сумму. Ответ запишите в восьмеричной системе счисления. Задание 4 Даны три числа в восьмеричной системе счисления: 1758, 1248, 11 6д. Найдите их сумму. Ответ запишите в шестнадцатеричной системе счисления. Задание 5 В какой системе счисления справедливо равенство: 98 + 89 = 121? Задание 6 В какой системе счисления справедливо равенство: 35 + 21 = 100? Задание 7 Найдите сумму шестнадцатеричных чисел А1, А3, А5, А7. Ответ запишите в восьмеричной системе счисления. Задание 8 Запишите число 255 в системе счисления с основанием 254. Задание 9 Школьный калькулятор работает в четверичной системе счисления и может выводить на экран максимум четырёхзначное число. Каким будет максимальное десятичное число, которое можно отобразить на экране этого калькулятора? Задание 10 Переведите в шестнадцатеричную систему счисления числа 34,1 2510 и 118,2510 и затем сложите их. Ответ запишите в восьмеричной системе счисления. Задание 11 В классе 1111002 процентов девочек и 11002 мальчиков. Сколько учеников в классе? 116 Итоговая проверочная работа Задание 1 а) Расположите числа в порядке убывания: 10001102; 4568; 25110. б) Сложите числа 100010102 и 12334. Результат запишите в восьмеричной системе счисления. в) Найдите разность чисел 1000010012 и 3218. Результат запишите в двоичной системе счисления. г) Переведите число 234,0810 в пятеричную систему счисления. Задание 2 а) Запишите в десятичной системе счисления: • наибольшее трёхзначное число в восьмеричной системе счисления; • наибольшее трёхзначное число в шестнадцатеричной системе счисления. б) Найдите сумму и разность чисел 5678 и 10216. Ответ запишите в восьмеричной системе счисления. в) Переведите числа 234,5510 и 123,7510 в шестеричную систему счисления с точностью до второго знака после запятой и найдите их разность. Задание 3 а) Вычислите значение выражения: 1 238 + AB16 - 8110. Ответ запишите в восьмеричной системе счисления. б) Переведите числа 234,5510 и 123,7510 в шестнадцатеричную систему счисления с точностью до второго знака после запятой и найдите их сумму и разность. в) Расставьте вместо знаков «?» знаки арифметических операций так, чтобы были верны следующие равенства в двоичной системе счисления: • 11002 ? 112 ? 1002 = 1000002; • 11002 ? 102 ? 102 = 1002; • 11002 ? 102 ? 102 = 1100002. § 6. Деление и умножение в позиционных системах счисления 117 § 6. Деление и умножение в позиционных системах счисления ПОСТАНОВКА ПРОБЛЕМЫ УРОКА Из четырёх арифметических действий над числами в системах счисления вы освоили два: сложение и вычитание. Конечно, при желании можно было бы обходиться только ими: умножение заменять сложением, а деление — вычитанием. Но на практике умение умножать и делить сильно сокращает время вычислений. Как вы думаете, какие полезные навыки вы будете сейчас приобретать? Сформулируйте тему урока в виде вопроса. Сравните свой вариант с авторским (с. 142 учебника). НЕБХОДИМЫЕ БАЗОВЫЕ ЗНАНИЯ Назовите характеристики позиционной системы счисления. (§ 1) Как производится операция сложения в произвольной системе счисления? (§ 4) Как производится операция вычитания в произвольной системе счисления? (§ 4) РЕШЕНИЕ ПРОБЛЕМЫ УМНОЖЕНИЕ Умножение чисел в любой системе счисления (двоичной, троичной, восьмеричной и т. д.) выполняется по тем же правилам, что и в десятичной системе. Если при умножении цифр в некотором разряде получается значение, большее старшей цифры в данной системе счисления, в соответствующий разряд результата надо записать остаток от деления этого значения на 10^ в данной системе. Образовавшуюся цифру переноса (частное от деления на 10 ) нужно учитывать при вычислении в следующем разряде. Можно пользоваться следующим приёмом умножения. Цифры в разряде умножаются в десятичной системе, а результат умножения затем переводится в нужную систему счисления. В двоичной системе счисления операция умножения значительно упрощается, так как умножаются только цифры 0 и 1. Причём умножение на 1 первого сомножителя означает просто его копирование с соответствующим сдвигом по разрядам, без вычислений, а умножение на 0 вообще пропускается. 118 Модуль 2. Системы счисления Пример 1 110 1 ________110 0 110 1 110 1________ 10 0 1 1 10 0 11012^11002 = 100111002 Пример 2 1 0 1, 0 1 у 1 0 0, 1 10 10 1 10 10 1___________ 10 1 1 1, 1 0 1 101,012 •100,12 = 10111,1012 Пример 3 Нахождение произведения восьмеричных чисел: 1 7 2 3 2 0 6. 5 5 3 2 7 6. 1 7 2 7 6. При умножении в 1-м разряде в десятичной системе счисления получается 3010 = 368, поэтому в 1-м разряде пишем 6, а 3 переносим во 2-й разряд. При следующем умножении получаем 15 (6 ^2+3 = 15) в десятичной системе счисления, 1510 = 178, поэтому во 2-м разряде пишем 7, а 1 переносим в следующий разряд и т. д. 7258 ^2063 = 17 25768 ДЕЛЕНИЕ Деление чисел в любой системе счисления производится так же, как и в десятичной системе счисления. Можно пользоваться при выполнении действий десятичной системой, результаты переводить в нужную систему. Пример 4 Деление чисел 110012 и 1012: 1 10 0 1 1 0 1 1 0 1 1 0 1 0 0 0 Пример 5 Деление чисел 1111112 и 101012: 1 0 1 0 10 10 1 1 1 0 0 0 0 0 X § 6. Деление и умножение в позиционных системах счисления 119 Пример 6 Деление чисел 1011012 и 100102: 1 0 1 1 0 1 1 0 0 1 0 1 0 0 1 0 1 0 1 1 0 0 1 0 1 0 0 1 0 0 Пример 7 Деление чисел 233638 и 738: 2 3 3 6 3 7 3 1 6 6 2 5 1 4 4 5 4 6 7 7 7 3 3 0 В числе 2338 поместится 2^738 = 1668. В числе 4568 поместится 5^738 = 4478. 4568 - 4478 = 78 В числе 738 поместится 1^738 = 738. АРИФМЕТИЧЕСКИЕ ОПЕРАЦИИ НАД ШЕСТНАДЦАТЕРИЧНЫМИ ЧИСЛАМИ Примеры Сложение: 2 A D E 5 2 4 1- й разряд: (2 + 4)16 = (2 + 4)10 = 610 = 616; 2- й разряд: (Е + 5)16 = (14 + 5)10 = 1910 = 1316; пишем 3, а 1 переносим в 3-й разряд: (2 + A + 1)16 = (2 + 10 + 1)10 = 1310 = D16. Вычитание: 69 _2_А_ 3 F 1 -й разряд: занимаем 1^161 (1 610) из 2-го разряда; (9 + 16 - А)16 = (9 + 16 - 10)10 = 1510 = F16; 2-й разряд: (5 -2)16 = 316. + 6 120 Модуль 2. Системы счисления Умножение: 2 2 E _____3_ 8 A 1 -й разряд: (Е • 3)16 = (14 • 3)10 = 4210 = (2^161 + Ю^160)10 = 2A, пишем A, 2 переносим в следующий разряд; 2-й разряд: (2^3 + 2) = 816. Деление: B 4 ■ 8_ 3 4 ■ 3___4 0 4______ B16 = 1110; (11:4)10 = 2 (ост. 3)10 = 2 (ост. 3)16; 2 D 3416 = (3^161 + 4)10 = 52ю; (52:4)10 = 1310 = D10. ОБОБЩЕНИЕ НОВЫХ ЗНАНИЙ Деление и умножение в произвольной системе счисления производятся по тем же правилам, что и в десятичной системе. ПРИМЕНЕНИЕ ЗНАНИЙ Вычислите значения следующих выражений: а) 234,58 +15,28< 218 - 12в; б) 11100112:110012; в) 27110:1910; г) 2558 + 11001,112 • (008 + 1410) - 1 F10. Ответ запишите в четверичной системе счисления. X § 7. Запись числа в общем виде 121 § 7. Запись числа в общем виде ПОСТАНОВКА ПРОБЛЕМЫ УРОКА Теперь вы знаете, как раскладывается число по степеням основания в любой позиционной системе счисления. Проанализируйте, что общего во всех таких записях и чем они различаются. Вспомните, как с развёрнутой формой связано обычное представление числа. • Какие закономерности вы обнаружили? Сформулируйте проблему урока. Сравните свой вариант с авторским (с. 142 учебника). НЕБХОДИМЫЕ БАЗОВЫЕ ЗНАНИЯ Вспомните основные характеристики системы счисления (основание и базис). (§ 1) Вспомните, что такое развёрнутая форма записи числа. (§ 1) Вспомните, как переводится в десятичную систему счисления число, записанное в произвольной системе счисления. (§ 2) РЕШЕНИЕ ПРОБЛЕМЫ Давайте вспомним, как переводится в десятичную систему счисления число, записанное в произвольной системе счисления. Нас не будет в данный момент интересовать результат перевода (не надо выполнять арифметические действия), обратим внимание на запись этих чисел. Примеры: 100,1225 = 1^52 + О^б1 + 0^50 + 1^5-1 + 2^5-2 + 2^5-3; 11010,1102 = 1^24 + 1^23 + 0^22 + 1^21 + 0^20 + 1^2-1 + 1^2-2. Выведем теперь общий вид записей чисел в развёрнутой форме. 1. Обозначим основание системы счисления буквой р, степень основания буквой т, а коэффициент при рт обозначим буквой a с индексом m (равным степени основания). 2. Убывающие на 1 в каждом следующем слагаемом степени основания будут обозначены как т, т - 1, т - 2 и т. д. 3. Основания в этих степенях будут выглядеть как рт, pm-1, pm-2 и т. д. 4. Коэффициенты при этих слагаемых будут обозначены соответственно am, am-1, ат-2 и т. д 122 Модуль 2. Системы счисления Число в любой позиционной системе счисления можно представить в общем виде: N = a -рт + a .• P ^ ^ m-1 ^ m -1 a0* P0 + a_1 • p-1 + a_2 • p _2 ■ a_k'P~ целая часть дробная часть где m _ максимальная для этого числа положительная степень основания, к _ максимальная отрицательная (_k _ минимальная!) степень основания. От m до 0 _ область целой части, от _1 до _к _ дробной. Пример 1 Число N = 893,70510 = 8-102 + 9-101 + 3-100 + 7*10_1 + 0*10_2 + 5*10_3 представляется в общем виде так: N = a2p2 + a1 p1 + a0 p0 + a_1 p_1 + a_2 p_2 + a_3 p_3, где р = 10, a2 = 8, a1 = 9, a0 = 3, а_1 = 7, а_2 = 0, а_3 = 5. Наиболее часто число в общем виде представляется только в виде совокупности коэффициентов, записанных в соответствующих позициях. Разделителем целой и дробной части служит запятая: N = a a . a^, a ^ ^ a , m m_1^ 0 _1 _2^ _k целая часть дробная часть Пример 2 Число N = 321,024 представим в развёрнутой форме: 321,024 = 3-42 + 2-41 + 1-40 + 0*4_1 + 2*4_2. Общий вид этого числа в виде совокупности коэффициентов: N = a2a1 a0, a_1 a_2, где a2 = 3, a1 = 2, a0 = 1, a_1 = 0, a_2 = 2. То есть запись 321,02 _ это и есть представление числа в виде совокупности коэффициентов. Замечание. Обратите внимание: если в представлении числа в развёрнутой форме отсутствует какая-то степень, то, с учётом того, что система счисления _ позиционная, в месте, соответствующем этой степени, в записи числа в виде совокупности коэффициентов должен появиться 0. Не забывайте про это. к § 7. Запись числа в общем виде 123 ОБОБЩЕНИЕ НОВЫХ ЗНАНИЙ Для всех позиционных систем счисления существует общий вид числа: N = am-pm + • pm-1 +_+ a0*p° + a_1 • p-1 + a_2* p-2 +...+ a_^* p-k, где p _ основание системы счисления, m _ максимальная для этого числа положительная степень основания, к _ максимальная отрицательная (_k _ минимальная!) степень основания, am,_, a_k _ коэффициенты при степенях основания. Наиболее часто число представляется только в виде совокупности коэффициентов, записанных в соответствующих позициях: N = am am_1..a0, a_ia_2..a_k- ПРИМЕНЕНИЕ ЗНАНИЙ 1. Запишите число в развёрнутой форме. Укажите, чему равно основание p и коэффициенты am,., a_k при соответствующих степенях основания: а) 2376, 268; б) 304, 016; в) 10A, 2316. 2. Запишите число в виде совокупности коэффициентов, записанных в соответствующих позициях: а) 2-53 + 3-51 + 1*5_1; б) 1 *164 + 3-162 + D*16_2; в) 1 • 27 + 1 -24 + 1 -22 + 1 -20 + 1 -2_2 + 1-2_3. Подсказка. Для решения следующих задач запишите числа в развёрнутой форме, обозначив неизвестное основание системы счисления как p. 3. Учитель записал, что в олимпиаде по информатике принимало участие 10 учеников 8-го класса и 50 учеников 9-го класса. Общее количество учеников _ 100. В какой системе счисления учитель записал данные? 4. 60 груш разрезали пополам, и получилось 1 50 половинок. В какой системе счисления записаны числа? Чему равно количество груш в десятичной системе счисления? 124 Модуль 2. Системы счисления § 8. Кодирование чисел. Представление чисел (беззнаковых и целых) в памяти компьютера ПОСТАНОВКА ПРОБЛЕМЫ УРОКА До сих пор вы изучали числа, представленные в разных системах счисления, в том числе и двоичной, без связи с компьютером. Множество чисел (как целых, так и вещественных) бесконечно. Никогда при «ручных» вычислениях не возникает проблемы, что число куда-то «не поместится». Другое дело — компьютер. Одна из его важных характеристик — объём оперативной памяти. Она не бесконечна и определяется характеристиками компьютера. Числа разных типов требуют для своего размещения разное количество памяти. Сегодня мы говорим о целых числах. Есть ли разница в том, как мы записываем числа, и в том, как они представлены в памяти компьютера? Какую проблему вы видите? Сформулируйте тему урока в виде вопроса. Сравните свою формулировку с авторской (с. 142 учебника). НЕБХОДИМЫЕ БАЗОВЫЕ ЗНАНИЯ Вспомните, как переводятся числа из десятичной системы счисления в двоичную и обратно. (§ 2) Вспомните, как переводятся двоичные числа в восьмеричную и шестнадцатеричную системы счисления. (§ 3) РЕШЕНИЕ ПРОБЛЕМЫ Познакомимся с некоторыми важными терминами. Разряд - элемент памяти, способный находиться в одном из двух состояний (0/1), служащий для хранения одного разряда двоичного числа. Таким образом, в одном разряде хранится 1 бит данных. Ячейка памяти - минимальная адресуемая часть памяти компьютера. Она может составлять для конкретной машины 1 байт, 2 байта и т. п. Существуют два основных формата представления чисел в памяти компьютера. Один из них используется для кодирования целых чисел - это формат с фиксированной запятой (говорят также: с фиксированной точкой). В этом случае каждому разряду памяти соответствует всегда один и тот же разряд числа, а запятая «располагается» справа от младшего разряда (вне разрядной сетки). Второй формат служит для представления чисел с плавающей запятой (точкой), используется для задания вещественных (дробных) чисел. Его мы рассмотрим в следующем параграфе. Для размещения чисел разных типов используется разное количество ячеек (байтов) памяти. Обратим внимание на представление целых чисел в памяти компьютера. § 8. Кодирование чисел. Представление чисел (беззнаковых и целых) в памяти компьютера 125 ЦЕЛЫЕ ЧИСЛА БЕЗ ЗНАКА Для представления целых чисел без знака может использоваться 1 байт или 2 байта. Максимально возможное число без знака: Однобайтовый формат (8 битов): 1 1 1 1 1 1 1 1 28 - 1 = 255 Двухбайтовый формат (16 битов): 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 216 - 1 = 65 535 ЦЕЛЫЕ ЧИСЛА СО ЗНАКОМ Для представления целых чисел со знаком в компьютере используются прямой, обратный и дополнительный коды числа. Для положительного числа прямой, обратный и дополнительный коды совпадают и представляют двоичный код числа. Старший (крайний левый) бит в представлении числа отводится под знак числа и для положительного числа содержит 0. Отрицательное число в прямом, обратном и дополнительном кодах отображается по-разному: • прямой код - двоичный код модуля числа; • обратный код - инвертированный (включая знак числа) двоичный код модуля числа. Инвертировать бит числа - значит изменить его значение на противоположное: 0 на 1, а 1 на 0 (вспомните, в § 4 мы уже выполняли инвертирование двоичного числа); • дополнительный код получается путём прибавления 1 к обратному коду. Отрицательные целые числа в компьютере представляются в дополнительном коде. В знаковом разряде при этом находится 1 - признак отрицательного числа. Алгоритм получения дополнительного кода отрицательного числа: 1. Найти двоичный код модуля этого числа. 2. Инвертировать содержимое всех разрядов, включая разряд знака. 3. Прибавить 1 к обратному коду. 126 Модуль 2. Системы счисления Пример Представление в обратном и дополнительном коде числа -6710: Степени основания (р = 2): 1. Прямой код модуля числа |-67| 2. Обратный код числа -67: 3. Дополнительный код числа -67: 7 6 5 4 3 2 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 Отрицательные числа при вводе в машину преобразуются в дополнительный код и в таком виде хранятся, участвуют в операциях, перемещаются, а при выводе результата происходит обратное преобразование в отрицательное десятичное число. Для этого дополнительный код инвертируется, и к результату прибавляется 1. Получается модуль числа, который и переводится в десятичную систему счисления. Потом добавляем знак «-» - и готово. Диапазон значений целых чисел со знаком на примере однобайтового представления: Максимальное число 7 6 5 4 3 2 1 0 0 1 1 1 1 1 1 1 127 Минимальное число 7 6 5 4 3 2 1 0 1 0 0 0 0 0 0 0 -128 Целые числа со знаком обычно занимают в памяти компьютера 1,2 или 4 байта. Диапазоны значений целых чисел со знаком: Формат числа, байты Значение 1 -128^127 2 -32 768^32 767 4 -2 147 483 648^2 147 483 647 Задача. Число N = -67 представлено в однобайтовом формате в дополнительном коде. Затем чётные биты были инвертированы (0-й бит считать чётным). Какому десятичному числу соответствует полученный код? Какому шестнадцатеричному числу соответствует полученный код? + § 8. Кодирование чисел. Представление чисел (беззнаковых и целых) в памяти компьютера 127 Решение 1. Находим двоичное выражение |-67|. 2. Находим обратный код. 3. Вычисляем дополнительный код, получаем код числа -67. 4. Инвертируем содержимое чётных разрядов. 7 6 5 4 3 2 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 1 0 1 1 1 1 0 1 1 1 1 0 1 0 0 0 Определяем модуль полученного отрицательного числа: 1. Инвертируем содержимое всех разрядов. 2. Прибавляем 1. 3. Получаем модуль шестнадцатеричного числа: 18, ■^16. 4. Получаем модуль десятичного числа: 241 0 0 0 1 0 1 1 1 0 0 0 1 1 0 0 0 , , 1 8 1^24+1^23 = 2410 Ответ: десятичное число: -2410; шестнадцатеричное число: -1816. ОБОБЩЕНИЕ НОВЫХ ЗНАНИЙ Числа в компьютере кодируются двоичным кодом. Целые числа представляются в формате с фиксированной запятой. Целые положительные числа представляются в прямом коде (это двоичный код числа), в старший бит записывается 0. Для представления целого отрицательного числа служат прямой, обратный и дополнительный коды. Отрицательные числа в памяти компьютера представляются в дополнительном коде. Старший бит целого отрицательного числа содержит 1. При выводе результата происходит обратное преобразование: дополнительный код инвертируется, и к нему прибавляется 1. ПРИМЕНЕНИЕ ЗНАНИЙ 1. Запишите 8-битовое представление в памяти компьютера следующих чисел: -2510, 11710, 2510. Как будут выглядеть шестнадцатеричные коды этих чисел? 2. Запишите 12-битовое представление в памяти компьютера следующих чисел: 12310, -2310 Как будут выглядеть шестнадцатеричные коды этих чисел? 3. Для хранения целого числа -8910 в дополнительном коде используется однобайтовое представление. Сколько единиц оно содержит? 128 Модуль 2. Системы счисления § 9. Запись числа в нормализованном виде. Числа с плавающей запятой. Представление вещественных чисел в памяти компьютера ПОСТАНОВКА ПРОБЛЕМЫ УРОКА Вы имеете большой опыт вычислений, в которых используются дробные (вещественные) числа. Очень большие и очень маленькие числа участвуют в вычислениях при решении задач по физике и химии. Оперировать с такими числами в виде, как мы их привыкли записывать, неудобно. Вы узнаете, как записать такие числа, чтобы вычисления стали более эффективными. Как вы считаете, как решается указанная проблема? Сформулируйте тему урока в виде вопроса. Сравните свой вариант с авторским (с. 142 учебника). РЕШЕНИЕ ПРОБЛЕМЫ СТАНДАРТНЫЙ ВИД ЧИСЛА Для записи больших чисел, например данных о Земле: радиус - R3 (средний) = 6 371 000 м; масса - Мз = 6 000 000 000 000 миллиардов тонн; или очень маленьких, например данных об электроне: масса - Мэ = 0,0000^09 кг (30 нулей после запятой!), неудобно пользоваться числами, записанными в привычном виде. Такие числа записываются в стандартном виде N = ± &• 10^, где 0 < а < 10, q - порядок числа (степень основания системы счисления), a - мантисса числа: Пз (средний) = 6 371 000 м = 6,371^106 м, q = 6 (порядок числа равен 6); Мз = 6 000 000 000 000 млрд тонн = 6^1012 млрд тонн = 6^1024 кг, q = 24; Мэ = 0,0^09 кг = 9^10-31 кг, q = -31 (для дробных чисел порядок отрицательный). Как видите, знак порядка будет положительным для чисел, больших 1, и отрицательным для чисел, меньших 11 |. Насколько компактной получается запись! Кроме удобства записи, у чисел, записанных в стандартном виде, есть самое главное преимущество: действия над ними производить гораздо легче, и меньше возможность ошибиться. НОРМАЛИЗОВАННЫЙ ВИД ЧИСЛА Число в нормализованном виде выглядит так: N = ± m^pq, где m - мантисса числа, q - порядок числа, p - основание системы счисления. Мантисса должна быть меньше 1, и первая её значащая цифра не должна быть нулём. (Вспомним, что для чисел, меньших 1, q < 0; например: 0,002310 = 0,23^10-210.) § 9. Запись числа в нормализованном виде. Числа с плавающей запятой^ 129 При записи числа в нормализованной форме принято мантиссу и порядок записывать в соответствующей системе счисления, а основание системы счисления - в десятичной системе. Примеры Числа в нормализованном виде: Ю1 3,510 = 0,35 10’ 1101,0112 = 0,1101011 ■21002 (m = 0,11010112; p = 2^; q=4ю = 1002) ПРЕДСТАВЛЕНИЕ ВЕЩЕСТВЕННЫХ ЧИСЕЛ В КОМПЬЮТЕРЕ Для представления вещественных чисел в компьютере используется запись числа с плавающей запятой (говорят также: с плавающей точкой). Предварительно вещественное число (так же, как и целое) должно быть переведено в двоичную систему счисления. При представлении чисел с плавающей запятой в старший бит записывается знак числа, часть разрядов отводится для записи порядка числа, остальные - для записи значащей части. Для того чтобы не хранить знак порядка (он может быть положительный или отрицательный), используется способ представления чисел с помощью смещённого порядка (СП). К истинному значению порядка прибавляется смещение. Смещение выбирается так, чтобы минимальному значению порядка соответствовал 0. Смещённый порядок рассчитывается по формуле: СП = (2^-1 - 1) + q, где q - истинный порядок числа, к - количество разрядов, отводимых в ячейке для записи смещённого порядка. В зависимости от представления числа (от типа числа) под порядок отводится различное количество разрядов. Например, в 4-байтовом представлении для записи порядка отводится 1 байт (8 битов), к = 8. 2к-1 - 1 = 28-1 - 1 = = 12710. Таким образом, в четырехбайтовом представлении может разместиться число, имеющее порядок (q), принимающий значения в диапазоне от -1 28 до +1 27. Формула для СП будет выглядеть так: СП = 11111112 + q2. Значения смещённого порядка (СП) при этом меняются от 0 до 25510. Существует стандарт для представления чисел с одинарной точностью (4 байта) и с двойной точностью (8 байтов). Он основан на том факте, что для представления числа в памяти компьютера его записывают таким образом, что в значащей части, перед запятой всегда 1. В целях экономии ресурсов были установлены следующие правила: 1) для хранения этой единицы не выделяется дополнительный бит: единица подразумевается, как и двоичная запятая; 2) в данном стандарте принято, что мантисса всегда больше 1; то есть диапазон значащей части лежит в пределах от 1 до 2. 130 Модуль 2. Системы счисления Алгоритм представления числа с плавающей запятой: 1. Перевести модуль числа из системы счисления с основанием p в двоичную систему счисления. 2. Представить двоичное число в нормализованной форме (1 < m < 2). 3. Вычислить смещённый порядок числа. 4. Разместить знак числа, СП и мантиссу в соответствующих разрядах ячейки. Задача 1 Требуется представить число -147,12510 в компьютерном виде, в 4-байтовом представлении. Найти его шестнадцатеричный код. Решение 1. Найдём двоичное представление числа |-147,125|: а) 14710 = 1^27 + 1^24 + 1^21 + 1^2° = 100100112; б) 0,12510 = 0,0012. 147,125 = 10010011,0012. 2. Представим это число в нормализованной форме: 10010011,001 = 1,0010011001^2111; q=111; m = 1,00100110012. 3. СП = 11111112 + 1112 = 100001102. 4. Разместим данные в памяти, убирая 1 из значения мантиссы и помня, что старший бит отводится под знак числа. Так как в данном случае число отрицательное, пишем 1. 1 1 0 0 0 0 1 1 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 * смещённый порядок (8 битов) абсолютная величина мантиссы (23 бита) * - знак числа (мантиссы): 0 - для положительного числа, 1 - для отрицательного. Шестнадцатеричный код занимает меньше места: С3132000: 110 0 0 0 11 0 0 0 1 0 0 11 0 0 10 0 0 0 0 0 0 0 0 0 0 0 0 С 3 1 3 2 0 0 0 Задача 2 Значение переменной представлено в формате с плавающей запятой и выражено в шестнадцатеричной системе счисления: N = C253000016. Требуется найти десятичное значение числа. § 9. Запись числа в нормализованном виде. Числа с плавающей запятой^ 131 Решение 1. Найдём двоичное выражение шестнадцатеричного числа: 110 0 0 0 10 0 10 1 0 0 11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 C 2 5 3 0 0 0 0 2. В старшем бите записана 1, значит, число отрицательное. 3. Выделим смещённый порядок (отсчитаем 8 позиций от старшего бита): СП = 10000100. 4. Найдём истинный порядок (q). Так как СП = (28-1 - 1) + q, то q = 100001002 - 11111112 = 1012, q = 510. 5. Учитывая «убранную» 1, запишем мантиссу: m = 1,1010011. 6. Учитывая порядок (q = 510), запишем двоичное число: N = -110100,112. 7. Находим десятичное число: N = -52,7510. ОБОБЩЕНИЕ НОВЫХ ЗНАНИЙ Существуют различные способы записи вещественных (дробных) чисел. При вычислении выражений с очень большими и очень маленькими десятичными числами «вручную» удобно пользоваться числами, записанными в стандартном виде: N = ± a^10q, где 0 < а < 10, q < 0 для a < 1, q > 0 для a > 1. Число в нормализованном виде выглядит так: N = ± m^pq, причём мантисса (m < 1, первая цифра мантиссы больше 0) и порядок (q) записываются в текущей системе счисления, а основание системы счисления (p) -в десятичной. Для представления вещественных чисел в компьютере используется запись числа с плавающей запятой (точкой). Предварительно вещественное число (так же, как и целое) должно быть переведено в двоичную систему счисления и представлено в нормализованной форме (1 < m < 2). Для того чтобы не хранить знак порядка (он может быть положительный или отрицательный), используется способ представления чисел с помощью смещённого порядка. 132 Модуль 2. Системы счисления ПРИМЕНЕНИЕ ЗНАНИИ 1. Объясните, чем отличается запись числа в стандартном виде от записи в нормализованном виде. 2. Как изменяются правила записи числа в нормализованном виде для представления данного числа в компьютере? 3. Запишите числа в стандартном виде. а) -124 834,3410; б) 0,0000404004510; в) 600000000000010. 4. Запишите числа в нормализованном виде. а) -32423,225; б) 11100112,223; в) 0,000001112. 5. Как представлены в компьютере в четырёх байтах следующие числа? Определите их шестнадцатеричные коды. а) -25,2510; б) 188,12510. § 10. Сложение целых чисел в памяти компьютера 133 § 10. Сложение целых чисел в памяти компьютера ПОСТАНОВКА ПРОБЛЕМЫ УРОКА Вы знаете, что числа в компьютере кодируются двоичным кодом, и знакомы с некоторыми способами их размещения в памяти компьютера. Но в оперативной памяти числа не только хранятся, из ячеек памяти процессор берёт данные для вычислений. Вы умеете выполнять арифметические действия с двоичными числами «вручную», но в то же время знаете, что представление чисел в компьютере отличается от того, в каком виде вы их используете для вычислений. Как вы считаете, какая проблема в этой ситуации? Сформулируйте тему урока в виде вопроса. Сравните свой вариант с авторским (с. 142 учебника). НЕБХОДИМЫЕ БАЗОВЫЕ ЗНАНИЯ Вспомните, как представляются целые числа в памяти компьютера. (§ 8) РЕШЕНИЕ ПРОБЛЕМЫ Мы будем говорить о сложении целых чисел в компьютере. Почему из всех арифметических действий мы выбрали именно сложение? Дело в том, что одной операции сложения достаточно для того, чтобы через неё получить все другие. Разберём алгоритм сложения на примерах, рассмотрим все варианты знаков чисел. Найдём для дальнейшего использования прямой, обратный и дополнительный коды целых чисел А и В, где | А | = 8, | Б| = 7: Код |А| = 8 |В| = 7 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 Прямой 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 Обратный 1 1 1 1 0 1 1 1 1 1 1 1 1 0 0 0 Дополнительный 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0 1 Алгоритм сложения чисел в компьютере: 1. Разместить слагаемые в разрядных сетках в прямых кодах. 2. Отрицательное слагаемое (слагаемые) преобразовать в дополнительный код. 3. Слагаемые складываются по правилам сложения двоичных чисел. При этом знаковые разряды участвуют в вычислениях наряду с числовыми разрядами. 4. Единицу переноса из знакового разряда (если таковая возникнет) отбросить. 134 Модуль 2. Системы счисления 5. Если результат положителен, то он представлен в прямом коде и не требует никаких преобразований. Если результат отрицателен, то он представлен в дополнительном коде. По известным правилам преобразовать его в прямой код модуля числа. Знак «-» дописать к результату. • Вспомните правила преобразования чисел из дополнительного кода в прямой. Что при этом получается? Разберём возможные случаи соотношения знаков слагаемых А и В. 1. Оба числа положительные (А = 8, В = 7): Степени двойки 7 6 5 4 3 2 1 0 А (прямой код) 0 0 0 0 1 0 0 0 В (прямой код) 0 0 0 0 0 1 1 1 Сумма (прямой код), единица переноса не возникает 0 0 0 0 1 1 1 1 Ответ: А + В = 11112 = 1510 0 0 0 0 1 1 1 1 2. Оба числа отрицательные (А = -8, В = -7): Степени двойки 7 6 5 4 3 2 1 0 А (дополнительный код) 1 1 1 1 1 0 0 0 В(дополнительный код) 1 1 1 1 1 0 0 1 Сумма (дополнительный код), единица переноса 1 1 1 1 0 0 0 1 отбрасывается Получение модуля числа. Ответ: А + В = -11112 = -1510 0 0 0 0 1 1 1 1 3. Числа разных знаков, положительное число по модулю больше отрицательного (А = 8, В = -7): Степени двойки 7 6 5 4 3 2 1 0 А (прямой код) 0 0 0 0 1 0 0 0 В(дополнительный код) 1 1 1 1 1 0 0 1 Сумма (прямой код), единица переноса отбрасывается 0 0 0 0 0 0 0 1 Ответ: А + В = 12 = 110 0 0 0 0 0 0 0 1 4. Числа разных знаков, положительное число по модулю меньше отрицательного (А = -8, В = 7): Степени двойки 7 6 5 4 3 2 1 0 А (дополнительный код) 1 1 1 1 1 0 0 0 В (прямой код) 0 0 0 0 0 1 1 1 Сумма (дополнительный код), единица переноса не 1 1 1 1 1 1 1 1 возникает Получение модуля числа. Ответ: А + В = -12 = -110 0 0 0 0 0 0 0 1 § 10. Сложение целых чисел в памяти компьютера 135 Самостоятельно найдите прямой и дополнительный коды чисел 87 и 67. 5. Оба числа положительные, их сумма не меньше, чем 2П-1 (А = 87, В = 67, А + В > 128, для восьмибитового представления): Степени двойки 7 6 5 4 3 2 1 0 Л (прямой код) 0 1 0 1 0 1 1 1 В (прямой код) 0 1 0 0 0 0 1 1 Сумма - несовпадение знака суммы со знаками слагаемых 1 0 0 1 1 0 1 0 Ошибка: появилась единица в знаковом разряде. 6. Оба числа отрицательные, сумма их модулей не меньше, чем 2П-1 (А = -87, В = -67, | Л | + | Б| > 128, для восьмибитового представления): Степени двойки 7 6 5 4 3 2 1 0 Л (дополнительный код) 1 0 1 0 1 0 0 1 В(дополнительный код) 1 0 1 1 1 1 0 1 Сумма - несовпадение знака суммы со знаками слагаемых 0 1 1 0 0 1 1 0 Ошибка: переполнение разрядной сетки ОБОБЩЕНИЕ НОВЫХ ЗНАНИЙ Суммирование целых чисел происходит поразрядно. Отрицательное число представляется в дополнительном коде. Единица переноса (если она возникает) отбрасывается. Если результат положителен, он представлен в прямом коде и не требует никаких преобразований. Если результат отрицателен, то он представлен в дополнительном коде. По известным правилам он преобразуется в прямой код модуля числа. ПРИМЕНЕНИЕ ЗНАНИЙ Выполните сложение десятичных чисел. Укажите, в каких случаях имеет место переполнение разрядной сетки. а) 100 - 56; б) - 110 + 66; в) 125 + 100; г) -45 - 34. 136 Модуль 2. Системы счисления Проверь себя Задание 1 Найдите произведение чисел 458 и 128. Задание 2 Найдите частное от деления 100001002 на 11002. Задание 3 Как представлено десятичное число 117 в памяти компьютера? Задание 4 Как представлено десятичное число -234 в памяти компьютера? Найдите его шестнадцатеричный код для 1 2-битового представления. Задание 5 Запишите десятичное число 25,5 в 4-байтовом представлении. Каков его шестнадцатеричный код? ПРИМЕНЕНИЕ ЗНАНИЙ [необходимый уровень) Задание 1 Определите число по приведённым данным - основанию системы счисления и коэффициентам в его записи в общей форме: р = 4, а3 = 1, а2 = 0, а^ = 3, а0 = 0, а-1 = 1. Задание 2 Представьте целые десятичные числа в однобайтовом формате. а) 115; б) -100; в) 122; г) 65. Задание 3 Представьте целые десятичные числа в однобайтовом формате. Определите шестнадцатеричный код представления. а) -117; б) -88; в) -1 00; г) -87. Задание 4 Найдите произведение чисел. а) 1234 и 1114; б) 1101112 и 101112; в) 10223 и 2223. Задание 5 Найдите частное от деления чисел. а) 1010011112 и 10000112; б) 11111012 и 110012; в) 1001101002 и 101102. Задание 6 Десятичное число N = -100 представлено в формате с фиксированной запятой в дополнительном коде. Длина формата - 8 двоичных разрядов. Определите, какому восьмеричному числу соответствует код. 138 Модуль 2. Системы счисления Задание 7 Как представляется в памяти компьютера десятичное число -112,25? ПРИМЕНЕНИЕ ЗНАНИЙ (повышенный уровень) Задание 1 Числа записаны в дополнительном коде в восьмибитовом представлении. Определите, какому шестнадцатеричному числу будет соответствовать этот код. а) 10011111; б) 11001010; в) 11101010; г) 11000001. Задание 2 Числа записаны в дополнительном коде в восьмибитовом представлении. Найдите их десятичные представления. а) 10000111 б) 01111010 в) 00101010 г) 11011101 Задание 3 Как представлены вещественные числа в компьютере (в четырёхбайтовом представлении)? а) -123,2310; б) 1011011010,111012. Задание 4 Выполните операцию A + B. Отрицательное число представьте в дополнительном коде. Формат - 1 байт. а) A = 9, B = -2; б) A = -17, B = 12. Задание 5 Десятичное число N = -117 представлено в формате с фиксированной запятой в дополнительном коде. Длина формата - 12 двоичных разрядов. Определите, какому шестнадцатеричному числу соответствует код. Задание 6 Найдите произведение восьмеричных чисел 3178 и 258. Задание 7 Найдите частное от деления четверичных чисел 33204 и 204. ПРИМЕНЕНИЕ ЗНАНИЙ (максимальный уровень) Задание 1 Шестизначное десятичное число оканчивается цифрой 4. Если эту цифру переставить из конца числа в начало, то есть приписать её перед первой цифрой, не изменяя порядок остальных пяти, то получится число, которое в четыре раза больше первоначального. Найдите это число. Подсказка. Представим первое число: А = 10^у + 4. (Что обозначим как у?) Тогда второе число: B = 4^10" + у. (Что обозначим как n? Чему равно n для данной задачи?) Составив и решив уравнение, получите ответ. Задание 2 Десятичное число N = -145 представлено в формате с фиксированной запятой в дополнительном коде. Длина формата - 16 двоичных разрядов. Определите, какому шестнадцатеричному числу будет соответствовать код, если значения битов с номерами 0, 1, 2, 3 и 4 инвертировать. Номера битов отсчитываются справа налево, начиная с нуля. Младший бит - бит с номером 0. Задание 3 Даны два числа: десятичное число А = -3010 и шестнадцатеричное число В = -2016. В памяти компьютера эти числа представлены в формате с фиксированной запятой в дополнительном коде. Длина формата - 12 двоичных разрядов. Выполните операцию А + В - определите восьмеричный дополнительный код результата операции. Задание 4 Выполните операцию A + B, где A = 2, B = -9. Отрицательное число представлено в дополнительном коде. Формат - 1 байт. Представьте код результата в шестнадцатеричной системе счисления. Задание 5 Найдите произведение чисел. а) 101116 и 12316; б) 2278 и 17,28. Задание 6 Найдите частное от деления чисел Е6516 и 3716. 140 Итоговая проверочная работа Задание 1 а) Десятичное число N = -89 представлено в формате с фиксированной запятой в дополнительном коде. Длина формата - 8 двоичных разрядов. Определите этот код. б) Найдите произведение чисел 11011012 и 11012. в) Найдите сумму чисел А = 12, В = 6 в восьмибитовом формате. Ответ запишите в шестнадцатеричном коде. г) Запишите десятичную дробь 133,125 в представлении в памяти компьютера. Задание 2 а) Десятичное число N = -121 представлено в формате с фиксированной запятой в дополнительном коде. Длина формата - 12 двоичных разрядов. Определите шестнадцатеричный код этого представления. б) Найдите произведение чисел 24,58 и 478. в) Найдите сумму чисел А = -12, В = -15 в восьмибитовом формате. Код суммы запишите в восьмеричной системе счисления. г) Запишите десятичную дробь -145,25 в представлении в памяти компьютера. Задание 3 а) Десятичное число N = -151 представлено в формате с фиксированной запятой в дополнительном коде. Длина формата - 12 двоичных разрядов. Определите, какому десятичному числу будет соответствовать код, если значения битов с чётными номерами (бит с номером 0 считать чётным) инвертировать. Номера битов отсчитываются справа налево, начиная с нуля. Младший бит - бит с номером 0. б) Трёхзначное десятичное число оканчивается цифрой 3. Если эту цифру переместить на два разряда влево, то есть так, что с неё будет начинаться запись нового числа, то это новое число будет на единицу больше утроенного исходного числа. Найдите исходное число. в) Найдите сумму чисел А = -112, В = -126 в восьмибитовом формате. Ответ запишите в шестнадцатеричном коде. г) Найдите произведение чисел 24,78 и 22,28. Ответ запишите в шестнадцатеричной системе счисления. д) Найдите частное от деления ЕЕ16 и 7016. Ответ запишите в двоичной системе счисления. Содержание Дорогие ребята!.....................................................3 Модуль 1. Алгоритмизация и программирование.........................9 Введение...........................................................10 § 1. Знакомство с математической логикой.........................11 Что означают понятия «логика» и «математическая логика»? § 2. Поиск в массиве.............................................20 Как искать данные в массиве? § 3. Упорядочение массивов.......................................25 Что такое упорядочение массивов и как оно происходит? § 4. Структурирование программ. Подпрограммы.....................33 Что делать, если алгоритм включает в себя повторяющийся несколько раз другой алгоритм? § 5. Передача параметров в подпрограммы..........................40 Как данные передаются в подпрограммы и каким образом подпрограммы передают основной программе результаты своей работы? § 6. Знакомство с математической логикой: продолжение............53 Какие возможности предоставляет математическая логика? § 7. Использование констант и собственных типов..................60 Как сделать написание и чтение программ более удобным? § 8. Работа с упорядоченными массивами...........................65 Какими преимуществами обладает упорядоченный массив по сравнению с неупорядоченным? § 9-10. Поговорим об эффективности...............................71 Что такое эффективная программа? Модуль 2. Системы счисления........................................87 Введение ..........................................................88 § 1. Что такое системы счисления.................................89 От чего зависят правила записи чисел? § 2. Перевод числа из произвольной системы счисления в десятичную. Перевод целого числа из десятичной системы счисления в произвольную...............................................94 Существуют ли правила преобразования чисел из одной системы счисления в другую? Каковы они? § 3. Переход между системами счисления, основания которых - степени двойки...............................................97 Существует ли другой способ перевода чисел из одной системы счисления в другую, если у них основания - степени двойки? 142 § 4. Сложение и вычитание чисел в произвольных системах счисления.102 Как производить арифметические действия в произвольной позиционной системе счисления? § 5. Перевод правильной десятичной дроби в произвольную систему счисления.............................109 Как перевести из десятичной системы счисления в произвольную десятичную дробь? § 6. Деление и умножение в позиционных системах счисления.........117 Как делить и умножать в произвольной системе счисления? § 7. Запись числа в общем виде ...................................121 Можно ли найти общий вид записи чисел в позиционной системе счисления? § 8. Кодирование чисел. Представление чисел (беззнаковых и целых) в памяти компьютера..........................................124 Как представлены целые числа в компьютере? § 9. Запись числа в нормализованном виде.Числа с плавающей запятой. Представление вещественных чисел в памяти компьютера..............128 Как представлены вещественные числа в компьютере? § 10. Сложение целых чисел в памяти компьютера....................133 Как выполняются арифметические действия в компьютере? Горячев, А.В. Г67 Информатика. 8 кл.: учеб. для организаций, осуществляющих образователь- ную деятельность. В 2 ч. Ч. 2 / А.В. Горячев, В.Г. Герасимова, Л. А. Макарина, А.В. Паволоцкий, А.А. Семёнов, Т.Л. Чернышёва. - М. : Баласс, 2015. - 144 с.: ил. (Образовательная система «Школа 2100»). ISBN 978-5-85939-993-2 ISBN 978-5-85939-940-6 (ч. 2) Учебник «Информатика» для 8 класса соответствует Федеральному государственному образовательному стандарту основного общего образования. Является продолжением непрерывного курса информатики и составной частью комплекта учебников развивающей Образовательной системы «Школа 2100». Содержание учебника представлено в виде отдельных учебных модулей, из которых учитель может выбрать нужные в соответствии с требованиями основной образовательной программы школы. Учебный материал предлагается на необходимом и повышенном уровнях. Может использоваться как учебное пособие. УДК 373.167.1:004+004(075.3) ББК 32.81я721 Горячев Александр Владимирович, Герасимова Вера Георгиевна, Макарина Любовь Александровна, Паволоцкий Александр Владимирович, Семёнов Андрей Александрович, Чернышёва Татьяна Леонидовна ИНФОРМАТИКА 8 класс В 2 частях. Часть 2 Концепция оформления и художественное редактирование - Е.Д. Кова.левская Подписано в печать 16.03.15. Формат 70x90/16. Печать офсетная. Бумага офсетная. Гарнитура Европа. Объём 9 п.л. Тираж 5 000 экз. Заказ № Общероссийский классификатор продукции ОК-005-93, том 2; 953005 — литература учебная Издательство «Баласс». 109147 Москва, Марксистская ул., д. 5, стр. 1 Почтовый адрес: 111123 Москва, а/я 2, «Баласс» Телефоны для справок: (495) 368-70-54, 672-23-12, 672-23-34 https://www.school2100.ru E-mail: [email protected] Отпечатано в филиале «Смоленский полиграфический комбинат» ОАО «Издательство "Высшая школа"» 214020 Смоленск, ул. Смольянинова, 1