Задание 6

1. Общие сведения

2. Пример задания

3. Другие задачи

4. История

1. Общие сведения

Сложность: базовая.

Примерное время решения (для тех, кто будет выполнять часть 2):  2 минуты

Тема: Алгоритмы и программирование

Подтема: Анализ алгоритма на естественном языке

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

Замечание. Частным случаем выполнения алгоритма является проверка истинности условия.

 

Общий вид задания:

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

Приводятся 4 объекта (числа, слова и т.п.).

Примеры вопросов:

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

2) Определить, какой из приведенных объектов может (не может) приводить к заданному результату.

 

Замечание. Можно накладывать дополнительные условия (наибольший, наименьший и т.п.). Тогда вместо задачи формата А «указать, кто принадлежит заданному множеству» получаем задачу формата Б – указать (единственный!) элемент множества, удовлетворяющий дополнительному условию.

2. Пример задания

2.1. Условие задачи.

Задача 2012-А5-1.

Автомат получает на вход два трехзначных числа. По этим числам строится новое число по следующим правилам.

1. Вычисляются три числа – сумма старших разрядов заданных трехзначных чисел, сумма средних разрядов этих чисел, сумма младших разрядов.

2. Полученные три числа записываются друг за другом в порядке убывания (без разделителей).

Пример. Исходные трехзначные числа:  835, 196. Поразрядные суммы: 9, 12, 11. Результат: 12119

Определите, какое из следующих чисел может быть результатом работы автомата.

1) 151303 2) 161410 3) 191615 4) 121613

 

2.2. Набросок решения.

Сумма двух однозначных чисел может быть либо однозначным числом (от 0 до 9), либо двузначным числом – от 10 до 9+9=18.

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

а) все они находятся в  отрезке от 10 до 18;

б) каждое следующее (слева направо) число меньше или равно предыдущему.

 

Рассмотрим указанные в условии числа.

1)    Не подходит. Третья пара начинается с нуля (не выполнено условие а) )

2)    ОК. Возможные исходные трехзначные числа: 875 и 875, 999 и 751 и т.п.

3)    Не подходит. Первая пара равна 19 (не выполнено условие а) )

4)    Не подходит. Вторая пара больше первой (не выполнено условие б) )

 

2.3. Рекомендации для учителей: как разбирать задачу с учениками

Эти рекомендации – не догма, а попытка сделать выводы из собственного опыта. Ждем комментариев и Ваших рекомендаций.

А. Сильные ученики.

1. Скорее всего, они и так решат эту задачу.

2. Если нет – обратите их внимание на ключевые моменты:

- разбиение шестизначного числа на пары;

- какие пары невозможны (19 и больше, а также те, которые начинаются с нуля),  лучше, если школьники сами сформулируют эти условия.

3. Придумывайте свои подходы и пробуйте их. J

 

Б. Не столь сильные ученики.

1. Первую (может быть, главную) трудность составляет само условие задачи. Предложите ученикам выполнить описанный алгоритм для нескольких входных данных. Убедитесь, что все выполнено правильно.

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

3. Предложите ученикам придумать число, которое НЕ может быть результатом работы алгоритма. Даже, если они ничего не придумают, это поможет понимать Ваши объяснения.

4. Обратите внимание учеников на то, что шестизначные числа однозначно разбиваются на три двузначных.

5. Выясните с учениками,  какие пары невозможны (19 и больше, а также те, которые начинаются с нуля),  лучше, если школьники сами сформулируют эти условия.

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

7. Придумывайте свои подходы и пробуйте их. J

 

2.4. Рекомендации для учеников: как решать подобные задачи

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

1. Прочитайте условие задачи. Попробуйте придумать условия, необходимые и достаточные для того, чтобы объект мог быть результатом работы алгоритма (для задачи 2012-А05-1 – это условия а) и б) ). На худой конец – сформулируйте необходимые условия, достаточность  в общем виде доказывать не обязательно. Если не смогли придумать необходимых условий – не тратьте на это много времени (не более 1 минуты). Начинайте смотреть объекты-кандидаты.

2. По очереди рассмотрите все объекты-кандидаты. Для каждого объекта попробуйте придумать входные данные, которые дают на выходе этот объект. Если получилось, - задача почти решена (см. п.3).  Если не получилось,  попробуйте доказать, что это невозможно. Если доказали, вычеркиваем объект из списка кандидатов и идем дальше. Если нет, - потом вернемся к этому объекту.

3. Что делать, если нашли объект, который удовлетворяет условию задачи. Лучше – просмотреть остальные объекты и убедиться, что они под условие не подходят. Если так не получится – можно найти у себя ошибку и исправить ее.

4. Что делать, если не удалось вычеркнуть все объекты, кроме одного, а для этого одного доказать, что для него условие выполнено. Если из оставшихся есть ровно один объект, для которого Вы можете доказать (или просто уверены), что условие выполнено, - выбирайте его. Если таких объектов несколько или ни одного - придется угадывать. Удачи!

Замечание. Похожие соображения применимы при решении многих задач группы А. См. TacticA.doc.

 

