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:
<!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>