Программа для Калькулятора это последовательность команд. Сколько различных чисел можно получить из числа 1 с помощью программы, которая содержит ровно 5 команд? icon

Программа для Калькулятора это последовательность команд. Сколько различных чисел можно получить из числа 1 с помощью программы, которая содержит ровно 5 команд?



НазваниеПрограмма для Калькулятора это последовательность команд. Сколько различных чисел можно получить из числа 1 с помощью программы, которая содержит ровно 5 команд?
Дата конвертации17.09.2012
Размер110.48 Kb.
ТипПрограмма

© К. Поляков, 2009-2012

B13 (повышенный уровень, время – 7 мин)


Тема: Анализ дерева решений.

Что нужно знать:

  • уметь строить дерево решений

  • уметь искать одинаковые числа в списке

  • уметь считать разные числа в списке

Пример задания:


У исполнителя Калькулятор две команды:

1. прибавь 3,

2. вычти 2.

Первая из них увеличивает число на экране на 3, вторая – уменьшает его на 2 (отрицательные числа допускаются).

Программа для Калькулятора – это последовательность команд. Сколько различных чисел можно получить из числа 1 с помощью программы, которая содержит ровно 5 команд?

^ Решение (1 способ, построение полного графа решения):

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



  1. теперь посмотрим, что удается получить за 2 шага; учитывая, что (-2+3)=(+3-2), одно из значений повторяется: мы можем получить -1 + 3 = 2 и 4 – 2 = 2, то есть получается не дерево, а граф:



так с помощью программ, содержащих ровно 2 команды, можно получить 3 различных числа

  1. строим еще уровень: программы из 3-х команд дают 4 разных числа:



