Question

Помогите с информатикой пожалуйста!! У исполнителя Калькулятор две команды, которым присвоены номера: 1. прибавь 1 2. умножь на 3 Сколько есть программ, которые число 5 преобразуют в число 49? Интересует само решение

Answer 1

Поиск пути по принципу дерева

Код на Руби
def f0(number, log) #
  v = 1
  n = number + v
  # log = "#{log} + #{v}"
  log = "#{log} + 1"
  return [n, log]
end

def f1(number, log) #
  v = 3
  n = number * v
  # log = "#{log} + #{v}"
  log = "(#{log}) * 3"
  return [n, log]
end

def countWays(start_num, end_num, op_number, max_steps = 0)
  ways = {}
  ways.store(start_num.to_s, start_num)

  max_steps = max_steps == 0 ? (start_num - end_num).abs : max_steps
  count = 0

  for steps in 1..max_steps
      # puts "steps = #{steps}"
      new_ways = {}
      ways.each_pair{|log, num|

          for k in 0..op_number-1
              num1, log1 = f0(num, log) if k == 0
              num1, log1 = f1(num, log) if k == 1

              if num1 == end_num then
                  log1 += " = " + end_num.to_s
                  count += 1
                  puts log1
              elsif num1.between?(start_num, end_num)
                  new_ways.store(log1, num1)
              else
                  # log1 = log1 + " = " + num1.to_s + " BAD "
                  # puts log1
              end
          end
      }
      # p [steps, ways.size, new_ways.size]
      ways = new_ways
  end
  return count
end

p countWays(5, 49, 2, 49)

Вывод
((5) * 3 + 1) * 3 + 1 = 49
((5) * 3) * 3 + 1 + 1 + 1 + 1 = 49
(5 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1) * 3 + 1 = 49
(5 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1) * 3 + 1 + 1 + 1 + 1 = 49
(5 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1) * 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 49
(5 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1) * 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 49
(5 + 1 + 1 + 1 + 1 + 1 + 1 + 1) * 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 49
(5 + 1 + 1 + 1 + 1 + 1 + 1) * 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 49
(5 + 1 + 1 + 1 + 1 + 1) * 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 49
(5 + 1 + 1 + 1 + 1) * 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 49
(5 + 1 + 1 + 1) * 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 49
(5 + 1 + 1) * 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 49
(5 + 1) * 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 49
(5) * 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 49
5 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 49
15

Ответ 15 вариантов программ

Как это решается аналитически я не знаю, но программно явно быстрее

Answer 2

Для решения данной задачи можно использовать рекурсивный подход, так как у исполнителя Калькулятор есть две команды, которые могут изменять число.

Предположим, что у нас есть функция f(x), которая возвращает количество программ, которые могут преобразовать число x в число 49, используя только команды "прибавь 1" и "умножь на 3". Тогда нам нужно найти f(5).

Чтобы найти f(x), мы можем рассмотреть два варианта:

1. Если текущее число x уже равно 49, то существует только одна программа, которая ничего не делает, и это программа преобразовывает x в 49. Таким образом, f(49) = 1.

2. Если текущее число x не равно 49, то у нас есть два варианта:

   • Выполнить команду "прибавь 1": это приведет к изменению числа на x + 1, поэтому нам нужно найти f(x + 1).
   • Выполнить команду "умножь на 3": это приведет к изменению числа на 3 * x, поэтому нам нужно найти f(3 * x).

Таким образом, f(x) = f(x + 1) + f(3 * x) для x ≠ 49.

Теперь можем написать рекурсивную функцию для нахождения f(x):

pythonCopy code
def count_programs(x):
    if x == 49:
        return 1
    return count_programs(x + 1) + count_programs(3 * x)

# Найдем количество программ для числа 5, чтобы преобразовать его в 49:
result = count_programs(5)
print(result)  # Выведет ответ

Однако стоит отметить, что рекурсивное решение может быть неэффективным для больших значений, так как оно может привести к повторным вычислениям. В этом случае, можно использовать метод динамического программирования или мемоизации, чтобы избежать повторных вычислений и ускорить процесс нахождения количества программ.