Главная страница «Первого сентября»Главная страница журнала «Информатика»Содержание №18/2008


В мир информатики
Задачник

Ответы, решения, разъяснения

к заданиям, опубликованным в газете
“В мир информатики” № 105 (“Информатика” № 5/2008)

 

1. Задача “Восстановить числа”

Решение

1. Обозначим фигуры (а следовательно, и цифры в них) на схеме, приведенной в условии, буквами:

— причем А, С, D, E, I — нечетные цифры, а B, F, G, H — четные.

2. Четная цифра B больше четырех нечетных цифр (А, С, D и E), значит, B = 8.

3. Нечетные цифры А и D не могут быть равны
9 (т.к. B = 8). Тогда из трех оставшихся нечетных цифр (С, E, I) девятью может быть только I (I > Е и I > С).

Запишем найденные цифры в схему:

 

4. Четная цифра F больше двух оставшихся четных цифр (H и G), значит, F = 6, H = 4, G = 2. Запишем и это:

 

5. Видно, что Е = 5.

6. Остались нечетные цифры А, D и С. Так как А и D больше некоторых значений, то никакая из них не равна 1. Остается, что С = 1. Тогда А = 7, D = 3.

Итак, все решение:

 

Ответы представили:

— Алексейчук Анжела, Батманова Анастасия, Ан-
на К. (фамилия в письме указана неразборчиво), Мясникова Юлия и Ширкина Ирина, г. Нижний Новгород, Детский (подростковый) центр “Агнес”, клуб “Космос”, преподаватель Занозин Д.А.;

— Андронова Мария, Данильчик Павел, Калита Никита, Кривошей Диана, Немчик Андрей, Филиппович Александр и Флакс Тамара, Республика Беларусь, г. Минск, школа № 177, учителя Климкина Е.Г. и Раткевич Т.Н.;

— Андрушко Мария и Кулешова Ксения, г. Орел, лицей № 4, учитель Чапкевич И.М.;

— Аникина Ольга, Артемьев Павел, Бабич Анастасия, Белослудцева Юлия, Воронцова Юлия, Гавшина Анастасия, Главатских Константин, Главатских Мария, Главатских Светлана, Данилов Дмитрий, Ехлаков Дмитрий, Жигалов Денис, Жигалов Руслан, Жигалова Юлия, Иванов Кирилл, Иванов Максим, Ильин Михаил, Ильин Никита, Калинина Галина, Каракулова Дарья, Касимова Анна, Кондратьева Диана, Ложкина Дарья, Мазура Евгения, Максимова Ирина, Малыгин Александр, Небогатиков Никита, Никитина Юлия, Поздеева Анна, Русских Анатолий, Селиверстов Григорий, Селиверстова Татьяна, Селукова Мария, Снигирев Никита, Спешилов Илья, Хохряков А., Худяков Тимур, Яковлева Полина и Якушев Илья, Кезская средняя школа № 1, Удмуртская Республика, учитель Ветошкина Н.В.;

— Башкирова Владислава, Исакова Олеся, Пашкова Светлана и Федоренко Иван, поселок Лимбяяха Новоуренгойского р-на Тюменской обл., школа № 9, учитель Исакова И.С.;

— Белаш Артем и другие учащиеся Академии информатики для школьников при Санкт-Петербургском государственном политехническом университете, преподаватель Ленгауэр Е.И.;

— Бикмайкина Рената, Волгаева Наталия, Кузьмина Анна, Морозов Александр и Полушкин Евгений, Кемлянская средняя школа Ичалковского р-на Республики Мордовия, учитель Силантьев О.П.;

— Бурухин Александр, Куминская средняя школа,
Тюменская область, Ханты-Мансийский автономный округ — Югра, Кондинский р-н, учитель Шишигина О.В.;

— Врублевская Ирина, Гроза Анастасия, Дюбарова Анастасия, Ерош Татьяна, Климентьев Владимир, Колосов Владимир, Кузьмин Евгений, Кулакова Оксана, Лебедева Анастасия, Мельник Кристина и Смолярова Наталья, г. Лесосибирск Красноярского края, поселок Стрелка, школа № 8 им. Константина Филиппова, учитель Лопатин М.А.;

— Гайсина Галия, г. Уфа, Республика Башкортостан, школа № 18, учитель Искандарова А.Р.;

— Галушкова Карина, ученица 2-го класса (в прошлом учебном году) средней школы поселка Надвоицы, Республика Карелия, учитель Богданова Л.М.;

— Горшкова Алина, Литтау Алина, Лукьянова Мария и Телегин Дмитрий, г. Струнино Владимирской обл., школа № 11, учитель Волкова Т.П.;

— Ежова Ольга, Республика Татарстан, Сармановский р-н, поселок Джалиль, школа № 1, учитель Давлетова И.М.;

— Загафуранова Айсылу, средняя школа села Сейтяково Балтачевского р-на, Республика Башкортостан, учитель Загафуранова А.Ф.;

— Закиева Яна и Ямалетдинова Эльмира, г. Уфа, Республика Башкортостан, гимназия № 3, учитель Болдырева С.В.;