обратим внимание, что числа на каждом уровне отличаются друг от друга на 5 =(+3-(-2), то есть они не могут повторяться

  1. четвертый уровень дает 5 различных чисел:



  1. и пятый – 6 решений:



  1. Ответ: 6.

Решение (2 способ, краткий):

  1. как следует из приведенных построений, если система команд исполнителя состоит из двух команд сложения/ вычитания, то все возможные программы, содержащие ровно N команд , дают N+1 различных чисел

  2. Ответ: 6.

Решение (3 способ, Л.В. Зенцова, лицей № 36 ОАО "РЖД" г.Иркутска):

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

  2. поэтому существует всего 6 возможных программ, состоящих ровно из 5 команд (с точностью до перестановки):
    11111
    11112
    11122
    11222
    12222
    22222

  3. Ответ: 6.

^

Ещё пример задания:


У исполнителя Калькулятор две команды:

1. прибавь 1

2. умножь на 2.

Первая из них увеличивает число на экране на 1, вторая – удваивает его.

Программа для Калькулятора – это последовательность команд. Сколько различных чисел можно получить из числа 2 с помощью программы, которая содержит ровно 4 команд?

^ Решение (1 способ, построение полного графа решения):

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



  1. теперь посмотрим, что удается получить за 2 шага:



в отличие от предыдущей задачи, здесь порядок выполнения операций влияет на результат, поэтому пока все числа получаются разные

  1. делаем 3-й шаг, получаем 8 разных чисел:



  1. на 4-ом шаге рассматриваем все возможные программы из 4-х команд, получаем числа

6, 10, 9, 16, 8, 14, 13, 24, 7, 12, 11, 20, 10, 18, 17, 32

  1. здесь всего 16 чисел, но одно из них (10) повторяется 2 раза, а остальные встречаются по 1 разу, поэтому получаем 15 различных чисел

  2. Ответ: 15.
^

Ещё пример задания (ege.yandex.ru):


У исполнителя Калькулятор две команды:

1. прибавь 6

2. вычти 3.

Первая из них увеличивает число на экране на 6, вторая – уменьшает на 3. Если в ходе вычислений появляется отрицательное число, он выходит из строя и стирает написанное на экране.

Программа для Калькулятора – это последовательность команд. Сколько различных чисел можно получить из числа 1 с помощью программы, которая содержит ровно 10 команд?

Решение:

  1. особенность этой задачи – у дополнении к условию: «^ Если в ходе вычислений появляется отрицательное число, он выходит из строя и стирает написанное на экране»

  2. сначала решим задачу без этого ограничения; поскольку две команды 1 и 2 можно переставлять (последовательное применение команд 1 и 2 дает тот же результат, что и последовательное применение команд 2 и 1), количество различных чисел, которые можно получить с помощью программы из N = 10 команд равно N+1 = 11 (см. разборы задач, приведенные выше)

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

  4. минимальное число получается, если применить к начальному числу 10 команд 2:

1 – 10·3 = –29

  1. соседние числа в дереве (см. выше) отличаются на 6 – (–3) = 9, поэтому эти 11 чисел

–29 –20 –11 –2 7 16 25 34 43 52 61

  1. из них только 7 чисел положительные

  2. Ответ: 7.

Решение (2 способ):

  1. заметим, что поскольку две команды 1 и 2 можно переставлять (последовательное применение команд 1 и 2 дает тот же результат, что и последовательное применение команд 2 и 1), количество различных чисел, которые можно получить с помощью программы из N = 10 команд равно N+1 = 11 (см. разборы задач, приведенные выше)

  2. разница между соседними числами равна (+6)-(-3)=9 (команды «+6» и «-3»)

  3. начальное число – 1, наибольшее число можно получить, применив 10 команд увеличения на 6; получается число

1 + 10·6 = 61


  1. строим ряд чисел – арифметическую прогрессию с разностью (–9):

61 52 43 34 25 16 7 …

все остальные значения отрицательные

  1. таким образом, можно получить только 7 положительных чисел

  2. это значение можно посчитать сразу, не выписывая все числа; ответим на вопрос «Сколько раз можно отнять 9 от числа 61, чтобы получить первое отрицательное число» – получим 7, так как 61 – 9·7 = –2

  3. Ответ: 7.

Решение (3 способ, неравенство, А.А. Серокурова, лицей №6, г. Тольятти):

  1. по условию программа содержит только операции сложения («+6») и вычитания («-3»), которые можно переставлять, не меняя результат

  2. поэтому число, получаемое в результате выполнения некоторой программы из числа 1, можно представить в виде



где – количество команд «+6», а – количество команд «-3»

  1. поскольку по условию всего в программе 10 команд, получаем, что дает



  1. нам требуется определить, сколько неотрицательных чисел может быть получено таким образом, поэтому получаем неравенство



  1. решая последнее неравенство, получаем

  2. поскольку – целое число, получаем

  3. с другой стороны, количество команд «-3» не может быть меньше нуля, поэтому



  1. очевидно, что в этом диапазоне находятся 7 значений (от 0 до 6 включительно), что позволяет получить 7 различных неотрицательных чисел

  2. Ответ: 7.
^

Ещё пример задания:


У исполнителя Акробат три команды:

1. вверх

2. влево

3. вправо

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

Решение (1 способ, уравнение, перебор):

  1. Акробат перемещается по клетчатой доске, поэтому можно рассматривать его движение как изменение координат по осям X и Y

  2. пусть – количество команд «влево», – количество команд «вправо» и - количество команд «вверх». Тогда изменения координат вычисляются как



  1. В программе 4 команды, поэтому

  2. поскольку перемещение Акробата по оси Y определяется только значением , можно зафиксировать (предположить, что оно равно какому-то числу) и при этих условиях найти, сколько есть таких клеток, в которые Акробат может попасть при этом ; затем останется сложить все результаты для всех возможных значений

  3. пусть , тогда и ; при этом получаем изменение координаты по оси Х:



  1. при условии, что возможно 5 разных допустимых целых значений , каждое из которых даёт своё значение ; поэтому при есть 5 таких клеток

  2. аналогично находим, что при существует 4 клетки, при есть 3 клетки и т.д.; увеличение на 1 приводит к уменьшению числа достижимых клеток на 1; при остается одна единственная клетка;

  3. складываем: 5 + 4 + 3 + 2 + 1 = 15.

  4. Ответ: 15.

  5. в общем виде: если программа для Акробата содержит команд, то число достижимых клеток равно (по формуле суммы членов арифметической прогрессии):




^

Задачи для тренировки1:


  1. У исполнителя Калькулятор две команды:

1. прибавь 2

2. прибавь 3.

Первая из них увеличивает число на экране на 2, вторая – на 3. Сколько различных чисел можно получить из числа 2 с помощью программы, которая содержит ровно 10 команд?

  1. У исполнителя Калькулятор две команды:

1. прибавь 1

2. прибавь 2.

Первая из них увеличивает число на экране на 1, вторая – на 2. Сколько различных чисел можно получить из числа 2 с помощью программы, которая содержит не более 4 команд?

  1. У исполнителя Калькулятор две команды:

1. прибавь 2

2. умножь на 3.

Первая из них увеличивает число на экране на 2, вторая – утраивает его. Сколько различных чисел можно получить из числа 2 с помощью программы, которая содержит ровно 3 команды?

  1. У исполнителя Калькулятор две команды:

1. прибавь 2

2. умножь на 3.

Первая из них увеличивает число на экране на 2, вторая – утраивает его. Сколько различных чисел можно получить из числа 2 с помощью программы, которая содержит не более 4 команд?

  1. У исполнителя Калькулятор две команды:

1. прибавь 1

2. прибавь 4.

Первая из них увеличивает число на экране на 1, вторая – на 4. Сколько различных чисел можно получить из числа 2 с помощью программы, которая содержит не более 3 команд?

  1. У исполнителя Калькулятор две команды:

1. умножь на 2

2. умножь на 3.

Первая из них умножает число на экране на 2, вторая – утраивает его. Сколько различных чисел можно получить из числа 2 с помощью программы, которая содержит ровно 3 команды?

  1. У исполнителя Калькулятор две команды:

1. умножь на 2

2. умножь на 3.

Первая из них умножает число на экране на 2, вторая – утраивает его. Сколько различных чисел можно получить из числа 2 с помощью программы, которая содержит не более 3 команд?

  1. У исполнителя Калькулятор две команды:

1. прибавь 4,

2. вычти 3.

Первая из них увеличивает число на экране на 4, вторая – уменьшает его на 3 (отрицательные числа допускаются). Программа для Калькулятора – это последовательность команд. Сколько

различных чисел можно получить из числа 1 с помощью программы, которая содержит ровно 7 команд?

  1. У исполнителя Калькулятор две команды:

1. прибавь 4,

2. вычти 3.

Первая из них увеличивает число на экране на 4, вторая – уменьшает его на 3. Если в ходе вычислений появляется отрицательное число, он выходит из строя и стирает написанное на экране. Программа для Калькулятора – это последовательность команд. Сколько различных чисел можно получить из числа 0 с помощью программы, которая содержит ровно 17 команд?

  1. У исполнителя Калькулятор две команды:

1. прибавь 2,

2. вычти 4.

Первая из них увеличивает число на экране на 2, вторая – уменьшает его на 4. Если в ходе вычислений появляется отрицательное число, он выходит из строя и стирает написанное на экране. Программа для Калькулятора – это последовательность команд. Сколько различных чисел можно получить из числа 5 с помощью программы, которая содержит ровно 20 команд?

  1. У исполнителя Калькулятор две команды:

1. прибавь 3,

2. вычти 2.

Первая из них увеличивает число на экране на 3, вторая – уменьшает его на 2. Если в ходе вычислений появляется отрицательное число, он выходит из строя и стирает написанное на экране. Программа для Калькулятора – это последовательность команд. Сколько различных чисел можно получить из числа 2 с помощью программы, которая содержит ровно 18 команд?

  1. У исполнителя Калькулятор две команды:

1. прибавь 5,

2. вычти 3.

Первая из них увеличивает число на экране на 5, вторая – уменьшает его на 3. Если в ходе вычислений появляется отрицательное число, он выходит из строя и стирает написанное на экране. Программа для Калькулятора – это последовательность команд. Сколько различных чисел можно получить из числа 4 с помощью программы, которая содержит ровно 30 команд?

  1. У исполнителя Калькулятор две команды:

1. прибавь 3,

2. вычти 4.

Первая из них увеличивает число на экране на 3, вторая – уменьшает его на 4. Если в ходе вычислений появляется отрицательное число, он выходит из строя и стирает написанное на экране. Программа для Калькулятора – это последовательность команд. Сколько различных чисел можно получить из числа 5 с помощью программы, которая содержит ровно 15 команд?

  1. У исполнителя Калькулятор две команды:

1. прибавь 3,

2. вычти 2.

Первая из них увеличивает число на экране на 3, вторая – уменьшает его на 2. Если в ходе вычислений появляется отрицательное число, он выходит из строя и стирает написанное на экране. Программа для Калькулятора – это последовательность команд. Сколько различных чисел можно получить из числа 3 с помощью программы, которая содержит ровно 25 команд?

  1. У исполнителя Калькулятор две команды:

1. прибавь 4,

2. вычти 2.

Первая из них увеличивает число на экране на 4, вторая – уменьшает его на 2. Если в ходе вычислений появляется отрицательное число, он выходит из строя и стирает написанное на экране. Программа для Калькулятора – это последовательность команд. Сколько различных чисел можно получить из числа 8 с помощью программы, которая содержит ровно 16 команд?

  1. У исполнителя Калькулятор две команды:

1. умножь на 6,

2. подели на 2.

Первая из них увеличивает число на экране в 6 раз, вторая – уменьшает его в 2 раза. Программа для Калькулятора – это последовательность команд. Сколько различных чисел можно получить из числа 512 с помощью программы, которая содержит ровно 6 команд?

  1. У исполнителя Калькулятор две команды:

1. умножь на 15,

2. подели на 2.

Первая из них увеличивает число на экране в 15 раз, вторая – уменьшает его в 2 раза. Программа для Калькулятора – это последовательность команд. Сколько различных чисел можно получить из числа 4096 с помощью программы, которая содержит ровно 12 команд?

  1. У исполнителя Калькулятор две команды:

1. умножь на 8,

2. подели на 3.

Первая из них увеличивает число на экране в 8 раз, вторая – уменьшает его в 3 раза. Программа для Калькулятора – это последовательность команд. Сколько различных чисел можно получить из числа 729 с помощью программы, которая содержит ровно 6 команд?

  1. У исполнителя Акробат три команды:

1. вверх

2. вниз

3. влево

4. вправо

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

  1. Исполнитель Акробат «живет» на числовой оси. Система команд исполнителя:

1. Вперед 4 (Акробат прыгает вперед на 4 единицы)

2. Назад 3 (Акробат прыгает назад на 3 единицы)

Отрицательные числа допускаются. Программа для Акробата – это последовательность команд. Начальное положение Акробата – точка 40. В скольких различных точках может оказаться Акробат поле выполнения различных программ, которые содержат ровно 10 команд?

  1. Исполнитель Акробат «живет» на числовой оси. Система команд исполнителя:

^ 1. Вперед 4 (Акробат прыгает вперед на 4 единицы)

2. Назад 5 (Акробат прыгает назад на 5 единиц)

Отрицательные числа допускаются. Программа для Акробата – это последовательность команд. Начальное положение Акробата – точка 4. В скольких различных точках может оказаться Акробат поле выполнения различных программ, которые содержат ровно 8 команд?


1 Источники заданий:

  1. Тренировочные работы МИОО 2011-2012.

  2. Авторские разработки.




Похожие:

Программа для Калькулятора это последовательность команд. Сколько различных чисел можно получить из числа 1 с помощью программы, которая содержит ровно 5 команд? iconПрограмма для Утроителя это последовательность команд. Сколько есть программ, которые число 1 преобразуют в число 20?
Заметим, что количество вариантов меняется только в тех столбцах, где n делится на 3, поэтому из всей таблицы можно оставить только...
Программа для Калькулятора это последовательность команд. Сколько различных чисел можно получить из числа 1 с помощью программы, которая содержит ровно 5 команд? iconТема : Поиск алгоритма минимальной длины для исполнителя
Выполняя первую из них, Калькулятор прибавляет к числу на экране 3, а выполняя вторую, умножает его на Запишите порядок команд в...
Программа для Калькулятора это последовательность команд. Сколько различных чисел можно получить из числа 1 с помощью программы, которая содержит ровно 5 команд? iconТема : Поиск алгоритма минимальной длины для исполнителя
Выполняя первую из них, Калькулятор прибавляет к числу на экране 3, а выполняя вторую, умножает его на Запишите порядок команд в...
Программа для Калькулятора это последовательность команд. Сколько различных чисел можно получить из числа 1 с помощью программы, которая содержит ровно 5 команд? iconГрафическое «перо» – draw
В строке символов записывается последовательность графических команд, причём каждая команда состоит из латинских букв и целых чисел....
Программа для Калькулятора это последовательность команд. Сколько различных чисел можно получить из числа 1 с помощью программы, которая содержит ровно 5 команд? iconОсновные конструкции, используемые при получении случайных чисел
Получить 10 случайных целых чисел в интервале от 0 до 100. (Повторить запуск программы несколько раз – числа будут разные)
Программа для Калькулятора это последовательность команд. Сколько различных чисел можно получить из числа 1 с помощью программы, которая содержит ровно 5 команд? iconМатериал из Википедии — свободной энциклопедии
Числа Бернулли — последовательность рациональных чисел B0,B1, найденная Я. Бернулли в связи с вычислением суммы одинаковых степеней...
Программа для Калькулятора это последовательность команд. Сколько различных чисел можно получить из числа 1 с помощью программы, которая содержит ровно 5 команд? iconXiii чемпионат Республики Беларусь по шахматам среди клубных команд и команд коллективов Минск, 4-8 марта 2011г

Программа для Калькулятора это последовательность команд. Сколько различных чисел можно получить из числа 1 с помощью программы, которая содержит ровно 5 команд? iconВнеклассное мероприятие Информатика это интересно" 5 классы 26 января 2009 г Представление команд Эстафета 1 "Волшебные ребусы"
На столе стояли 3 стакана с вишней. Оксана съела один стакан вишни. Сколько стаканов осталось?
Программа для Калькулятора это последовательность команд. Сколько различных чисел можно получить из числа 1 с помощью программы, которая содержит ровно 5 команд? iconПлан занятия: Теоретическая часть
Основные средства определения форматов представления информации и таблиц Excel сосредоточены в меню Формат. С помощью соответствующих...
Программа для Калькулятора это последовательность команд. Сколько различных чисел можно получить из числа 1 с помощью программы, которая содержит ровно 5 команд? iconЭкспериментальное народное самолетостроение
Алгоритм система точных и понятных предписаний (команд, директив) о содержании и последовательности выполнения конечного числа действий,...
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©podelise.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы

Разработка сайта — Веб студия Адаманов