Решение задач 90—102 из учебника

Задача 90 (необязательная). Стратегии решения таких задач подробно описаны в комментарии к задаче 44.

Задача 91 (необязательная). Задача на повторение темы «Перед каждой бусиной. После каждой бусины». Особенность этой задачи состоит в том, что значки, которые в ней использованы, непривычны, и детям придётся много раз обращаться к сноске, чтобы вспомнить, какой значок обозначает какой вид спорта.

Несложно заметить, что, во-первых, каждая фигурка в задаче представлена в трёх экземплярах. Во-вторых, четыре фигурки различных видов можно сложить в один фрагмент цепочки так, что оба утверждения станут истинными. Дальше можно взять снова четыре разные фигурки и сложить их в том же порядке. После этого и последнюю четвёрку упорядочить так же. При этом утверждения подсказывают такой порядок следования значков в каждом из трёх фрагментов: «велоспорт — фехтование — футбол — теннис» или «фехтование — велоспорт — теннис — футбол».

Задача 92 (необязательная). Имеется восемь (закрашенных) клеток, на каждой из которых Робик мог находиться перед выполнением программы. Здесь детям поможет метод перебора (полного или систематического). Чтобы осуществить полный перебор, необходимо поочерёдно выбирать каждую из закрашенных клеток в качестве начального положения Робика и пытаться из неё выполнить программу (можно использовать запасное поле из листа вырезания). Если при этом получается позиция, приведённая в задании, мы нашли начальное положение; если в какой-то момент Робик вышел за пределы закрашенных клеток, то предполагаемое начальное положение вычёркиваем и переходим к другой клетке. При этом, естественно, следует выполнять программу и вычёркивать клетки на разных полях, иначе легко запутаться.

Многие ученики догадаются, что из некоторых позиций запускать Робика просто нет смысла. Например, если поместить Робика в верхнюю закрашенную строку, он первым же ходом выскакивает в незакрашенную часть. Постепенно становится ясно, что Робик должен начинать выполнять программу из второй снизу строки. И действительно, анализ программы показывает, что в результате её выполнения Робик сместился по вертикали сначала вверх на одну клетку, а затем на две клетки вниз (потом ещё раз на две клетки вверх, но это уже не столь важно). Чтобы не выйти за пределы закрашенных клеток, ему надо стартовать в среднем ряду. Применяя то же рассуждение для перемещений по горизонтали, видим, что сначала Робик сдвинулся на одну клетку вправо, а затем — на две влево. Такое возможно только из средней клетки среднего ряда, она и даёт положение Робика до выполнения программы. Осталось выполнить программу и отметить конечное положение Робика.

Есть и другой способ решения таких задач. Можно выполнить программу на клетчатой бумаге (на «поле без границ») и посмотреть, из какой клетки конечного рисунка Робик начал движение. Останется перенести результат на заданное поле для Робика. Этот способ, с одной стороны, облегчает работу, но, с другой стороны, необходимое при этом способе перенесение результата может оказаться затруднительным. Поэтому мы бы предпочли, чтобы ребёнок сам изобрел для себя такой способ: сделав интеллектуальное усилие, он наверняка будет способен довести решение до конца. Если же навязать такой способ решения, то продолжение работы может оказаться слишком сложным для ребёнка.

Решение задачи:

Задача 93 (необязательная). Дети, скорее всего, будут решать эту задачу методом проб и ошибок, и не нужно им мешать. Если у кого-то дело совсем не идёт, посоветуйте ему построить две какие-нибудь любые цепочки, для которых справедливо переместительное свойство. Так, если взять две цепочки длины 1, состоящие из разных бусин, переместительное свойство выполняться не будет, а если цепочки будут из одинаковых бусин — будет. Постепенно становится ясно, что переместительное свойство выполняется для пары одинаковых цепочек. Этот факт в данной задаче позволяет построить решение.

Задача 94 (необязательная). Задача на повторение лексики, связанной с деревьями, а также на работу с утверждениями, не имеющими смысла в какой-то ситуации. Здесь дети впервые сталкиваются с такими утверждениями для деревьев. На листах определений на с. 19—20 эта тема обсуждается и приводятся утверждения, не имеющие смысла для данных деревьев. Напомните об этом тем детям, которые будут решать задачу.

Какие рассуждения могут помочь при решении задачи? Рассмотрим третье утверждение: «В этом дереве предыдущая буква перед Т — буква О». Для дерева L оно не имеет смысла, так как буква Т в нём не одна, а для деревьев R, S, Q оно не имеет смысла, так как буквы Т в них нет. В дереве N буква Т есть, причём одна. Кроме того, предыдущая бусина перед Т — буква О, поэтому для дерева N третье утверждение истинно. Аналогичные рассуждения подойдут и для четвёртого утверждения.