— Кузьмин Заур и Шебалов Владимир, средняя школа поселка Татищево, Саратовская обл., Татищевский р-н, учитель Копылова С.В.;

— Лекомцев Денис, средняя школа села Юнда Балезинского р-на Удмуртской Республики, учитель Иванова О.Б.;

— Маркечко Антон, г. Уфа, Республика Башкортостан, гимназия № 3, учитель Галеева Д.М.;

— Никитин Слава, г. Смоленск, школа № 29, учитель Родикова Р.Д.;

Овсянников Антон и Чурсина Наталья, г. Сегежа, Республика Карелия, школа № 5, учитель Меньшиков В.В.;

— Олесова Наталья, средняя школа села Качикатцы Хангаласского улуса, Республика Саха (Якутия), учитель Яковлева М.Д.;

— Пучкина Елена, г. Стерлитамак, Республика Башкортостан, гимназия № 5, учитель Пучкина С.А.;

— Стрибляченко Александр, г. Новочеркасск, Суворовское училище МВД РФ, преподаватель Воронкова О.Б.;

— Шингина Альбина, средняя школа села Ложниково, Омская обл., Тарский р-н, учитель Коровин Д.В.

Заметим, что Мария Андрушко и Ксения Кулешова из г. Орла и Артем Белаш из Санкт-Петербурга для решения задачи разработали компьютерную программу, причем Мария представила программу на двух языках программирования (Паскаль и Си), а Артем, как сообщила его преподаватель Е.И. Ленгауэр, разработал программу всего за 8 минут (включая набор текста).

В некоторых ответах не учитывался (или ошибочно учитывался) знак между цифрами Е и F.

2. Статья “Гармонические числа и… игральные карты”

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

1) определить, каким будет выступ в случае использования колоды из:

— 52 карт;

— миллиона карт;

2) установить, при каком минимальном числе карт величина выступа будет превышать длину одной карты, которая равна двум единицам.

Ответы

Прежде всего заметим, что для того чтобы верхняя карта полностью выступала за край стола, вовсе не нужно очень много карт. Нам нужно ровно столько карт, чтобы величина выступа немного превышала длину одной карты, которая равна двум единицам. А поскольку первым гармоническим числом, которое превышает 2, является H4 = 25/12, то достаточно всего лишь четырех карт.

В случае же 52 карт мы получаем выступ величиной H52 единиц, который оказывается равным H52/2 2,27 длинам карт.

Миллионное гармоническое число равно Н1000000 14,392726, что означает, что стопка из миллиона карт может выступать над краем стола на длину несколько более чем семи карт (всего лишь!).

Литература

1. Гармонические числа. / “В мир информатики” № 96 (“Информатика” № 20/2007).

2. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. М.: Мир, 1998.

3. Задача “Переход по пустыне”

Напомним, что необходимо описать алгоритм действий участников перехода по пустыне, при условии, что путешественник и носильщик могут нести запас пищи и еды на 4 дня на одного человека, для следующих вариантов маршрута:

а) маршрут шестидневный незамкнутый, носильщик находится в его конечном пункте;

б) маршрут семидневный замкнутый;

в) маршрут семидневный незамкнутый, носильщик находится в его конечном пункте.

Решение

1. Вариант а)

Идея решения задачи для такого случая — надо предварительно создать запас еды и воды в конце маршрута пятого дня (в точке F — см. рис. 1). Каким должен быть этот запас?

Можем рассуждать так. Путешественник “самостоятельно” дойдет до точки Е. Туда носильщик должен будет доставить еду и воду.

Находясь в точке F, носильщик должен:

1) добраться до точки Е (требуется V1);

2) обеспечить путешественника едой и водой для перехода до точки F (требуется V1);

3) вернуться вместе с путешественником в точку F (требуется V1).

Рис. 1

Итак, выйдя из точки F в точку Е, носильщик должен иметь с собой V3. Кроме того, путешественнику и его помощнику предстоит переход в конечный (исходный) пункт — точку A. Для этого потребуется еще V2. Значит, в момент перед переходом носильщика из F в точку Е в точке F следует иметь V5. Его можно обеспечить следующим образом. Так как носильщик, придя в точку F из точки A, сможет иметь с собой максимум V3 (V1 будет им израсходован), то V2 надо доставить в точку F заблаговременно. Последнюю задачу решить несложно.

Осталось только синхронизировать действия носильщика и путешественника, чтобы последний не страдал от голода и жажды в точке Е. Так как на создание запаса в точке F требуется два дня и еще два дня нужны для перехода носильщика в точку Е, то он должен начать “работать” в первый день путешествия.

2. Вариант б)

Сначала носильщик (или путешественник) должен заблаговременно создать запас V2 в точке F (см. рис. 1). Решение этой задачи не должно вызвать у читателя затруднений. Последующие действия (считая дни с 1-го) описаны в табл. 1.

3. Вариант в)

