Help! Informatica! Kal'kulator!

Question

Help! Informatica! Kal'kulator!

---

Answer 1

3+(2+2+2+2+2+2+2+1)=18. Это восемь значений одна команда. каждая двойка кроме предпосленей может разбиваться на (1+1) и их 6, т.е. надо рассмотреть все случаи изменения, значит в каждом случае заменять 2 н 1+1 и у нас выходит 21 команда плюс самая первая, значит ответ 22 команды

Comments

Не думаю, что это правильная схема. Например, программу 3 + (1 + 2 + 1 + 2 + 2 + 2 + 2 + 2 + 1) = 18 нельзя получить, просто разбивая двойки. Кроме того, если вы хотите посчитать количество способов разбить шесть двоек, то оно равно 2^6 = 64, так как каждую из них можно разбивать или не разбивать -> каждая может пребывать в одном из двух состояний -> всего 2^6

---

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

---

возьмем самую длинную цепочку 3+(1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+2+1)=18 тут 14 цифр, тогда будем наоборот собирать единицы в двойки, каждые две еденицы в интервале 1 могут привратиться в двойку, т.е. надо рассмотреть все случаи и будет точный отвеь. к сожалению я не знаю быстрооо алгоритма, но если у вас есть время вы можите подсчитать, а ответ выйдет точный

---

Не совсем понял насчет повторений, ну да ладно. (Скажем, с двумя двойками получилось бы так: 2+2, 2+1+1, 1+1+2, 1+1+1+1 - 4 = 2^2 варианта). И еще надо учесть, что последняя команда не обязательно +1. На самом деле, мне кажется, все егэшные задачи на эту тему решаются по принципу, что, скажем, количество программ из 3 в 12 = количество программ из 3 в 11 (приписываем +1 в конце - получаем 3 -> 12) + количество программ из 3 в 10 (приписываем в конце +2). ...

---

... Соответственно, здесь можно по отдельности посчитать количество программ из 3 в 15 (если последние две команды: +2 +1) и из 3 в 14 (если +2 + 2), а потом их сложить. Считается все довольно просто, если, скажем, построить таблицу количества программ, переводящих 3 в X. 3:1, 4:1 , 5:2, 6:3. 7:5, 8:8, 9:13, 10:21 и т.д. Кстати, это числа Фибоначчи

---

А еще можно заметить, что к такому же ответу можно прийти, если просто посчитать количество программ из 3 в 16. Действительно, возьмем любую такую программу и вставим команду "+2" на предпоследнюю позицию. Получится программа из 3 в 18, соответствующая условию

---

Интересно, числа Фибоначм еще не прошел, но обязательно про это прочитаю. Кстати я смотря вам не очень нужна была помощь, ведь вы достаточно эрудированы, чтобы самостоятельно релить задачу=)

---

Эм. Спасибо. Но я просто проходил мимо, задачу выложил другой человек

---

Все моя невнимательность)