2.5. Клоны задачи 2012-А5-1.

Ниже приведены еще четыре варианта задачи 2012-А5-1. Приведены только варианты ответов, основной текст – тот же, что в п.2.1.

 

А. 1) 171511 2) 201615 3) 171618 4) 151309 Б.  1) 211610 2) 181415 3) 121008 4) 171110 В.  1) 151314 2) 161101 3) 181614 4) 191817

Г.  1) 121101 2) 121110 3) 111012 4) 221211

Правильные ответы:

А: 1; Б: 4; В: 3; Г:2.

3. Другие задачи

Задача 2012-А5-2.

Автомат получает на вход два трехзначных числа. По этим числам строится новое число по следующим правилам.

1. Если в числах есть цифра, большая, чем 7, то автомат прекращает работу, не выдавая результата.

2. Вычисляются три числа – сумма старших разрядов заданных трехзначных чисел, сумма средних разрядов и  сумма их младших разрядов.

3. Полученные три числа записываются друг за другом в порядке невозрастания (без разделителей).

Пример. Исходные трехзначные числа:  153, 351. Поразрядные суммы: 4, 10, 4.  Результат: 1044.

Определите, какое из следующих чисел может быть результатом работы автомата (даны 4 варианта задачи).

А.  1) 131207 2) 141210 3) 111012 4) 151211

Б.  1) 131211 2) 171412 3) 141112 4) 121009

В.  1) 161310 2) 141113 3) 131107 4) 121110

Г.  1) 121011 2) 121101 3) 121110 4) 211211

Правильные ответы:

А:2; Б: 1; В: 4; Г: 3.

 

Задача 2012-А5-3.

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

Пример. Исходные цифры: А, А, 3. Суммы: А+А = 14; A+3 = D. Результат: 14D.

Укажите, какое из следующих чисел может быть получено в результате (даны 4 варианта задачи).

А. 1) 812 2) AC 3) 86 4) 1F1

Б. 1) 905 2) F5 3) G6 4) 211

В. 1) G3 2) 1F1 3) B0B 4) 1A10

Г. 1) 1B11 2) 11B1 3) 707 4) 1F10

Правильные ответы:

А:3; Б: 2; В: 4; Г: 1.

 

 

Задача 2012-А5-4.

Саша и Женя играют в такую игру. Саша пишет слово русского языка. Женя заменяет в нем каждую букву на другую букву так, чтобы было выполнено такие правила.

  1. Гласная буква меняется на согласную, согласная – на гласную.
  2. В получившемся слове буквы следуют в алфавитном порядке.

Пример. Саша написала: МАМА. Женя может написать, например, ЕНОТ или ИКУЦ. Но не может написать ПАПА или ОРЁЛ.

Варианты заданий.

А. Саша написал: АСЯ.

Укажите, какое из следующих слов может написать Женя

1) КОТ 2) РАК 3) СОЯ 4) КОРТ

 

Б. Саша написала: ТИМ.

Укажите, какое из следующих слов может написать Женя

1) АНТ 2) АНУШ 3) АНЯ 4) ОЛЯ

 

В. Саша написала: СОЯ.

Укажите, какое из следующих слов может написать Женя

1) ЕЛЬ 2) ИКС 3) ИСК 4) ДЕЛО

 

Правильные ответы:

А: 1;  Б: 3, В: 2.

 

Задача 2012-А5-5.

Автомат получает на вход трехзначное число. По этому числу строится новое число по следующим правилам.

  1. Перемножаются первая и вторая, а также вторая и третья цифры.

2.   Полученные два числа записываются друг за другом в порядке убывания (без разделителей).

Пример. Исходное трехзначное числа:  157. Произведения: 1*5 = 5; 5*7 = 35.   Результат: 355.

Определите, какое из следующих чисел может быть результатом работы автомата (даны 4 варианта задачи).

А.  1) 197 2) 187 3) 186 4) 777

Б.  1) 1214 2) 1612 3) 3512 4) 555

В.  1) 2112 2) 1221 3) 2212 4) 2512

Г.  1) 1514 2) 8824 3) 2428 4) 2821

 

Правильные ответы:

А:3; Б: 2; В: 1; Г: 4.

 

 
 

5 комментариев

  1. Алексей:

    не Терпенье и труд, а Терпение и труд. (в правом верхнем углу)

  2. Т.С.:

    Задача 2012-А5-2. Верные ответы:
    вариант А. - 2 и 4; вариант Б. - 1 и 2; вариант В. - 1 и 4

  3. Т.С.:

    Задача 2012-А5-2. По условию 2 поразрядные суммы записываются по возрастанию, в примере к задаче уже 3 поразрядные суммы записаны по возрастанию, "правильные" ответы дают 3 числа по убыванию.

    Задача 2012-А5-3. В варианте Г 2) 11B также является правильным ответом

    Спасибо за сайт.

    • editor:

      Спасибо, вроде все исправил 🙂
      Рад, что Вам сайт понравился. Шлите еще замечания и пожелания!

 
 

Что думаете?

 




 
 

 
 
Яндекс.Метрика