On the 30th of the USE, there is absolutely no time for preparation, a program that solves problems of such a plan came across by chance:

The performer has two teams,
which numbers are assigned:
1. add 2
2. multiply by 3.
How many programs are there that the number 1 translates into the number 55?

But it is on Win XP, and I would use it on my iPod. Of course, I can solve the problem, but there you can make a mistake in the calculations + comrade nfiga does not understand this, I would also like to help him. Well, I fired up to write a program for iPod; I don’t have any knowledge of Objective C, I decided to just make a page on the internet in JS, where it will be possible to solve it. But I began to think that I don’t even know how to do something.

The algorithm is as follows: it is gradual to perform this task for numbers less than 55, i.e. first for 2, then for 3, etc. The formula is as follows: R(n) = R(n-2) + R(n/3) is for this task. R(n) is the number of programs, n is the number into which to convert. If n is not divisible by 3, then R(n/3) equated to 0. And it turns out we need to find only R(2) , R(3) with our mind and logic, R(2)=0 (since such there are no programs), R(3) = 2 (you can multiply 1 by 3 or add 2 to 1). And then we substitute everything into the first formula: R(4) = R(4-2) + R(4/3) 4/3 is not divisible, therefore it is 0, therefore R(4) = R(2) = 0 . And so on, up to 55. This is the algorithm in principle I imagine how to organize. You can create an array with these values ​​simply and everything and also work, but it will not be R(2) , in R[2] . But I do not know how to calculate the first R(2) , R(3) using JS.

Help me please. After all, programs are rare, maybe from number 8 to number 27, with different performer operations (for example, they will be multiplied by 2 and added 3). And the question is how to determine the first elements of the array, so that we can build the rest of them from the formula R(n) = R(X) + R(X)

UPD: Here is the program, written thanks to the IVsevolod algorithm:

  <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"> <html><head> <meta http-equiv="Content-Type" content="text/html; charset=windows-1251"> <title>Б13</title> <script type="text/javascript"> function Schet(n) { var f = document.getElementById('forma'); var result = 0; var num = Number(f.num2.value); if(f.can1.value=='plus') var n1 = n + Number(f.k1.value); else if(f.can1.value=='mnozh') var n1 = n * f.k1.value; else if(f.can1.value=='sqr') var n1 = n * n; if(f.can1.value!=""){ if (n1 == num) result++; if (n1 < num) result += Schet(n1); } if(f.can2.value=='plus') var n2 = n + Number(f.k2.value); else if(f.can2.value=='mnozh') var n2 = n * f.k2.value; else if(f.can2.value=='sqr') var n2 = n * n; if(f.can2.value!=""){ if (n2 == num) result++; if (n2 < num) result += Schet(n2); } if(f.can3.value=='plus') var n3 = n + Number(f.k3.value); else if(f.can3.value=='mnozh') var n3 = n * f.k3.value; else if(f.can3.value=='sqr') var n3 = n * n; if(f.can3.value!=""){ if (n3 == num) result++; if (n3 < num) result += Schet(n3); } return result; } function ECHO(msg){ document.getElementById('answer').innerHTML = '<b>Ответ:</b> '+msg; } </script> </head> <body> <form id=forma> <b>Исполнитель умеет выполнять следующие команды:</b><br/> <select name=can1><option value=""> </option><option selected value='plus'>Прибавь</option><option value='mnozh'>Умнож на</option><option value='sqr'>Возведи в квадрат</option></select> <input name=k1 type=text value="2" size=5><br/><br/> <select name=can2><option value=""> </option><option value='plus'>Прибавь</option><option selected value='mnozh'>Умнож на</option><option value='sqr'>Возведи в квадрат</option></select> <input name=k2 type=text value="3" size=5><br/><br/> <select name=can3><option selected value=""> </option><option value='plus'>Прибавь</option><option value='mnozh'>Умнож на</option><option value='sqr'>Возведи в квадрат</option></select> <input name=k3 type=text value="0" size=5><br/><br/> <b>Сколько есть программ, которые преобразуют</b><br/> число <input name=num1 type=text value="1" size=5> в число <input name=num2 type=text value="55" size=5> <br/> <button OnClick="ECHO(Schet(Number(document.getElementById('forma').num1.value)));return false;">Решить!</button> <div id=answer></div> </form> </body> </html>
  • one
    Well, the wording on the exam ... Understood from the text of 20 percent :) - Zhukov Roman
  • The performer Utroitel has two commands that are assigned numbers: 1. add 2, 2. multiply by 3.> But I don’t know how to calculate the first R (2), R (3) using JS. I correctly understood that you do not know how many ways by adding the number 2 and multiplying by 3 to get the numbers ... 2 and 3? - Nofate ♦
  • Nofate, I know that, I do not know how to teach the program to recognize it, because all the data is dynamic, everything is changeable. Zhukov Roman, yes, horror. 4 years ago it was much easier, I helped my brother get ready. - iproger
  • 2 and 3 for the case with multiplication / addition by 2 and 3 are a reference point and are performed in one operation. If you generally have * multiplication by a * adding b then R (a) = R (b) = 1 and nothing else - Nofate ♦
  • what a terrible code, I hope all the same, your code always works correctly :) - IVsevolod

2 answers 2

Hm As I understand the number 55 can vary?

I would do recursively , something like this (I will write in pseudo language):

 функция Считаем(число) { результат = 0; число1 = число + 2; число2 = число * 3; если (число1 == 55) то результат ++; иначе если (число1 < 55) nj результат += Считаем(число1); если (число2 == 55) то результат ++; иначе если (число2 < 55) nj результат += Считаем(число2); вернуть реузльтат; } выводим Считаем(1);

JS syntax is pretty simple. On the html page you can screw a couple of molds, and screw the action to the button.

I hope it helped, and the question got it right :)

  • Well, yes, I have the main algorithm, I know JS and HTML. I'll try your program, but it seems to me that it skips some options, well, I'll rewrite it in JS and try it, thanks a lot)) - iproger
  • one
    For some reason, it turns out to be 1, it should be 32. Right now I'll try to figure it out, but it's hard to figure out the recursion. - iproger
  • @mctrane don't forget to show the solution :) - lampa
  • @lampa I right now the program will interface and lay out the source) - iproger
  • @mctrane, please) was glad to help :) - IVsevolod

I translated the pseudocode from the IVsevolod response to Java (with some liberties) and added the output of the resulting programs for this virtual machine.

 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())); } }

Maybe someone will be interested to indulge. :)