141 Составь диалог компьютера и Робота при выполнении каждого цикла в ситуации, когда Робот стоит: а) в закрашенной клетке; б) в незакрашенной клетке. Если выполнение алгоритма приведёт к зацикливанию — прерви описание диалога и напиши о зацикливании.
нц пока клетка чистая
закрасить
кц
нц пока клетка закрашена
Первый цикл: нц пока клетка чистая закрасить кц
а) Робот стоит в закрашенной клетке Компьютер проверяет условие: клетка чистая? Робот отвечает: нет. Цикл не выполняется, алгоритм сразу завершается.
б) Робот стоит в незакрашенной клетке Компьютер проверяет условие: клетка чистая? Робот отвечает: да. Компьютер: закрасить. Робот закрашивает клетку. Компьютер снова проверяет условие: клетка чистая? Робот отвечает: нет. Цикл завершается.
Второй цикл: нц пока клетка закрашена закрасить кц
а) Робот стоит в закрашенной клетке Компьютер проверяет условие: клетка закрашена? Робот отвечает: да. Компьютер: закрасить. Робот снова закрашивает клетку (что бессмысленно, так как клетка уже закрашена). Компьютер снова проверяет условие: клетка закрашена? Робот отвечает: да. Цикл повторяется бесконечно — зацикливание.
б) Робот стоит в незакрашенной клетке Компьютер проверяет условие: клетка закрашена? Робот отвечает: нет. Цикл не выполняется, алгоритм сразу завершается.
142 Составь алгоритмы влево до стены, вправо до стены, вверх до стены, о которых идёт речь на с. 88. Запиши условия дано и надо. Проверь, что алгоритмы составлены правильно — что не возникнет отказа и что цикл не будет повторяться вечно.
1. Дано и надо Дано: Робот стоит в произвольной клетке, где-то перед ним есть стена. Надо: Робот должен двигаться в заданном направлении, пока не упрётся в стену.
2. Алгоритмы Влево до стены: алг влево до стены нач нц пока слева свободно влево кц кон
Вправо до стены: алг вправо до стены нач нц пока справа свободно вправо кц кон
Вверх до стены: алг вверх до стены нач нц пока сверху свободно вверх кц кон
Вниз до стены (из параграфа): алг вниз до стены нач нц пока снизу свободно вниз кц кон
3. Проверка на корректность Отказа не возникнет: если стена сразу перед Роботом, то условие пока <направление> свободно сразу окажется ложным, и цикл не начнется. Зацикливания не будет: Робот движется в заданном направлении, а проверка условия происходит перед каждым шагом. Как только он упирается в стену, цикл завершается.
143 Робот находится у левой стены прямоугольного поля, огороженного со всех сторон стенами. Внутри поля стен нет, раз меры поля неизвестны. Надо составить такой алгоритм, при выполнении которого Робот закрасит горизонтальный ряд клеток от исходного положения до правой стены и вернётся в исходное положение: сначала Робота надо довести до правой стены, по дороге закрашивая клетки, а затем вернуть в исходное положение и закрасить эту исходную клетку. Вот этот алгоритм:
алг закрасить ряд вправо и вернуться
дано | Робот стоит у левой стены поля
надо | закрашен весь горизонтальный ряд,
| в котором стоит Робот, | Робот в исходном положении
нач
вправо до стены с закрашиванием
влево до стены
кон
Вспомогательный алгоритм влево до стены ты построил в ходе решения задачи 142. Построй вспомогательный алго ритм вправо до стены с закрашиванием. Запиши условия дано и надо. Проверь, что алгоритм составлен правильно — что не возникнет отказа и что цикл не будет повторяться вечно.
1. Дано и надо Дано: Робот стоит в произвольной клетке, перед ним справа есть стена (на неизвестном расстоянии). Надо: Робот должен двигаться вправо, закрашивая все клетки на своём пути, пока не упрётся в стену.
2. Алгоритм алг вправо до стены с закрашиванием нач нц пока справа свободно закрасить вправо кц закрасить кон 3. Проверка на корректность Отказа не возникнет: если стена сразу справа, то пока справа свободно окажется ложным, и Робот просто закрасит свою текущую клетку. Зацикливания не будет: Робот движется вправо, а проверка условия выполняется перед каждым шагом. Как только он упирается в стену, цикл завершается.
144 Составь алгоритм с таким заголовком (см. ниже).
алг закрасить прямоугольник
дано | Робот стоит в левом нижнем углу
| поля без внутренних стен
надо | весь прямоугольник закрашен,Робот
| в исходном положении
Используй в качестве вспомогательного алгоритм закрасить ряд вправо и вернуться, составленный при решении задачи 143.
1. Дано и надо Дано: Робот стоит в левом нижнем углу прямоугольного поля без внутренних стен. Надо: Весь прямоугольник закрашен, Робот возвращается в исходное положение.
2. Алгоритм алг закрасить прямоугольник нач нц пока сверху свободно закрасить ряд вправо и вернуться вверх кц закрасить ряд вправо и вернуться нц пока снизу свободно вниз кц кон 3. Проверка на корректность Отказа не возникнет: если поле состоит из одной строки, цикл пока сверху свободно не выполнится, и робот просто закрасит этот ряд. Зацикливания не будет: Робот двигается вверх построчно, а затем возвращается вниз, пока не достигнет исходного положения.
145 Реши задачу 144, считая, что о начальном положении Робота на поле ничего не известно.
1. Дано и надо Дано: Робот находится в произвольной клетке прямоугольного поля без внутренних стен. Надо: Весь прямоугольник закрашен, Робот возвращается в исходное положение.
2. Алгоритм алг закрасить прямоугольник из любого положения нач влево до стены вниз до стены нц пока сверху свободно закрасить ряд вправо и вернуться вверх кц закрасить ряд вправо и вернуться нц пока снизу свободно вниз кц кон 3. Проверка на корректность Робот всегда оказывается в левом нижнем углу перед началом закраски. Алгоритм закрашивает поле построчно, двигаясь вверх. После закраски Робот возвращается в исходное положение. Отказа не возникнет, так как Робот всегда сначала корректирует свою позицию. Зацикливания не будет, так как верхняя граница поля ограничена.
146 Нарисуй такой же четырёхугольник по клеткам в тетради. По том нарисуй, как разрезать его на части, чтобы из них можно было собрать квадрат на сетке. Нарисуй такой квадрат и покажи штриховыми линиями, из ка ких частей он составлен.
Смотри вложение вверху.
147 На поле Робота ровно одна стена. Это горизонтальная стена, которая не примыкает к границам поля. Робот находится в одной из клеток, прилегающих к стене сверху. Точные размеры поля и стены и точное расположение Робота неизвестны. Составь алгоритм, при выполнении которого
Робот:
а) окажется в одной из клеток, прилегающих к стене снизу;
б) закрасит все клетки, прилегающие к стене снизу;
в) закрасит все прилегающие к стене клетки.
1. Дано и надо Дано:
На поле ровно одна горизонтальная стена, не примыкающая к границам. Робот находится в одной из клеток, прилегающих к стене сверху. Точные размеры поля, стены и начальное положение Робота неизвестны. Надо: а) Робот оказывается в одной из клеток, прилегающих к стене снизу. б) Робот закрашивает все клетки, прилегающие к стене снизу. в) Робот закрашивает все прилегающие к стене клетки.
2. Алгоритм для спуска под стену алг спуститься под стену нач нц пока снизу занято вправо кц вниз кон Пояснение: Робот движется вправо, пока не найдёт конец стены, а затем спускается вниз.
3. Алгоритм для закрашивания клеток под стеной алг закрасить под стеной нач спуститься под стену влево до стены с закрашиванием вправо до стены с закрашиванием кон Пояснение: После спуска под стену Робот закрашивает все клетки, прилегающие к ней снизу, двигаясь сначала влево, затем вправо.
4. Алгоритм для закрашивания всех клеток вокруг стены алг закрасить вокруг стены нач закрасить под стеной вверх вправо до стены с закрашиванием влево до стены с закрашиванием кон Пояснение: После закрашивания клеток под стеной Робот поднимается наверх и закрашивает все клетки сверху.
5. Проверка на корректность Робот всегда находит конец стены и спускается вниз. Закрашивание выполняется корректно и без пропусков. Отказ невозможен, так как Робот начинает движение только при наличии свободного пространства. Зацикливания нет, так как Робот двигается до конца стены и выполняет закраску один раз для каждой клетки.
148 Робот стоит в левом конце горизонтального коридора, нижняя стена которого сплошная, а в верхней имеется несколько выходов. Составь алгоритм, который заставляет Робота переместиться из клетки А в клетку В (см. рисунок, сколь ко клеток между клетками А и В, неизвестно) и закрасить все те клетки коридора, которые расположены напротив боковых выходов.
Решение: алг закрасить выходы и дойти до конца нач нц пока справа свободно если сверху свободно то закрасить вправо кц кон Объяснение: Робот движется вправо, пока не достигнет конца коридора. В каждой клетке он проверяет, есть ли сверху выход. Если выход есть, Робот закрашивает текущую клетку, после чего продолжает движение.
Корректность:
Зацикливание невозможно, так как Робот движется вправо, пока может. Отказ невозможен, так как проверяется наличие выхода перед закрашиванием. Алгоритм закрашивает только нужные клетки и не пропускает выходы.
149 Реши задачу.
В нашем классе из 31 учащегося по итогам первой четверти неуспевающих нет (ни у кого нет ни одной четвертной двойки). При этом у нас имеется 3 круглых отличника и 3 круглых троечника (тех, у кого тройки в четверти по всем предметам). Пятеро учеников закончили четверть только на четвёрки и пятёрки. Известно также, что пятёрки имеют среди четвертных оценок 18 учеников и 24 ученика имеют среди четвертных оценок четвёрки. Сколько учеников нашего класса имеют в четверти и тройки, и четвёрки, и пятёрки? Сколько учеников нашего класса не получили в четверти ни одной четвёрки?
Для решения задачи нарисуй схему с множествами:
Обозначим:
Всего учеников: 31. Круглые отличники («5» по всем предметам): 3. Круглые троечники («3» по всем предметам): 3. Ученики, у которых только «4» и «5»: 5. Ученики, у которых есть хотя бы одна «5»: 18. Ученики, у которых есть хотя бы одна «4»: 24. Шаг 1: Определим, сколько учеников имеют в четверти и тройки, и четвёрки, и пятёрки
Ученики, имеющие «5»:
Отличники (3) и ученики с «4» и «5» (5) не могут иметь «3», значит, их исключаем. Значит, среди учеников с «5» остаётся 18 - (3 + 5) = 10 человек, у которых могут быть и «3». Ученики, имеющие «4»:
Среди них есть ученики с «4» и «5» (5) и троечники (3), у которых нет ни «4», ни «5». Значит, среди учеников с «4» остаётся 24 - 5 = 19 человек. Эти 10 учеников — это те, у кого есть и «3», и «4», и «5».
Шаг 2: Определим, сколько учеников не получили ни одной четвёрки
Всего в классе 31 человек, из них 24 человека имеют хотя бы одну «4».
Тогда учеников, у которых нет четвёрок: 31 - 24 = 7 человек.
Ответ: 10 учеников имеют в четверти и тройки, и четвёрки, и пятёрки. 7 учеников не получили в четверти ни одной четвёрки.
150 Нарисуй в тетради по клеткам:
а) прямоугольник, не являющийся квадратом, площадь которого равна 64 ед. кв.;
б) прямоугольный треугольник, площадь которого равна 17 ед. кв.;
в) четырёхугольник, площадь которого равна 13 ед. кв.;
г) два разных прямоугольных треугольника, площадь каждого из которых равна 10 1/2 ед. кв.;
д) два разных четырёхугольника, не являющихся прямоугольниками, площадь каждого из которых равна 21 ед. кв.
а) Прямоугольник с площадью 64 ед. кв., но не являющийся квадратом: Площадь прямоугольника вычисляется по формуле: S = a * b, где a и b — длины сторон. 64 можно разложить, например, как 8 × 8 (но это квадрат), значит, берем 4 × 16, 2 × 32 или 1 × 64.
б) Прямоугольный треугольник с площадью 17 ед. кв.: Формула площади: S = (a * b) / 2. Подходящие размеры: a = 4, b = 8.5, a = 2, b = 17 и т. д.
в) Четырёхугольник с площадью 13 ед. кв.: Можно взять произвольную трапецию или выпуклый четырёхугольник с известной формулой площади. Например, трапеция с основаниями 5 и 3 и высотой 2.
г) Два разных прямоугольных треугольника с площадью 10 1/2 ед. кв. (10.5 ед. кв.): S = (a * b) / 2 = 10.5, значит, например:
a = 6, b = 3.5, a = 7, b = 3. д) Два разных четырёхугольника, не являющихся прямоугольниками, с площадью 21 ед. кв.: Можно взять две разные трапеции или произвольные выпуклые четырёхугольники, например:
Трапеция с основаниями 6 и 8 и высотой 3. Равнобедренную трапецию с другими параметрами (например, 7 и 5, высота 3).
151 К полю для игры Крестики-нолики добавлена одна клетка. Правила игры при этом остались прежними: Первый ставит крестики, Второй — нолики. Выигрывает тот, кто первым построит ряд из трёх своих значков по горизонтали, вертикали или диагонали. В отличие от игры на обычном поле, в игре Крестики-нолики на таком поле Первый имеет выигрышную стратегию. Куда должен поставить крестик Первый на первом ходу, чтобы наверняка выиграть?
Первый должен поставить крестик в центр стандартного поля 3×3, то есть в клетку (2,2) (если считать от 1 до 3 по горизонтали и вертикали).
После этого, независимо от ходов Второго игрока, Первый сможет выстроить выигрышную комбинацию за счёт дополнительной клетки, используя её для манёвра.
Если дополнительная клетка примыкает к стандартному полю, стратегия может изменяться, но в большинстве случаев центральная позиция даёт наилучший контроль над игрой
152 Вот правила игры 7 камней:
Правила игры 7 камней
Начальная позиция. Куча из 7 камешков.
Возможные ходы. На каждом ходу игрок разделяет любую из имеющихся куч на две (необязательно попо лам).
Как определить победителя. Игра заканчивается, если очередной ход сделать невозможно. Выигрывает тот, кто сделал последний ход.
Исследуй игру 7 камней. Попытайся объяснить, почему в этой игре выигрышная стратегия не нужна, — победа не за висит от того, насколько умело играют игроки. Кто выигрывает в игре 7 камней?
В игре 7 камней стратегия не имеет значения, потому что победа не зависит от мастерства игроков, а определяется только начальным количеством камней.
Разберёмся, почему так происходит.
Анализ игры В начале есть 7 камней в одной куче. Каждый ход игрок разделяет одну из куч на две. Игра заканчивается, когда все кучи состоят из одного камня, потому что больше нельзя делать ходы. Побеждает тот, кто сделал последний ход. Подсчёт количества ходов Начальная куча: 7 камней.
Разделим её: 7 → (3,4) → (3,2,2) → (2,2,2,1) → (2,1,1,1,1) → (1,1,1,1,1,1,1). Каждый раз количество куч увеличивается на 1. Так как начинается одна куча, а заканчивается 7 куч, значит, было сделано 6 ходов.
Кто выигрывает? Первый игрок делает 1-й, 3-й, 5-й ход. Второй игрок делает 2-й, 4-й, 6-й (последний!) ход. Побеждает Второй игрок, потому что он делает последний ход независимо от того, какие разбиения выбирают игроки.
Вывод В этой игре выигрышная стратегия не нужна, так как исход заранее предопределён. Если игра начинается с 7 камней, то побеждает Второй игрок при любом раскладе.
153 Реши задачу.
Почтальон Печкин, выйдя из почтового отделения, разнёс почту в каждый дом деревни, после чего зашёл с посылкой к дяде Фёдору (зайдя сначала за ней на почту), а потом вернулся домой. На рисунке показаны все тропинки, по которым проходил Печкин, причём, как оказалось, ни по одной из них он не проходил дважды. Каков мог быть маршрут почтальона Печкина? В каком доме живёт дядя Фёдор?
Определяем дом дяди Фёдора Почтальон Печкин зашёл на почту дважды:
В самом начале – чтобы забрать почту. Перед тем, как зайти к дяде Фёдору – чтобы взять для него посылку. Следовательно, дом дяди Фёдора – тот, куда Печкин направился сразу после второго посещения почты.
Если внимательно посмотреть на рисунок, то только дом №6 соединён с почтой таким образом, что можно пройти по всем дорожкам, не возвращаясь назад.
Вывод: дядя Фёдор живёт в доме №6.
Маршрут почтальона Печкина Поскольку он прошёл по каждой тропинке ровно один раз, его маршрут должен быть эйлеровым путем – то есть проходить по каждому ребру (тропинке) ровно один раз.
Один из возможных маршрутов:
Почта →2 2 → 3 3 → 4 4 → 5 5 → 6 6 → 7 7 → 1 2 → 7 7 → Почта (забрал посылку) Почта → 6 (отнёс посылку дяде Фёдору) 6 → 4 (вернулся домой) Этот маршрут охватывает все дома и соответствует условиям задачи