Исполнитель увеличитель345 преобразует число, записанное на экране. у исполнителя три команды, которым присвоены номера: 1. прибавь 3 2. прибавь 4 3. прибавь 5 первая из них увеличивает число на экране на 3, вторая увеличивает это число на 4, а третья – на 5. программа для исполнителя увеличитель345 – это последовательность команд. определите, сколько существует программ, преобразующих число 22 в число 80. можно решать как с электронной таблицы, так и путем составления программы.

224

407

Посмотреть ответы 3

Ответы на вопрос:

porotnikova03

Информатика

4,7(43 оценок)

//ruby 22 def factorial(n) f = 1; for i in 1..n; f *= i; end; f end n=0 for i in 0..80/3 for j in 0..80/4 for k in 0..80/5 if 22+3*i+4*j+5*k==80 nn = factorial(i+j+k)/factorial(i)/factorial(j)/factorial(k) n+=nn p [i,j,k] end end end end p n как работает программа: сначала мы находим способы получить из 22 число 80. для удобства шаги мы упорядочеваем: сначала прибавляем тройки, потом четверки, потом пятерки. ищем все возможные наборы (i, j, k) которые отвечают равенству 22 + 3i + 4j + 5k = 80. для каждого такого набора высчитываем кол-во перестановок с повторениями и суммируем их. ответ 3174448

V369906

Информатика

4,8(78 оценок)

Можно решать по-другому, используя динамическое программирование. обозначим f[n] - число способов получить число n и положим f[18]=f[19]=f[20]=f[21]=0, а f[22]=1. тогда f[k] = f[k-3]+f[k-4]+f[k-5] для любого k > = 23. (почему так? возьмём некоторое число k. его можно получить из чисел k-3, k-4, k-5 путём прибавления тройки, четвёрки и пятёрки соответственно, притом если мы договорились, например, что последней операцией будем прибавление пятёрки, то число способов получить число k будет равно числу способов получить k-5, ведь последнюю операцию мы определим однозначно. поэтому число способов получить k - сумма количеств способов получить k-3, k-4 и k-5) итак, f[k] = f[k-3]+f[k-4]+f[k-5], f[18]=f[19]=f[20]=f[21]=0 и f[22]=1. по этой рекуррентной формуле можно даже посчитать вручную (это будет немного долго), или воспользоваться компьютером. например, на python 3 можно написать такую программу: a = [0] * 5; n = 22; a[n % 5] = 1; while n < 80: n += 1; a[n % 5] = a[(n-3) % 5] + a[(n-4) % 5] + a[(n-5) % 5]print(a[n % 5])ответ: 3174448