Здесь нужно создавать запасы в двух пунктах — в точках G и F (см. рис. 2). Аналогично первой задаче, в момент перед переходом носильщика из точки F в точку Е в точке F следует иметь V5, который позволит обоим участникам перехода вернуться в точку G, где должен быть заблаговременно подготовлен запас V2.

 

Рис. 2

Основные этапы решения задачи:

1. Создание V2 в точке G и возврат в точку А5.

2. Создание V2 в точке F и возврат в точку А, при этом запас в точке G будет использован.

3. Создание V2 в точке G и возврат в точку А.

4. Увеличение запаса в точке F на V2 до V4 и возврат в точку А, при этом запас в точке G будет использован.

5. Создание V2 в точке G и возврат в точку А.

6. Переход носильщика с V3 в точку F. В этот момент у него останется V1 и еще V4 будет находиться в этой точке.

7. Переход носильщика с V3 в точку Е.

8. Переход путешественника и носильщика в точку F.

9. Переход путешественника и носильщика в точку G (они используют V2, оставшийся в точке F).

10. Переход путешественника и носильщика в конечную точку маршрута (они используют V2, имевшийся в точке G).

Можно также на этапе 4 в точке F создать V3, тогда на этапе 6 носильщику придется выйти с V4.

Ответы прислали:

— Баженов Василий и Баженов Михаил, средняя школа села Горелово Тамбовской обл., учитель Шитова Л.А.;

— Гайсина Галия, г. Уфа, Республика Башкортостан, школа № 18, учитель Искандарова А.Р.;

— Деминцев Борис, средняя школа села Сердар, Республика Марий Эл, учитель Чернова Л.И.;

— Мнацаканян Ашот, средняя школа поселка Новопетровский Московской обл., учитель Артамонова В.В.;

— Хотеев Сергей, Москва, гимназия № 1530, учитель Шамшев М.В.;

— Ященко Алексей, г. Ковров Владимирской обл., школа № 43, учитель Федосеев С.А.

Новый вариант задачи

Решите задачу для случая одного носильщика, находящегося в конечном пункте восьмидневного незамкнутого маршрута.

4. Статья “Из одной старой публикации”

Напомним, что в статье описывался метод формирования так называемого “помехоустойчивого кода”, который применялся в ЭВМ первых поколений и заключавшийся в том, что к исходному числу приписывалась (в конце) дополнительная цифра. При этом сумма цифр каждого разряда (включая контрольный дополнительный), умноженных на номера этих разрядов, должна делиться на 11 без остатка.

Определить значение дополнительного разряда для заданного четырехзначного числа n можно следующим образом.

1. Выделить цифры a (первая слева), b, c и d числа n.

2. Вычислить сумму произведений цифр числа на номера разрядов (начиная нумерацию с двойки справа):

S = 5a + 4b + 3c + 2d.

3. Определить ближайшее большее к S число, кратное 11. Это можно сделать по формуле:

К11 = (S div 11 + 1) ? 11,

— где div — операция целочисленного деления.

4. Найти разность R между К11 и S.

Искомая величина dop определяется по схеме:

если R = 11

то

dop := 0

иначе

если R = 10

то

Для заданного числа

код сформировать нельзя

иначе

dop := R

все

все

Вторую задачу (найти количество чисел из диапазона 1–99, для которых формирование кода провести нельзя) решить можно аналогично, подсчитав количество одно- и двузначных чисел, у которых R = 10.

Можно также использовать электронную таблицу Microsoft Excel. Фрагмент листа приведен ниже:

 Искомое значение может быть определено как количество чисел в диапазоне F2:F100, равных 10.

Предлагаем читателям:

1) разработать компьютерную программу формирования 5-значного кода заданного 4-значного числа по описанной методике;

2) оформить лист электронной таблицы Microsoft Excel для решения второй задачи, самостоятельно определив необходимые формулы.

Программу и/или фрагмент листа с формулами, пожалуйста, пришлите в редакцию. Фамилии всех приславших правильные решения будут опубликованы, а лучшие ответы мы поощрим.

Найти и заменить

В текстовом редакторе набран текст:

КРЕСНЫЙ ДАЛ ЛЕСНЫЙ ОТЗЫВ НА ПИРОГ ИЗ ПРЕСНОГО ТЕСТА.

Команда для исправления ошибок должна иметь вид:

1) найти “ЕС”; заменить на “ЕСТ”;

2) найти “ЕСН”; заменить на “ЕСТН”;

3) найти “ЕСНЫ”; заменить на “ЕСТНЫ”;

4) найти “СН”; заменить на “СТН”;

5) найти “С”; заменить на “СТ”.

Укажите номер правильной команды.


3 Так в оригинале. - М.Ц.

4 200 фунтов - две большие зарубки сверху, 30 фунтов - три зарубки снизу слева, 6 фунтов - шесть косых зарубок снизу, 4 шиллинга - четыре меньших зарубок внизу, правее - 3 пенса (три малых зарубки) и 1/2 пенса - один "укол шилом" справа. (Все это показывает использование десятичной системы счета. - М.Ц.)

5 Более детальное выполнение этого и других этапов реализуйте самостоятельно

TopList