- •Пример задания:
- •Еще пример задания:
- •Еще пример задания:
- •Еще пример задания:
- •Еще пример задания:
- •Пример задания:
- •1. Прибавь 3
- •2. Умножь на 4
- •Еще пример задания:
- •1. Сдвинь влево
- •2. Вычти 1
- •Еще пример задания:
- •Еще пример задания:
- •Еще пример задания:
- •Пример задания:
- •1. Прибавь 1
- •2. Умножь на 3
- •Пример задания:
- •1. Прибавь 3,
- •2. Вычти 2.
- •Ещё пример задания:
- •1. Прибавь 1
- •2. Умножь на 2.
- •Ещё пример задания (ege.Yandex.Ru):
- •1. Прибавь 6
- •2. Вычти 3.
- •Пример задания:
- •Ещё пример задания:
- •Еще пример задания:
Пример задания:
У исполнителя Калькулятор две команды:
1. Прибавь 3,
2. Вычти 2.
Первая из них увеличивает число на экране на 3, вторая – уменьшает его на 2 (отрицательные числа допускаются).
Программа для Калькулятора – это последовательность команд. Сколько различных чисел можно получить из числа 1 с помощью программы, которая содержит ровно 5 команд?
Решение (1 способ, построение полного графа решения):
будем строить дерево решений следующим образом: выясним, какое число можно получить из начального значения 1 за 1 шаг:
теперь посмотрим, что удается получить за 2 шага; учитывая, что (-2+3)=(+3-2), одно из значений повторяется: мы можем получить -1 + 3 = 2 и 4 – 2 = 2, то есть получается не дерево, а граф:
так с помощью программ, содержащих ровно 2 команды, можно получить 3 различных числа
строим еще уровень: программы из 3-х команд дают 4 разных числа:
обратим внимание, что числа на каждом уровне отличаются друг от друга на 5 =(+3-(-2), то есть они не могут повторяться
четвертый уровень дает 5 различных чисел:
и пятый – 6 решений:
Ответ: 6.
Решение (2 способ, краткий):
как следует из приведенных построений, если система команд исполнителя состоит из двух команд сложения/ вычитания, то все возможные программы, содержащие ровно N команд , дают N+1 различных чисел
Ответ: 6.
Решение (3 способ, Л.В. Зенцова, лицей № 36 ОАО "РЖД" г.Иркутска):
для сложения справедлив переместительный (коммутативный) закон, значит, порядок команд в программе не имеет значения
поэтому существует всего 6 возможных программ, состоящих ровно из 5 команд (с точностью до перестановки): 11111 11112 11122 11222 12222 22222
Ответ: 6.
Ещё пример задания:
У исполнителя Калькулятор две команды:
1. Прибавь 1
2. Умножь на 2.
Первая из них увеличивает число на экране на 1, вторая – удваивает его.
Программа для Калькулятора – это последовательность команд. Сколько различных чисел можно получить из числа 2 с помощью программы, которая содержит ровно 4 команд?
Решение (1 способ, построение полного графа решения):
будем строить дерево решений следующим образом: выясним, какое число можно получить из начального значения 1 за 1 шаг:
теперь посмотрим, что удается получить за 2 шага:
в отличие от предыдущей задачи, здесь порядок выполнения операций влияет на результат, поэтому пока все числа получаются разные
делаем 3-й шаг, получаем 8 разных чисел:
на 4-ом шаге рассматриваем все возможные программы из 4-х команд, получаем числа
6, 10, 9, 16, 8, 14, 13, 24, 7, 12, 11, 20, 10, 18, 17, 32
здесь всего 16 чисел, но одно из них (10) повторяется 2 раза, а остальные встречаются по 1 разу, поэтому получаем 15 различных чисел
Ответ: 15.
Ещё пример задания (ege.Yandex.Ru):
У исполнителя Калькулятор две команды:
1. Прибавь 6
2. Вычти 3.
Первая из них увеличивает число на экране на 6, вторая – уменьшает на 3. Если в ходе вычислений появляется отрицательное число, он выходит из строя и стирает написанное на экране.
Программа для Калькулятора – это последовательность команд. Сколько различных чисел можно получить из числа 1 с помощью программы, которая содержит ровно 10 команд?
Решение:
особенность этой задачи – у дополнении к условию: «Если в ходе вычислений появляется отрицательное число, он выходит из строя и стирает написанное на экране»
сначала решим задачу без этого ограничения; поскольку две команды 1 и 2 можно переставлять (последовательное применение команд 1 и 2 дает тот же результат, что и последовательной применение команд 2 и 1), число различных чисел, которые можно получить с помощью программы из N = 10 команд равно N+1 = 11 (см. разборы задач, приведенные выше)
проблема в том, что из этих 11 чисел нужно выбросить все отрицательные, так как при появлении отрицательного числа исполнитель выходит из строя
минимальное число получается, если применить к начальному числу 10 команд 2:
1 – 10·3 = –29
соседние числа в дереве (см. выше) отличаются на 6 – (–3) = 9, поэтому эти 11 чисел
–29 –20 –11 –2 7 16 25 34 43 52 61
из них только 7 чисел положительные
Ответ: 7.
Решение (2 способ):
заметим, что поскольку две команды 1 и 2 можно переставлять (последовательное применение команд 1 и 2 дает тот же результат, что и последовательной применение команд 2 и 1), число различных чисел, которые можно получить с помощью программы из N = 10 команд равно N+1 = 11 (см. разборы задач, приведенные выше)
разница между соседними числами равна (+6)-(-3)=9 (команды +6 и -3)
начальное число – 1, наибольшее число можно получить, применив 10 команд увеличения на 6; получается число
1 + 10·6 = 61
строим ряд чисел – арифметическую прогрессию с разностью (–9):
61 52 43 34 25 16 7 …
все остальные значения отрицательные
таким образом, можно получить только 7 положительных чисел
это значение можно посчитать сразу, не выписывая все числа; ответим на вопрос «Сколько раз можно отнять 9 от числа 61, чтобы получить первое отрицательное число» – получим 7, так как 61 – 9·7 = –2
Ответ: 7.
Тема: Кодирование и декодирование информации.
Что нужно знать:
кодирование – это перевод информации с одного языка на другой (запись в другой системе символов, в другом алфавите)
обычно кодированием называют перевод информации с «человеческого» языка на формальный, например, в двоичный код, а декодированием – обратный переход
один символ исходного сообщения может заменяться одним символом нового кода или несколькими символами, а может быть и наоборот – несколько символов исходного сообщения заменяются одним символом в новом коде (китайские иероглифы обозначают целые слова и понятия)
кодирование может быть равномерное и неравномерное; при равномерном кодировании все символы кодируются кодами равной длины; при неравномерном кодировании разные символы могут кодироваться кодами разной длины, это затрудняет декодирование
закодированное сообщение можно однозначно декодировать с начала, если выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова;
закодированное сообщение можно однозначно декодировать с конца, если выполняется обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова;
условие Фано – это достаточное, но не необходимое условие однозначного декодирования.