Задание из ЕГЭ по информатике с помощью JS

#javascript

30го числа ЕГЭ, время на подготовку совсем нету, чисто случайно попалась программа,
котоая решает задачи подобного плана: 

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

Но она на Win XP, а мне бы на айподе её использовать. Конечно задачку то я решить
могу, но там можно ошибиться в вычислениях + товарищ нифига не смыслит в этом, тоже
хотелось бы и ему помочь. Ну и я загорелся написать программу под айпод, т.к. знаниями
Objective C не располагаю, решил просто на JS сделать страничку в инете, на которой
можно будет это решать. Но вот начал думать, что-то даже и не знаю, как сделать. 
Алгоритм то такой: постипенно выполнять эту задачу для чисел меньше 55, т.е. сначала
для 2, потом для 3 и т.д. Формула такая: R(n) = R(n-2) + R(n/3) это для данной задачи.
R(n) - это кол-во программ, n это число в которое преобразовать. Если n не делется
на 3, то R(n/3) приравнивать к 0. И получается нам нужно найти только R(2),R(3) своим
умом и логикой, R(2)=0 (т.к. таких программ не существует), R(3) = 2 (можно умножить
1 на 3 или прибавить 2 к 1). А дальше уже подставляем всё в первую формулу: R(4) =
R(4-2) + R(4/3) 4/3 не делится, поэтому равно 0, следовательно R(4) = R(2) = 0. И так
далее, до 55. Вот такой алгоритм впринципе я представляю как организовать. Можно создать
массив с этими занчениями просто и всё и также работать, только будет не R(2), в R[2].
Но я не знаю как вычислить первые R(2),R(3) с помощью JS. 
Помогите пожалуйста. Ведь программы раздые бывают, может быть из числа 8 в число
27, с разными операциями исполнителя(например будут уже умножить на 2 и прибавить 3).
И вопрос именно как определить первые элементы массива, чтобы от них уже строить остальные
по формуле R(n) = R(X) + R(X) 
UPD:
Вот и программа, написал благодаря алгоритму IVsevolod:
    









Исполнитель умеет выполнять следующие команды:

 ПрибавьУмнож наВозведи в квадрат 



 ПрибавьУмнож наВозведи в квадрат 



 ПрибавьУмнож наВозведи в квадрат
 


Сколько есть программ, которые преобразуют

число  в число  






    

Ответы

Ответ 1

Хм. как я понял число 55 может меняться?
я бы сделал рекурсивно, что-то типо этого (напишу на псевдо языке):
функция Считаем(число)
{
  результат = 0;
  число1 = число + 2;
  число2 = число * 3;
  если (число1 == 55) то результат ++; 
  иначе если (число1 < 55) nj результат += Считаем(число1);

  если (число2 == 55) то результат ++; 
  иначе если (число2 < 55) nj результат += Считаем(число2); 
  вернуть реузльтат;    
}

выводим Считаем(1);

Синтаксис JS достаточно прост. На html страничку можно прикрутить пару формочек,
и действие прикрутить к кнопке. 
надеюсь помог, и вопрос понял правильно :)


Ответ 2

Оттранслировал псевдокод из ответа IVsevolod на Java (с некоторыми вольностями) и
добавил вывод получившихся программ для этой виртуальной машины.

public class main {
    static int printCounter = 1;

    static int recurse(int arg, StringBuilder b){
        return check(arg+2, new StringBuilder(b).append("+"))
             + check(arg*3, b.append("*"));
    }


    static int check(int arg, StringBuilder b){
        final int checkResult = 55;

        if (arg == checkResult){
            System.out.print(printCounter++);
            System.out.print("\t");
            System.out.println(b);
            return 1;
        }

        if (arg < checkResult)
            return recurse(arg, b);

        return 0;
    }

    public static void main(String[] arg){
        System.out.println(check(1, new StringBuilder()));
    }
}


Может, кому-то будет интересно побаловаться. :)