Информатика ЕГЭ

Всем здравствуйте. Меня интересует такой вопрос как задание ЕГЭ в Информатике части С, а именно С3.
Не могу сообразить как делать с тремя командами, если условие с двумя, вроде делается легко (научился),а вот с тремя никак не выходит. Не могли бы вы мне объяснить как правильно нужно выполнять это задание — У исполнителя "Калькуятор" три команды: +1, +2, *3. Сколько способов существует, чтобы из числа 1 получить число 12. Или дайте ресурс, где подробно описывается система решения таких задач.
Заранее больше спасибо!

Задача легко сводится к случаю двух первых команд. Вначале заметим, что любая программа может содержать не более двух умножений на 3. Обозначим f(m, n) количество способов, которыми из числа m можно получить число n с помощью команд +1 и +2; заметим также, что f(m, n)=f(1, n-m+1).
Общее число способов складывается из тех, которые не содержат *3 (их будет f(1, 12)), содержат ровно одно умножение на 3 и содержат ровно 2 умножения на 3. Начнём с последней группы.
Начало такой программы:
*3*3 — и затем f(9,12)=f(1,4) способов продолжения;
*3+1*3 — один способ.

Программы, содержащие одно умножение на 3:
*3 — и затем f(3,12)=f(1,10) способов продолжения;
[+1]*3 — и затем f(6,12)=f(1,7) способов продолжения;
[+2]*3 — и затем f(9,12)=f(1,4) способов продолжения;
[+3]*3 — 1 программа.
(В квадратных скобках — общая сумма, прибавленная командами +1, +2 перед умножением на 3.)

Количество префиксов (начал программы перед умножением на 3) определяется так:
[+1]: f(1,2)=1;
[+2}: f(1,3)=2;
[+3}: f(1,4)=3.

Не забудьте учесть f(1,12) "складывающих" программ.

Ну, а вычислять f(1,k) Вы умеете, сами сознались.

Расскажите уже до конца, пожалуйста, а то такой способ первый раз вижу *_*

Что именно? Откуда получились эти оценки (вроде всё изложено исчерпывающе) или как находить f(m, n) (вроде Вы это уже знаете)?

Замечу, что количество программ с умножением на 3 подсчитывалось отдельно, так как, во-первых, умножение на 3, в отличие от двух других команд, чувствительно к начальному значению m, а, во-вторых, их посчитать несложно непосредственно (чем мы и занимались).А вычисление f(m,n) — классическая задача динамического программирования.

вы можете написать просто готовый ответ? Вот вам дана задача — У исполнителя "Калькуятор" три команды: +1, +2, *3. Сколько способов существует, чтобы из числа 1 получить число 12. И вы должны дать полный ответ. Напишите просто ответ, как на экзамене, от начала и до конца :)

Ошибаетесь. Это ВАМ дана задача. И это ВЫ должны дать по лный ответ, как на экзамене, от начала и до конца. Я же могу только помочь.

Наша задача — научиться подсчитать число способов расстановки команд +1 и +2, чтобы в сумме получить заданное натуральное k>=0. Обозначим его g(k), тогда f(1,k)=g(k-1).
Один из способов — записать k команд +1. Остальные способы, если это возможно, содержат хотя бы одну команду +2. Это все программы, которые:
— начинаются с +2; их будет g(k-2), т.к. 2 уже прибавлено, осталось прибавить k-2, а вариации касаются лишь остатка программы;
— начинаются с +1+2, их будет g(k-3);
.........
-- начинаются с +1...+1 [k-2 раз] +2, их будет g(0).

Заметим, что g(0)=g(1)=1 (существует единственная программа, пустая или +1),
g(2)=2: (это программы +1+1 и +2).
Для бОльших значений k имеем рекуррентное соотношение:
g(k)=1+g(k-2)+g(k-3)+...+g(0).
В частности,
g(3)=1+g(1)+g(0)=1+1+1=3;
g(4)=1+g(2)+g(1)+g(0)=1+2+1+1=5 (для проверки: 1111, 211, 22, 121, 112) и т.д.

Осталось вычислить те f(1, k), которые упоминались в # 2.

Когда получите ответ, я сообщу, совпал ли он с моим.

у меня получилось- 225.

У меня тоже :-) Не могли же два умных человека ошибиться одновременно! :-)))

Спасибо за пояснение :)

Шахматные ходы кодируются при помощи символов:1-8,а-h, С(слон), Ф(ферзь), КР(король),Л(ладья,К(конь), +(шах),х(мат),-(пробел). Пешка никак не обозначается. Ходы записываются в виде: Кb1-с3 d7-d6. Для кодирования используется минимальное количество бит. Сколько информации содержит код: Сf1-с4К g8-f6+ ? А) 65 бит, В)65 байт; С) 70 бит; Д) 70 байт

Есть задача – построить множественную регрессию в программе Excel 2010 зависимости курса рубля от стоимости нефти, золота и акций газпрома.

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

Входные данные для построения уже есть.

Мне надо возводить заданное число(переменное) в последовательные степени 2,3,;,...999,1000,... по заданному модулю(переменному). Хочу сделать это в Exel. Я одноразово это научился, а вот, чтобы получилась последовательность- не получается. Помогите.