Деревья устроены из знакомых учащимся слов, но значение некоторых слов они могут не знать. Если кто-то не знает значения слова, попросите найти это слово в толковом словаре.

Решение задачи:

Задача 95 (необязательная). Задача довольно сложная. Однозначно по количеству букв определяются только слова МАЙ и СЕНТЯБРЬ, при заполнении других окон полной однозначности нет. Например, имеются три слова длины 4: ИЮНЬ, ИЮЛЬ и МАРТ. Если ученик не успел ещё об этом подумать, то, увидев цепочку из четырёх пустых окон, может написать туда, предположим, МАРТ, в этом случае довести до конца решение ему уже не удастся. Поэтому в данной задаче ребёнок не сможет действовать чисто формально, ему каждый раз придётся сопоставлять сразу несколько окон и слов. При этом возможны ошибки.

Решение задачи:

Задача 96 (необязательная). Задача напоминает задачу 93, но в отличие от неё здесь не удаётся построить решение из двух одинаковых цепочек. Детям снова поможет метод проб и ошибок. Постепенно в ходе этих проб становится ясно, что надо как-то использовать одинаковые бусины. Например, можно построить обе цепочки из бусин одинаковой формы и цвета. Тогда длина цепочек может быть любой и можно обеспечить выполнение второго утверждения. Скорее всего, дети построят именно такое решение, но есть и другие варианты. Так, можно построить обе цепочки из одинаковых фрагментов любой длины. В цепочку А нужно взять столько фрагментов, чтобы выполнялось второе утверждение, а в цепочку Б — любое число. Вот пример цепочек А и Б, построенных из одинаковых фрагментов длины 3:

Задача 97 (необязательная). Подобные задачи дети уже решали (это задачи 32 и 43). В этой задаче мешков меньше, но различных предметов в мешках больше. Можно обсудить с детьми, которые решили все три задачи, какую задачу, по их мнению, проще решать и почему. Скорее всего, данная задача покажется ребятам сложнее, чем задачи 32 и 43.

Ответ: два одинаковых мешка — М и Н.

Задача 98 (необязательная). Больше других эта задача напоминает задачу 86, только здесь результат склеивания не задан явно, но известно, что должно получиться русское название животного. Как и в задаче 86, здесь предполагается перебор. Но он был бы очень большим, если бы детям по ходу дела не помогали лингвистические соображения. Так, для большинства цепочек в мешке сразу видно, могут ли они быть началом или концом слова — названия животного. Это позволяет сократить перебор, а не сопоставлять каждое слово с каждым. Начало слова (первый аргумент), для которого не найдётся окончание (второй аргумент), можно сразу вычеркивать. Так постепенно количество вариантов решения будет сужаться.

Задача 99 (необязательная). Положение Робика до выполнения программы не задано. Начальным положением для Робика может служить любая из закрашенных клеток, и в зависимости от выбора клетки возможные варианты программы Е могут быть самыми разными, в том числе и по длине. Естественно, чем больше Робик возвращается, т. е. чем больше клеток он посещает дважды, тем длиннее программа. При этом правильным ответом считается любая программа, в результате выполнения которой Робик закрашивает на поле данный рисунок. Ученики будут стремиться к простоте программы интуитивно, из соображений здравого смысла. Большинство ребят «запустят» Робика из конца верхней или нижней палочки буквы Е.

Задача 100 (необязательная). Эту задачу можно разделить на две части: сначала решить вопрос о цвете пропущенных бусин, а затем об их форме. Из первого утверждения следует, что пятая бусина синяя, из второго — что вторая бусина зелёная, из третьего — что шестая бусина красная. Не определился только цвет третьей бусины. Он может быть любым, в том числе и синим. Теперь начинаем разбираться с формой бусин. Самое простое решение одновременно и самое естественное — раскрасить окна в найденные цвета, то есть сделать все бусины квадратными. Поскольку ни в одном утверждении про квадратные бусины не говорится, то на истинность утверждений квадратные бусины не повлияют. Таким образом, мы получили цепочку Г (на самом деле с учетом возможных цветов третьей бусины мы получили шесть разных вариантов цепочки Г). Возможно, кто-то захочет определить форму недостающих бусин «по-честному», т. е. провести полные рассуждения. В этом случае важно проследить выполнение условия, если какие-то бусины в окнах окажутся круглыми, треугольными или синими.

