Допущено Министерством просвещения
Российской Федерации
2-е издание,стереотипное
Москва «Просвещение» 2022
УДК 3 73.16 7.1:004+004(0 75.3)
ББК 32.81я721
СЗО
На учебник получены положительные заключения
научной (заключение РАО № 451 от 14.11.2016 г.),
педагогической (заключение РАО № 138 от 05.10.2016 г.)
и общественной (заключение РКС № 128-ОЭ от 19.12.2016 г.)
экспертиз.
Издание разработано при поддержке Института киберне
тики и образовательной информатики Федерального исследо
вательского центра «Информатика и управление» Российской
академии наук.
Уроки, посвящённые исполнителям, написаны в сотрудничестве с А. Г. Кушниренко и \М. А. Ройтбергом\.
написаны
Уроки,
посвящённые
биоинформатике,
М. А. Ройтбергом совместно с Т. А. Рудченко и Е. С. Архиповой.
Авторы благодарны профессору |А. В. Гладкому} и его книге
«Введение в современную логику».
Компьютерный проект разработан Е. Н. Хохловой.
Издание выходит в pdf-формате.
Семёнов, Алексей Львович.
СЗО
Информатика : 6-й класс : учебник : издание в pdf-формате /
А. Л. Семёнов, Т. А. Рудченко. — 2-е изд., стер. — Москва :
Просвещение, 2022. — 159, [1] с. : ил.
ISBN 9 78-5-09-10174 5-8 (электр. изд.). — Текст : электрон
ный.
ISBN 9 78-5-09-093 739-9 (печ. изд.).
Учебно-методический комплект для 5—6 классов состоит из учебника, тетради
проектов и пособия для учителя, которое содержит сведения о построении всего
курса информатики, тематическое планирование, комментарии важных понятий
курса, обсуждение и решение задач, подробные инструкции по работе в проектах
и в компьютерном практикуме и др.
Среду Кумир для компьютерного практикума можно скачать с сайта разработчи
ков http://www.niisi.ru/kumir Электронная версия пособия для учителя размещена
на сайтах: www.int-edu.ru и www.prosv.ru
УДК 373.167.1:004+004(075.3)
ББК 32.81я721
ISBN 978-5-09-101745-8 (электр. изд.)
ISBN 978-5-09-093739-9 (печ. изд.)
Введение
Дорогой друг!
Мы продолжаем наш курс информатики. В этом году, как
и в прошлом, ты будешь строить алгоритмы для управления
исполнителями, познакомишься с новыми важными конструк
циями алгоритмического языка. Кроме этого, мы обсудим раз
ные виды сортировок, графы и деревья перебора, различные
математические игры и выигрышные стратегии в таких играх.
Отдельный раздел учебника посвящён шифрованию и биоин
форматике.
Как и в прошлом году, каждая глава начинается с объяс
нительного текста. Рассмотрев и прочитав его, ты сможешь са
мостоятельно ознакомиться с новыми понятиями, которые бу
дешь использовать для решения задач — самой важной части
учебника. Задачи в учебнике встречаются очень разные. Есть
задачи простые и сложные, на сообразительность и смекалку,
есть задачи математические, лингвистические, биологические,
географические. Как ты уже знаешь, все эти области знания се
годня обращаются к информатике.
Задачи с синим номером являются необязательными, но это
не значит, что решать их не стоит, ведь самые интересные и
увлекательные задачи находятся именно среди них. Для решения
некоторых задач удобно сначала вырезать заготовку (например,
таблицы) из листа вырезания тетради проектов, наклеить её в те
традь и заполнить. Такие задачи помечены значком «ножницы».
Компьютерный практикум в этом году будет в основном по
свящён работе с исполнителями. Помимо этого, мы предлагаем
тебе научиться снимать и монтировать видео — в проекте «С
видеокамерой в руках...» у тебя будет возможность поучаство
вать в создании небольшого фильма.
Желаем успехов!
Обозначения:
Обязательная задача.
Необязательная задача.
Важная информация.
Указание,
К задаче есть лист вырезания в тетради проектов.
Сортировка: упорядочение
и классификация
В информатике сортировкой называется наведение порядка
в некотором наборе объектов. Представьте, как долго мы будем
искать нужную книгу в библиотеке, если книги будут там просто
свалены в кучу на полу. Поэтому в библиотеке книги упорядо
чены — каждая книга находится на строго определённом месте.
Упорядочено и расписание движения поездов, самолётов или
автобусов. Задачи составления расписаний и вообще упорядо
чивания большого количества объектов (в информатике говорят
«больших массивов») решаются сегодня при помощи компьютера.
Если мы хотим, чтобы в некотором наборе объектов можно
было легко найти нужный, мы должны разложить эти объекты
в определённом порядке — рассортировать. Это можно сделать
по-разному.
Один из способов сортировки — расположить все объек
ты в последовательность по определённому, удобному для нас
правилу. Такой процесс сортировки называется упорядочением.
Например, при составлении словарей обычно слова распола
гают в словарном (лексикографическом) порядке. Общее прави
ло словарного порядка выглядит так:
1. Сравним первые буквы двух слов: если эти буквы раз
ные, то раньше будет идти то слово, первая буква кото
рого идёт раньше в алфавите.
2. Если у двух слов первые буквы одинаковые, то сравним
вторые буквы: если эти буквы разные, то раньше будет
идти то слово, вторая буква которого идёт раньше в ал
фавите.
3. Если и вторые буквы у двух слов одинаковые, то сравним
третьи буквы: если эти буквы разные, то раньше будет идти
то слово, третья буква которого идёт раньше в алфавите.
4. Если и третьи буквы у двух слов одинаковые, будем
сравнивать четвёртые, пятые и т. д., пока не дойдём
до двух разных букв или пока одно из слов не закончит
ся. В этом случае раньше идёт то слово, которое короче.
4
Есть словари, в которых слова упорядочены по другим пра
вилам, об этом мы поговорим потом.
Можно сортировать объекты и по-другому — классифициро
вать их по группам по определённому правилу. Например, при
сортировке пуговиц у бабушки в комоде достаточно разложить
их по кучкам, скажем, так, чтобы в каждой кучке все пуго
вицы были одинаковыми, или так, чтобы в каждой кучке все
пуговицы были одного размера, или так, чтобы в каждой кучке
все пуговицы были одного тона.
Такая сортировка называется классификацией. В результа
те классификации получается несколько групп объектов, а вну
три каждой группы объекты не упорядочены.
Иногда при сортировке бывает удобно использовать и клас
сификацию, и упорядочение: сначала классифицировать объ
екты, а затем внутри каждой группы их упорядочивать.
Так, например, часто сортируют книги в библиотеке. Сначала
классифицируют по теме: приключения, фантастика, книги
о животных и др., а внутри каждой темы располагают по ал
фавиту.
При решении задач ты встретишься с разными способами
сортировки.
0
Расположи эти слова в словарном порядке: построй из всех этих
слов такую последовательность, в которой слова стоят в словар
ном порядке.
зяблик ласточка
неясыть
казарка
какаду соловей
журавль
воробей
клёст
дятел
иволга киви
горлица
тетерев
орёл
удод
коршун
буревестник малиновка аист
Петух
фазан
Рябчик
щегол
Обрати внимание, что все слова в этой задаче — это названия
птиц.
5
■•■
Расположи слова в словарном порядке. При этом каждое слово пиши с новой строки и после каждого слова пропускай одну
строку. Теперь напиши на пропущенных строках другие русские
слова так, чтобы словарный порядок слов в последовательности
(сверху вниз) сохранился.
олень
один
0
1234567
98765
6
оперение
океан
обвал
овал
огарок
омлет
Расположи числа в порядке возрастания — построй из всех этих
чисел такую последовательность, в которой каждое число (кроме
первого) больше предыдущего.
12345
4
они
1234
987
2345
98
89
123
9876
234
23
123456
12
987654
Классифицируй фигуры по одинаковости — выпиши имена много
угольников по группам так, чтобы в каждой группе все фигуры были
одинаковыми, а две любые фигуры из разных групп были разными.
Напиши список учащихся своего класса:
а) в словарном порядке фамилий (учащихся с одинаковыми фа
милиями можно располагать в этом списке в любом порядке);
б) в словарном порядке полных имён (учащихся с одинаковыми
именами можно располагать в этом списке в любом порядке);
в) упорядоченный по возрасту: начиная с самого старшего уча
щегося и заканчивая самым младшим (учащихся, родившихся
в один день, можно располагать в этом списке в любом порядке).
Нарисуй такой же прямоугольник по клеткам в тетради. Затем на
рисуй, как разрезать прямоугольник Ю, чтобы получились четыре
одинаковых многоугольника на сетке (с вершинами в узлах сетки).
Найди площадь каждой части в единичных квадратах (ед. кв.).
Среди данных множеств найди:
а) множество, равное объединению двух других данных множеств;
б) два каких-нибудь множества, пересечение которых равно мно
жеству из одной бусины;
в) два каких-нибудь множества, пересечение которых равно мно
жеству из двух бусин.
Записывай полные ответы.
0
7
0
Слова в последовательности Ф упорядоче
ны по некоторому правилу с использованием
алфавитного порядка. Опиши это правило.
Классифицируй дорожные знаки — выпиши
имена знаков по группам так, чтобы в одной
группе были только предупреждающие зна
ки, в другой группе — только запрещающие,
в третьей — только предписывающие, в чет
вёртой — все остальные, не вошедшие ни
в какую из первых трёх групп. Чтобы уточнить,
какой знак к какой группе относится, найди
Правила дорожного движения в библиотеке
или в Интернете.
8
Ф
классики
I
усики
I
трусики
I
ботики
I
плечики
бубенчики
I
блинчики
I
щипчики
I
прыгалки
I
посиделки
I
опилки
I
носилки
I
чулки
I
догонялки
I
потёмки
I
санки
I
валенки
I
ботинки
I
гонки
I
автогонки
Расположи названия городов Великобритании в словарном по
рядке.
Manchester
..
Liverpool.
London
Edinburgh
a
Birmingham
Plymouth
.
.
Leeds
Bristol
Cardiff
Sheffield
oneiiieiu
Glasgow
В случае затруднений можешь воспользоваться английским ал
фавитом.
Расположи слова по следующему правилу (по этому правилу
упорядочивают слова в так называемых обратных словарях):
1. Сравним последние буквы двух слов: если эти
буквы разные, то раньше будет идти то слово, по
следняя буква которого идёт раньше в алфавите.
2. Если у двух слов последние буквы одинаковые,
то сравним предпоследние буквы: если эти буквы
разные, то раньше будет идти то слово, предпо
следняя буква которого идёт раньше в алфавите.
3. Если и предпоследние буквы у двух слов одинако
вые, то сравним третьи с конца буквы: если эти бук
вы разные, то раньше будет идти то слово, третья
с конца буква которого идёт раньше в алфавите.
4. Если и третьи с конца буквы у двух слов одинако
вые, будем сравнивать четвёртые, пятые с конца
и т. д., пока не дойдём до двух разных букв или
пока одно из слов не закончится. В этом случае
раньше идёт то слово, которое короче.
ударение
часок
квасок
басок
„
обезьянка
дутый
плечо
куплет
воздух
Дерево сортировки
Классифицируем множество всех бусин сначала по цветам,
а затем в каждой полученной группе по форме. Такой процесс
удобно изобразить в виде дерева*.
Дерево А — дерево сортировки множества всех бусин. Вна
чале было множество всех бусин, состоящее из 18 элементов.
В результате первого этапа классификации получилось 6 мно
жеств, в каждом из этих множеств бусины одного цвета. В ре
зультате второго этапа классификации получились множества,
состоящие из отдельных бусин.
Как видишь, дерево А позволило нам изобразить сразу весь
процесс сортировки, при этом видны результаты каждого её
этапа: результаты каждого этапа находятся на своём уровне
дерева.
Вспомни: начало дерева мы обозначаем так же, как на
чало последовательности. Листья (элементы дерева, после ко
торых нет следующих элементов) мы обозначаем так же, как
последний член последовательности, — стрелкой.
В дереве после одного элемента может следовать сразу не
сколько элементов. Но каждый элемент дерева имеет не боль
ше одного предыдущего элемента.
10
Мы называем в дереве следующий элемент ребёнком,
а предыдущий — родителем. Элемент первого уровня дерева
не может быть ребёнком ни для какого элемента, а лист дерева
не может быть родителем ни для какого элемента.
Каждому
листу
дерева
соответствует
последователь
ность — последовательность элементов дерева, следующих друг
за другом. Первый член такой последовательности — элемент
первого уровня, а последний член — лист дерева. Последователь
ности, соответствующие разным листьям, могут оказаться одина
ковыми.
Дерево, как мы его описали, позволяет удобно представить
набор последовательностей элементов из бусин дерева. В мате
матике употребляются и другие определения дерева.
12
Построй в тетради дерево такой сортировки бусин, при которой
все бусины группируются сначала по форме, а затем по цвету.
Ответь на вопросы:
а) Сколько в твоём дереве получилось элементов первого
уровня?
б) Сколько в твоём дереве получилось листьев?
Найди площадь многоугольника У.
14
Расположи слова в словарном порядке.
бубличек
будильник
бубенец
буженина
бугор
будни
бублик
будить
бубен
бубнить
бубенчик
будочник
бузина
будто
бУД°чка
будущий
буйвол
11
Выпиши в порядке убывания последовательность всех двузнач
ных чисел, которые делятся на 17.
Расположи слова в порядке обратного словаря (правило упоря
дочения приведено в задаче 11).
16
тренькать
помелькать
крякать
баюкать
булькать
убаюкать
хрюкать
дзинькать
мелькать
Вот дерево Ю сортировки некоторого множества чисел. Сколь
ко этапов было в этой сортировке? Для каждого этапа запиши
правило, по которому сортировались числа.
В таблице даны русские слова в морфологическом представ
лении из лингвистического словаря (точки в слове делят слово
на части, знак 0 означает отсутствие той или иной части сло
ва). Выпиши из таблицы:
а) все слова, классифицировав их по корням;
б) все слова, классифицировав их по приставкам;
в) все слова с корнем раз/рез;
г) все слова с приставкой раз/рас;
д) одно слово, которое будет единственным в группе, если рас
сортировать все слова таблицы сначала по корням, а потом по
приставкам.
Слово
Приставка
Корень
об.лом.ов.к.а
об
лом/лам
на.рез.к.а
на
раз/рез
раз.рез.к.а
раз/рас
раз/рез
лом.к.а
0
лом/лам
за. кат. к.а
за
кат
об.раз. 0
об
раз/рез
об.рез. 0
об
раз/рез
об.рез.к.и
об
раз/рез
об.лом.к.и
об
лом/лам
каток 0
0
кат
об.ЛОМ. 0
об
лом/лам
раз.лом. 0
раз/рас
лом/лам
за.кат. 0
за
кат
на.кат. 0
на
кат
об.лам.ыв.а.т.ь
об
лом/лам
раз.рез.а.т.ь
раз/рас
раз/рез
рас.кат.а.т.ь
раз/рас
кат
13
19
Даны числа, классифицированные на четыре группы по некото
рому правилу. Опиши это правило. Запиши ответ по образцу:
«В группе А находятся числа, у которых...»
37
64
19
73
82
76
85
67
94
49
Реши задачу.
Каждый из трёх мальчиков на
писал 100 слов, после этого
мальчики сравнили свои за
писи. Если слово встретилось
хотя бы у двоих, то его вычёрки
вали из всех списков и вносили
в новый список — «Список со
впадающих слов». В результате
у первого мальчика в списке осталось 58 слов, у второго — 66,
у третьего — 62. В «Списке совпадающих слов» оказалось 54 сло
ва. Сколько было слов, которые встретились сразу в трёх списках?
Классифицируй слова по частям речи и внутри каждой группы
расположи слова в словарном порядке. Рядом с каждой груп
пой напиши, к какой части речи относятся слова этой группы.
Словари
Словарь — это справочная книга, которая содержит слова,
расположенные в определённом порядке.
Уточним, что именно мы имеем в виду, когда говорим «сло
во словаря». Как ты знаешь, в информатике словом называют
любую последовательность букв. Но наука о языке (она назы
вается языковедением или лингвистикой) рассматривает не лю
бые последовательности букв, а только те слова, которые есть
в языке.
Кроме того, слово в словаре и слово в тексте — не одно и
то же. В тексте следуют друг за другом формы слов (или, как
говорят, словоформы). Разные формы слов могут относиться
к одному словарному слову (например, слон, слона, слонов от
носятся к одному словарному слову слон) или к разным словам
словаря (например, формы слона, слонёнка, слонихой относят
ся к разным словарным словам: слон, слонёнок, слониха).
Словари — это не просто сборники слов, а собрания каких-то
специальных сведений о словах. Каждому слову в словаре от
водится словарная статья, содержащая сведения об этом слове
(в разных словарях разные, например, его перевод на другой
язык или толкование, т. е. объяснение его смысла).
Ты пользуешься двуязычным словарём. В таком словаре
основное содержание словарной статьи — это набор перево
дов слова на другой язык. Словарные статьи этого словаря
упорядочены в словарном порядке алфавита первого языка:
в немецко-русском словаре используется словарный порядок
немецкого языка, а в русско-немецком — русского.
С некоторыми одноязычными словарями, например тол
ковыми и орфографическими, ты тоже уже знаком. Бывают
и другие одноязычные словари. Один из самых интересных од
ноязычных словарей — Грамматический словарь русского языка,
составленный одним из крупнейших современных лингвистов
А. А. Зализняком. В каждой его словарной статье содержится
информация о грамматическом поведении слова — как оно скло
няется, как спрягается, как у него изменяется при склонении
или спряжении ударение и т. п. Вся эта информация записана
сокращённо с помощью специальных словарных индексов. Слова
в этом словаре стоят в обратном словарном порядке.
15
3*а
3°а
3°а
За
м
3*а
МО 3*а
м
3*а
м
3*а
м
3*а
м
3*Ь
м
3*а
м
3*Ь
м
3*а
м
3*а
м
3*Ь
МО 3*Ь
м
3*а®
м
3*а®
м
3*а
м
3*Ь
м
ЗЬ
м
3*Ь
м
3*Ь
м
3*а
Фрагмент Грамматического сло
варя русского языка А. А. За
лизняка
dove
die Taube
la colombe
holubice
bullfinch
der Gimpel
le bouvreuil
hyl
cardinal
der Kardinal
le cardinal
Kardinal
Фрагмент англо-немецко-француз
ско-чешского детского словаря в
картинках
16
Создаются
также
много
язычные переводные словари.
Обычно это словари терминов
по каким-то отдельным обла
стям знаний: словарь математи
ческих терминов, словарь назва
ний животных и растений и др.
Словари-энциклопедии (дет
ские и взрослые) часто созда
ются в форме словаря в кар
тинках и бывают и одно
язычные,
и
многоязычные.
Словарь в картинках может по
мочь, когда нужно найти, на
пример, английское название
какого-то предмета или живот
ного, но вы забыли (а может
быть, и не знали), как это на
зывается по-русски.
Существуют и словари, в ко
торых собраны все слова, встре
чающиеся в произведениях од
ного автора, например Словарь
языка Пушкина. Есть словариэнциклопедии, например Му
зыкальный энциклопедический
словарь, Мифологический сло
варь, Исторический словарь.
Почти все словари, кото
рыми мы сегодня пользуемся,
создавались вручную. Вручную
создавался и Грамматический
словарь русского языка, насчи
тывающий более 110 000 сло
варных статей. Вот что пишет
его автор в предисловии к из
данию: «Начало работы над
ним относится к 1964 году.
Нынешним молодым читателям
ИНФОРМАТИВНЫЙ, -ая, -ое;
яоШт]^ on м.р. 1) гражданин;
2) горожанин, житель города;
соотечественник
яоДата^ нар. много раз, много
кратно, часто
яоНакХаогоуа ср.р. мн.ч. во мно
го раз больше
яоХ1)Хоу(а, а£ ж.р. многословие;
длинная молитва
лоХпцЕрй^ нар. многосторонне,
многообразно
icoXwoiKiko^, ov многосторон
ний, многообразный
лоХб£, лоЩ, лоХп (род.п.
лоХХоп, д^, on) 1. прил. 1) мно
гий, много, многочисленный;
2) большой, значительный; 3) силь
ный, громкий (о плаче); богатый
{об урожае); поздний (о часе);
долгий, продолжительный (о
Фрагмент древнегреческо-русско
го словаря
вен,
-вна. Насыщенный информацией, хо
рошо информирующий. // сущ. инфор
мативность, -и, ж.
ИНФОРМАТИКА, -и, ж. Наука об общих
свойствах и структуре научной инфор
мации, закономерностях ее создания,
преобразования, накопления, передачи
и использования.
ИНФОРМАТОР, -а, м. Тот, кто инфор
мирует. // прил. информаторский, -ая,
-ое.
ИНФОРМАЦИЯ, -и, ж. 1. Сведения об
окружающем мире и протекающих в нем
процессах, воспринимаемые человеком
или специальным устройством (спец.). Tea
рия информации (раздел кибернетики,
изучающий способы измерения и переда
чи информации). 2. Сообщения, осведом
ляющие о положении дел, о состоянии чего-н. Научно-техническая и. Газетная и.
Средства массовой информации (печать,
радио, телевидение, кино). ♦ Генетиче
ская информация (спец.) —совокуп
ность наследственных признаков, пере
даваемых от клетки к клетке, от орга
низма к организму. /I прил. информа
ционный, -ая, -ое. Информационное
бюро. И. бюллетень
Фрагмент Толкового словаря русского
языка С. И. Ожегова
уже трудно представить себе, что эта работа делалась вручную.
„Это же немыслимый абсурд — делать такую работу без компьютера“, — доводилось мне слышать. В действительности ра
бочим инструментом были четыре хлебных лотка, раздобытые
в соседней булочной; в каждый входило по 25 тысяч карточек
из тонкой бумаги». И все эти тысячи карточек сортировались
вручную, притом что хороший темп опытного сортировщика со
ставлял тысячу карточек в час. Сегодня такую сортировку по
ручают компьютерной программе.
Умение пользоваться словарём является важной частью ин
формационной культуры, о которой мы говорили в самом на
чале этого учебника. Это относится не только к умению быстро
найти нужное слово в словаре, но и к умению правильно вы
брать словарь, а также к умению правильно истолковать и ис
пользовать информацию, взятую из словаря.
17
Вот русско-английский словарик названий рыб. Составь
англо-русский словарик этих же названий. Не забудь упорядо
чить слова в словарном порядке.
Сом — sheat
Треска — cod
Тунец — tuna
Угорь — eel
Форель — trout
Щука — pike
Когда составляли некоторый толковый словарь русского язы
ка, завели два набора карточек. На одних карточках писа
ли глаголы, а на других — их значения. Случилось так, что
карточки перепутали. Восстанови соответствие глаголов и
их значений.
ЕХАТЬ
ДОГОНЯТЬ
УДАЛЯТЬСЯ
из \
ИДТИ
^''^^^^адрчг^^ на- ’ \--------- —----
у\и^°
п
О^ОГ°
^
СрО^оД^
^6
fZ?
Объект
Другим
ВаеТся
\ ч^ло Д
госЯ-
ОТСТАВАТЬ
о6ъектому
и
и
Два объекта перемещаются
в одном и том же направ
лении, расстояние
между
увеличивается,
и
ними
из
них
находится
поодин
зади другого.
Sr,»*»,
одного ПпонУе^
"^РУгой
ни о ПерестУпая ^Нкта в
и ни ■
пва объекта "^^направв оД^с^ между
"^^^^
из
другого.
18
"—
возаДи
Расположи слова в порядке обратного словаря (правило упоря
дочения приведено в задаче 11).
понемножку
взаправду
неподалёку
25
понемногу сбоку
смолоду
между
наяву
сразу
внизу
наружу
повсюду
Вот латинско-русский словарик названий птиц. Составь руссколатинский словарик этих названий. Не забудь упорядочить сло
ва в словарном порядке.
1. Запиши первый член последовательности: одно
значное число, большее 1.
2. Запиши второй член последовательности: одно
значное число, большее 2, не равное первому чле
ну последовательности.
3. Каждый следующий член находи по правилу:
искомое число равно сумме последнего и пред
последнего из уже построенных членов последо
вательности.
4. Строй последовательность до тех пор, пока в по
следовательности не появится трёхзначное число.
19
27
Выпиши названия всех месяцев года на любых двух иностран
ных языках.
Выписанные переводы и русские названия размести в таблице:
в каждом столбце должны быть названия месяцев на одном
языке, а в каждой строке — название одного месяца на разных
языках. Для работы тебе понадобятся двуязычные словари.
28
Классифицируй названия государств по их принадлежности
к Европе, Африке или Южной Америке, а затем в каждой груп
пе расположи слова в словарном порядке.
Финляндия
Россия
Чехия
Боливия
Франция
Беларусь
Танзания
Польша
Алжир
29
20
Венесуэла
Колумбия
Гвинея
Молдова
Ватикан
Эстония
Латвия
Аргентина
Сомали
Ангола
Бразилия
Парагвай
Египет
Литва
чили
Реши задачу.
По соседству стоят два города:
город Рыцарей и город Лже
цов, жители которых ездят друг
к другу в гости. При этом ры
цари всегда говорят правду,
а лжецы всегда лгут. В одном
из этих городов встретились
двое, и между ними состоялся
такой разговор:
Первый. Жители этого города — рыцари. А ты — лжец.
Второй. Нет, я рыцарь. Каждый мой сосед скажет, что я рыцарь.
Кто был Первый и кто Второй? В каком городе состоялся этот
разговор?
Вот таблица с приближённым описанием свойств планет Сол
нечной системы. Выпиши планеты:
а) в порядке возрастания диаметра;
б) в порядке убывания расстояния от Солнца;
в) в порядке убывания продолжительности года (периода об
ращения планеты вокруг Солнца).
Продол
жительность
года
Планета
Диаметр
Среднее
расстояние
от Солнца
Меркурий
4800 км
58 млн км
88 суток
Венера
12 000 км
108 млн км
225 суток
Земля
12 800 км
150 млн км
365 суток
Марс
6700 км
228 млн км
687 суток
Юпитер
140 000 км
778 млн км
12 лет
Сатурн
120 000 км
1431 млн км
29 лет
Уран
51 000 км
3 млрд км
84 года
Нептун
49 500 км
4,5 млрд км
165 лет
Плутон
2300 км
6 млрд км
248 лет
Придумай классификацию последовательностей по четырём
группам. Выпиши имена последовательностей этих групп. Опи
ши признак, по которому собрана каждая группа.
21
Исполнители и олгоритллы
Мы называли исполнителем любое устройство, которое
способно выполнять определённый набор действий. Все ко
манды, которые понимает исполнитель, образуют систему
команд этого исполнителя. В каждый момент исполнитель
находится в одном из возможных
для него состояний. Команды-прика
Система команд
зы изменяют состояние исполнителя.
исполнителя
Водолей
При выполнении команды-запроса
исполнитель сообщает информацию
наполни А
о своём состоянии, состояние испол
наполни В
нителя не изменяется. Начальным
наполни С
состоянием исполнителя мы называ
перелей из А в В
ем его состояние перед выполнением
перелей из В в С
программы.
перелей из А в С
Ты знаком с исполнителями Водо
перелей из В в А
лей, Удвоитель, Кузнечик и Робот.
перелей из С в В
В системе команд Водолея командперелей из С в А
запросов нет. Состояние Водолея (при
вылей А
заданной вместимости сосудов) описы
вылей В
вается тем, сколько мер воды в данный
вылей С
момент налито в каждый сосуд.
В системе команд Удвоителя ко
Система команд
манд-запросов нет. Состояние испол
исполнителя
Удвоитель
нителя Удвоитель описывается только
одним числом — это число отображает
умножь на 2
ся на экране. В начальном состоянии
прибавь 1
Удвоителя на экране обычно отобра
жается число 0, но в задачах бывают
и другие начальные состояния.
Исполнитель Кузнечик работает на числовой прямой:
-7 -6 -5 -4 -3 -2 -1
0
1
2
3
4
5
6
7
Эта числовая прямая получилась объединением двух чис
ловых лучей: один числовой луч построен от точки «0» вправо,
22
а другой числовой луч построен от точки «О» влево. На левом чис
ловом луче числа помечены знаком «—». Скоро ты узнаешь, что
такие числа называются отрицательными.
Кузнечик — это не один исполнитель,
Пример
системы команд
а много похожих исполнителей. Кузнечики
исполнителя
различаются системами команд. У каждо
Кузнечик
го Кузнечика в системе ровно две команды
вперёд 3
(вперёд... и назад...), но числа в коман
назад 2
дах (количество шагов, на которые прыга
ет Кузнечик) могут быть разными. Пример
системы команд исполнителя Кузнечик приведён справа.
Кузнечик в начальном состоянии обычно стоит в точке «О»,
но в некоторых задачах может быть задано и другое начальное
состояние.
Исполнитель Робот работает на прямоугольном поле, разбитом на клетки. Между некоторыми клетками поля могут сто
ять стены (на рисунке стены отмечены жирными линиями). Не
которые клетки поля могут быть закрашены. Сам Робот всегда
занимает ровно одну клетку поля.
Исполнитель Робот умеет выполнять 17 команд: 5 командприказов и 12 команд-запросов. Мы изучили пока только
команды-приказы: вверх, вниз, вправо, влево, закрасить.
По командам вверх, вниз, вправо, влево Робот перемеща
ется в соседнюю клетку поля в указанном направлении. Если на
пути Робота оказывается стена, команда не
может быть выполнена: происходит отказ. В
этом случае Робот команду не выполняет и
^
выдаёт сообщение об ошибке. Например, из
состояния, показанного на рисунке, Робот
не может выполнить команду вверх.
По команде закрасить Робот закра
шивает ту клетку, в которой стоит. Если эта клетка уже была
закрашена, она останется закрашенной, т. е. команда будет вы
полнена, но никаких видимых изменений при этом не произойдёт.
В быту человек чаще всего управляет устройствами-испол
нителями непосредственно: даёт исполнителю команду, ис
полнитель выполняет её, затем человек смотрит на результат
и даёт следующую команду и т.д. При этом человек выбирает
следующую команду в зависимости от результата выполнения
23
предыдущей команды и состояния исполнителя после ее выпол
нения.
Однако часто возникают ситуации, когда непосредственное
управление неудобно или даже невозможно. В таких случаях
можно составить план действий (иногда говорят «программу дей
ствий»), в котором будет указано, какие команды нужно давать
исполнителю. Такой план называется алгоритмом. Алгоритм
должен быть описан так, чтобы его мог выполнить компьютер.
Для записи алгоритмов есть специальные языки, они называ
ются языками программирования. Алгоритм, записанный
на языке программирования,
называют программой.
алг крючок
Выполняя
программу,
дано I слева от Робота
компьютер читает её и даёт
I не меньше 3
команды исполнителю. Какие
I клеток поля,
выдавать команды и когда,
I снизу не меньше
компьютер узнаёт из програм
I 2 клеток
мы. В программе могут быть
надо I Робот нарисовал
команды-запросы. В этом слу
I крючок и
чае команда, которую компью
I вернулся назад
тер даст исполнителю, будет
нач
зависеть от ответа исполните
закрасить
ля на запрос.
влево
В учебнике для записи
закрасить
алгоритмов
мы используем
влево
школьный алгоритмический
закрасить
язык и для краткости назы
влево
закрасить
ваем его алгоритмический
вниз
язык. С этим языком ты по
закрасить
знакомился в 5 классе. На
вниз
пример, вот алгоритм крючок
закрасить
и поле Робота после выполне
вправо
ния этого алгоритма:
^
закрасить
вправо
вправо
вверх
вверх
кон
24
Вспомогательный
алгоритм
Алгоритм крючок, приведённый на предыдущей странице,
можно использовать в других алгоритмах. Например:
алг узор
дано | Робот в правом нижнем
надо
I углу поля
| Робот нарисовал узор и
I оказался в правом
I верхнем углу поля
нач
закрасить
вверх
закрасить
вверх
крючок
вверх
закрасить
вверх
закрасить
вверх
закрасить
вверх
крючок
вверх
закрасить
вверх
закрасить
вверх
закрасить
вверх
крючок
вверх
закрасить
кон
25
Наряду с обычными командами, в алгоритме узор есть ко
манда крючок — это команда вызова алгоритма крючок. Прочи
тав эту команду, компьютер последовательно отдаёт Роботу все
команды, предписанные алгоритмом крючок. После этого ком
пьютер переходит к следующей строке алгоритма узор. В этом
случае говорят, что алгоритм крючок
является вспомогательным алгоритмом
алг вычисления!
для алгоритма узор.
дано I
Любой алгоритм можно использо
надо |
вать как вспомогательный. Для этого
нач
достаточно указать его имя в качестве
умножь на 2
команды в каком-то другом алгоритме.
умножь на 2
Использование уже написанных алго
умножь на 2
ритмов как вспомогательных позволяет
умножь на 2
свести новую задачу к уже решённым.
кон
Справа приведены два алгорит
ма
для
Удвоителя:
вычисления!
и
вычисления2. При этом алго
алг вычисления2
ритм вычисления! используется как
дано |
вспомогательный в алгоритме вычис —
надо |
ления2.
нач
Что нам нужно знать об алгоритме,
вычисления!
чтобы мы могли его использовать как
прибавь 1
вспомогательный?
умножь на 2
1. Необходимо знать имя этого ал
прибавь 1
горитма, чтобы можно было записать
умножь на 2
это имя в качестве команды.
прибавь 1
2. Необходимо знать, из какого со
умножь на 2
стояния исполнителя этот алгоритм
кон
может быть исполнен.
3. Необходимо знать, что получится
в результате выполнения вспомогательного алгоритма — как из
менится состояние исполнителя.
Вся эта информация должна содержаться в заголовке
алгоритма — в строках алг, дано, надо. При этом для исполь
зования алгоритма как вспомогательного необязательно знать,
какую именно последовательность команд он содержит.
Таким образом, заголовок алгоритма содержит всю информа
цию, необходимую для использования этого алгоритма как вспомо-
26
гательного. Поэтому при решении задач старайся писать коммен
тарии в строках дано (начальное состояние, если оно задано, или
ограничения, если они известны) и надо (то, что нужно получить в
результате выполнения алгоритма, если это указано в задаче).
Какое число будет отображаться на экране Удвоителя после
выполнения им алгоритма вычисления2 (с. 26) из начально
го состояния «1»? Измени одну команду во вспомогательном
алгоритме вычисления! так, чтобы в результате выполнения
алгоритма вычисления2 из начального состояния «1» на экра
не Удвоителя отобразилось число «94». Напиши исправленный
вариант алгоритма вычисления!.
Составь алгоритм для Кузнечика с системой команд вперёд 7,
назад 5, который переводит Кузнечика на один шаг вперёд на
числовой прямой — например из точки «4» переводит Кузнечика
в точку «5». Дай алгоритму имя шаг вперёд.
Теперь, используя алгоритм шаг вперёд как вспомогательный,
составь алгоритм, в котором не больше 3 команд и который
переводит Кузнечика на 8 шагов вперёд.
34
35
Используя алгоритм шаг вперёд, составленный при решении
задачи 33, как вспомогательный, составь алгоритм, в котором
ровно 3 команды и который переводит Кузнечика: а) на 3 шага
вперёд; б) на 9 шагов вперёд; в) на 15 шагов вперёд.
Составь алгоритм для Водолея с вместимостью сосудов 3, 5
и 11 мер, после выполнения которого в сосуде А оказывается
ровно 1 мера воды, а сосуды В и С будут пустыми. Дай алго
ритму имя налей в А 1 меру.
Теперь, используя алгоритм налей в А 1 меру как вспо
могательный, составь алгоритм, в котором не больше 4 команд
и в результате выполнения которого сосуды А и В оказываются
пустыми, а в сосуде С налито ровно 2 меры воды.
Для проверки работы своих алгоритмов заполняй такую таблицу:
Команда
А (3 меры)
В (5 мер)
С (11 мер)
27
36
Используя алгоритм налей в А 1 меру
(задача 35) как вспомогательный, со
ставь:
а) алгоритм, в котором ровно 4 команды
и в результате выполнения которого со
суды А и С оказываются пустыми, а в со
суде В налито ровно 4 меры воды;
б) алгоритм, в котором ровно 4 команды
и в результате выполнения которого со
суды А и В оказываются пустыми, а в со
суде С налито ровно 9 мер воды.
Для проверки работы своих алгоритмов
заполняй таблицу, (см задачу 35).
Составь алгоритм, в котором не боль
ше 6 команд, который переводит Робота
из точки F в точку D. Для этого сначала
построй вспомогательный алгоритм.
D
F
38
28
Даны алгоритмы фрагмент и фигура
(справа). Напиши комментарий для дано
каждого из двух алгоритмов: укажи, ка
ким должно быть поле и в какой клетке
поля должен находиться Робот в началь
ном положении, чтобы при выполнении
алгоритма не произошло отказа.
Нарисуй результат выполнения алгорит
ма фигура, считая, что весь лист тетра
ди — это поле Робота. Выбери начальное
положение Робота, отметь крестиком
клетку, выбранную тобой для начального
положения Робота, закрась клетки, кото
рые Робот закрасит в результате выпол
нения алгоритма, отметь кружком (ноли
ком) клетку, в которой Робот окажется
после выполнения алгоритма.
алг фрагмент
дано I
надо I
нач
закрасить
вправо
закрасить
вправо
закрасить
вправо
закрасить
вниз
закрасить
вниз
закрасить
вниз
закрасить
влево
закрасить
влево
закрасить
влево
закрасить
вправо
вправо
вправо
вверх
кон
алг фигура
дано |
надо |
нач
фрагмент
фрагмент
фрагмент
фрагмент
фрагмент
кон
Сколько команд закрасить компьютер даст Роботу при вы
полнении алгоритма фигура из задачи 38? Сколько клеток при
этом будет закрашено дважды?
40
41
42
Подумай, как разрезать фигуру на две части так, чтобы из этих
частей можно было сложить квадрат 8x8. Нарисуй линии разреза
на фигуре слева и границы между частями на квадрате справа.
Построй дерево сортировки множе
ства чисел А, в которой на первом
этапе числа классифицируются по
принадлежности к сотням (числа
первой сотни, числа второй сот
ни и т. д.), на втором этапе числа
классифицируются по принадлеж
ности к десяткам (числа первого
десятка сотни, числа второго де
сятка сотни и т. д.), а на третьем
этапе — по чётности и нечётности.
237
91
541
50
549
120
300
600
200
392
595
117
193
45
100
60
297
53
199
240
550
Вот русско-английский словарик названий фруктов. Составь
англо-русский словарик этих названий. Не забудь упорядочить
слова в словарном порядке.
Айва — quince
Ананас — pineapple
Банан — banana
Гранат — pomegranate
Грейпфрут — grapefruit
Груша — pear
Инжир — fig
Киви — kiwi fruit
Лимон — lemon
Мандарин — mandarin
Хурма — persimmon
Яблоко — apple
29
43
30
Рассмотри эмблемы различных ведомств России. Найди две
одинаковые фигурки.
Дерево перебора вариантов.
Дерево перебора
подмножеств
Мы познакомились с деревьями сортировки. Ещё один вид
деревьев, которые часто используются в информатике, — деревья
перебора вариантов. Чтобы построить множество всех возмож
ных вариантов какого-либо процесса, не потеряв ни одного из
вариантов и не добавив лишних, очень полезно построить дерево.
Задача 1. Если сначала подкинуть одну монету, а потом дру
гую — какими способами они могут упасть на стол?
Монета может упасть на стол двумя
способами — орлом или решкой.
Чтобы выписать все возможные
варианты, построим дерево перебора
вариантов А. На первом уровне дере
ва поместим все способы падения пер
вой монеты — орёл и решка. На втором
уровне после каждого элемента первого
уровня поместим все способы падения
второй монеты.
В дереве А всего 4 последователь
ности, и все они разные. В каждой
последовательности из дерева А первый
член — это одна из сторон первой моне
ты, а второй член — одна из сторон вто
рой монеты.
О
Множество всех последовательностей из дерева А и есть
множество всех способов, которыми могут упасть на стол
две монеты, — таких способов 4:
31
Задача 2. Найти все трёхзначные числа,
в записи которых участвуют только цифры из
множества М (возможно, с повторениями).
Для решения этой задачи построим дерево Б, множество
всех последовательностей из которого будет её решением. Три
уровня дерева Б будут соответствоватьтрём разрядам наших
трёхзначных чисел. В искомых числах в каждом разряде мо
жет стоять любая цифра из множества М. Поэтому на первом
уровне помещаем все цифры из множества М, на втором и на
третьем уровнях помещаем цифры так, чтобы множество всех
детей каждого родителя было равно множеству М.
Б
246246246246246246246246246
фффффффффф\/ффффффф^
фффффф
Множество последовательностей дерева Б и является реше
нием задачи.
Построение дерева поможет нам и в построении всех под
множеств данного множества.
Задача 3. Построить все подмножества множества В.
Для каждого из трёх элементов множества В
все подмножества можно разделить на две груп
пы: те, которые содержат данный элемент, и те,
которые его не содержат. Используя это, будем
строить дерево Д. Сначала выберем какой-ни
будь один элемент множества В, например си
нюю треугольную бусину. На первом уровне де
рева Д поместим знаки «есть синяя треугольная
бусина» и «нет синей треугольной бусины». По
сле каждого элемента первого уровня поместим
32
знаки «есть жёлтая круглая бусина» и «нет жёлтой круглой бу
сины». После каждого элемента второго уровня поместим знаки
«есть зелёная квадратная бусина» и «нет зелёной квадратной
бусины». Получим дерево Д.
Члены каждой последовательности из дерева Д изобража
ют одно из подмножеств множества В. При этом для каждого
возможного подмножества в дереве Д есть соответствующая ему
последовательность.
33
44
Сначала подкинули одну монету, затем вторую, потом третью
(все монеты разные). Сколькими способами могут упасть на
стол эти три монеты? Построй дерево перебора вариантов.
Сколько всего существует вариантов падения трёх разных
монет?
Конечно, рисовать монеты не надо — можно просто рисовать
круги с буквой О (для орла) и Р (для решки). Круги для разных
монет рисуй разными цветами.
45
Сколько всего существует чётных двузначных чисел, в записи
которых нет цифр 0, 2 и 3? Построй дерево перебора вариан
тов. Пользуясь деревом, выпиши все такие числа.
Построй все подмножества множества W.
Для этого сначала построй дерево пере
бора подмножеств.
47
Для трёх множеств слов построй множество всех последова
тельностей слов длины 3, таких, что первый член последова
тельности — слово из множества Р, второй — слово из множе
ства Q, третий — слово из множества R. Для решения построй
дерево перебора вариантов.
Катя
Даша
Петя
Миша
48
34
слушает
читает
сказку
рассказ
стихи
Реши задачу, построив дерево перебора вариантов.
У Вовы были в кармане 4 монеты: 1 к., 5 к., 10 к., 50 к. Он до
стал из кармана некоторое количество монет (он мог достать
и все монеты, мог не достать и ни одной). Сколько денег ока
залось в руке у Вовы?
Укажи все возможные варианты.
49
50
51
52
53
Сформулируй задачу, решению которой поможет дерево пере
бора вариантов К.
а) Построй алгоритм для Удвоителя, в котором меньше
8 команд. После выполнения этого алгоритма на экране должно
отобразиться число 15.
б) Построй алгоритм для Удвоителя, в котором меньше
12 команд. После выполнения этого алгоритма на экране долж
но отобразиться число 1024.
Найди площадь многоугольника F.
Сколько всего существует нечётных
трёхзначных чисел, больших чем 500
и таких, что сумма их цифр равна 9?
Построй дерево перебора вариантов.
Пользуясь деревом, выпиши все та
кие числа.
Построй множество всех последо
вательностей из двух разных букв,
в записи которых участвуют только
буквы из множества М. Сначала по
строй дерево перебора вариантов.
35
54
Сначала подкинули монету, а затем бро
сили игральную кость. Сколькими спосо
бами могут упасть монета и игральная
кость? Построй дерево перебора вари
антов.
Игральная кость может упасть на стол шестью способа
ми — кверху одной из шести своих граней (см. рисунок).
55
Построй все возможные последовательности длины 3, состав
ленные только из нулей и единиц.
56
Сколько разных чисел можно получить, переставляя цифры чис
ла 543? Построй дерево перебора вариантов.
57
36
Измени вспомогательный алгоритм фрагмент из задачи 38
так, чтобы при выполнении алгоритма фигура Робот пере
местился из А в В и закрасил клетки, как на рисунке ниже. На
пиши исправленный вариант алгоритма фрагмент.
Сколько команд закрасить компьютер даст Роботу при вы
полнении алгоритма фигура с исправленным вспомогательным
алгоритмом фрагмент? Сколько клеток при этом будет закра
шено дважды?
Рассмотри меню, которое предлагается посетителям кафе «Та
верна». Сколько вариантов завтраков (включающих яичницу или
кашу и один напиток) могут заказать посетители кафе «Тавер
на»? Построй дерево перебора вариантов.
Сколько вариантов обедов (включающих один салат, суп, одно
второе блюдо, один десерт и один напиток) могут заказать
посетители кафе «Таверна»? Построй дерево перебора вариантов.
МЕНЮ
Супы
^^' Яичница
Ci/пчик дня
/Саша овсяная
Вторые блюда
/Су/ища
no -корсикански
Салат. «Цезарь»
Яй/почки
Салат мясной
Напитки
ШолОКО
(Только no iftnfiaM.)
Шашлык
Судак
но-польски
Чай
Шоролсеное
37
Поиск кротчайшего пути
Рассмотри схему дорог между сёлами М, А, Б, В и Г. Числа
на схеме указывают длину дорог, проложенных между сёлами,
в километрах (дороги далеко не всегда бывают прямые, поэтому
длина дороги между сёлами не всегда равна самому короткому
расстоянию между ними).
Такая схема называется графом.
О
Вообще графом называется набор точек (вершин графа),
некоторые из которых соединены линиями (рёбрами графа).
Каждое дерево является графом — ведь в дереве тоже есть
вершины (в них стоят элементы), и они соединены линия
ми — рёбрами.
На нашей схеме каждые две вершины соединены между
собой ребром, каждое ребро помечено числом — длиной дороги
между сёлами.
Теперь решим такую задачу:
Задача. В селе М находится почта, и почтальон должен
развезти письма в остальные четыре села (и, конечно, вер-
38
нуться обратно на почту). Существует много различных марш
рутов такой поездки. Как выбрать из них самый короткий?
Для решения задачи построим дерево Д перебора вариан
тов всех возможных маршрутов. Ясно, что если почтальон будет
возвращаться в село, в котором уже побывал, то такой маршрут
не будет самым коротким, поэтому такие маршруты мы рассма
тривать не будем.
Каждое ребро дерева Д пометим числом, обозначающим дли
ну дороги между сёлами, и для каждой последовательности дере
ва Д вычислим длину маршрута (т. е. сумму чисел на его рёбрах).
Получилось всего 24 последовательности (24 варианта марш
рутов). Наименьшая длина маршрута — 28 км. Этой длине пути
соответствуют два маршрута: М—В—Б—А—Г—М и М—Г—А—
Б—В—М. Впрочем, на самом деле это один и тот же путь, толь
ко пройденный в разных направлениях.
Графы и деревья, каждому ребру которых присвоено чис
ло, называют взвешенными. При этом число, присвоенное
ребру, называется весом этого ребра.
39
Конечно, взвешенные деревья и графы можно использовать
не только для поиска кратчайшего пути. Это может быть, на
пример, самый дешёвый путь (при передвижении на транспор
те), или самый безопасный путь, или путь, который требует
наименьших затрат энергии, или путь, выбранный по другим
критериям. Так можно решать самые разные задачи на поиск
наилучшего способа.
59
60
Рассмотри граф, представляющий схему дорог от дома, где
живёт Коля, до школы. Нарисуй дерево перебора возможных
маршрутов от дома Коли до школы. В качестве элементов та
кого дерева используй имена вершин графа. Через каждую
точку можно проходить не больше одного раза, по дорогам со
стрелками можно двигаться только в направлении стрелок. Ка
кой путь оказался самым коротким?
Построй все подмножества множества V.
Для этого сначала построй дерево пе
ребора подмножеств.
40
61
Процесс вычисления значения арифметического выражения
тоже можно изобразить при помощи дерева. В таком дереве
каждый родитель является результатом арифметической опера
ции, применённой ко всем его детям. При этом родитель изо
бражается в виде знака этой операции. Для каждого дерева на
пиши арифметическое выражение, которое соответствует этому
дереву.
Реши задачу.
Крыса бежит по лабиринту, ко
торый устроен так, что сначала
она должна выбрать один из двух
проходов, затем один из трёх
проходов, а за каждым из них её
ожидают четыре прохода. Войдя
в какой-то проход, крыса не мо
жет вернуться через него обрат
но. Сколькими различными путя
ми крыса может пройти лабиринт
от начала до конца?
41
63
о
Инициалы — это первые буквы имени и отчества. Например,
инициалы Татьяны Михайловны — Т. М., инициалы Николая Ни
колаевича — Н. Н.
Сосчитай, сколько в русском языке может быть таких двухбук
венных инициалов.
Ясно, что в инициалах не встретятся буквы Ъ, Ь. Имена, на
чинающиеся на остальные буквы, даже если их нет в списке
русских имён, могут встретиться в именах у других народов,
например: Йорган, Ёшка, Щедрик. Поэтому остальные буквы
следует учитывать.
Дерево перебора в этой задаче будет большим. Не строя дере
ва, опиши его по образцу:
1. В этом дереве ... уровня.
2. В этом дереве у каждого элемента первого уровня ров
но ... детей.
3. В этом дереве всего ... листьев.
Теперь, пользуясь своим описанием, ответь на вопрос за
дачи.
64
Построй все такие последовательности бусин, для которых
все следующие утверждения истинны:
Длина этой последовательности меньше 4.
Каждая бусина этой последовательности содер
жится в множестве Р.
В этой последовательности есть две одинаковые бусины.
65
42
Реши задачу.
В очереди стоят Юра, Миша, Вова, Саша и Олег. Юра стоит
раньше Миши, но после Олега. Вова и Олег не стоят рядом.
Саша не стоит рядом ни с Олегом, ни с Юрой, ни с Вовой. В ка
ком порядке стоят ребята? Объясни, почему твой ответ — един
ственное возможное решение.
Алгоритмы: цикл «N роз» ■
Компьютер может исполнять миллионы вычислительных опе
раций в секунду, например повторять одну и ту же последова
тельность действий. Конечно, программисты не записывают при
этом миллион раз одну и ту же последовательность команд, они
используют специальную составную команду алгоритмического
языка (конструкцию) — цикл «N раз», где N — целое число:
нц раз
кц
Служебные слова нц (начало цикла) и кц (конец цикла) пи
шутся строго одно под другим. Повторяемая последовательность
команд записывается с отступом вправо.
Вот пример алгоритма, в котором используется цикл
«N раз». В этом цикле число повторений N = 5.
алг из А в В
дано I Робот
надо
I
I
I
в клетке А
Робот
в клетке В
нач
нц 5 раз
вверх
вверх
вправо
вниз
вниз
вправо
При выполнении этого алго
ритма компьютер 5 раз повторит
последовательность команд
вверх
вверх
вправо
вниз
вниз
вправо
и Робот окажется в клетке В:
кц
кон
При выполнении алгоритма закрасить ряд из 9 клеток,
в котором два раза используется цикл «N раз», компьютер даст
Роботу 27 команд: сначала 9 раз будет выполнена пара команд
закрасить, вправо, а затем 9 команд влево.
43
алг закрасить ряд из 9 клеток
дано I на поле Робота нет стен,
I справа от клетки с Роботом
I есть 9 клеток поля
надо I Робот закрасил 9 клеток ряда
I и вернулся в исходное положение
нач
нц 9 раз
закрасить
вправо
кц
нц 9 раз
влево
кц
кон
Если вместо числа 9 поставить число 100, Робот выпол
нит уже 300 команд, но при этом количество строк в алго
ритме не увеличится! Таким образом, с помощью составной
команды цикл «N раз» можно коротко записывать алгорит
мы, которые описывают очень длинные последовательности
действий.
Внутри цикла, как и в других местах алгоритма, можно
вызывать вспомогательные алгоритмы — смотри, например,
алгоритм закрасить квадрат 1 на следующей странице.
Внутри цикла могут быть и другие циклы — смотри, на
пример, алгоритм закрасить квадрат 2. Цикл, который
находится внутри другого, называется вложенным циклом.
В данном случае использование вложенных циклов не очень
удобно: алгоритм закрасить квадрат 2 выглядит более гро
моздким и менее понятным, чем алгоритм закрасить ква
драт 1.
Правила алгоритмического языка допускают задание лю
бого целого числа повторений N в конструкции цикл «N раз».
Это число может равняться нулю и даже быть отрицатель
ным! Это не считается ошибкой и не приведёт к отказу при
44
алг закрасить квадрат 1
дано 1 на поле Робота нет стен,
I
1
1
1
надо
справа от клетки с Роботом есть 9 клеток поля,
сверху над клеткой с Роботом есть 9 клеток поля
Робот закрасил квадрат 9 X 9 и
вернулся в исходное положение
нач
нц 9 раз
закрасить ряд из 9 клеток
вверх
кц
нц 9 раз
вниз
КЦ
кон
алг закрасить квадрат 2
дано 1 на поле Робота нет стен,
надо
1
1
1
1
справа от клетки с Роботом есть 9 клеток поля,
сверху над клеткой с Роботом есть 9 клеток поля
Робот закрасил квадрат 9 X 9 и
вернулся в исходное положение
нач
нц 9 раз
нц 9 раз
закрасить
вправо
кц
нц 9 раз
влево
кц
вверх
КЦ
нц 9 раз
вниз
кц
кон
45
выполнении алгоритма. В таком случае тело цикла не будет
выполнено ни разу, а компьютер перейдёт к командам, запи
санным после кц.
66
67
Составь алгоритм для Робота, который закрашивает все клетки
на квадратном поле без внутренних стен размером 10x10. В на
чальном состоянии Робот находится в левом верхнем углу поля,
после выполнения алгоритма Робот оказывается в правом нижнем
углу поля. Используй как вспомогательный алгоритм закрасить
ряд из 9 клеток со с. 44 и составную команду цикл «N раз».
Нарисуй результат выполнения Роботом алгоритма узор2.
Сколько раз Робот выполнил команду закрасить, выполняя
алгоритм узор2? Сколько всего на поле стало закрашенных
клеток? Сколько клеток Робот закрасил по одному разу?
алг узор2
дано | на поле Робота нет стен,
I
10 X 10 клеток,
Робот в верхнем левом углу поля
надо I
нач
нц 5 раз
нц 3 раз
закрасить
вправо
кц
нц 3 раз
закрасить
вниз
кц
нц 2 раз
закрасить
влево
вверх
закрасить
КЦ
кц
кон
46
68
Выписаны подряд без пробелов все натуральные числа от 1 до
50 включительно. Какая цифра стоит на 79-м месте?
69
Заполни таблицу выполнения Кузнечиком с системой команд
вперёд 13, назад 8 алгоритма следующее число по образцу.
алг следующее число
дано |
надо | Кузнечик переместился
си
d
си
I на шаг вправо
о
>
со
ф
о.
вперёд 13
13
вперёд 13
26
нач
нц 5 раз
вперёд 13
КЦ
нц 8 раз
ь
си
назад 8
КЦ
кон
70
Составь алгоритм, который, как и алгоритм следующее чис
ло, переводит Кузнечика с системой команд вперёд 13, на
зад 8 на шаг вправо, но так, что при его выполнении Кузнечик
не удаляется от начального положения больше чем на 50 ша
гов. Используй составную команду цикл «N раз».
Даны три множества латинских букв. Построй:
а) пересечение множеств А и Б;
б) объединение множеств Б и В;
в) пересечение множеств Б и В;
г) пересечение множеств А, Б и В.
z ^v
47
72
73
Составь алгоритм для Кузнечика с системой команд вперёд 3,
назад 2, который переводит Кузнечика из точки «О» в точку
«360». Используй составную команду цикл «N раз».
Составь алгоритм для Кузнечика с системой команд вперёд 3,
назад 2 , который заставит Кузнечика перейти из точки «0»
в точку «100», побывав при этом в каждой точке от 0 до 100
ровно по одному разу. Используй составную команду цикл
«N раз».
Прежде чем решить эту задачу, реши аналогичную задачу
для короткого отрезка, например для отрезка от 0 до 5.
74
Составь алгоритм, который переводит Робота из точки А в точ
ку В и раскрашивает все те клетки, которые раскрашены на поле
на рисунке. Используй составную команду цикл «N раз» и вло
женный цикл.
А
В
75
76
48
Составь другой алгоритм, который тоже переводит Робота
из точки А в точку В и раскрашивает все те клетки, которые
раскрашены на поле на рисунке (см. рисунок из задачи 74), но
в котором используется не вложенный цикл, а вспомогательные
алгоритмы.
Реши задачу, построив дерево перебо
ра вариантов.
В школьной столовой продают шоко
ладки по 15 р. и мороженое по 12 р.
за порцию. У Оли есть 102 р. Сколько
Оле нужно купить шоколадок и сколько
порций мороженого, чтобы истратить
все свои деньги? Найди все возмож
ные варианты такой покупки.
Построй алгоритм для Удвоителя (система команд Удвоителя
приведена на с. 22), после выполнения которого на экране ото
бразится число 2014. Используй только составную команду цикл
«N раз» и команду прибавь 1. Дай этому алгоритму имя при
бавь 2014 раз по 1. Сколько всего команд компьютер передаст
Удвоителю при выполнении алгоритма прибавь 2014 раз по 1?
Затем составь такой алгоритм, после выполнения которого
на экране тоже отобразится число 2014, но при выполнении ко
торого компьютер передаст Удвоителю не больше 20 команд.
Дай этому алгоритму имя получи 2 014.
78
Найди площадь многоугольника Ф.
79
Сколько было брёвен, если, сделав 52 распила
(каждый раз распиливали ровно одно бревно),
из них получили 72 полена?
80
Найди все возможные варианты чисел, которые
могут быть отображены на экране Удвоителя
после выполнения им не больше 5 команд из на
чального положения «1». Для решения построй дерево пере
бора вариантов. Пользуясь построенным деревом, найди все
числа второго десятка, которые нельзя получить на экране
Удвоителя не больше чем за 5 команд.
81
Вот греческие буквы. Найди три одинаковые буквы, напиши та
кую букву в тетради. Найди букву, которая встречается здесь
ровно один раз, напиши такую букву в тетради.
0 СО р Т ф U I о л 8 а 5 ф
у п
Позиции, которые получились после ходов Первого, помече
ны в последовательности W синим цветом. Позиции, которые
получились после ходов Второго, остались чёрными.
Первый член последовательности W — это начальная пози
ция, второй член — позиция после первого хода (напомним, что
56
первый ход всегда делает Первый) и т. д., последний член по
следовательности W — заключительная позиция.
Заключительная позиция получилась в результате хода
Второго: Второй забрал 2 оставшихся камешка и выиграл в
партии W.
Дерево игры
Последовательность позиций изображает только одну партию.
Построим теперь дерево перебора всех возможных партий игры
с данными правилами. Такое дерево называется деревом игры.
Единственным элементом первого уровня дерева игры
является начальная позиция, элементами второго уровня — все
позиции, возможные после первого хода, элементами третьего
уровня — все позиции, возможные после второго хода, и т. д.
Листья дерева игры — это заключительные позиции.
Позиции нашей игры Камешки после ходов Первого помече
ны в дереве А синим, а после ходов Второго — чёрным. Для удоб
ства можно пометить каждое ребро дерева числом, которое пока
зывает, сколько камешков забрал игрок на этом ходу.
о
57
О
Каждая последовательность дерева игры является последо
вательностью позиций одной из возможных партий игры.
Последовательности дерева — это возможные в данной
игре партии. При этом в дереве есть последовательность
для каждой возможной партии.
Игроки играют в игру Камешки с такими правилами: начальная
позиция — 11 камешков; за один ход можно взять 1, 2 или 3 ка
мешка. Придумай две партии этой игры так, чтобы в одной пар
тии выиграл Первый, а в другой — Второй. Построй последова
тельности позиций для этих партий. Позиции изображай числами.
Устройте соревнование с соседом
по парте — сыграйте 8 партий в Ка
мешки (начальная позиция 7 камеш
ков, разрешается брать 1 или 2 ка
мешка за один ход).
Начинайте игру по очереди: пусть
один из вас играет Первым в пар
тиях с чётными номерами, а дру
гой — с нечётными. Заполни табли
цу соревнования (образец таблицы
дан справа, такая же таблица есть
на вкладыше тетради проектов).
В клетки таблицы записывай, сколь
ко очков набрал каждый игрок в оче
редной партии. За каждую победу
игрок получает 1 очко, а за пораже
ние — 0 очков. Сколько раз в вашем
соревновании выиграл Первый?
Игроки
S
Партии
:ф
О
со
Н
си
«С
ф
о
о
о
к
S
1-я партия
2-я партия
3-я партия
4-я партия
5-я партия
6-я партия
7-я партия
8-я партия
Итого
Нарисуй дерево Б игры Камешки (начальная позиция 5 камешков, разрешается брать 1 или 2 камешка за один ход). Запиши
позиции, которые получились в результате хода Первого, си
ним, а позиции, которые получились в результате хода Второ
го, чёрным. Обведи синим листья дерева Б, соответствующие
партиям, в которых выиграл Первый. Обведи зелёным листья,
соответствующие партиям, в которых выиграл Второй.
58
96
Составь алгоритм, который заставит Робота закрасить клетки
квадратного поля 10x10 в шахматном порядке, начиная с ле
вого верхнего угла поля. Используй составную команду цикл
«N раз» и вложенный цикл.
97
Пусть S — множество всех букв, которые встречаются в слове
КАРТОШКА, и R — множество всех букв, которые встречают
ся в слове МАКАРОНЫ. Построй пересечение и объединение
множеств S и R.
98
Построй последовательность А позиций такой партии игры
Камешки (начальная позиция 5 камешков, разрешается брать
1, 2 или 4 камешка за один ход), в которой на третьем ходу
партии выиграл Первый.
Построй последовательность Б позиций такой партии той
же игры, в которой на четвёртом ходу выиграл Второй. За
тем построй дерево В этой игры. Найди в дереве В после
довательность, равную последовательности А, и обведи лист,
соответствующий этой последовательности, красным. Найди
в дереве В последовательность, равную последовательности
Б, и обведи лист, соответствующий этой последовательности,
синим.
99
Прочитай описание игры Крестики-нолики.
Игра ведётся на поле размером 3x3 клетки.
В игре принимают участие два игрока, которые де
лают ходы по очереди. Во время хода игрок рисует
свой значок в свободной клетке поля. Первый игрок
рисует крестики, второй игрок рисует нолики. Если
на поле возник ряд из трёх крестиков (по горизон
тали, по вертикали или по диагонали), то выиграл
первый игрок; если возник ряд из трёх ноликов, то
выиграл второй игрок. Если все клетки поля запол
нены значками, но ряда из трёх одинаковых знач
ков не возникло, то игра закончилась вничью.
59
Сформулируй правила этой игры по образцу:
Начальная позиция.
Возможные ходы.
Как определить победителя. В этой игре заключи
тельные позиции бывают трёх видов:
1) ... (выиграл Первый);
2) ... (выиграл Второй);
3) ... (партия закончилась вничью).
Нарисуй примеры заключительных позиций каждого из трёх ви
дов, напиши, кто выигрывает при такой заключительной позиции.
100
Рассмотри последовательность М позиций партии игры Кре
стики-нолики. Ответь на вопросы:
а) Сколько ходов было сделано в этой партии?
б) Сколько ходов сделал Первый и сколько — Второй?
в) Каков исход партии?
X
X
101
X
X
о
о
X о
X о
о Xо
о Xо
X о
о
о Xо
о
о
Реши лингвистическую задачу.
Даны болгарские слова и словосочетания и их переводы на
русский язык в перепутанном порядке:
ледена планина
иглолистно дърво
горска ягода
горски пояс
иглолистна гора
градина
планинска верига
градинска ягода
горолом
сад
горная цепь
хвойный лес
бурелом
клубника
земляника
лесополоса
айсберг
хвойное дерево
Установи русские переводы всех болгарских слов и словосо
четаний.
60
Болгарский и русский языки — родственные, и многие болгар
ские слова похожи на русские. Например, болгарское слово
«дърво» похоже на русское слово «дерево» и действительно пе
реводится как «дерево». Но похожие русские и болгарские слова
необязательно обозначают одно и то же. Поэтому для решения
задачи нужно провести исследование всех слов и рассуждение.
Команды-запросы Робота.
Условие
Представьте себе начальника, который отдаёт приказы, но не
получает никаких донесений о результатах их выполнения; по
вара, который не может попробовать блюдо; шофёра, ведущего
автомобиль с закрытыми глазами. Понятно, что так далеко не
уедешь: если мы хотим составлять алгоритмы для решения слож
ных задач, то надо уметь не только командовать исполнителем,
но и анализировать обстановку, в которой он оказался.
Например, для Робота обстановка — это поле, на котором
он находится (расположение стен на поле, раскраска клеток,
температура и уровень радиации в каждой клетке), а также то,
в какой клетке находится Робот.
Для анализа обстановки у Робота есть 12 команд-запросов,
будем для краткости называть их просто запросами:
Команды-запросы Робота
сверху стена
снизу стена
справа стена
слева стена
сверху свободно
снизу свободно
справа свободно
слева свободно
клетка закрашена
клетка чистая
температура
радиация
61
Отвечая на запрос, Робот
сообщает информацию об обста
новке в той клетке, где он нахо
дится: о закраске этой клетки, о
наличии стен на границах клет
ки, о температуре и радиации в
клетке.
Смысл этих вопросов ясен из
их имён. Мы будем использовать
пока только первые 10 команд-за
просов — с командами-запросами
температура и радиация мы бу
дем работать позже.
Итак, рассмотрим командызапросы, которые касаются на
личия или отсутствия стены на
границах клетки и того, закра
шена ли клетка, на которой сто
ит Робот. Когда Робот получает
такую команду, он определяет
истинность соответствующего ут
верждения и даёт ответ — «исти
на» или «ложь». Можно считать,
что, давая такую команду-запрос, компьютер или человек за
даёт Роботу вопрос и получает от него в ответ «да» или «нет».
В нижней части пульта дистанционного управления Робо
том (см. рисунок слева) есть кнопки «Стена/Закрашено», «Свободно/Чисто». Например, чтобы дать Роботу команду-запрос
сверху стена, надо нажать на пульте две кнопки: сначала
кнопку «Стена», а потом кнопку со стрелкой вверх. Чтобы дать
Роботу команду-запрос клетка чистая, надо нажать на пульте
кнопку «Чисто», а потом центральную кнопку. Для получения
ответов Робота используется экран пульта — на нём появляет
ся слово «да» («истина») или «нет» («ложь»).
Задача 1. Робот охраняет помещение, состоящее из
двух соседних клеток (см. рисунок справа). Неизвестно,
в какой из двух клеток находится Робот. Необходимо пе
ревести его в другую клетку.
62
Сначала решим задачу в режиме непосредственного управле
ния Роботом. По условию задачи мы не видим, в какой клетке
поля он находится. Чтобы узнать, в какой клетке Робот сейчас
находится, дадим ему команду-запрос: справа свободно. Ответ
«истина» («да») означает, что Робот в левой клетке и должен
сделать шаг вправо. Ответ «ложь» («нет») означает, что Робот
в правой клетке и должен сдвинуться влево. Наши действия
при непосредственном управлении Роботом можно описать
так: если справа свободно, то скомандовать вправо, иначе (если
справа не свободно, стоит стена) скомандовать влево.
При решении задачи 1 мы давали Роботу запрос и в за
висимости от ответа выбирали следующее действие. Для описания
такого выбора в алгоритмическом языке существует специальная
составная команда если. Общий вид команды если таков:
если
то
иначе
все
или
если
то
все
Служебные слова если, то, иначе имеют тот же смысл,
что и в русском языке. Слово все означает конец команды
(«всё»), это слово пишется строго под словом если. После то
записывается
последовательность
команд
(последователь
ность команд 1), которая выполняется в случае истинности
условия. После иначе записывается другая последовательность
команд (последовательность команд 2), которая выполняется
в случае ложности условия. Последовательность команд 2
вместе со служебным словом иначе может отсутствовать.
При обработке составной команды если компьютер посыла
ет Роботу команду-запрос, чтобы проверить истинность условия,
63
записанного в строке если. Если Робот сообщает, что условие
истинно, то компьютер посылает Роботу команды из после
довательности 1, а команды из последовательности 2 про
пускает. Если Робот сообщает, что условие ложно, то компьютер
посылает Роботу команды из последовательности 2 (если она
есть). Если условие ложно, а последовательность
команд 2
вместе с иначе отсутствует, то компьютер сразу переходит к вы
полнению команд, записанных после слова все.
Вот как можно записать алгоритм решения задачи 1:
алг дежурство
дано I Робот в одной из клеток
«двухкомнатного» помещения
| Робот в другой клетке
I
надо
нач
если справа свободно
то вправо
иначе влево
все
кон
Задача 2. Робот стоит в левом конце горизонтального коридора
длиной в 23 клетки. Нижняя стена коридора сплошная, а в верх
ней имеется несколько выходов. Надо перевести Робота в правый
конец коридора (из А в В) и закрасить все те клетки коридора, из
которых есть выход вверх (см. рисунок). Количество выходов и их
точное расположение заранее неизвестны.
А
В
Итак, Робот должен пройти по горизонтальному коридо
ру, при этом закрашивать надо только те клетки коридора,
где есть выход вверх. Другими
словами, если сверху свободно,
если сверху свободно
то клетку надо закрасить, ина
то закрасить
че — красить не надо. Попробу
иначе ...
ем записать это в виде состав
все
ной команды если:
64
А что собственно «иначе»? Как записать, что иначе ничего
делать не надо? Для таких случаев и существует краткая форма
составной команды если, в которой слова иначе вообще нет:
если сверху свободно
то закрасить
все
При выполнении этой составной команды компьютер даст
Роботу команду определить истинность условия сверху сво
бодно. Если Робот ответит «истинно», то компьютер скоман
дует Роботу закрасить. Если же Робот ответит «ложно», то
компьютер вызов команды закрасить пропустит. Вот алгоритм
решения задачи 2:
алг разметка выходов из коридора
дано | Робот в левой клетке
I
надо
|
I
I
горизонтального коридора
Робот в самой правой клетке коридора,
клетки коридора, из которых
есть выход вверх, закрашены
нач
если сверху свободно
то закрасить
все
нц 22 раз
вправо
если сверху свободно
то закрасить
все
кц
кон
Обрати внимание: в этом алгоритме первая составная
команда если служит для того, чтобы Робот раскрасил клет
ку А, если из неё есть выход из коридора. Дальше Робот 22
раза повторяет следующее: делает шаг вправо, проверяет, сво
бодно ли сверху, и закрашивает клетку, если свободно. Если
сверху стоит стена, Робот клетку не закрашивает, а сразу пере
ходит на шаг вправо.
65
102
Определи истинность каждого
утверждения (условия) в табли
це для каждой из отмеченных
клеток поля. Заполни такую
таблицу
в
тетради — напиши
в каждой клетке букву И или Л.
А
С
В
D
F
F
Н
G
Клетка
В
А
Утверждение
D
С
Е
F
G
Н
сверху свободно
справа стена
снизу свободно
слева стена
клетка чистая
Клетка
к
L
м
N
о
р
Q
R
сверху свободно
и
Л
л
и
л
и
л
л
справа стена
л
и
л
л
л
и
л
л
снизу свободно
л
л
и
л
л
и
и
л
слева стена
л
л
л
и
л
л
и
и
клетка чистая
и
л
л
л
и
л
л
и
Утверждение
66
104
Вот буквы армянского алфавита. Найди три одинаковые бук
вы, напиши такую букву в тетради.
buihmlji|g[ii[uipqD^
nupqifntiq]uti{qinlj
JimpqJiJupuhilghiq
Нарисуй состояние Робота после
выполнения им алгоритма пере
ход из данного начального состо
яния.
Построй такую последовательность
партии игры Крестики-нолики, в ко
торой на седьмом ходу выигрывает
Первый.
107
108
Реши задачу.
Разложи по семи кошелькам 127
рублёвых монет так, чтобы любую
сумму от 1 до 127 р. можно было
выдать, не открывая кошельков
(другими словами, отдав всё со
держимое одного или нескольких
кошельков).
алг переход
дано I
надо I
нач
влево
влево
если снизу
свободно
то вниз
вправо
вправо
все
вправо
закрась
вправо
закрась
вниз
если снизу
свободно
то вниз
иначе влево
вниз
все
кон
Построй состояние Робота после выполнения каждого алго
ритма из каждого из данных начальных состояний. Построй
таблицу по образцу — в каждую клетку наклей заготовку поля,
раскрась клетки, нарисуй положение Робота.
Начальное состояние 1:
алг А
дано I
надо I
нач
нц б раз
если справа свободно
то вправо
все
если снизу свободно
то вниз
все
кц
кон
^^
Начальное состояние 2:
Начальное состояние 3:
алг Б
дано I
надо I
нач
нц б раз
если снизу свободно
то вниз
все
если справа свободно
то вправо
все
кц
кон
Начальное
состояние
68
Состояние после
выполнения
алгоритма А
^
Начальное состояние 4:
^
Состояние после
выполнения
алгоритма Б
109
Несколько костяшек из одного набора домино уложили так,
как показано на рисунке. Определи, где проходят грани
цы между костяшками. Для этого вырежи такой же рисунок
со вкладыша тетради проектов, наклей его в тетрадь и про
веди на нём эти границы жирными линиями.
О
Нужно иметь в виду, что в одном наборе домино все костяшки
разные.
no
Составь такой алгоритм для Робота, после выполнения кото
рого из каждого из данных начальных состояний Робот ока
жется в левом нижнем углу поля.
• •
•
•
• • • •
•
• • • •
Начальное состояние 1:
• •• •• •• ••
•
Начальное состояние 2:
ф
На поле Робота стен нет. В ряду правее той клетки, где сто
ит Робот, некоторые клетки закрашены, причём самая даль
няя закрашенная клетка находится не дальше чем в 10 ша
гах от Робота, например, как на рисунке ниже. Какие именно
клетки закрашены изначально, неизвестно, известно только,
что больше закрашенных клеток на поле нет.
69
Составь алгоритмы, которые заставляют Робота:
а) закрасить клетку на шаг ниже каждой из закрашенных
начально;
б) закрасить клетку на шаг выше и на шаг ниже каждой из
крашенных изначально;
в) закрасить клетку на шаг левее каждой из закрашенных
начально;
г) закрасить клетку на шаг правее каждой из закрашенных
начально.
112
из
за
из
из
Даны правила игры Ползунок.
Правила игры Ползунок
Начальная позиция. Игровое
поле состоит из нескольких рядов
точек, расположенных в прямо
угольнике. Пример такого поля
приведён справа.
Возможные ходы. На первом ходу Первый со
единяет горизонтальным или вертикальным отрезком
две любые соседние точки. На каждом из следующих
ходов игрок проводит горизонтальный или верти
кальный отрезок, соединяющий один из концов по
лучившейся до этого ломаной линии с какой-нибудь
соседней точкой, через которую линия ещё не про
шла. Например, такие ходы не разрешены:
Как определить победителя. Игра заканчивает
ся, если очередной ход сделать нельзя. Выигрывает
игрок, который сделал последний ход.
70
Рассмотри последовательность S позиций партии игры Пол
зунок на поле 4x3 точки. Ходы Первого помечены синим,
ходы Второго — оранжевым. Ответь на вопросы:
а) Сколько ходов было сделано в этой партии?
б) Сколько ходов сделал Первый и сколько — Второй?
в) Кто выиграл?
Придумай такую партию игры Ползунок на поле 4 х 3, в кото
рой выиграл Второй. Построй последовательность позиций
этой партии. Заготовки полей есть на вкладыше тетради про
ектов. Теперь построй последовательность Р позиций такой
партии, в которой выиграл Первый.
114
Построй дерево, для которого все утверждения в таблице
имеют указанные истинностные значения.
Имя
Утверждение
Значение
А
Все листья этого дерева — элементы
третьего уровня.
И
В
Все бусины в этом дереве только двух
цветов — чёрные и белые.
И
С
В этом дереве есть две одинаковые по
ел едо вател ьн ости.
Л
D
Каждый элемент этого дерева — круглая
бусина.
И
Е
В этом дереве меньше восьми после
довательностей.
Л
71
Определи по
из города Л в
гаться только
но проезжать
графу, сколькими способами можно проехать
город М. По дорогам со стрелками можно дви
в направлении стрелок, по каждой дороге мож
не больше одного раза.
Выигрышная стратегия
Мы строили различные партии игр, но при этом совсем
не принимали во внимание стремление игроков к победе. Те
перь нас будут интересовать лишь такие партии, в которых оба
игрока стремятся к победе. Будем называть такие партии раз
умными. Игроков, которые стараются победить, а не делают
ходы наугад, мы тоже будем называть разумными.
Итак, играют двое и каждый из них стремится к победе. Если
правила игры не допускают ничьей, то в каждой партии кто-то
из игроков обязательно выигрывает. Оказывается, что в каждой
игре с полной информацией, правила которой не допускают ни
чьей, существует выигрышная стратегия для одного из игроков.
Выигрышная стратегия — это правило, следуя которому
один из игроков может выиграть, как бы ни играл его про
тивник.
Используя это правило, можно победить любого сопер
ника — и разумного, и не очень. Ясно, что для каждой игры
с определёнными правилами выигрышную стратегию может
иметь только один из игроков.
Мы упоминали о том, что шахматы и шашки тоже игры
с полной информацией. Значит, и в этих играх есть выигрыш
ная стратегия для одного из игроков. Почему же тогда никто
не воспользуется такой стратегией? Поиск выигрышной стра
тегии в игре с полной информацией часто можно выполнить
только при помощи перебора всех возможных партий игры.
Для этого строится дерево игры и изучаются вершины построен
ного дерева. Дерево игры в шахматы огромно: на первом уровне
такого дерева 20 вершин, на втором — уже 400 вершин! Постро
ить такое дерево пока не удалось никому, даже при помощи са
мого мощного компьютера, поэтому и выигрышную стратегию
найти тоже пока не удалось. Неизвестно даже, кто из игроков
в шахматной игре имеет такую стратегию.
В играх, которые допускают ничью, может существовать ни
чейная стратегия — правило, позволяющее каждому из игро
ков свести любую партию к ничьей. Ничейная стратегия есть,
например, в игре Крестики-нолики.
Рассмотрим игру Камешки с начальной позицией 8 камеш
ков, в которой разрешается брать на каждом ходу 1, 3 или 4 ка
мешка. Изучать позиции игры будем с точки зрения разумного
игрока, чья очередь делать ход (кто именно из игроков — Пер
вый или Второй — неважно). Разместим все возможные пози
ции игры на числовой линейке.
01 2345678
Назовём позицию выигрышной, если из неё есть ход, кото
рый оставит противнику проигрышную позицию.
О
Назовём позицию проигрышной, если любой ход из неё
оставляет противнику выигрышную позицию.
Позиция О проигрышная: партия закончена, игрок, чья оче
редь была бы делать ход, уже проиграл.
Позиции 1, 3 и 4 выигрышные: игрок может забрать все ка
мешки и тем самым оставить противнику проигрышную пози
цию О.
Позиция 2 проигрышная: из этой позиции можно сделать
только один ход — взять 1 камешек и тем самым оставить про
тивнику выигрышную позицию 1.
На числовой линейке выигрышные позиции пометим крас
ным, а проигрышные — синим.
01 2345678
Позиция 5 выигрышная: взяв 3 камешка, игрок оставляет
противнику проигрышную позицию 2. Так же и позиция 6 вы
игрышная: взяв 4 камешка, игрок оставляет противнику про
игрышную позицию 2.
0 1 2 3 4 5 6 7 8
Позиция 7 проигрышная: все ходы, которые можно сделать
из этой позиции, оставляют противнику выигрышную позицию
6, 4 или 3.
74
Начальная позиция 8 выигрышная: взяв 1 камешек, игрок
оставляет противнику проигрышную позицию 7.
01 2345678
Изучая позиции игры от заключительной к начальной, мы
последовательнопометили все возможные позиции игры как
выигрышные или проигрышные. При этом начальная позиция
оказалась выигрышной. Это означает, что в данной игре вы
игрышную стратегию имеет Первый (тот, кто должен делать
ход в начальной позиции).
Пользуясь раскрашенной числовой линейкой, сформулиру
ем выигрышную стратегию для Первого:
1. На первом ходу взять один камешек (при этом Второму
достаётся 7 камешков).
2. На третьем ходу взять столько камешков, чтобы оставить
на столе только 2 камешка или 0 камешков (сколько
именно камешков при этом надо взять, зависит от того,
сколько камешков возьмёт Второй на втором ходу).
3. На пятом ходу (если игра не закончилась раньше) за
брать оставшийся камешек и выиграть.
Выигрышная стратегия заключается в том, чтобы после
каждого хода оставлять противнику проигрышную пози
цию.
Поэтому выигрышную стратегию в игре имеет тот игрок, ко
торый первым сможет занять выигрышную позицию. Поэтому:
Если начальная позиция выигрышная, то выигрышную
стратегию имеет Первый, если проигрышная — Второй.
Найди выигрышную стратегию в игре Камешки (начальная по
зиция 15, разрешается брать 1, 3 или 4 камешка). Для этого
исследуй все позиции игры, раскрась числовую линейку (мож
но вырезать заготовку числовой линейки со вкладыша тетради
проектов). Выясни, у кого из игроков есть выигрышная стра
тегия. Построй последовательность такой партии, в которой
этот игрок следует выигрышной стратегии, а его противник
на каждом ходу берёт один камешек.
117
Найди выигрышную стратегию в игре Камешки (начальная
позиция 14, разрешается брать 1, 3 или 4 камешка). Можешь
воспользоваться числовой линейкой, уже раскрашенной в хо
де решения задачи 116. Выясни, у кого из игроков есть вы
игрышная стратегия в этой игре, сформулируй выигрышную
стратегию.
118
Найди выигрышную стратегию в игре Камешки (начальная по
зиция 214, разрешается брать 1 или 2 камешка).
Для решения необязательно раскрашивать числовую линейку
от 0 до 214 целиком. Вместо этого можно:
1) раскрасить позиции от 0 до 15;
2) найти закономерность расположения проигрышных пози
ций на числовой прямой;
3) определить, какой будет начальная позиция, а значит, вы
яснить, у кого из игроков есть выигрышная стратегия;
4) сформулировать выигрышную стратегию, не перечисляя
проигрышные позиции, а описывая их.
119
Робот находится в центре коридора без боковых выходов,
идущего в неизвестном направлении: вертикальном (идуще
го вверх-вниз) или горизонтальном (идущего вправо-влево).
Составь алгоритм, выводящий Робота из коридора, если из
вестно, что сейчас он находится
на расстоянии не больше 15 ша
гов до каждого из двух выходов
коридора.
120
Реши задачу.
Пятеро друзей встретились и об
менялись рукопожатиями каждый
с каждым. Сколько всего было
рукопожатий?
121
Даны правила игры Сотня.
Правила игры Сотня
Начальная позиция. Число О.
Возможные ходы. На каждом ходу игрок при
бавляет к имеющемуся числу любое целое число
от 1 до 9 включительно.
Как определить победителя. Игра заканчивает
ся, если позиция оказывается равной 100. При этом
выиграл тот, кто прибавил последнее число.
Устройте соревнование с соседом по парте — сыграйте 4 пар
тии в Сотню.
Начинайте игру по очереди: пусть один из вас играет Первым
в партиях с чётными номерами, а другой — с нечётными. Заполни
таблицу соревнования (образец такой таблицы дан в задаче 94,
вырежи такую таблицу из вкладыша тетради проектов). За каж
дую победу игрок получает 1 очко, а за поражение — 0 очков.
Сколько раз в вашем соревновании выиграл Второй?
122
Найди выигрышную стратегию в игре Сотня.
Для этого:
1) начни раскрашивать числовую линейку, начиная с заключи
тельной позиции — от 100 до 78 (можно вырезать заготовку
числовой линейки со вкладыша тетради проектов);
2) найди закономерность расположения проигрышных пози
ций на числовой прямой;
3) определи, какой будет начальная позиция — выигрышной
или проигрышной, а значит, выясни, у кого из игроков есть
выигрышная стратегия;
4) сформулируй выигрышную стратегию.
123
Построй последовательность бусин Г длины не меньше пяти,
такую, чтобы все следующие утверждения не имели смысла
для этой последовательности:
В последовательности Г седьмая бусина — красная тре
угольная.
В последовательности Г следующая бусина после каждой
круглой — квадратная.
В последовательности Г предыдущая бусина перед каждой
квадратной — треугольная.
124
78
Дерево игры Ползунок (см. задачу 112) на поле 5x4 очень
большое, оно не помещается на странице. Дерево L —это
часть полного дерева игры, состоящая из некоторого элемен
та (т. е. позиции) А и всех элементов, в которые из А идут
последовательности. Таким образом, L есть дерево перебора
всех возможных окончаний игры из позиции А.
Определи, какой игрок — Первый или Второй—должен хо
дить в позиции А. Затем определи, у кого из игроков есть
выигрышная стратегия. Для этого:
1) перерисуй дерево L в тетрадь, заменив позиции их именами;
2) исследуй все позиции дерева L в учебнике и в тетради,
имя каждой выигрышной позиции обведи красным, а про
игрышной — синим;
3) определи, у кого из игроков есть выигрышная стратегия,
и запиши эту стратегию в виде последовательности позиций.
125
Даны правила игры Пешка.
Правила игры Пешка
Начальная позиция. Игра
ведётся на шахматной доске,
пешка стоит на одном из по
лей (на каком именно поле —
устанавливается
дополни
тельными правилами).
Возможные ходы. На каж
дом ходу игрок передвигает
пешку на одно поле влево или на одно поле вниз.
Как определить победителя. Игра заканчивает
ся, если пешка оказывается в левом нижнем углу
доски — на поле al. Выигрывает тот игрок, который
сделал последний ход.
Исследуй игру Пешка. Попытайся объ
яснить, почему в этой игре выигрышная
стратегия не нужна: победа не зависит
от того, насколько умело играют игроки.
При каких начальных позициях в игре
Пешка выигрывает Первый и при ка
ких — Второй?
126
а) Нарисуй, как разрезать много
угольник Q, чтобы получилось четыре
одинаковых многоугольника.
б) Нарисуй, как разрезать многоуголь
ник G, чтобы получилось два одинаковых
многоугольника.
127
За один ход фишка может сдвинуть
ся на одно поле влево или на одно
поле вверх. Сколькими различными
путями фишка может пройти по
шахматной доске из поля с5 на
поле а8, если будет двигаться толь
ко влево или вверх?
79
Выигрышные стратегии
Продолжим изучение игр и поиск выигрышных стратегий
путём исследования всех позиций игры. Ты знаешь, что у боль
шинства игр деревья игры слишком велики, чтобы мы могли
исследовать все позиции такой игры на дереве. Если каждую
позицию можно представить в виде числа (как в играх Камеш
ки и Сотня), то все позиции такой игры можно разместить на
числовой линейке и исследовать по порядку. Это возможно
только тогда, когда разных позиций-чисел не слишком много.
Рассмотрим другие примеры игр, все позиции которых мы
можем удобно расположить.
Такими играми, например, являют
ся игры на шахматной доске, в которых
игра ведётся только одной фигурой. В та
кой игре каждая позиция соответствует
тому полю шахматной доски, на котором
находится фигура (полем в шахматах
называется клетка шахматной доски). Ис
следовав все поля шахматной доски, мы
исследуем все возможные позиции игры.
Каждое поле шахматной доски имеет имя, состоящее из
латинской буквы и цифры. Например, поле с красной точкой
имеет имя d4, а поле с зелёной точкой — имя g6.
|
Правила игры Король
Начальная позиция. Игра ведётся на
шахматной доске, король стоит на одном
из полей (на каком именно, устанавли
вается дополнительными правилами).
Возможные ходы. На каждом ходу
игрок передвигает короля на одно поле
влево, или на одно поле вниз, или на
одно поле влево-вниз по диагонали.
Как определить победителя. Игра заканчивается, если
король оказывается в левом нижнем углу доски — на поле
al. Выигрывает игрок, который сделал последний ход.
Исследуем все позиции игры Король
с начальной позицией d4. Возьмём рису
нок шахматной доски, не раскрашенный
в шахматном порядке: ведь шахматная
раскраска в этой игре роли не играет,
а нам при раскрашивании полей она
будет мешать. Выигрышные позиции
будем раскрашивать красным цветом,
проигрышные — синим.
Начнём
с
заключительной
пози
ции — поля al. Эта позиция проигрышная.
Все позиции, из которых за один ход
можно попасть на поле al, — поля а2,
Ъ2, Ы — выигрышные позиции. Дальше
выбираем для исследования только те
поля, все ходы из которых ведут на уже
раскрашенные поля.
С поля аЗ можно пойти только на
поле а2 (выигрышное) — значит, пози
ция аЗ проигрышная. Аналогично этому
позиция cl проигрышная. Из позиции ЬЗ
можно перейти в проигрышную позицию
аЗ — значит, позиция ЬЗ выигрышная.
Аналогично этому выигрышной является
позиция с2. Все ходы из позиции сЗ ведут
в выигрышные позиции, поэтому позиция
сЗ проигрышная.
Мы будем раскрашивать поля, пока
не раскрасим все поля квадрата 4x4.
Остальные поля доски раскрашивать не надо, потому что они
не являются позициями игры Король с начальной позицией d4.
Начальная позиция (поле d4) выигрышная; значит, выигрыш
ная стратегия есть у Первого, и заключается она в следующем:
1. Пойти на поле сЗ;
2. В зависимости от хода Второго пойти на поле cl либо
на поле аЗ;
3. Какой бы ход ни сделал Второй, пойти на поле al.
81
Есть и другие игры, для которых все позиции можно распо
ложить в таблице, похожей на изображение шахматной доски.
Такова, например, игра Две кучи камешков.
Правила игры Две кучи камешков
Начальная позиция. Две кучи
камешков (количество камешков
в каждой куче устанавливается до
полнительными правилами).
Возможные ходы. На каждом
ходу игрок может взять либо один камешек из одной из
куч, либо по одному камешку из обеих куч одновременно.
Как определить победителя. Игра заканчивается, если
все камешки закончились. Выигрывает тот игрок, кото
рый забрал последний камешек.
Каждая позиция этой игры — это две кучи камешков; её
можно представить в виде пары чисел, где первое число — ко
личество камешков в первой куче, а второе — во второй. Напри
мер, пара (5; 2) — позиция игры, где в первой куче 5 камешков,
а во второй — 2.
Все возможные позиции такой игры можно расположить
в таблице, столбцы и строки которой занумерованы числами О,
1, 2 и т. д. Каждая клетка таблицы соответствует некоторой по
зиции: номер столбца, в котором находится данная клет
ка, — это число камешков в первой куче, а номер строки — чис
ло камешков во второй.
На рисунке справа показана таблица
012 3 4 5 6
для игры Две кучи камешков, где в началь0______________
ной позиции в первой куче 6 камешков, а во
1______________
второй — 7. Зелёной точкой помечена клет2•
ка, соответствующая позиции (5; 2).
3
При помощи такой таблицы все пози4
ции данной игры можно исследовать так
5
же, как мы исследовали позиции игры Ко6______________
роль. Это ты сделаешь, когда будешь ре71
I I
I
шать задачи.
82
128
Исследуй все позиции игры Король с начальной позицией h8:
1) раскрась шахматную доску, начиная с заключительной по
зиции — с клетки а 1;
2) определи, выигрышной или проигрышной будет начальная
позиция, а значит, выясни, у кого из игроков есть выигрышная
стратегия.
129
Даны правила игры Ладья.
J
Правила игры Ладья
• Начальная позиция. Игра
ведётся на шахматной доске,
ладья стоит на одном из полей
(на каком именно — устанав
ливается
дополнительными
правилами).
Возможные ходы. На каж
дом ходу игрок передвигает
ладью на сколько угодно по
лей вправо или на сколько угодно полей вверх.
Как определить победителя. Игра заканчивает
ся, если ладья оказывается в правом верхнем углу
доски — на поле h8. Выигрывает игрок, который
сделал последний ход.
Сыграй с соседом по парте две партии в игру Ладья с началь
ной позицией а/ и две партии с начальной позицией а2. На
рисуй на шахматной доске путь, который прошла ладья в ходе
одной из сыгранных вами партий.
130
Определи, при каких начальных позициях в игре Ладья выиг
рышная стратегия есть у Первого и при каких —у Второго:
1) раскрась шахматную доску, начиная с заключительной по
зиции — поля h8\
2) постарайся коротко описать, при каких начальных позициях
выигрышную стратегию имеет Первый и при каких — Второй;
3) сформулируй выигрышную стратегию для Первого в игре
с начальной позицией на поле а2\
4) сформулируй выигрышную стратегию для Второго в игре
с начальной позицией на поле а1.
83
131
Даны правила игры Ферзь.
|
Правила игры Ферзь
*
Начальная позиция. Игра
ведётся на шахматной доске,
ферзь стоит на одном из полей
(на каком именно — устанавливается
дополнительными
правилами).
Возможные
ходы.
На
каждом ходу игрок передви
гает ферзя на сколько угодно полей: влево, вниз или
по диагонали влево-вниз.
Как определить победителя. Игра заканчивает
ся, если ферзь оказывается в левом нижнем углу
доски — на поле al. Выигрывает игрок, который
сделал последний ход.
Найди выигрышную стратегию в игре Ферзь с начальной по
зицией д8 и в той же игре с начальной позицией h5:
1) раскрась все поля шахматной доски, начиная с заключи
тельной позиции — поля аГ,
2) для каждой из двух начальных позиций (д8 и h5) определи,
какой она будет — выигрышной или проигрышной, а значит,
у кого из игроков есть в игре с этой начальной позицией вы
игрышная стратегия;
3) сформулируй выигрышную стратегию для каждой из этих
двух начальных позиций.
Выпиши имена шести полей, с начальными позициями в кото
рых в игре Ферзь выигрышная стратегия есть у Первого. Вы
пиши имена ещё шести полей, с начальными позициями в ко
торых в игре Ферзь выигрышная стратегия есть у Второго.
132
Построй часть дерева игры Ползунок с данной по
зицией в элементе первого уровня. По образцу,
приведённому на странице 78, дай всем элементам
полученного дерева имена и найди выигрышную
стратегию окончания игры из этой позиции.
Для этого проведи исследование, как в задаче 124.
84
133
Найди выигрышную стратегию в игре Две кучи камешков с на
чальной позицией (4; 5): раскрась поле, начиная с заключи
тельной позиции — клетки (0; 0), и определи, какой будет на
чальная позиция — выигрышной или проигрышной, а значит,
у кого из игроков есть выигрышная страте
гия. Запиши последовательность позиций ка
кой-нибудь партии, в которой один из игро
ков использует выигрышную стратегию,
а другой на первом своём ходу берёт по од
ному камешку из каждой кучи, а на следу
ющем берёт один камешек из одной из куч
(позиции обозначай парами чисел).
134
Построй два разных множества, для каждого из которых ис
тинны все следующие утверждения:
Все элементы этого множества — двузначные нечётные
числа.
Сумма цифр каждого числа из этого множества равна 10.
Самое большое число из этого множества на 1 меньше
суммы всех остальных чисел из этого множества.
135
Составь алгоритм со следующим заголовком:
алг переход в противоположный угол
дано | Робот стоит в каком-то углу поля
I размером 10x14 клеток, на поле
I стен нет
надо I Робот перешёл в противоположный
I угол
136
Робот находится внутри тупика: горизонтального коридора без
боковых выходов, закрытого с одного из концов (правого или
левого — неизвестно). Составь алгоритм, выводящий Робота
из этого коридора, если известно, что в начальном состоянии
он находится на расстоянии 10 шагов до выхода из коридора
и в 10 шагах до закрытого его конца.
85
137
Реши задачу, используя поиск
выигрышной стратегии в игре.
Алёша Попович и Добрыня
Никитич воюют с девятиглавым
змеем. По очереди богатыри хо
дят к его пещере и отрубают 1,
2 или 3 головы. Как начавшему
бой Алёше обрести славу побе
дителя змея (отрубить послед
нюю голову)?
Найди выигрышную стратегию в игре Камешки (начальная по
зиция 10, разрешается брать 1, 2 или 3 камешка).
Для этого исследуй все позиции игры, раскрась числовую ли
нейку. Выясни, у кого из игроков есть выигрышная стратегия.
Построй последовательность позиций такой партии, в кото
рой игрок следует выигрышной стратегии, а его противник на
каждом ходу берёт 2 камешка.
139
Прочитай описание игры Назови 26.
Играют двое.
Первый игрок называет любое натуральное чис
ло, не превосходящее 4, т. е. одно из чисел 1, 2, 3, 4.
Второй игрок прибавляет к названному числу
своё число, также не превосходящее 4.
К этой сумме первый прибавляет какое-либо на
туральное число, не превосходящее 4, и сообщает
сумму и т. д.
Выигрывает тот, кто первым достигнет числа 26.
Сформулируй правила этой игры как игры с полной инфор
мацией. Найди выигрышную стратегию в этой игре.
140
86
Нарисуй в тетради по клеткам два разных прямоугольных тре
угольника, площадь каждого из которых равна 12 ед. кв.
Цикл «пока»
Решим задачу.
Задача. На поле где-то ниже Робота на неизвестном расстоянии
есть стена. Нужно, чтобы Робот подошёл вплотную к этой стене.
Если мы командуем Роботом вручную, без компьютера, то
задачу можно решить так: дадим Роботу запрос снизу свобод
но. Если Робот ответит «нет», значит, он уже у стены и задача
решена. Если же Робот ответит «да», то можно скомандовать
вниз и опять дать запрос снизу свободно. Если Робот ответит
«да»—опять скомандовать вниз, дать запрос снизу свободно,
и так поступать дальше, пока Робот не ответит «нет». Заранее
неизвестно, сколько раз мы дадим команду вниз — 0, 3, 8 или
2014 раз, это зависит от начального расположения Робота отно
сительно стены. Например, если Робот уже стоял рядом со сте
ной, то команда вниз не подавалась бы ни разу. Если Робот стоял
в 101-й клетке от стены, то команда вниз подавалась бы 100 раз.
Наши действия при решении этой задачи можно описать
так: пока на запрос снизу свободно Робот отвечает «да», надо
командовать вниз и повторять запрос. Такое описание пригодно
при любом, расстоянии от Робота до стены.
Наша цель, однако, не ручное управление Роботом,
а составление программы (алгоритма) для компьютера. По
этому приведённую выше последовательность действий надо
описать на алгоритмическом языке. Алгоритм должен быть
универсальным, т. е. не должен зависеть от расстояния меж
ду Роботом и стеной. Для этого в алгоритмическом языке есть
специальная составная команда — цикл «пока». В общем виде
цикл «пока» записывается так:
нц пока
КЦ
Слова нц и кц имеют тот же смысл, что и в цикле «N раз», —
они отмечают начало и конец цикла. При выполнении цикла
«пока» компьютер повторяет следующие действия:
а) проверяет условие, записанное после служебного слова
пока;
87
б) если условие не соблюдается (Робот ответил «нет»), то
выполнение цикла завершается и компьютер начинает выпол
нять команды, записанные после кц. Если же условие соблюда
ется (Робот ответил «да»), то компьютер выполняет последова
тельность команд цикла, потом снова проверяет условие и т. д.
Вот алгоритм вниз до стены для решения задачи, в нём ис
пользована составная команда цикл «пока»:
алг вниз до стены
дано I
надо | Робот идёт вниз,
I
I
пока не дойдёт
до стены
нач
нц пока снизу свободно
вниз
КЦ
кон
Аналогично можно составить алгоритмы влево до стены,
вправо до стены, вверх до стены, которыми мы далее часто
будем пользоваться.
Как Робот выполняет такой алгоритм?
Например, пусть Робот стоит в клетке А. Тогда при выпол
нении алгоритма вниз до стены диалог между Роботом и ком
пьютером будет таким:
компьютер: снизу свободно?
Робот: да
компьютер: вниз
Робот:
компьютер: снизу свободно?
Робот: да
компьютер: вниз
Робот:
компьютер: снизу свободно?
Робот: нет
88
Поскольку Робот ответил «нет», т. е. записанное после
пока условие не соблюдается, то на этом выполнение цикла
«пока» и алгоритма вниз до стены заканчивается.
Свойства цикла «пока»
Свойство 1. Последовательность команд цикла может не
выполниться ни разу.
Если условие в цикле «пока» не соблюдается с самого
начала, то последовательность команд цикла не выполняет
ся ни разу. Например, если в алгоритме вниз до стены Ро
бот на первый же запрос снизу свободно ответит «нет»
(т. е. если по нижней границе клетки, в которой находит
ся Робот, с самого начала уже стоит стена), то компьютер
не вызовет команду вниз ни разу. Важно понимать, что си
туация, когда цикл ни разу не выполняется, не является
отказом. Это нормальный вариант выполнения алгоритма.
Свойство 2. Выполнение цикла может не завершиться.
Выполнение цикла «пока» может не завершиться, если ус
ловие всё время будет соблюдаться. Такая ситуация обычно воз
никает из-за ошибок в составлении алгоритма. Она называется
зацикливанием.
Например, рассмотрим такой фрагмент алгоритма:
нц пока снизу свободно
вниз
вверх
кц
Если снизу от Робота нет стены, он будет бесконечно топ
таться на месте, совершая шаги вверх и вниз. Исполнение ал
горитма никогда не закончится.
Свойство 3. Условие цикла не проверяется в процессе вы
полнения последовательности команд цикла.
Условие в цикле «пока» проверяется только перед выпол
нением последовательности команд цикла, но не проверяется
в процессе выполнения этих команд.
89
Пример. Пусть Робот находится в клетке А (см. рисунок)
и компьютер выполняет такой цикл:
нц пока снизу свободно
вниз
вниз
КЦ
Тогда диалог между компьютером и Роботом будет таким:
В процессе выполнения последовательности команд цик
ла компьютер не проверяет, истинно ли условие выполне
ния цикла. Если после выполнения какой-то команды внутри
цикла «пока» условие перестанет соблюдаться, то компьютер
всё равно будет выполнять последовательность команд цик
ла до конца.
Свойство 4. Перед каждым выполнением последовательно
сти команд цикла условие обязательно выполняется.
Это очевидное свойство: если компьютер приступает к вы
полнению последовательности команд цикла, значит, условие
выполнено.
Свойство 5. Сразу
выполняется.
90
после
окончания
цикла
условие
не
Это свойство тоже очевидно: цикл заканчивается в тот мо
мент, когда при очередной проверке условие оказалось невы
полненным.
Составление алгоритма
с циклом «пока»
Цикл «пока» используется всякий раз, когда число повто
рений каких-то действий заранее неизвестно. Составление та
ких циклов — трудная задача.
Чтобы не запутаться и что-нибудь не забыть, лучше всего
строить цикл «пока» по частям:
1. Понять, когда цикл должен закончиться, т. е. сформулиро
вать условие выполнения цикла. Иногда это удобно делать
от противного — записать противоположное условие.
2. Описать, что происходит при однократном выполнении цикла
(принято говорить «за один шаг цикла»), т. е. выполнить
один раз последовательность команд цикла.
3. Проверить, что цикл рано или поздно закончится, а не будет
повторяться вечно.
Циклы «N раз» и «пока» оформляются в алгоритмическом
языке почти одинаково — обе эти команды задают повторяю
щуюся последовательность команд. Однако у этих двух ци
клов есть одно существенное различие. Начиная выполнять
цикл «N раз», компьютер знает, сколько раз придётся по
вторить последовательность команд цикла. При исполнении
цикла «пока» это не так: компьютер каждый раз проверяет
условие цикла и не может заранее определить, через сколько
повторений выполнение закончится. Определить количество
повторений цикла «пока» можно только после того, как цикл
завершён.
Отсюда ясно, в каких случаях какой цикл следует исполь
зовать. Если к моменту начала цикла количество повторений
известно, можно воспользоваться циклом «N раз». Если же ко
личество повторений заранее определить нельзя, необходим цикл
«пока».
91
141
Составь диалог компьютера и Робота при выполнении каждого
цикла в ситуации, когда Робот стоит: а) в закрашенной клетке;
б) в незакрашенной клетке. Если выполнение алгоритма при
ведёт к зацикливанию — прерви описание диалога и напиши
о зацикливании.
нц пока клетка чистая
закрасить
кц
нц пока клетка закрашена
закрасить
кц
142
Составь алгоритмы влево до стены, вправо до стены,
вверх до стены, о которых идёт речь на с. 88. Запиши
условия дано и надо- Проверь, что алгоритмы составлены
правильно — что не возникнет отказа и что цикл не будет по
вторяться вечно.
143
Робот находится у левой стены прямоугольного поля, огоро
женного со всех сторон стенами. Внутри поля стен нет, размеры
поля неизвестны. Надо составить такой алгоритм, при выпол
нении которого Робот закрасит горизонтальный ряд клеток от
исходного положения до правой стены и вернётся в исходное
положение: сначала Робота надо довести до правой стены, по
дороге закрашивая клетки, а затем вернуть в исходное положе
ние и закрасить эту исходную клетку. Вот этот алгоритм:
алг закрасить ряд вправо и вернуться
дано | Робот стоит у левой стены поля
надо | закрашен весь горизонтальный ряд,
I
I
в котором стоит Робот,
Робот в исходном положении
нач
вправо до стены с закрашиванием
влево до стены
закрасить
кон
92
144
Вспомогательный алгоритм влево до стены ты построил
в ходе решения задачи 142. Построй вспомогательный алгоритм
вправо до стены с закрашиванием. Запиши условия дано
и надо. Проверь, что алгоритм составлен правильно — что не
возникнет отказа и что цикл не будет повторяться вечно.
Составь алгоритм с таким заголовком (см. ниже).
алг закрасить прямоугольник
дано I Робот стоит в левом нижнем углу
I поля без внутренних стен
надо I весь прямоугольник закрашен,Робот
I в исходном положении
Используй в качестве вспомогательного алгоритм закра
сить ряд вправо и вернуться, составленный при реше
нии задачи 143.
145
146
147
Реши задачу 144, считая, что о начальном положении Робота
на поле ничего не известно.
Нарисуй такой же четырёхуголь
ник по клеткам в тетради. Потом
нарисуй, как разрезать его на ча
сти, чтобы из них можно было со
брать квадрат на сетке. Нарисуй
такой квадрат и покажи штриховы
ми линиями, из каких частей он со
ставлен.
На поле Робота ровно одна стена. Это горизонтальная сте
на, которая не примыкает к границам поля. Робот нахо
дится в одной из клеток, прилегающих к стене сверху. Точ
ные размеры поля и стены и точное расположение Робота
неизвестны. Составь алгоритм, при выполнении которого
Робот:
а) окажется в одной из клеток, прилегающих к стене снизу;
б) закрасит все клетки, прилегающие к стене снизу;
в) закрасит все прилегающие к стене клетки.
93
148
149
Робот стоит в левом конце горизонтального коридора, ниж
няя стена которого сплошная, а в верхней имеется несколь
ко выходов. Составь алгоритм, который заставляет Робота
переместиться из клетки А в клетку В (см. рисунок, сколько
клеток между клетками А и В, неизвестно) и закрасить все
те клетки коридора, которые расположены напротив боковых
выходов.
Реши задачу.
В нашем классе из 31 учащегося по итогам первой четверти
неуспевающих нет (ни у кого нет ни одной четвертной двой
ки). При этом у нас имеется 3 круглых отличника и 3 круглых
троечника (тех, у кого тройки в четверти по всем предме
там). Пятеро учеников закончили четверть только на чет
вёрки и пятёрки. Известно также, что пятёрки имеют среди
четвертных оценок 18 учеников и 24 ученика имеют среди
четвертных оценок четвёрки. Сколько учеников нашего клас
са имеют в четверти и тройки, и четвёрки, и пятёрки? Сколь
ко учеников нашего класса не получили в четверти ни одной
четвёрки?
Для решения задачи нарисуй схему с множествами:
А(?)
В(?)
пересечение
А, В и С (?)
пересечение
А и В (?)
пересечение
А и С (?)
пересечение
В и С (?)
объединение А, В и С(?)
94
150
Нарисуй в тетради по клеткам:
а) прямоугольник, не являющийся квадратом, площадь кото
рого равна 64 ед. кв.;
б) прямоугольный треугольник, площадь которого равна
17 ед. кв.;
в) четырёхугольник, площадь которого равна 13 ед. кв.;
г) два разных прямоугольных треугольника, площадь каждого
из которых равна ю| ед. кв.;
д) два разных четырёхугольника, не являющихся прямоуголь
никами, площадь каждого из которых равна 21 ед. кв.
151
152
К полю для игры Крестики-нолики добав
лена одна клетка. Правила игры при этом
остались прежними: Первый ставит крес
тики, Второй — нолики. Выигрывает тот,
кто первым построит ряд из трёх своих
значков по горизонтали, вертикали или
------ ------ ------ -----диагонали. В отличие от игры на обыч
ном поле, в игре Крестики-нолики на таком поле Первый име
ет выигрышную стратегию. Куда должен поставить крестик
Первый на первом ходу, чтобы наверняка выиграть?
Вот правила игры 7 камней:
Правила игры 7 камней
Начальная позиция. Куча из 7 камешков.
Возможные ходы. На каждом ходу игрок разде
ляет любую из имеющихся куч на две (необязатель
но пополам).
Как определить победителя. Игра заканчива
ется, если очередной ход сделать невозможно. Вы
игрывает тот, кто сделал последний ход.
Исследуй игру 7 камней. Попытайся объяснить, почему в этой
игре выигрышная стратегия не нужна, — победа не зависит от
того, насколько умело играют игроки. Кто выигрывает в игре
7 камней?
95
153
Реши задачу.
Почтальон Печкин, выйдя из почтового отделения, разнёс
почту в каждый дом деревни, после чего зашёл с посылкой
к дяде Фёдору (зайдя сначала за ней на почту), а потом вер
нулся домой. На рисунке показаны все тропинки, по которым
проходил Печкин, причём, как оказалось, ни по одной из них
он не проходил дважды. Каков мог быть маршрут почтальона
Печкина? В каком доме живёт дядя Фёдор?
Равновесные выигрышные
стратегии
До сих пор, для того чтобы построить выигрышную страте
гию, мы исследовали все позиции игры и выделяли выигрыш
ные и проигрышные позиции. Но для многих игр существуют
стратегии, построение которых не требует исследования всех
позиций. Таковы, например, равновесные стратегии, которыми
мы сейчас займёмся.
96
Рассмотрим игру Монеты на весах.
Правила игры Монеты на весах
Начальная позиция. На каждой чашке весов лежат мо
неты (сколько именно монет лежит на каждой чашке, уста
навливается дополнительными правилами). Все монеты оди
наковые.
Возможные ходы. На каждом ходу игрок может взять
сколько угодно монет с одной чашки.
Как определить победителя. Игра заканчивается, если
все монеты закончились. Выигрывает игрок, который забрал
последнюю монету.
Пусть в начальной позиции на каждой чашке лежит по
20 монет. При такой начальной позиции весы находятся в рав
новесии — ведь монет на чашках поровну и все монеты одинако
вые. Первый любым своим ходом это равновесие нарушит — он
возьмёт монеты только с одной чашки. А Второй может восста
новить равновесие — взять столько же монет с другой чашки.
Пусть и дальше Второй каждым своим ходом восстанавливает
равновесие. Выигрышна ли такая стратегия для Второго?
Восстанавливая равновесие на каждом ходу, Второй доби
вается того, что все равновесные позиции достаются Первому.
Но и заключительная позиция равновесная (на обеих чашках
ничего нет), так что и эта позиция в какой-то момент игры до
станется Первому. При этом Первый уже не сможет сделать
очередной ход и проиграет. Таким образом, описанная страте
гия является выигрышной для Второго.
Итак, для предложенной равновесной стратегии мы прове
рили два условия:
1. Второй всегда сможет сделать свой ход.
2. Заключительная позиция обязательно достанется Первому
(и поэтому он обязательно проиграет).
Оба эти условия выполнены, значит, наша стратегия вы
игрышная.
Стратегию, при которой игрок на каждом своём ходу вос
станавливает равновесие (т. е. делает позицию равновес
ной), мы будем называть равновесной стратегией.
97
В игре Монеты на весах, где начальная позиция неравно
весная (например, на одной чашке лежит 15 монет, а на дру
гой — 29), равновесную стратегию имеет Первый: на первом
ходу он должен сделать позицию равновесной (взять 14 мо
нет из 29), а дальше повторять ходы Второго, восстанавливая
равновесие. Эта стратегия выигрышна для Первого: он всегда
сможет сделать ход, а заключительная позиция обязательно до
станется Второму.
Равновесную стратегию можно строить не только в играх со
взвешиванием, но и во многих других играх. Обычно это игры,
в которых проигравшим считается тот, кто не может сделать
очередной ход. Для построения равновесной стратегии в такой
игре нужно сначала сообразить, какие позиции считать равно
весными. При этом важно, чтобы и заключительная позиция
тоже оказалась равновесной.
Равновесную стратегию можно построить, например, для
игры Ладья.
Действительно, можно считать равновесными такие по
зиции этой игры, в которых ладья стоит на чёрной диагонали
шахматной доски. Тогда в игре с начальной позицией al рав
новесная стратегия Второго состоит в том, чтобы каждый раз
после хода Первого возвращать ладью на эту диагональ (и тем
самым делать позицию снова равновесной). Такая стратегия
оказывается выигрышной для Второго. Следуя этой стратегии,
Второй каждый раз передвигает ладью на столько же полей, на
сколько её передвинул Первый на предыдущем ходу; но если
Первый сделал ход по вертикали, то Второй ходит по горизон
тали, и наоборот. Второй всегда сможет сделать такой ход, и за
ключительная позиция непременно достанется его противнику.
На рисунке показан пример партии,
в которой Второй следует этой страте
гии (на рисунке показана схема пути
ладьи в этой партии).
Заметим, что эта равновесная стра
тегия ничем не отличается от той стра
тегии, которую мы построили, изучив
все позиции игры: мы просто получили
один и тот же результат разными спо
собами.
98
Приведём ещё один пример игры,
для которой можно построить равно
весную стратегию. Это знакомая тебе
игра Ползунок на поле 5x4. Какие
позиции в этой игре мы будем счи
тать равновесными? Начальную по
зицию этой игры можно повернуть
«вверх ногами» — от этого рисунок поля не изменится (см. ри
сунок). Будем считать равновесными и другие позиции, кото
рые не изменяются при таком повороте. Вот примеры таких
позиций:
Пусть теперь Первый следует такой равновесной стратегии:
на первом ходу он проводит вертикальный отрезок в центре
поля (при этом позиция остаётся равновесной). А потом после
каждого хода Второго Первый восстанавливает равновесие: если
Второй сделал ход на одном конце ползунка (ломаной), то Пер
вый проводит отрезок на другом конце и в обратном направ
лении. Вот пример начала партии, в которой Первый следует
такой стратегии:
При такой стратегии если Второму удалось сделать ход, то
и Первому это удастся — он всегда сможет провести отрезок на
другой стороне поля и восстановить равновесие. Если же Вто
рой сделать ход не может, то он уже проиграл. Следовательно,
описанная равновесная стратегия выигрышна для Первого.
99
В задачах ты встретишься и с другими играми, в кото
рых можно построить выигрышную равновесную стратегию.
Некоторые игры будут похожи на те, которые мы разобрали,
а другие будут непохожи. В каждой такой игре нужно будет
выделить равновесные позиции и описать равновесную стра
тегию для одного из игроков. После этого останется только
убедиться, что построенная равновесная стратегия является
выигрышной — как бы ни играл противник, игрок, следу
ющий этой стратегии, непременно выиграет.
154
Даны правила игры Шары и ящики.
Правила игры Шары и ящики
Начальная позиция. Два открытых ящика,
в каждом лежат шары. Сколько шаров в каждом
ящике, определяется дополнительными правилами.
Возможные ходы. На каждом ходу игрок заби
рает из одного ящика сколько угодно шаров.
Как определить победителя. Игра заканчивает
ся, если очередной ход сделать невозможно — шары
закончились. Выигрывает тот, кто сделал последний
ход.
Исследуй игру Шары и ящики для различных начальных пози
ций. Кто из игроков обладает выигрышной стратегией? Опи
ши эту стратегию.
Нужно рассмотреть два варианта начальных позиций:
1) если шаров в ящиках поровну;
2) если шаров в ящиках не поровну.
155
100
В игре Ползунок на поле 4x3 существует рав
новесная выигрышная стратегия для Первого,
подобная той, которая описана на с. 99. По
строй последовательность позиций какой-либо
партии этой игры, в которой Первый следует
равновесной выигрышной стратегии.
156
Сформулируй равновесную выигрышную стратегию для Пер
вого в игре Ладья с начальной позицией аЗ. Приведи пример
партии этой игры, в которой Первый следует твоей страте
гии, — нарисуй путь ладьи в такой партии.
157
Классифицируй числа множества Р по остаткам от деления
на 4: в одну группу помести все числа множества Р, которые
делятся на 4 без остатка, в другую — те числа, при делении
которых на 4 получается остаток 1, и т. д.
158
Даны правила игры Минусы.
Правила игры Минусы
Начальная позиция. В строке написано несколь
ко минусов. Сколько именно, определяется дополни
тельными правилами.
Возможные ходы. На каждом ходу игрок пере
правляет один минус на плюс или два соседних ми
нуса на два плюса.
Как определить победителя. Игра заканчивает
ся, если очередной ход сделать невозможно — ми
нусы закончились. Выигрывает тот, кто сделал по
следний ход.
Найди выигрышную стратегию в игре Минусы с начальной
позицией 18 минусов и в той же игре с начальной позицией
21 минус. Определи, кто обладает выигрышной стратегией,
и опиши эту стратегию для каждой из данных начальных по
зиций. Теперь попробуй обобщить свои выводы — опиши вы
игрышную стратегию для любой игры Минусы.
а) если начальная позиция — нечётное число минусов;
б) если начальная позиция — чётное число минусов.
101
159
В игре Ползунок на поле 4x4 равновесную выигрышную
стратегию для Первого, которая описана на с. 99, постро
ить не удастся. Но в этой игре существует другая равно
весная выигрышная стратегия для Первого.
Она получается, если считать равновесными
такие позиции, в которых при перегибании
поля по синей линии его правая и левая
части совпадают. Эта стратегия заключает
ся в зеркальном повторении ходов Второго
(представь себе, что зеркало стоит на си
ней прямой).
Построй последовательность позиций какой-либо партии,
в которой Первый следует такой стратегии и первым ходом
соединяет две средние точки нижнего ряда.
•
•
•
•
160
• •
• •
• •
•- -•
•
•
•
•
Построй два таких множества бусин А и В, для которых все
следующие утверждения истинны:
Множество П равно пересечению множеств А и В.
Множество О равно объединению множеств А и В.
В множестве А жёлтых бусин больше, чем квадратных.
В множестве В треугольных бусин больше, чем красных.
О
102
161
Робот находится на прямоугольном поле, внутри которого
стен нет. Составь алгоритм, при выполнении которого Робот
закрашивает все клетки поля, прилегающие к стенам.
162
Сколько разных чисел можно получить, переставляя цифры
числа 5434? Построй дерево перебора вариантов.
163
Исследуй игру Оттесни шашку. У кого из игроков есть рав
новесная выигрышная стратегия? Сформулируй эту стратегию.
Правила игры Оттесни шашку
Начальная позиция. Полоска 1 х 20 клеток. В край
них клетках полоски стоят белая и чёрная шашки.
Возможные ходы. Каждый игрок на своём ходу
передвигает свою шашку на одну или две клетки по
направлению к середине полосы, если это возмож
но. Перепрыгивать через шашку противника нельзя.
Первый двигает белую шашку, Второй — чёрную.
Как определить победителя. Игра заканчива
ется, если очередной ход сделать невозможно. Вы
игрывает тот, кто сделал последний ход.
164
Найди выигрышную стратегию в игре Камешки (начальная по
зиция 308, разрешается брать 1, 2 или 3 камешка).
Для решения необязательно раскрашивать числовую линейку
от 0 до 308 целиком, а можно:
1) раскрасить позиции от 0 до 16;
2) найти закономерность расположения проигрышных пози
ций на числовой прямой;
3) определить, какой будет начальная позиция, а значит, вы
яснить, кто из игроков обладает выигрышной стратегией;
4) сформулировать выигрышную стратегию, не перечисляя
проигрышные позиции, а описывая их.
165
Построй последовательность однозначных чисел
длины 5, для которой все следующие утвержде
ния истинны:
В этой последовательности следующее число
после каждого нечётного — чётное.
Первый член этой последовательности больше третьего на 2.
Каждый член этой последовательности есть в множестве К.
103
166
Даны правила игры Две кучи камешков 2.
Правила игры Дее кучи камешков 2
Начальная позиция. Две кучи камешков (сколь
ко камешков в каждой куче, устанавливается допол
нительными правилами).
Возможные ходы. На каждом ходу игрок может
взять либо сколько угодно камешков из одной ку
чи, либо поровну камешков из обеих куч одновре
менно.
Как определить победителя. Игра заканчива
ется, если все камешки закончились. Выигрывает
игрок, который забрал последний камешек.
Напиши последовательность позиций партии игры Две кучи
камешков 2:
а) с начальной позицией (9; 6), в которойвыиграл Первый;
б) с начальной позицией (7; 4), в которой выиграл Второй.
167
Найди выигрышную стратегию в игре Две кучи камешков 2
с начальной позицией (6; 10) и в той же игре с начальной по
зицией (9; 8):
1) раскрась таблицу 11 х 11, начиная с заключительной пози
ции — клетки (0; 0);
2) определи, какой будет каждая из данных начальных пози
ций — выигрышной или проигрышной, а значит, у кого из
игроков есть в этой позиции выигрышная стратегия;
3) сформулируй выигрышную стратегию для каждой из дан
ных начальных позиций.
Теперь для каждой из данных начальных позиций запиши по
следовательность позиций какой-нибудь партии, в которой
один из игроков использует выигрышную стратегию, а дру
гой на каждом ходу берёт по одному камешку из каждой кучи.
168
104
Робот находится в тупике (в закрытом конце) прямого кори
дора шириной в 1 клетку, идущего в неизвестном направле
нии. В конце коридора есть выход. Составь алгоритм, выво
дящий Робота из этого коридора.
169
Английский математик Джон Хортон Конвей (род. 1937) при
думал много интересных математических игр. Вот правила
одной из таких игр:
Правила игры Ободок
Начальная позиция. Несколь
ко точек на плоскости.
Возможные ходы. На каждом
ходу игрок может провести одну
замкнутую кривую (ободок) либо
через одну из точек, либо через
две. При этом два ободка пересе
каться не должны. Вот примеры
разрешённых ходов:
Как определить победителя. Игра заканчивает
ся, если очередной ход сделать невозможно — все
точки лежат на ободках. Выигрывает тот, кто сде
лал последний ход.
Известно, что в игре Ободок с любой начальной позицией
у Первого есть равновесная выигрышная стратегия. Найди рав
новесную выигрышную стратегию для этой игры с начальной
позицией 7 точек и для той же игры с начальной позицией
8 точек. Как в каждой из этих двух начальных позиций Первый
должен провести ободок, чтобы сделать позицию равновесной?
(Своим первым ходом Первый должен разделить все точки на
две части так, чтобы каждый ход, сделанный в одной части,
можно было повторить в другой.) Сформулируй выигрышную
стратегию для каждой из данных начальных позиций.
Попробуй обобщить своё решение — построй выигрышную стра
тегию для игры Ободок: а) если в начальной позиции нечётное
число точек; б) если в начальной позиции чётное число точек.
105
170
Двое играют в следующую игру: каждый игрок по очереди
вычёркивает одно число из ряда 1, 2, 3, 4, 5, 6, 7, 8, 9,
10, 11, 12, 13, 14, 15, 16, 17, 18, 19 до тех пор, пока
не останется два числа. Если сумма этих чисел делится на
5, то выигрывает первый игрок, если не делится — второй.
У кого из игроков в этой игре есть выигрышная стратегия?
Опиши эту стратегию.
Составные условия:
слова «и», «или», «не» м
При составлении алгоритмов иногда бывает нужно исполь
зовать не одно условие, а сразу два.
Пусть, например, Робот стоит на поле, в котором нет
внутренних стен. Чтобы понять, находится ли Робот в верх
нем левом углу поля, нужно выяснить истинность двух усло
вий: слева стена, сверху стена. Если оба условия одновре
менно истинны, то Робот стоит в левом верхнем углу поля
(на котором нет внутренних стен). Если хотя бы одно из этих
условий ложно, то Робот стоит в другой клетке поля.
Другой пример. Нам надо выяснить, не находится ли Ро
бот рядом с любой из двух вертикальных границ поля. Для
этого мы должны проверить истинность двух условий: слева
стена, справа стена. Если хотя бы одно из этих условий
истинно, то Робот находится рядом с одной из вертикальных
границ поля. Если оба условия одновременно ложны, то Ро
бот не находится у вертикальной стены.
Посмотри: чтобы объяснить, какие значения истинности
должны иметь два условия, нам пришлось написать целый абзац.
Чтобы иметь возможность это записать кратко, в информатике
и в математике принято использовать слова «и», «или», «не».
При этом условие, которое получается из простых условий с по
мощью слов «и», «или», «не», называется составным условием.
Слово «и». В русском языке сложное предложение, обра
зованное с помощью союза «и» (или с помощью близкого по
значению союза «а»), истинно в том и только в том случае,
когда истинны оба составляющие его простые предложения
106
(утверждения). Например, предложение «Лондон — столица
Англии, а Париж — столица Франции» истинно, а каждое из
следующих предложений ложно:
«Лондон — столица Англии, а Париж — столица Норвегии»,
«Лондон — столица Швеции, а Париж — столица Франции»,
«Лондон — столица Швеции, а Париж — столица Норвегии».
В информатике и в математике значение истинности утверж
дения, состоящего из двух утверждений (условий), связанных
словом «и», определяется точно так же, как в русском языке.
Это можно записать с помощью такой таблицы истинности
(здесь А, В — имена двух простых утверждений):
А
В
А и В
И
И
И
И
Л
Л
Л
И
Л
Л
л
Л
Из таблицы видно: если оба условия А и В истинны, то истин
но и составное условие «А и В». Если хотя бы одно из простых
условий ложно (или ложны оба), то составное условие ложно.
Таким образом, если Робот находится в левом верхнем углу
поля, то он на составное условие
слева стена и сверху стена
ответит «да». Если Робот находится в другой клетке поля без
внутренних стен, то Робот ответит «нет», так как либо сверху,
либо слева от него стены не будет.
Слово «или». В русском языке союз «или» имеет несколько
разных значений. В математике используется только одно значе
ние — такое, как, например, в предложении «Здесь близко река
или озеро», иначе «Здесь близко река или здесь близко озеро».
Это предложение образовано из двух простых предложений с по
мощью союза «или». При этом говорящий не знает точно, истин
но ли каждое из простых предложений, но утверждает, что хотя
бы одно из них истинно, а может быть, и оба. Это предложение
107
будет истинным, если близко есть только река, но нет озера, или
реки нет, но озеро есть, или есть и озеро, и река. Ложным это
предложение будет, только если близко нет ни реки, ни озера.
Это можно записать с помощью такой таблицы истинности:
А
В
А или В
И
и
л
и
л
И
И
Л
Л
И
И
Л
Таким образом, если Робот находится около какой-нибудь
из вертикальных границ поля, то он на составное условие
слева стена или справа стена
ответит «да». Если Робот находится в другой клетке поля
без внутренних стен, то Робот ответит «нет», так как ни спра
ва, ни слева от него стены не будет.
Слово «не». В русском языке частица «не» имеет несколько
значений. Но если в предложение добавить частицу «не» перед
сказуемым, то в новом предложении будет отрицаться то, что
утверждалось в старом. Например: «Он не ездил вчера в город»,
«Кит — это не рыба». В таком случае полученное предложение
называется отрицанием исходного.
В информатике и в математике слово
«не» используется именно в этом значе
А
не А
нии — при приписывании «не» к утверж
дению новое утверждение получает про
И
Л
тивоположное значение истинности: если
Л
И
утверждение А истинно, то утверждение
не А ложно, и наоборот. Это можно запи
сать с помощью такой таблицы истинности:
В школьном алгоритмическом языке отрицание условия
тоже используется. При этом полученное условие, например не
сверху стена, мы тоже будем называть составным. Составное
условие не сверху стена имеет противоположное значение ис
тинности по сравнению с простым условием сверху стена.
108
Определи истинность каждого составного
условия в таблице для каждой из отме
ченных клеток поля. Заполни такую таб
лицу в тетради — напиши в каждой клетке
букву И или Л.
Составное условие
А
В
С
D
Е
F
G
Н
сверху свободно
или снизу свободно
слева свободно
или сверху стена
справа стена
и клетка закрашена
клетка чистая
и снизу свободно
не слева стена
не снизу свободно
172
Для каждого составного условия с частицей «не» напиши про
стое условие с таким же значением истинности — построй
и заполни таблицу в тетради.
№
Составное условие
1
не клетка закрашена
2
не справа свободно
3
не снизу стена
4
не слева стена
5
не сверху свободно
6
не справа стена
7
не клетка чистая
Простое условие
109
173
Нарисуй такое же поле в те
тради, напиши в каждой клетке
номер составного условия, ко
торое истинно для этой клетки.
При этом, конечно, в клетке мо
жет стоять несколько номеров.
№
Составное условие
1
клетка закрашена или сверху свободно
2
снизу свободно и слева свободно
3
клетка чистая и слева стена
4
не клетка закрашена
5
не справа свободно
174
110
Имя
Состав-^^^^клетки
ное условие
А
В
с
D
Е
F
G
Н
клетка закрашена
или сверху стена
И
и
и
И
Л
Л
Л
Л
снизу свободно или
слева свободно
И
л
л
И
и
л
Л
И
справа стена
и снизу стена
Л
л
и
И
л
л
И
И
175
Нарисуй состояние Робота после выполнения алгоритма бег
с препятствиями из данного начального состояния.
^
алг бег с препятствиями
дано I
надо I
нач
нц 22 раз
если слева свободно и клетка чистая
то закрасить
влево
иначе вверх
влево
вниз
все
кц
кон
176
177
Найди все возможные числа, в которые может попасть Кузне
чик с системой команд вперёд 3, назад 2, после выполне
ния им не больше 15 команд из начального положения «100».
Вот грузинские буквы. Найди три одинаковые буквы, напи
ши такую букву в тетради. Найди букву, которая встречается
здесь ровно один раз, напиши эту букву в тетради.
111
178
Допиши алгоритм бег с препятствиями 2 — напиши со
ставное условие с союзом «и» так, чтобы при выполнении это
го алгоритма из данного начального состояния не возникло
отказа. Нарисуй состояние Робота после выполнения этого
алгоритма из данного начального состояния.
алг бег с препятствиями 2
дано |
надо I
нач
нц 22 раза
если
и
то вверх
влево
вниз
иначе вниз
влево
вверх
все
кц
кон
Нарисуй состояние Робота после выполнения алгоритма вы
ход из коридора из каждого из двух данных начальных со
стояний. Построй таблицу по образцу из задачи 108 — в каж
дую клетку наклей заготовку поля, раскрась клетки, нарисуй
положение Робота.
Начальное состояние 1:
Начальное состояние 2:
^ь
^
112
алг выход из коридора
дано I
надо I
нач
нц 7 раз
если снизу стена и сверху стена
то вправо
закрасить
все
кц
если снизу свободно
то нц 9 раз
если снизу свободно
то вниз
закрасить
иначе влево
закрасить
все
кц
иначе нц 9 раз
если сверху свободно
то вверх
закрасить
иначе вправо
закрасить
все
кц
все
кон
180
Робот выполнил алгоритм выход из коридора из задачи
179 на поле 7x7 клеток. Нарисуй поле и расставь в нём вну
тренние стенки так, чтобы в результате выполнения Роботом
этого алгоритма на твоём поле Робот, начав из нижнего ле
вого угла, оказался в верхнем правом углу поля.
181
Робот находится внутри прямого коридора шириной в 1 клет
ку, открытого с двух концов, неизвестной длины, идущего
в неизвестном направлении. В коридоре есть боковые про
ходы, ведущие в тупики, при этом нет ни одной клетки, из
которой есть сразу два боковых выхода. Составь алгоритм,
выводящий Робота из этого коридора.
113
Биоинформатика.
Белки и ДНК. Почему дети
похожи но родителей?
С древних времён люди замечали, что у тигров рождают
ся тигрята, у птиц — птенцы, у людей — дети. Мало того, дети
обычно внешне похожи на родителей — имеют тот же цвет
глаз, цвет волос или форму носа. Новорождённый младенец
часто не похож ни на мать, ни на отца, но со временем он при
обретает черты внешнего сходства с матерью и отцом. Получа
ется, что любой организм уже при рождении (а на самом деле
ещё до рождения) «знает», какие у него во взрослом состоянии
будут глаза, рост или голос. Значит, вся эта информация уже
заложена с рождения, она где-то хранится, а по мере роста
организм считывает эту информацию и приобретает те черты,
которые ему предписаны наследственной программой.
Где же и как хранится наследственная информация? Как ор
ганизм считывает её и понимает? Как он использует эту инфор
мацию по мере развития и роста? Этим вопросам много веков.
Но ответы учёные стали находить только в последние 50 лет.
Всё в мире состоит из отдельных частей — и предметы, и жи
вые организмы. В свою очередь, эти части сами состоят из частей
и т. д. Некоторые более крупные части мы видим, а есть такие
Почему дети похожи на родителей?
114
маленькие, которые наш глаз не способен различить (они в мил
лионы раз тоньше человеческого волоса). Мы видим, например,
что дом сложен из кирпичей, но мы не можем различить, из ка
ких частичек состоит вода в стакане. И в воде, и в кирпичах,
из которых построен дом, и в клетках тела человека можно вы
делить мельчайшие частицы, которые называются молекулами.
Всё вокруг нас — и живое, и неживое — построено из молекул.
В разных веществах молекулы различны. Они очень малы, их
невозможно увидеть без специальных приборов. К счастью, та
кие приборы существуют — они помогают изучать молекулы.
Среди молекул любого живого организма на нашей пла
нете основную часть составляют молекулы особых ве
ществ — белков.
Различных белков, т. е. различных видов молекул белков,
очень много — несколько миллионов. Например, только в ор
ганизме человека встречается около 30 000 различных белков.
Но при этом молекулы всех белков устроены похожим образом.
О Молекула любого белка — это цепочка (последователь
ность), состоящая из сотен, а иногда и тысяч звеньев. При
этом во всех известных молекулах белков встречается
только 20 видов звеньев! (Можно сказать, что книга жиз
ни написана в 20-буквенном алфавите.)
Звенья белковых цепей называют аминокислотными
остатками. Каждый аминокислотный остаток имеет своё на
звание и обозначение (одной буквой латинского алфавита), по
этому белки часто описывают словами (последовательностями
Компьютерная
модель молекулы
белка. Радужная расцветка позволя
ет проследить ход звеньев цепочки.
Молекула на рисунке увеличена при
мерно в миллиард раз
115
букв) в 20-буквенном алфавите (см. таблицу на форзаце в конце
учебника).
Именно набором белков один организм отличается от другого.
Наборы белков у двух людей (у двух кошек, у двух берёз) очень
похожи, только мелкие различия определяют, например, разный
цвет глаз у разных людей или разную расцветку шерсти двух ко
шек. Наборы белков у организмов разных видов разные, но чем
более родственны эти виды, тем более похожи наборы белков. На
пример, белки человека и шимпанзе совпадают на 99 % (т. е. раз
личается только одно звено из 100). А у человека и мыши степень
сходства около 80 % (различаются 20 звеньев из 100).
Где же хранится наследственная информация?
О
За хранение и передачу наследственной информации в жи
вых организмах отвечают специальные молекулы — моле
кулы ДНК.
ДНК — это сокращение, полное название — дезоксирибо
нуклеиновая кислота. Молекулы ДНК во всех клетках одно
го живого организма одинаковы. Но при этом молекулы ДНК
разных организмов разные: у каждого человека свои молекулы
ДНК, у каждой мышки свои.
Все молекулы ДНК, как и молекулы белков, — это цепоч
ки, но звенья в молекулах ДНК отличаются от звеньев белков.
О
Звенья ДНК называются нуклеотидами. В молекулах ДНК
встречается всего 4 вида нуклеотидов.
Молекулы ДНК в клетках живых организмов гораздо длин
нее молекул белков. Даже самые короткие молекулы ДНК (ДНК
вирусов) содержат сотни тысяч звеньев (нуклеотидов). А ДНК че
ловека содержит около трёх миллиардов нуклеотидов. То есть мо
лекула ДНК — это целая книга, написанная в 4-буквенном алфа
вите. Нуклеотиды обозначаются латинскими буквами А, С, G и Т.
О
Молекулы ДНК каждого живого организма полностью
определяют, какие белки будут в этом организме.
Но как именно это происходит? Иными словами, как в ДНК
закодированы (т. е. зашифрованы) белки? На этот вопрос мы
ответим позже. А пока займёмся просто шифрованием.
116
Шифрование
С древних времён люди использовали шифрование для се
кретной передачи и хранения информации. Шифрование вы
глядит как увлекательная игра, но преследует серьёзные цели.
Шифры используются в военных целях, для передачи секрет
ных сообщений, для хранения тайного знания и во многих дру
гих случаях.
Первые зашифрованные сообщения использовались ещё
в Древнем Египте. Способ шифрования тогда был очень прост,
сейчас он называется «шифрование простой подстановкой»:
каждый иероглиф исходного сообщения заменялся в зашиф
рованном сообщении другим. При этом одинаковые иерогли
фы заменялись одинаковыми, а разные — разными.
Сегодня существует много способов шифрования и шифров.
Мы будем пользоваться лишь одним способом, который постро
ен по следующим правилам:
1. Каждая русская буква, а также пробел или знак препи
нания заменяется последовательностью латинских букв
длины 3. Такая последовательность называется кодом.
При этом используются только четыре латинские бук
вы — А, С, G, Т.
2. Каждый код всегда заменяет (кодирует) одну и ту
же букву или знак. При этом одна буква или знак
необязательно всегда заменяется одним и тем же кодом.
3. При замене букв и знаков кодами порядок букв и зна
ков не меняется.
О
Замена каждой буквы её кодом называется шифрованием.
Обратная замена каждого кода на соответствующую ему
букву называется расшифровкой.
Для удобства шифрования и расшифровки строят шифро
вальную таблицу, в которой указан код (или все коды, если
их несколько) для каждой буквы, для пробела и знаков пре
пинания. Незаполненная часть такой таблицы помещена ниже.
117
Буква/знак
Код
А
Б
В
Г
д
Е
Ё
О
Полный
шифр — это
заполненная
шифровальная
таб
лица, указывающая соответствие каждой буквы или знака
и каждого кода.
Вот примеры шифровок:
Код буквы Я — CAT.
Шифровка слова ТЫ — CCCCGG.
Зашифруем слово ОНИ — получим шифровку ACTAGCTAA.
Закодируем слово КОМПЬЮТЕР — получим шифровку
AGGACTACGATCCTTCGACCC AGAAGT.
После раскодирования шифровки GAAAAACTCTAACCGAGTACTAAGAAAAGCAGCCGGACC получаем слово ЗАШИФРО
ВАННЫЙ.
Обратите внимание, что знак переноса нам помогает удобно
расположить на странице слова и их шифровки. При этом знак
переноса при шифровании и расшифровке не учитывается.
Полный шифр вы построите, решая задачи.
182
Вырежи из вкладыша тетради проектов заготовку шифро
вальной таблицы и вложи в тетрадь (лучше прикрепить её
скрепкой, чтобы потом не выпала). Используя коды из при
меров на этой странице выше, заполни в своей таблице все
строки, которые сможешь.
Проверь: в таблице должны быть коды для 19 букв.
118
183
Зашифруй те слова множества F, для шифрования которых
в твоей таблице имеются все необходимые коды. Запиши
шифровки в тетрадь.
ШАР
БАНАН
ОНА
ОН
ШАРФ
ВЬЮНОК
КАРТОШКА
ДЕДУШКА
Сколько различных последовательностей
длины 3 можно составить из букв множества
М (конечно, буквы могут повторяться)?
Построй дерево перебора вариантов. Можно
ли было использовать для шифрования букв
русского алфавита не тройки, а пары, со
ставленные из букв множества М? Поясни свой ответ.
При расшифровке удобно пользоваться обратной шифро
вальной таблицей — таблицей расшифровки. В такой таблице
в левой колонке выписаны все возможные коды (в словарном
порядке), а в правой — буквы или знаки, которые этим кодам
соответствуют. В заготовке таблицы расшифровки заполни
все строки, которые сможешь.
185
Раскодируй шифровки: перепиши их в тетрадь и напиши ря
дом с каждой шифровкой зашифрованное в ней слово.
AGGACTGAAAAA
AGGACTGAACGG
ATCAGAAGTAAGAAACAT
AAAAGCCCCAGTAAAAGGCCC
186
Нарисуй, как разрезать четырёх
угольник на части, чтобы из этих
частей можно было собрать прямо
угольник на сетке. Нарисуй этот
прямоугольник и покажи штриховы
ми линиями, из каких частей он со
ставлен.
119
187
Множество В — множество шифровок всех слов из мно
жества А. Запиши для каждого слова его шифровку и заполни
пустые клетки шифровальной таблицы и таблицы расшифровки.
Проверь себя — в каждой таблице теперь должны быть коды
для всех русских букв.
УХ эх
ЧАС
УЖ
БАЦ
БАС
ЛУГА
ДУГА
ЛУЖА
ОБЩИХ
ОБЪЁМ
188
CAGCCT
CCACCT
CCACAA
AACAAACAC
AACAAAATG
CGCAAAATG
ACACCAAATAAA
ATTCCACAAAAA
ATTCCAAATAAA
ACTAACGCCTAACCT
ACTAACTCCATAACG
Дано зашифрованное предложение. Слова в этой шифровке
разделены тройкой символов, кодирующей пробел. Расшиф
руй и запиши в тетрадь предложение. Дополни таблицы шиф
ровки и расшифровки кодом пробела.
ACGAAAACGAAACTAACGCGG
ATTAAACTAAGTAAAACGCCA
189
120
На квадратном участке расположе
ны три дома, а в ограде сделаны
три калитки. Проложи дорожку от
каждого дома к калитке с тем же
номером так, чтобы дорожки не пе
ресекались. Нарисуй схему участка
и дорожек в тетради. Дома
перерисовывать не надо — доста
точно поставить номера.
190
При помощи таблицы расшифровки раскодируй следующие
шифровки, запиши получившиеся слова.
Найди выигрышную стратегию для игры Двадцать пять.
Правила игры Двадцать пять
Начальная позиция. Число О.
Возможные ходы. На каждом ходу игрок при
бавляет к имеющемуся числу 1, 2, 3 или 4.
Как определить победителя. Игра заканчива
ется, если позиция оказывается равной 25. Вы
игрывает тот, кто добавил последнее число.
121
Биоинформатика.
Как кодируются белки
Ты уже знаешь, что в состав
любого живого организма входят
молекулы белков. Именно набор
белков определяет, например,
почему у одного человека глаза
карие, а у другого — голубые.
Каждая молекула белка — это
цепочка
(последовательность).
Звенья этой цепочки называют
ся аминокислотными остатка
ми или просто остатками. Все
белки каждого живого существа
закодированы в особой моле
куле — молекуле ДНК. Моле
кула ДНК — это тоже цепочка,
состоящая из звеньев другого
вида — нуклеотидов. Таким об
Раскрашенная модель молеку
разом, в одной последовательно
лы ДНК. Молекула ДНК очень
сти (молекуле ДНК) закодиро
длинная — здесь представле
ваны другие последовательности
на только небольшая её часть.
На модели видно, что молекула
(молекулы белков). А как имен
ДНК состоит из двух цепочек
но, каким шифром в ДНК зако
(одна раскрашена жёлтым, а
дированы белки?
другая — красным). В этих це
Оказывается, это проис
почках нуклеотиды расположе
ходит примерно так же, как
ны друг против друга и связаны
в задачах на шифрование, ко
особыми химическими связями
торые ты решал.
(они показаны голубым)
Аминокислотные остатки
(звенья молекул белка) могут
быть только двадцати видов. Это значит, что молекула белка
похожа на длинное слово, написанное в 20-буквенном алфавите.
Каждый из двадцати возможных остатков имеет своё название
и обозначается одной латинской буквой (см. таблицу на форзаце
в конце учебника).
122
Все молекулы ДНК построены только из четырёх видов ну
клеотидов. Вот их русские и английские названия и буквы, кото
рыми они обозначаются:
аденин (Adenine, А),
цитозин (Cytosine, С),
гуанин (Guanine, G),
тимин (Thymine, Т).
Молекулу ДНК можно сравнить с очень длинным словом,
написанным в 4-буквенном алфавите.
Не вся молекула ДНК кодирует белки, а только некоторые
её участки, которые называются генами. Молекула ДНК про
стейших организмов (вирусов, бактерий) почти вся состоит из
генов, а в молекуле ДНК человека гены составляют только око
ло 3 % всей длины. Зачем нужны остальные 97 % ДНК челове
ка, науке пока известно не очень хорошо.
В гене (как и в наших шифровках) каждый остаток белка ко
дируется тройкой нуклеотидов. Такие тройки биологи называют
кодонами. Например, тройка AAG (аденин — аденин — гуанин)
кодирует остаток лизин. При этом один и тот же остаток может
кодироваться разными тройками нуклеотидов. Специальные трой
ки кодируют начало и конец гена. В таблице на форзаце в конце
учебника вы найдёте полный список остатков и всех шифрующих
их кодонов. Эта таблица называется таблицей генетического кода.
О том, что белки могут кодироваться тройками нуклеоти
дов, догадался в середине XX века выдающийся физик и биолог
Георгий Гамов. Позже с помощью экспериментов учёные под
твердили эту догадку и определили, какой остаток кодируется
каждым кодоном. Замечательно, что генетический код един
для всех известных живых организмов!
195
В этой шифровке закодировано слово, но по ошибке то ли
одну букву пропустили, то ли вставили лишнюю. Не расшиф
ровывая слово, определи, какую именно ошибку допустили
при шифровании: пропустили букву или вставили лишнюю.
Объясни свой ответ.
123
196
Одно из слов множества Д зашифровали, но при этом допу
стили ошибки — одну букву в шифровке пропустили и встави
ли одну лишнюю (необязательно в то же место). Определи,
какое слово пытались зашифровать, запиши в тетрадь это
слово и его правильную шифровку.
С С А А ТА A G G
197
"ТОК
ШОК
ТАК
ШИК
ТИК
Разведчик зашифровал два слова — важный пароль и ответ на
него. В начале и в конце, а также между словами разведчик
вставил лишние тройки латинских букв, которые не входят
в послание, — они служат для того, чтобы замаскировать эти
важные слова в тексте (на случай перехвата послания про
тивником). При этом начало и конец каждой части послания
разведчик закодировал специальными тройками латинских
букв, чтобы в штабе послание всё же смогли расшифровать.
Этими тройками разведчик всегда кодирует начало и конец
предложения. Расшифруй и запиши в тетрадь пароль и ответ
на него. Дополни таблицы шифровки и расшифровки тройка
ми, кодирующими начало и конец предложения.
Реши задачу.
Известно, что К. М. Петров, В. Д. Петров, П. Б. Петров, Н. В. Пе
тров, М. С. Петров, И. В. Петров, А. К. Петров, Д. М. Петров,
Р. Б. Петров, Г. Д. Петров, Б. К. Петров — представители одного
рода, причём один из них — основатель рода, остальные — его
сыновья, внуки и правнуки. Других сыновей, внуков и правну
ков у основателя рода не было. Построй дерево родства Пе
тровых, если известно, что у каждого отца было по два сына,
внуков у основателя рода — четыре, а у его сыновей — по два.
199
Дано три шифровки одного слова с ошибками. В одной про
пустили одну букву, в другой вставили лишнюю, в третьей
произошло и то и другое. Запиши слово и его правильную
шифровку.
ACAGTCCCAACA
ATCAGGTCCAACA
ATCAGTCAACA
200
Наиболее важные послания разведчик шифрует более слож
ным шифром, чем обычно. Он использует те же коды для тех
же букв, что и раньше, но использует также и новые, допол
нительные коды (тоже тройки букв из того же 4-буквенного
алфавита). Таким образом, одну и ту же русскую букву он
может шифровать разными кодами (при этом один и тот же
код, как обычно, всегда кодирует одну и ту же букву). Мно
жество W состоит из разных шифровок двух слов: СМЕШНО
и ГЛАДИТ. Выясни, какая шифровка к какому слову отно
сится, дополни новыми кодами букв свою шифровальную
таблицу (в ней станет 52 кода) и таблицу расшифровки.
GGAGTTGAGGGCGTGTGT
TCTGCAGGTTCAGTATTA
AATATTGACGGCGTGCCC
TGCTTTGCTTCAAGCTTC
GGAGTTGATGGCTACTGT у
201
202
w
Молекула ДНК человека состоит из трёх миллиардов нуклео
тидов. При этом гены составляют только 3 % всей длины по
следовательности. Сколько нуклеотидов содержится во всех
генах человека?
На поле Робота стен нет. Робот находится в левом верхнем
углу прямоугольника из закрашенных клеток. Составь алго
ритм, переводящий Робота в правый нижний угол прямо
угольника.
125
203
Разведчик зашифровал два предложения и вставил лишние
тройки латинских букв, которые не входят в послание, в на
чале, в конце и между предложениями. Расшифруй послание.
ATG CCA GCC АСА GAC АСА
ААС AGCACCCACACCACGCCG
ATG САС CCA GAC GCC САА САС
кодирует такую последовательность остатков:
126
Пользуясь таблицами на форзаце в конце учебника, найди та
кой остаток, который в этом примере кодируется тремя раз
ными кодонами. Выпиши его название и его кодоны.
206
Дано множество R слов и множество Q шифровок этих слов. На
пиши рядом с каждым словом его шифровку. Дополни новыми
кодами букв шифровальную таблицу и таблицу расшифровки
(должен быть 61 код).
Реши задачу.
Каждый из четырёх гномов — Ваня,
Даня, Женя и Саня —либо всег
да говорит правду, либо всегда
врёт. Мы услышали такие отрыв
ки разговора: Ваня — Дане: «Ты
врун». Даня — Жене: «Ты врун!»
Женя — Сане: «Оба они вруны». По
том Женя подумал и добавил: «Да
и ты тоже врун». Кто из этих четы
рёх гномов всегда говорит правду?
Реши задачу.
При приготовлении пиццы выпекается большой хлебный корж
и посыпается тёртым сыром. К сыру добавляются разные
продукты, обеспечивающие тот или иной вкус. В распоряже
нии Марчелло имеются сладкий перец, репчатый лук, мари
нованные грибы, свежие помидоры, маринованная морковь
и анчоусы (мелкая рыбка — хамса специального посола). По
мнению Марчелло, имея один или несколько из этих продук
тов (в любых сочетаниях), а также корж и сыр, можно при
готовить пиццу. Сколько типов пиццы можно приготовить?
127
Автомат-сортировщик
Теперь мы познакомимся с методом половинного деления,
анализируя игру Угадай число.
Но сначала поговорим о сортировках и роботах-сортиров
щиках.
Представим себе Автомат, который умеет сортировать эле
менты множеств. Будем называть его Автомат-сортировщик.
Наш Автомат-сортировщик на каждом этапе сортировки раз
деляет каждое множество на две непустые части. На первом
этапе Автомат разделяет исходное множество на две части,
на втором разделяет каждую из двух полученных частей ещё
на две и так далее, пока в каждой части не останется только
один элемент. Если Автомату попадается множество, состоящее
только из одного элемента, то он с таким множеством ничего
не делает — оставляет его как есть. Для удобства назовём такой
Автомат-сортировщик Простым автоматом.
Пусть дано множество А чисел от 11 до 20.
А__________________
15
17 19
12 14 16
18 20
11
13
Дадим Простому автомату задание рассортировать это
множество. На следующей странице приведены два примера
деревьев такой сортировки.
В сортировке с деревом К было 5 этапов, в сортировке с де
ревом Л — 8 этапов. Как видите, сортировка Простым автома
том одного и того же множества может быть разной — множе
ство А можно рассортировать и в 5 этапов, и в 8 этапов (можно
даже в 9 этапов!).
Давайте теперь усовершенствуем Простой автомат. Пусть
теперь Автомат-сортировщик не просто разделяет множество
на две части, а всегда разделяет его примерно пополам. Если
в исходном множестве было чётное число элементов, то в мно
жествах, полученных после разделения, элементов будет по
ровну, а если в исходном множестве было нечётное число эле
ментов, то в полученных множествах число элементов будет
128
“1“ к
11
12
13
14
15
16
17
12 13 14 16 17 19 20
(l2 13 14 16 17)
(13 14 1б)
12
17
(l9 20)
Ql9
18
19 20
Я
11
15
15
QT П
11
20
18
^g^vv TV
л
11
12
13
14 15
17 18
19 20 )
16
17
18 20
14 15
17
18 20 )
16
14 15
12
12
14 17 18 20 J
( 14 17 18 20 ]
129
различаться на 1. Такой усовершенствованный Автомат-сорти
ровщик мы назовём Половинным разделителем.
Вот пример дерева сортировки Половинным разделителем:
Т
О
При всех способах сортировки одного и того же множества
Половинным разделителем число элементов дерева сорти
ровки будет одним и тем же. Никакой Автомат-сортиров
щик не сможет рассортировать элементы множества
за меньшее число этапов, чем Половинный разделитель.
209
130
Нарисуй какое-нибудь дерево сортировки Половинным раз
делителем множества всех гласных букв русского алфавита.
Сколько уровней в твоём дереве? Сколько этапов в сорти
ровке по этому дереву?
210
Вот описание игры Угадай число.
В игре Угадай число участвуют двое игроков:
Водящий и Угадывающий. Водящий загадывает
любое число, обычно от 1 и до заранее определён
ного числа. Угадывающий должен отгадать это
число, задавая Водящему вопросы, на которые
можно ответить только «Да» или «Нет».
Вопросы можно задавать самые разные, на
пример, не хочется ли Водящему съесть яблоко.
Можно просто перебирать числа: «Это число 1? Это
число 2? и т. д.» Но так игра затянется надолго.
Поэтому нужно установить, за какое число вопро
сов отгадывается число.
Сыграйте с соседом по парте че
тыре партии в игру Угадай число
с такими правилами: разрешает
ся загадывать число от 1 до 16,
разрешённое количество вопро
сов — четыре. Если за четыре
или меньше вопросов Угады
вающий называет число, игра
заканчивается и выиграл Угады
вающий. Если после четвёртого
вопроса число не отгадано, то
партия закончилась выигрышем
Водящего. Заполни таблицу со
ревнования.
СП
Игроки
К
S
:Ф
О
Партии
ф
о
О
О
К
S
1-я партия
2-я партия
3-я партия
4-я партия
211
Реши задачу.
В магазин привезли 223 л молока
в бидонах по Юл и по 17л. Сколь
ко было бидонов?
212
Найди площадь
угольника Ш.
данного
много
131
Метод половинного
деления
Подумаем, как играть в игру Угадай число (правила игры
см. в задаче 210), чтобы наверняка угадать число за заданное
число вопросов. Так как мы хотим угадать число наверняка, то
нам придётся спланировать игру для любого задуманного чис
ла, т. е. придумать все возможные вопросы, которые мы зада
дим Водящему в зависимости от его ответов. Сложность в том,
что заранее составить список вопросов здесь невозможно — ведь
каждый следующий вопрос зависит от того, как ответил Водя
щий на предыдущий вопрос— «Да» или «Нет». Поэтому при
дётся строить дерево вопросов. После каждого вопроса должны
следовать два: один вопрос задаётся в случае ответа «Да», дру
гой — в случае ответа «Нет».
Рассмотри пример такого дерева вопросов для игры Угадай
число от 1 до 8.
П
Обрати внимание, что ответ на любой правильно поставлен
ный вопрос разделяет исходное множество чисел на два мно
жества: одно, для чисел которого на данный вопрос правильно
ответить «Да», другое, для чисел которого на данный вопрос
правильно ответить «Нет». Значит, по каждому дереву вопросов
можно построить дерево сортировки исходного множества чисел
Простым автоматом.
132
Вот дерево сортировки Простым автоматом множества
чисел от 1 до 8, построенное по дереву вопросов П:
Итак, построив дерево вопросов и соответствующее ему
дерево сортировки Простым автоматом, можно наверня
ка отгадать число из заданного множества за заданное число
вопросов. При этом число вопросов будет наименьшим, если
дерево вопросов (и дерево сортировки) будет наименьшей вы
соты, а наименьшая высота получается при сортировке По
ловинным разделителем. Значит, вопросы Угадывающего
должны быть такими, чтобы ответы на них разделяли каждое
множество примерно пополам — так, как разделяет Половин
ный разделитель. Используя такие вопросы, Угадывающий
всегда отгадает загаданное число, задав наименьшее количе
ство вопросов.
Такой метод поиска элемента в заданном множестве назы
вается методом половинного деления.
Используя метод половинного деления, построй дерево Ш
вопросов в игре Угадай число от 1 до 16. Построй дерево Б
сортировки Половинным разделителем множества чисел от 1
до 16, соответствующее дереву Ш.
133
Сколько этапов в твоей сортировке? За сколько вопросов
можно наверняка отгадать число от 1 до 16?
Пользуясь построенным деревом, сыграй с соседом две пар
тии в игру Угадай число от 1 до 16.
Определи, за сколько вопросов можно наверняка отгадать
число в игре Угадай число от 1 до 25. Чтобы ответить на во
прос, построй дерево сортировки Половинным разделителем
множества чисел от 1 до 25.
Пользуясь построенным деревом, сыграй с соседом две пар
тии в игру Угадай число от 1 до 25 и проверь свои ответы.
Правила игры Угадай букву очень похожи на правила игры
Угадай число. В игре Угадай букву Водящий загадывает бук
ву русского алфавита.
Определи, за сколько вопросов можно наверняка отгадать
букву в игре Угадай букву. Чтобы ответить на вопрос, построй
дерево сортировки Половинным разделителем.
Пользуясь построенным деревом, сыграй с соседом две пар
тии в игру Угадай букву и проверь свои ответы.
216
Сколько существует трёхзначных чисел, в запись которых вхо
дит ровно одна цифра 5?
217
Реши логическую задачу.
Жители двух соседних городов — города Рыцарей и города Лже
цов — раз в год приезжают на ярмарку в город Хитрецов. Из
вестно, что рыцари всегда говорят правду, лжецы всегда лгут,
а хитрецы говорят правду через раз, т. е. из двух сказанных ими
подряд предложений одно — правда, а другое — ложь. На яр
марке встретились трое из разных
городов и затеяли спор:
Первый. Один из нас рыцарь.
Второй. Да уж ты-то точно лжец.
Третий. Оба вы лжецы. Хотя
я тоже не рыцарь.
Определи, кто такие Первый, Вто
рой и Третий, если точно извест
но, что все они живут в разных
городах.
134
Биоинформатика.
Как изучают белки
Ты уже знаешь, генетический
код в основном устроен так же,
как и код в наших задачах: есть
текст в 4-буквенном алфавите (А,
С, G, Т); тройки букв (тройки ну
клеотидов молекулы ДНК) коди
руют остатки — звенья молекул
белков.
Участки ДНК, которые коди
руют белки (они называются гёнами), ограничены специальными
тройками. Первая тройка в лю
бом гене — ATG (она называется
старт-кодоном). Кодон ATG — это
кодон остатка метионина (такой
остаток обозначается буквой М),
поэтому этот кодон встречается
и внутри генов. Последняя трой
На этой модели видно,
ка в каждом гене — это TAA, TAG
что аденин (А) всегда свя
или TGA. Эти кодоны называются
зан с тимином (Т), а ци
стоп-кодонами, они играют такую
тозин (С) — с гуанином
же роль, как точки в предложе
(G). Две цепочки молеку
нии. Стоп-кодоны не кодируют ни
лы ДНК закручены в спи
какого остатка, внутри генов они
раль — наподобие винто
не встречаются.
вой лестницы. Эту модель
Ты уже знаком с таблицей
(она называется «двойная
генетического кода. В ней для
спираль»)
придумали
в
каждого остатка приведены его ко
50-х гг. XX в. Дж. Уотсон
доны, при этом один остаток, как
и Ф. Крик
правило, может кодироваться не
сколькими разными кодонами. На
форзаце в конце учебника приведена и обратная таблица: для
каждого кодона указан соответствующий остаток.
135
Мы описали основной способ кодирования белков. Бывают
и более сложные случаи: например, гены могут перекрываться,
т. е. получается как бы одна шифровка, наложенная на другую.
Такое явление встречается в ДНК вирусов. Похожие ситуации
вам встретятся в задачах на шифрование.
Современные технологии позволяют определять последова
тельность нуклеотидов в молекулах ДНК. Сегодня уже полно
стью расшифрованы ДНК человека, шимпанзе, мыши, сотен
других животных и растений и десятков тысяч бактерий. Теперь
учёным важно понять, для чего служат различные фрагменты
ДНК, и прежде всего выделить участки, кодирующие белки.
Иногда учёным приходится иметь дело с данными, в которых
есть ошибки, — в ходе эксперимента некоторые буквы могут по
теряться, а могут и ошибочно появиться новые буквы. Подобные
задачи на шифрование тебе уже встречались. При их решении
ты использовал то, что не все тройки допустимы. В реальном же
кодировании белков это не так — каждая тройка имеет значение.
Поэтому, чтобы выделять кодирующие участки, учёным-биоло
гам приходится использовать более сложные методы.
218
136
Иногда в одной шифровке разведчику удаётся передать два
сообщения, наложив «одно поверх другого». Для этого он
так составляет шифровку, чтобы сначала читалось первое
сообщение, а с некоторого места (например, со второй бук
вы шифровки) читалось второе сообщение. Вот пример та
кой шифровки, в которой содержатся с перекрытием 2 слова
из 4 букв. Расшифруй и запиши в тетрадь эти слова, рядом
с каждым словом запиши его шифровку.
219
Пользуясь шифровальной таблицей, напиши 6 разных шиф
ровок слова МОЩЬ. Сколько всего существует таких шифро
вок? Объясни свой ответ.
220
Пользуясь своей шифровальной таблицей, определи, сколь
кими способами можно зашифровать слово ЖАДНЫЙ. Запи
ши все различныешифровки этого слова.
221
На форзаце в конце учебника приведена обратная таблица
генетического кода — для каждого кодона указан соответ
ствующий остаток. Обрати внимание, что главную роль в опре
делении остатка, соответствующего кодону, играют первые
2 буквы кодона. В одних случаях третья буква может быть лю
бой (так, например, для пролина годится любой кодон, первые
2 буквы которого — СС). В других — третьи буквы А или G со
ответствуют одному остатку, а С или Т — другому. Например,
ААА и AAG кодируют лизин, а ААС и ААТ — аспарагин.
Из этих правил есть только два исключения. Найди их в та
блице генетического кода.
222
В одной из шифровок слова РЫСЬ вычеркнули 3 буквы (не
обязательно идущие подряд), и получилась одна из шифро
вок слова ПЕЛ. Найди и запиши такую шифровку слова РЫСЬ,
подчеркни в ней те буквы, которые вычеркнули, чтобы полу
чить шифровку слова ПЕЛ.
223
Пользуясь своей шифровальной таблицей, придумай и запи
ши слово, которое можно зашифровать более чем 10 спосо
бами. Запиши любые 5 из возможных шифровок этого слова.
224
Запиши предложение, содержащееся в следующей шифровке
(слова, как обычно, разделены тройкой латинских букв, коди
рующей пробел):
Сколько разных чисел можно получить, переставляя цифры
числа 9854?
137
Биоинформатика. Сравнение
белков
У живых организмов различаются наборы белков. Наборы
белков у двух людей (у двух слонов, двух бактерий) очень по
хожи, только мелкие различия определяют, например, различ
ную форму уха у разных людей или разный цвет хвоста у двух
кроликов.
Наборы белков у организмов разных видов разные, но чем
более родственны эти виды, тем более похожи наборы белков.
Например, сходство между белками человека и шимпанзе до
стигает 99 %.
Верно и обратное: если два вида организмов имеют похожие
наборы белков, то эти виды являются родственными, т. е. про
исходят от какого-то одного вида древних животных. Пользуясь
методами сравнения белков, учёные восстанавливают родствен
ные связи и происхождение
различных видов животных
и растений. Например, недав
но стало известно, что, судя
по некоторым белкам, ин
дийские слоны более близки
к вымершим мамонтам, чем
к современным африканским
слонам.
Как
учёные
проводят
сравнение белков? Как вы те
перь знаете, белки — это по
следовательности
аминокис
лотных остатков, их можно
представить в виде длинных
слов — последовательностей
букв в 20-буквенном алфавите.
Поэтому задачу можно сфор
Индийские слоны
мулировать так: какие два
ближе к мамонтам,
слова считаются близкими, по
чем к африканским слонам
хожими, а какие — далёкими?
138
Превращение слов
Вы наверняка играли в игру, в которой одно слово надо пре
вратить в другое, заменяя на каждом шагу только одну букву.
Примерно такой игрой мы сейчас займёмся.
В отличие от тех игр, которыми мы занимались раньше, в эту
игру можно играть одному. Цель игры — за наименьшее число
шагов превратить одно слово в другое, соблюдая такое правило:
Правило превращения слов
На каждом ходу можно выполнить одно из трёх действий:
— заменить одну букву на другую;
— вставить одну букву;
— удалить одну букву.
Конечно, по этим правилам одно слово можно превратить
в другое разными способами. Например, из слова СЛОН можно
сделать слово СОН за один ход, а можно и за 7 ходов. После
довательности таких превращений помещены снизу. Но цель
нашей игры — найти самое короткое превращение, поэтому мы
выбираем превращение R.
W
R
Давайте усложним игру — присвоим каж
дому ходу цену.
СЛОН слон
Ход
Цена
сон
\р
АЛОН
ААОН
Замена гласной на гласную
1
Замена согласной на согласную
2
АААН
Замена гласной на согласную или на
оборот
3
ААА
Замена Ъ или Ь на другую букву или на
оборот
4
Вставка или удаление одной буквы
5
САА
СОА
СОН
139
R
W
Вычислим стоимость каждого превра
щения: стоимость R — 5 баллов, стоимость
СЛОН
W — 19 баллов. Чтобы было проще под
|3
считывать баллы, можно записывать цену
СОН
АЛОН
ходов прямо на схеме превращения, как по
|3
казано справа (примерно так мы записывали
ААОН
вес рёбер на деревьях и графах).
Теперь можно сформулировать новую
АААН
цель игры: построить для данной пары слов
самое дешёвое превращение одного слова
в другое. Стоимость такого превращения
ААА
|3
можно назвать расстоянием между словами.
Учёные сравнивают слова-белки примерно
САА
так же: ищут для них «самую дешёвую» це
почку преобразований (при подходящих стои
СОА
мостях замен и удалений). Например, замена
|з
остатка на остаток с близкими химическими
СОН
свойствами стоит дешевле, чем его замена
на непохожий остаток (как в нашей таблице
дешевле заменить гласную на гласную, чем
гласную на согласную). Удаление и вставка остатков стоят доро
же, чем замены. Конечно, полная таблица «удалённости» разных
остатков устроена гораздо сложнее, чем наша.
Результаты сравнения белков биоинформатики обычно изо
бражают в виде специальной схемы — выравнивания. Вот, на
пример, выравнивание слов ПАПКА и ПАПАХА и соответству
ющая цепочка превращения:
Сейчас учёным известны сотни тысяч
ПАП-КА
последовательностей белков. Получив но
вый белок, учёные прежде всего стараются
ПАПАХА
найти известные белки, похожие на него.
Не стоит забывать, что биоинформатика
имеет дело с очень длинными словами, ра
ботать с которыми можно только с помощью
ПАПКА
I
компьютеров. Для сравнения белков исполь
ПАПАКА
зуются компьютерные программы, которые
I
для любых двух белков могут определить
ПАПАХА
их наилучшее (т. е. имеющее наименьшую
стоимость) выравнивание. Такие программы
|5
слон
н
|5
н
140
и базы данных, содержащие последовательности известных
белков, доступны всем через Интернет.
Выравнивание позволяет предположить, какая последова
тельность остатков была у общего предка двух видов живых су
ществ. Вот, например, выравнивание двух фрагментов белков:
один из них — белок человека, а другой — белок мартышки:
VLSPADKTNVKAAWGKVGAHAGEYGAEALERMFLS
VLSPADKSNVKAAWGKVGSHAGDYGAEALERMFLS
Значит, можно предположить, что наш общий предок имел
такую белковую последовательность:
VLSPADK + NVKAAWGKVG + HAG + YGAEALERMFLS
(плюсами помечены места, буквы в которых нам неизвестны:
Т или S, А или S, Е или D).
226
Построй какое-нибудь (необяза
тельно самое дешёвое) превра
щение слова ТАНКИСТ в сло
во ТУРИСТ Напиши последо
вательность своего превращения
и вычисли его стоимость.
G
Q
ОБЪЕКТ
ОБЪЕКТ
ОБЕКТ
ОБЛЕКТ
ОБЛ КТ
ОБЛИКТ
ОБЛИТ
ОБЛИК
I
I
I
227
228
Вот последовательности G и Q
превращений слова ОБЪЕКТ в
слово ОБЛИК. Вычисли стоимость
каждого превращения и укажи бо
лее дешёвое.
I
I
I
I
ОБЛИК
V
Построй какое-нибудь превращение (необязательно самое
дешёвое) слова ВРАЗБРОС в слово ВРАЗРЕЗ. Напиши по
следовательность этого превращения и вычисли его стои
мость.
141
Построй превращение слова КОНТАКТ
в слово КОМПЛЕКТ, которое стоит 10
баллов.
КОНТА-КТ
КОМПЛ ЕКТ
Чтобы построить превращение с задан
ной стоимостью, удобно сначала вы
ровнять заданные слова: расположить одно слово под другим
так, чтобы одинаковые буквы (конечно, если они есть) стояли
друг под другом. При необходимости можно раздвигать бук
вы, вставляя чёрточку.
Как именно нужно расположить остальные (неодинаковые)
пары букв, зависит от того, какова заданная стоимость. На
пример, указанное выравнивание предполагает замену Н
на М (2 балла), замену Т на П (2 балла), замену А на
Л (3 балла) и вставку Е (5 баллов) — всего 12 баллов. Это
не та стоимость, какая требуется в задаче. Значит, надо
попытаться поставить чёрточку в другом месте и снова
подсчитать баллы.
230
Нарисуй, как разрезать многоуголь
ник У, чтобы получились два одинако
вых многоугольника на сетке.
231
За какое наименьшее число вопросов
можно наверняка отгадать натуральное
число, меньшее 1000, если на вопросы
можно отвечать только «да» и «нет»?
232
Построй превращение слова СЪЕДОБНЫЙ в слово ОГРОМ
НЫЙ, которое стоит 15 баллов.
233
Построй превращение слова ПОЛЬСКИЙ в слово КОНСКИЙ,
которое стоит меньше 10 баллов.
234
142
Построй превращение слова ПОДОСИНОВИК в слово ПОДБЕ
РЁЗОВИК, которое стоит 11 баллов.
Подумай, существует ли более дешёвое превращение слова ПОД
ОСИНОВИК в слово ПОДБЕРЁЗОВИК. Объясни свой ответ.
Повторение
235
Построй все подмножества множества Л.
236
Запиши последовательность чисел длины 5, для которой
истинны следующие утверждения:
Первый член последовательности — число 3.
Второй член последовательности — число 7.
Каждый член последовательности, кроме первого и послед
него, равен среднему арифметическому предыдущего
и следующего членов.
237
Даны названия месяцев года на разных языках: армянском,
грузинском, современном греческом и еврейском (иврите).
Пользуясь другими задачами в этом учебнике, рассортируй
слова по языкам. Конечно, сами слова переписывать не надо,
достаточно записать номер слова.
2 SEJtTE^Pprjg
1 h Juti Jiu
з Ур
4 АярьХг|д
6 O^gnobo
8 ifmj[iu
9 Maptr|g
11 ^О^О^З^^ о
13 ФХ£рарг|д
5 uhljinhifphp
7 "I^PD^D
ю тип
12 hJutiQmp
14McA^°
143
238
Элементами дерева А являются буквы,
а все последовательности дерева А вы
писаны справа. Построй дерево А, если
известно, что следующие утверждения
истинны:
В дереве А всего
первого уровня.
ОДИН
ДЕРЕВО
ДРУГ
ДРОЗД
ДЕРЕВНЯ
ДРОВА
ДЕРЖИ
ДРОВНИ
ДЕРЖАВА
элемент
В дереве А всего 23 элемента.
239
Расположи все чётные двузначные чис
ла, которые делятся на 7, в порядке
убывания.
240
Выдели подмножество множества Д, для которого все следу
ющие утверждения истинны:
Все элементы этого подмножества — двузначные числа.
Каждое число из этого подмножества больше 62.
В этом подмножестве всего 5 элементов.
В этом подмножестве нет чётных чисел.
Каждое число в этом подмножестве делится на 3.
В этом подмножестве нет чисел, в записи которых есть
цифра 5.
85
94
73
97
66
90
72
9
57
84
144
81
92
89
24
111
88
83
87
69
51
67
75
68
95
117
65
77
27
Ю2
123
78
/о
63
71
93
241
Реши задачу.
Из девяти монет одна фальши
вая — более лёгкая. Как найти её
двумя взвешиваниями на чашеч
ных весах без гирь? А сколько по
требуется взвешиваний для поиска
одной монеты из двадцати семи?
242
Даны правила игры Ромашка.
Правила игры Ромашка
Начальная позиция. Ромашка с лепестками (ко
личество лепестков у ромашки определяется допол
нительными правилами).
Возможные ходы. На каждом ходу игрок отры
вает либо один лепесток, либо два соседних (расту
щих рядом).
Как определить победителя. Игра заканчивает
ся, если очередной ход сделать невозможно — все
лепестки оторваны. Выигрывает тот, кто сделал по
следний ход.
Исследуй игру Ромашка для различных начальных позиций.
У кого из игроков есть равновесная выигрышная стратегия?
Сформулируй эту стратегию.
Нужно рассмотреть два случая:
а) если число лепестков в начальной позиции чётно;
б) если число лепестков в начальной позиции нечётно.
243
Построй дерево И, для которого все следующие утверждения
истинны:
Высота дерева И равна четырём.
Все последовательности дерева И — разные.
На каждом уровне дерева И ровно три листа.
На втором уровне дерева И ровно четыре элемента.
Все элементы дерева И — однозначные числа,
которые делятся на 3.
145
146
244
Составь такой алгоритм для Робота, чтобы, стартовав из лю
бой клетки любого из этих полей, после выполнения твоего
245
Реши задачу, построив схему с пересечением трёх множеств,
как в задаче 149.
В школьной олимпиаде по математике участвовало 100 чело
век, по физике — 50, по информатике — 48. Когда учеников
спросили, в скольких олимпиадах они участвовали, ответ
«В двух» дали вдвое меньше человек, чем ответ «В одной»,
а ответ «В трёх» — втрое меньше, чем ответ «В одной». Сколь
ко всего учеников участвовало в этих олимпиадах?
246
Робот находится в левом верхнем углу прямоугольного поля.
Внутри поля имеется одна горизонтальная стена с одним
проходом, идущая от левой до правой стены прямоугольника
(проход не прилегает ни к левой, ни к правой стене прямо
угольника). Составь алгоритм, при выполнении которого Ро
бот переместится в правый нижний угол прямоугольника.
247
Реши задачу, используя метод половинного деления.
Имеется стопка из восьми монет, одна из которых фальшивая
(она отличается по весу от всех осталь
ных). Как, имея четыре нефальшивые
монеты и чашечные весы, найти фаль
шивую монету за три взвешивания?
248
Можно ли разбить на «костяшки доми
но» (каждая из двух клеток) шахматную
доску без противоположных
углов — полей а 1 и 68?
249
I
250
На окружности нарисованы 20 точек. Двое игроков по очере
ди соединяют отрезком любые две из этих точек так, чтобы
никакие два отрезка не пересекались (но два отрезка могут
иметь общий конец). Проигрывает тот, кто не может сделать
следующий ход. У кого из игроков есть выигрышная страте
гия? Опиши эту стратегию.
Робот находится в левом верхнем углу прямоугольного поля
шириной 9 и высотой 7 клеток. Нарисуй такое поле и стен
ки на нём, чтобы, выполнив алгоритм спуск, Робот оказался
в правом нижнем углу поля,
алг спуск
дано I
надо I
нач
нц 8 раз
если снизу свободно
то вниз
иначе вправо
все
кц
нц 3 раз
если снизу свободно
то вниз
все
кц
нц 3 раз
если справа свободно
то вправо
все
кц
кон
251
Сосчитай, сколькими способами 7 человек могут встать в оче
редь к театральной кассе.
252
Нарисуй, как разрезать многоуголь
ник X чтобы получились два много
угольника на сетке одинаковой пло
щади.
147
253
Двое игроков по очереди перево
дят часовую стрелку на два или на
три часа вперёд. В начальной по
зиции часовая стрелка указывает
на 12. Побеждает тот, кто первым
поставит стрелку на 6 (прежде чем
остановиться на цифре 6, стрелка
может сделать несколько оборо
тов). У кого из игроков есть вы
игрышная стратегия?
Для решения задачи используй специальную круглую число
вую линейку, которую можно вырезать из вкладыша тетра
ди проектов. Обрати внимание: после того как ты обойдёшь
круглую линейку один раз, некоторые позиции останутся не
закрашенными. Чтобы раскрасить все позиции, нужно будет
обойти линейку несколько раз.
Прочитай рецепт приготовления торта «Пальчики оближешь».
Изобрази процесс приготовления торта в виде дерева, где
листья — необходимые продукты, элемент первого уров
ня — готовый торт.
Приготовление коржей. Сначала взбить три яйца
с одним стаканом сахарного песка до получения гус
той однородной пены. Затем добавить пол пачки мар
гарина и один стакан муки. Всё хорошо перемешать
и испечь два коржа.
Приготовление крема. Сварить густую манную ка
шу из трёх с половиной столовых ложек манки и двух
стаканов молока. Затем остудить, добавить одну пачку
сливочного масла и один стакан сахарного песку, хо
рошо перемешать.
Приготовление глазури. Растопить одну шоколад
ку в небольшом количестве молока.
Приготовление торта. Выложить на один из кор
жей весь крем, накрыть другим коржом и полить
сверху глазурью. Поставить на несколько часов в хо
лодильник — и торт готов.
148
Коля и Петя написали своему другу Васе записки, в каждой
из которых зашифровано сообщение. Мальчики шифровали
сообщение следующим образом: слова сообщения спрятаны
в тексте, не связанном по содержанию со смыслом сообще
ния. Слова сообщения в каждом из текстов спрятаны без
определённого правила, но порядок слов сообщения при этом
не изменяется.
Прочитай записки двух мальчиков. В каждой из них зашиф
ровано одно и то же сообщение, состоящее из двух предло
жений. Запиши текст зашифрованного сообщения. Поставь
знаки препинания.
Записка Коли.
Сегодня состоялся сбор представителей классов по
поводу турслёта, который будет завтра. В девять утра
началось обсуждение. Оно могло затянуться до вече
ра, у меня даже разболелась голова. Вышел из школы
и встретил старого друга, мы оба очень обрадовались. Он
нёс кораблик из дерева. Он сказал: «Возьми на память».
Я подарил ему карту нашего района, есть там и наш
дом, а также подробный план прилегающих дворов.
Записка Пети.
На биологии рассказывали про сбор хлопка. На зав
тра задали найти ответы в учебнике на девять вопро
сов. На перемене обсуждали программу предстоящего
вечера. Вообще-то у нас уже был план, но его переде
лали так, что не осталось ни одного старого конкурса.
Стенгазету хотели сделать в виде дерева. Вдруг Колька
возьми да и скажи: «Давайте сделаем карту школы,
пометим всё самое интересное. Главное — не забыть
директора и наш класс». Все начали спорить, и план
вечера так и остался незаконченным.
256
Найди выигрышную стратегию для Второго в игре
Ползунок на поле 3x3 при условии, что Первый на
первом ходу соединит центральную точку поля
с одной из боковых.
149
257
Составь такой алгоритм, чтобы после его выполнения из каж
дого из данных начальных состояний Робот оказался в какойнибудь клетке верхнего ряда поля.
Начальное состояние 1:
Начальное состояние 2:
0
258
Реши задачу, используя метод половинного деления.
Имеется 68 алмазов, все алмазы разные по весу. Как за
100 взвешиваний на чашечных весах найти самый лёгкий
и самый тяжёлый алмаз?
259
Реши задачу.
Все трое внуков Прохора Кольцова — Иван, Степан и Ники
фор — чем-то на него похожи (цветом глаз, цветом волос или
формой носа), но ни цветом глаз, ни цветом волос, ни фор
мой носа не похожи друг на друга. Каждые две дочери каж
дого из внуков Прохора похожи между собой именно тем, чем
они похожи на отца, а все три его дочери — тем, чем их отец
похож на своего деда Прохора. Вот описание дочерей Ивана,
Степана и Никифора. Опиши деда Прохора и его внуков.
Дочери Ивана
Настя: глаза карие, волосы русые, нос с горбинкой.
Ася: глаза голубые, волосы каштановые, нос с горбинкой.
Даша: глаза карие, волосы каштановые, нос с горбинкой.
Дочери Степана
Галя: глаза зелёные, волосы рыжие, нос вздёрнутый.
Валя: глаза карие, волосы рыжие, нос с горбинкой.
Люба: глаза зелёные, волосы рыжие, нос вздёрнутый.
Дочери Никифора
Оля: глаза голубые, волосы русые, нос прямой.
Поля: глаза голубые, волосы каштановые, нос прямой.
Лена: глаза голубые, волосы русые, нос вздёрнутый.
150
Пользуясь решением задачи 259, определи истинностное зна
чение утверждений, заполни таблицу истинности 1. Используя
таблицу 1, заполни таблицу 2.
Таблица 1
Имя
Утверждение
А
У Ивана карие глаза.
D
У Степана нос с горбинкой.
F
У Никиты русые волосы.
L
У Прохора голубые глаза.
Значение
Таблица 2
Утверждение
Утверждение (полностью)
Значение
А и D
D и L
L или F
D или А
не F
не D
Даны правила игры Три кучи камешков. Известно, что в игре
Три кучи камешков Первый имеет равновесную выигрышную
стратегию. Сформулируй эту стратегию.
Правила игры Три кучи камешков
Начальная позиция. Три кучи камешков, во
всех кучах камней поровну (сколько именно, уста
навливается дополнительными правилами).
Возможные ходы. На каждом ходу игрок может
взять любое число камешков, но только из одной кучи.
Как определить победителя. Игра заканчива
ется, если все камешки закончились. Выигрывает
игрок, который забрал последний камешек.
262
Выпиши все числа, меньшие 600, большие 400 и такие, что
число десятков в каждом из них меньше числа сотен и в каж
дом есть две одинаковые цифры.
263
Разведчики прячут слова донесения в тексте. Один развед
чик размещает слова в тексте в том же порядке, как они идут
в донесении, а другой размещает слова не по порядку. В каж
дой шифровке содержится одно и то же донесение.
Запиши текст этого донесения. По
ставь знаки препинания. В текстахшифровках попадаются случайно
совпадающие (лишние) предлоги.
Выбери нужные предлоги, учиты
вая падежи существительных.
Шифровка первого разведчика.
На собрание явка обязательна для всех проживающих
в доме. Будут обсуждаться следующие вопросы:
1. У жильцов верхних этажей низкая температура го
рячей воды.
2. Крыша сараев провалилась.
3. Новое решение домоуправления предписывает выде
лить место под детскую площадку.
4. Квартира под музыкальной школой отапливается
плохо.
5. Необходимо выделить людей для работы с цветоч
ным палисадником, находящимся рядом с магазином.
Шифровка второго разведчика.
Затея с субботником провалилась. Явка оказалась низ
кой. Ни у кого в доме не нашлось ни лопаты, ни лейки
для воды. Пришлось связываться с магазином. Выбрали
новое место для клумбы, но, пока ходили за цветочным
саженцем, все под разными предлогами разошлись. Ви
димо, своя квартира оказалась милее общего двора.
264
152
Запиши шифровку, длина которой не больше 18 латинских
букв, такую, чтобы в ней содержались 2 слова — БЕЛЫЙ
и НОГУ. Для того чтобы выполнить задание, тебе понадобится
использовать наложение шифровок, подобное тому, о кото
ром говорится в задаче 218.
265
266
267
268
В таблице размером 7x7 клеток двое игроков по очереди за
крашивают клетки так, чтобы раскрашенные клетки не имели
общих сторон. Проигрывает тот, кто не может сделать ход.
У кого из игроков есть выигрышная стратегия в этой игре?
Опиши эту стратегию.
Выпиши множество А всех чисел, меньших 30, которые де
лятся на 2. Выпиши множество В всех чисел, меньших 30, ко
торые делятся на 3. Найди пересечение и объединение мно
жеств А и В.
Роботу разрешается выполнять толь
алг уголок
ко алгоритм уголок (см. справа),
нач
а больше никакие команды движе
вправо
ния выполнять нельзя. Робот стоит
вниз
на поле, где-то внизу под ним — го
кон
ризонтальная граница поля, а спра
ва — вертикальная граница поля.
Внутренних стен на поле нет. Используя алгоритм уголок как
вспомогательный, построй алгоритм, выполняя который Робот
дойдёт до одной из этих стен.
Реши задачу.
Из трёх одинаковых по виду колец одно несколько легче, чем
каждое их двух других (а два других весят одинаково). Как од
ним взвешиванием найти более лёгкое кольцо?
А
В
с
D
Е
сверху свободно
И
Л
и
Л
И
справа свободно
Л
Л
л
Л
л
снизу свободно
И
л
и
И
и
слева свободно
Л
л
и
л
и
153
270
В
С
D
Е
сверху свободно
И
Л
и
И
Л
справа свободно
Л
Л
л
Л
Л
снизу свободно
Л
Л
и
И
И
слева свободно
Л
Л
л
Л
и
Пользуясь заполненной таблицей, для
каждого имени найди какую-нибудь клет
ку на поле, которой соответствуют ука
занные значения истинности составных
условий. Нарисуй такое поле в тетради,
расставь имена клеток так, чтобы таблица
была верной.
А
В
с
D
Е
F
слева свободно
и справа свободно
Л
л
л
И
Л
И
не сверху свободно
и не клетка закрашена
Л
и
л
Л
и
и
снизу свободно
или не слева свободно
И
и
л
И
л
л
271
Реши задачу, используя метод половинного деления.
Из четырёх деталей одна отличается по весу от остальных.
Можно ли выделить её двумя взвешиваниями на чашечных
весах без гирь?
272
Реши задачу.
В бутылке, стакане, кувшине и банке находятся молоко, ли
монад, квас и вода. Известно, что в бутылке не вода и не мо
локо, кувшин стоит рядом с лимонадом и далеко от кваса, в
банке не лимонад и не вода. Стакан стоит рядом с банкой и
далеко от молока. В какой сосуд налита каждая жидкость?
Для решения задачи удобно построить схему, выписав в од
ном столбце названия всех сосудов, а в другом — названия
всех напитков.
О
154
А
Робот находится в прямо
угольнике, в котором нет
внутренних стен, закраше
ны только клетки одного
ряда — все, кроме какой-то
одной. Построй алгоритм,
выполнив который Робот
остановится именно в этой
единственной незакрашен
ной клетке этого ряда.
274
Реши лингвистическую задачу.
Вот несколько айнских числительных (в латинской транскрип
ции):
3 — ге
11 — sine ikasma wan
22 — tu ikasma hot
37 — arwan ikasma wan e tu hot
47 — arwan ikasma tu hot
93 — re ikasma wan e asikne hot
135 — asikne ikasma wan e arwan hot
Определи, какое число по-айнски записывается так:
wan е re hot.
Запиши по-айнски числа: 1, 5, 12, 53, 67, 85, 100.
275
Реши задачу.
Вася и Петя играют в игру. Вася записывает в каждой стро
ке таблицы 4x4 клетки последовательность из букв М и А
так, чтобы последовательности во всех строках были разные.
Затем Вася закрывает каждую клетку белым квадратиком и
передаёт Пете. Петя должен открыть любые четыре клетки та
блицы и написать последовательность длины 4, составленную
из М и А, которой в таблице нет. Если Пете это удастся, то он
выиграл, если нет — выиграл Вася. Какие четыре клетки Петя
должен открыть, чтобы наверняка выиграть?
155
Компьютерный проект
С видеокамерой в руках...
Дорогие ребята!
Этот проект посвящён видеосъёмке. Сейчас трудно найти
человека, который не делал бы видеозаписи. Функция видео
съёмки имеется на большинстве моделей мобильных телефо
нов и коммуникаторов. Владельцы планшетных компьютеров
постоянно используют видеозапись для фиксации интересных
событий и быстро делятся этой информацией с другими, раз
мещая её в Интернете. Мы постараемся не просто зафиксиро
вать увиденное глазом, а создать интересный ресурс, используя
современные возможности цифровой видеосъёмки и монтажа.
Тема вашей работы может быть любой, главное, чтобы она
была вам понятна и интересна.
В качестве примера мы рассмотрим технологию работы
над фильмом об экскурсии. Идея проекта — сделать фильм,
который расскажет зрителям о каком-нибудь интересном ме
сте, в котором вам и вашим одноклассникам удалось побывать
вместе, и передаст впечатления от увиденного. В нашей стране
большое количество памятников истории и культуры. Надеем
ся, что в этом учебном году вы уже посетили один из них или
поедете на экскурсию в самое ближайшее время. Не забудьте
взять видеокамеру на штативе — сделанные во время экскурсии
видеозаписи будут использованы в нашем фильме. Имея даже
одну камеру, вы сможете снимать, передавая её друг другу. На
кануне экскурсии посмотрите подсказки начинающим видеолю
бителям, которые имеются в описании этого проекта в тетради
проектов. Постарайтесь не забыть о них во время съёмки.
Вы уже имеете опыт по созданию мультфильма, поэтому орга
низация работы над фильмом не станет для вас неожиданностью.
Готовясь к уроку, постарайтесь ответить на следующие вопросы:
•
О чём ваш фильм?
•
Для кого ваш фильм?
Сколько приблизительно времени будет длиться фильм?
•
Какие сюжеты будут в вашем фильме?
На все эти вопросы можно ответить при составлении сце
нарного плана. Создайте свою творческую группу из 3—5 че-
156
ловек, соберитесь вместе и посмотрите фотоматериалы по теме
будущей экскурсии в книгах или в Интернете, продумайте
план фильма (см. монтажный лист в тетради проектов). Хоро
шая подготовка к экскурсии позволит не растеряться, получив
в руки видеокамеру, и быстро найти взглядом интересные «кар
тинки» для вашего фильма. Вы можете включить в ваш сцена
рий интервью с участниками экскурсии, отснять которое можно
будет на уроке уже после экскурсии.
Чтобы превратить видеозаписи в короткий фильм, нам нужно
будет поработать с ними два урока. На первом уроке надо будет
перенести отснятый видеоматериал в компьютерную программу
для редактирования видео. Кроме того, нужно сделать всю основ
ную работу по подбору и редактированию клипов. Добавление ти
тров и работу со звуком можно отложить на второй урок.
В работе над фильмом нам поможет опыт мультипликации,
полученный в 5 классе, где мы использовали функцию фото.
В этом проекте мы используем функцию видеосъёмки. В ре
зультате при переносе информации на компьютер мы получаем
цепочку, состоящую из видеоклипов, которые можно просма
тривать, удалять из них лишние фрагменты и т. п.
Для мультфильма
Для фильма
1. Съёмка, создание видеоце
почки.
2. Расстановка кадров и уста
новка длительности.
1. Съёмка, создание видеоцепочки.
2. Импорт видеоматериала.
3. Просмотр и расстановка клипов
на «монтажной линейке», редакти
рование клипов.
4. Добавление титров.
5. Озвучивание (запись голоса).
6. Музыкальное сопровождение
Этапы создания мультфильма и видеофильма различаются
лишь одним этапом. Именно эти этапы нам и предстоит пройти
за два урока.
Постарайтесь справиться с работой быстрее, потому что
оставшееся время можно будет потратить на просмотр и обсуж
дение ваших удивительных фильмов. Не забудьте обсудить с
учителем, как можно посмотреть фильм со всей семьей, ведь
вашим родителям это тоже будет интересно.
157
Содержание курса
Введение..........................................................................................................
3
Сортировка: упорядочение и классификация..................................................
Проект. Словари...................................................................... тетрадь проектов
Проект. Сортировки.................................................................тетрадь проектов
Исполнители и алгоритмы...................................................................................
22
Практикум. Исполнители.................................................................... компьютер
Вспомогательный алгоритм..................................................................................
Алгоритмы: цикл «N раз».....................................................................................
43
Практикум. Цикл «N раз».................................................................... компьютер
Повторение...............................................................................................................
50
Игры с полной информацией .............................................................................
Цикл «пока»..............................................................................................................
87
Свойства цикла «пока»..........................................................................................
89
Составление алгоритма с циклом «пока» ......................................................
91
Практикум. Цикл «пока»...................................................................... компьютер
Равновесные выигрышные стратегии...............................................................
96
Составные условия: слова «и», «или», «не».....................................................
106
Практикум. Составные условия.........................................................компьютер
Биоинформатика. Белки и ДНК. Почему дети похожи на родителей?..... 114
Шифрование............................................................................................................
158
117
Биоинформатика. Как кодируются белки..............................................................
Компьютерный проект. С видеокамерой в руках ... (практика работы
с аудио- и видеоматериалами)............. тетрадь проектов, компьютер 156
Ответы к задачам:
№ 13: 10,5 ед. кв. № 20: 6 слов. № 51: 13,5 ед. кв.
№ 62: 24 путями. № 68: цифра 4. № 79: 20 брёвен. № 87: 59 мин.
№ 91: 15 человек. № 115: 24 способами. № 120: 10 руко
пожатий. № 127: 10 путями. № 149: 9 учеников, 1 ученик.
№ 162: 12 чисел. № 201: 90 000 000 нуклеотидов. № 204: А и Г.
№ 207: Саня и Даня. № 208: 63 типа. № 225: 24 числа.
№ 231: за 10 вопросов. № 248: нельзя.
159
Учебное издание
Семёнов Алексей Львович
Рудченко Татьяна Александровна
ИНФОРМАТИКА
6 класс
Учебник
Центр развития углублённого и профильного образования, функциональной
грамотности, технологии и ИКТ-компетенций
Ответственный за выпуск Е. А. Баклашова
Редакторы О. В. Платонова, Е. С. Карауш
Художественный редактор Т. В. Глушкова
Компьютерная графика Н. А. Артемьевой
Технический редактор и верстальщик Н. В. Лукина
Корректор Н. В. Игошева
Подписано в печать 27.01.2022. Формат 70x90/16. Гарнитура SchoolBookCSanPin.
Усл. печ. л. 11,7. Уч.-изд. л. 8,35. Тираж
экз. Заказ №
Акционерное общество «Издательство «Просвещение».
Российская Федерация, 127473, г. Москва, ул. Краснопролетарская, д. 16, стр. 3,
этаж 4, помещение I.
Адрес электронной почты «Горячей линии» — vopros@prosv.ru.
Обратная таблица генетического кода
Кодон
ААА
AAG
ААС
ААТ
AGA
AGG
AGC
AGT
АСА
ACG
АСС
ACT
АТА
ATG
АТС
АТТ
GAA
GAG
GAC
GAT
GGA
GGG
GGC
GGT
GCA
GCG
GCC
GCT
GTA
GTG
GTC
GTT
Приведены все 64 кодона в «ДНК-алфавитном» порядке, т. е.
порядок букв в алфавите такой: A, G, С, Т.
В таблице генетического кода, которую вы будете изучать
в старших классах, вместо буквы Т стоит U. Это связано с тем, что
создание белков в организме происходит в несколько этапов,
при этом создаётся промежуточное звено - молекула РНК,
в которой тимин (Т) заменяется урацилом (U).
ттт
АТА
ААА
СТТ
ATG
ААТ
ССТ
САА
CGT
ТСТ
ACT
GTT
TGG
ТАТ
ТАА
GCC
TGC
GAC
GAG
ТТС
АТС
AAG
СТС
GCA
GCG
ATT
СТА
CTG
ААС
ССС
CAG
CGC
ТСС
АСС
GTC
CCA
CCG
CGA
ТСА
АСА
GTA
CGG
TCG
ACG
GTG
ТАС
TAG
TGA
TTA
TTG
AGA
AGT
AGG
AGC
Слово «белок» происходит от названия белка куриного яйца. В курином
белке есть молекулы разных видов белков. Больше всего молекул белка
под названием овальбумин (от латинских слов ovum - Яйцо и albus белый). Молекула овальбумина состоит примерно из 1500 звеньев. В
живых организмах цепочки многих белков сложены в плотные структуры.