Задача 101 (необязательная). Подобную задачу дети уже решали (задача 92). Ребята, скорее всего, будут решать её методом проб и ошибок и, возможно, найдут правильное начальное положение, но, чтобы найти его наверняка, нужно воспользоваться методом перебора. Решение состоит в том, чтобы поочерёдно ставить Робика в закрашенные клетки и пытаться выполнить из них данную программу. Перебор можно существенно уменьшить, если внимательно посмотреть на команды программы. Сразу можно вычеркнуть клетки, из которых нельзя выполнить две первые команды вправо. Таких клеток оказывается довольно много. Остаётся проверить только пять оставшихся клеток:

Рисунок, который закрасил Робик в результате выполнения программы, довольно причудливый. Поэтому анализировать отдельно положение Робика на поле по горизонтали и по вертикали (как мы это делали в задаче 92) здесь сложно. Таким образом, попытки продолжения анализа программы с целью ещё уменьшить перебор не дают большого эффекта. Здесь проще проверить все оставшиеся варианты.

Проверьте, что ребята не забыли отметить также и положение Робика после выполнения программы на соответствующем поле.

Решение задачи:

Задача 102 (необязательная). В первой части курса приводилось много примеров объектов и явлений, являющихся цепочками (последовательностями). Здесь детям предлагается поработать ещё с одним таким примером. Обратите внимание, что направление цепочки противоположно направлению движения животных. Начало и конец цепочки задаёт условие: «Первым идёт аист… Последним в цепочке идёт жираф». В соответствии с этим нужно вписывать слова в утверждения. Для утверждений, где использованы понятия раньше / позже, есть несколько верных вариантов ответов.

Ответ:

Первым идёт аист.

Жираф идёт четвёртым после аиста.

Страус идёт позже аиста/жеребёнка.

Вторым с конца идёт слонёнок.

Жеребёнок идёт раньше страуса/слонёнка/жирафа.

Третьим идёт аист/жеребёнок/слонёнок/жираф.

 

Урок(и) «Путь дерева»

Ветвление

Ветвление времени, возможность выбора в истории всегда занимали философов и теологов. Если весь ход истории заранее записан в Книге или спланирован Господом, то что зависит от человека? Проблема эта неоднократно обыгрывалась и в научной фантастике. В частности, «эффект бабочки» (Рей Брэдбери) состоит в том, что выбор, случившийся в далёком прошлом и выглядевший там весьма незначительно (раздавленная бабочка), приводит к достаточно радикальным изменениям в истории цивилизации, грамматические правила и политические партии становятся иными.

В математике и информатике ветвящееся время и возможные миры — один из основных способов формального задания смысла логических высказываний в различных формальных языках. Это попытка отразить в формальных языках особенности естественных языков, в частности такие понятия, как «возможно», «необходимо», «вероятно», «когда-то», «желательно», «доказуемо». В другой ветви математики рассматриваются «теория катастроф» и «теория хаоса», также изучающие то, каким образом очень маленькие изменения и незначительные ветвления приводят к глобальным эффектам.

Этим применение формальных деревьев и их графических представлений в человеческой практике не ограничивается. Очень полезными оказываются деревья при классификации. Тогда ветвление соответствует выбору того или иного значения признака классификации. Например, можно классифицировать детей в школе по параллелям, внутри параллели по буквам (3 «А» и 3 «Б»), потом по алфавиту или как-то ещё.

В современном компьютерном мире широко распространились деревья ссылок в составе так называемых гипертекстов. Однако деревья ссылок от одного слова к другому существуют и в обычных, бумажных энциклопедиях.

Языковые структуры тоже удобно представлять в виде деревьев.

Полный перебор и деревья

Конструкция полного, исчерпывающего перебора важна в нашем курсе и вообще в жизни. (Представьте себе на секунду поиски пропавшего паспорта в квартире или ровно «той самой» кофточки. В этой ситуации бывает нужно последовательно просмотреть все места, полки, ящики и т. д. Часто вещь находится в самом неожиданном месте, там, куда вы её положили, «чтобы она не пропала». Надеемся, что в реальности вам не приходится заниматься такими поисками.)

Иногда бывает очень нужно сократить перебор, подумать, где вещи точно не может быть, и т. п. Но прежде чем изобретать разные стратегии сокращения перебора, нам следует понять, как организовать действительно полный перебор. С одной стороны, выписывание всех путей дерева является примером полного перебора, с другой стороны, во многих случаях перебор естественно представить в виде перемещения по дереву. Например, в случае поисков в квартире можно соотнести со всей квартирой корневую вершину; следующие вершины — это комнаты квартиры; за комнатами идут шкафы, полки и столы, стоящие в комнатах; в шкафах есть отделения и полки и т. д.