Отправлено: 11.03.21 10:10. Заголовок: Задание 23 №115

115) (С.С. Поляков) Исполнитель Калькулятор преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 5
3. Умножить на 3
Сколько существует программ минимальной длины, в результате выполнения которых при исходном числе 1 результатом является число 111?

Помогите, пожалуйста!
Что подразумевают под минимальной длиной? С какой стороны подойти к этой задаче?
Если можно, без Питона((

 Отправлено: 11.03.21 13:05. Заголовок: Ответ

сдающий пишет:

цитата:

Что подразумевают под минимальной длиной?

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

Минимальная длина программы - это минимальное количество команд, с помощью которых можно получить заданное число.

сдающий пишет:

цитата:

С какой стороны подойти к этой задаче? Если можно, без Питона((

Можно, например, строить дерево.

При одной команде в программе получаем числа: 2, 6, 3 (всего 3¹=3).
При двух командах в программе: 3, 7, 6, 7, 11, 18, 4, 8, 9 (всего 3²=9).
При трех командах в программе: 4, 8, 9, 8, 12, 21, 7, 11, 18, 8, 12, 21, 12, 16, 33, 19, 23, 54, 5, 9, 12, 9, 13, 24, 10, 14, 27 (всего 3³=27).

Продолжаем строить дерево до тех пор, пока среди полученных чисел не появится одно или несколько чисел 111.

Это произойдет при шести командах в программе, а количество чисел 111 среди полученных на этом шаге 729 чисел будет равно 5.

Значит, количество программ минимальной длины (она равна 6 командам), в результате выполнения которых при исходном числе 1 результатом является число 111, равно 5.

Ответ: 5.


Замечание:

При 7 командах таких программ будет 6, при 8 командах - 32, при девяти командах - 71 и так далее.

 Отправлено: 12.03.21 15:15. Заголовок: polyakovss пишет: М..

polyakovss пишет:

цитата:

Минимальная длина программы - это минимальное количество команд

спасибо за пояснение.

тогда, чуть изменив код от romad и зная что набор мин из 6 команд для получения 111, можно сделать полный перебор:

 
 def f(x, k):  
      global kk 
      if k > 0: 
          f(x * 3, k - 1)  
          f(x + 5, k - 1) 
          f(x + 1, k - 1) 
      else: 
          if x == 111:       
                  kk += 1 
        
 kk = 0 
 f(1, 6)   
 print(kk)

Или даже подставлять вместо 6 к= 4,5,6,7, и т.д.


На паскале проще - нет нужды описывать глобальную переменную kk:

var kk := 0;  
 Function f(x,k:integer):integer;  
 begin 
      if k > 0 then  
        begin 
          f(x * 3, k - 1); 
          f(x + 5, k - 1); 
          f(x + 1, k - 1); 
        end    
      else 
        if x = 111 then  kk := kk+1; 
 end;       
  
 Begin  
    kk := 0;    f(1, 6);    println(kk); 
 end. 

 Отправлено: 12.03.21 18:51. Заголовок: Ответ

глебарзамас пишет:

цитата:

... и зная что набор мин из 6 команд для получения 111...

Эта информация приведена в условии задачи? Где источник этой информации?


Без рекурсии построение дерева, описанное в (polyakovss Сообщение: 388), можно реализовать такой функцией:

 
 def f(kom): 
     a = [1] 
     for k in range(kom): 
         n = len(a) 
         for i in range(n): 
             a.append(a[0]+1) 
             a.append(a[0]+5) 
             a.append(a[0]*3) 
             a.remove(a[0]) 
     return a 
 

Тогда print(f(1)) даст: [2, 6, 3],

print(f(2)): [3, 7, 6, 7, 11, 18, 4, 8, 9],

print(f(3)): [4, 8, 9, 8, 12, 21, 7, 11, 18, 8, 12, 21, 12, 16, 33, 19, 23, 54, 5, 9, 12, 9, 13, 24, 10, 14, 27]


Полная программа для № 115:

 
 def f(kom): 
     a = [1] 
     for k in range(kom): 
         n = len(a) 
         for i in range(n): 
             a.append(a[0]+1) 
             a.append(a[0]+5) 
             a.append(a[0]*3) 
             a.remove(a[0]) 
     return a 
  
 kom = 0 
 while (111 not in f(kom)): 
     kom += 1 
 print(f(kom).count(111)) 
 

Следуя идее Короткова Михаила Сергеевича, полное решение можно записать короче так:

 
 a = [1] 
 while not 111 in a: 
     N = len(a) 
     for i in range(N): 
         a.append(a[0] + 1) 
         a.append(a[0] + 5) 
         a.append(a[0] * 3) 
         a.remove(a[0]) 
 print(a.count(111)) 
 

Ответ: 5.

 Отправлено: 13.03.21 09:05. Заголовок: polyakovss пишет: г..

polyakovss пишет:

цитата:

глебарзамас пишет:  цитата: ... и зная что набор мин из 6 команд для получения 111... Эта информация приведена в условии задачи? Где источник этой информации?

Можно менять это число - сначала взять 1, потом 2, и для 6 найдём решение.

 Отправлено: 13.03.21 12:44. Заголовок: polyakovss пишет: Э..

polyakovss пишет:

цитата:

Эта информация приведена в условии задачи? Где источник этой информации?

Это из вашего разбора решения, там ответы для 6,7,8 команд. Иначе пришлось бы в цикле перебирать k при вызове функции.

 Отправлено: 12.03.21 07:30. Заголовок: Спасибо! Деревом кон..

Спасибо!
Деревом конечно жесть получается.
Подскажите, пожалуйста, на паскале где подправить

 Function f(x,n:integer):integer; 
 Begin 
   If n<x then f:=0; 
   If n=x then f:=1; 
   If x<n then f:=f(x+1,n)+f(x+5,n)+f(x*3,n); 
 end; 
 Begin 
   writeln(f(1,111)); 
 end.

 Отправлено: 13.03.21 06:50. Заголовок: Подскажите как испра..

Подскажите как исправить программу на паскале

 Отправлено: 13.03.21 08:51. Заголовок: сдающий пишет: Подск..

сдающий пишет:

цитата:

Подскажите как исправить программу на паскале

Посмотрите ответ участника глебарзамас.

 Отправлено: 12.03.21 10:39. Заголовок: Решение аналогичной задачи № 113 на Питоне

У исполнителя Калькулятор есть три команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 5
3. Умножить на 3
Найдите длину самой короткой программы, в результате выполнения которой при исходном числе 1 результатом является число 227.

 def f(x, k): 
     global kmin 
     if x == 227: 
         if k < kmin: 
             kmin = k 
     if x * 3 <= 227: 
         f(x * 3, k + 1) 
     if x + 5 <= 227: 
         f(x + 5, k + 1) 
     elif x + 1 <= 227: 
         f(x + 1, k + 1) 
  
  
 kmin = 10000 
 f(1, 0) 
 print(kmin)

Ответ: 7

 Отправлено: 12.03.21 10:41. Заголовок: поправка к предыдущему сообщению

В заголовке задача 13, надо 113

 Отправлено: 12.03.21 18:58. Заголовок: Без рекурсии

Без рекурсии № 113:

 
 def f(kom): 
     a = [1] 
     for k in range(kom): 
         n = len(a) 
         for i in range(n): 
             a.append(a[0]+1) 
             a.append(a[0]+5) 
             a.append(a[0]*3) 
             a.remove(a[0]) 
     return a 
  
 kom = 0 
 while (227 not in f(kom)): 
     kom += 1 
 print(kom) 
 

Решение Короткова Михаила Сергеевича (mskorotkov Сообщение: 13) короче:

 
  a = [1]  
  length = 0  
  while not 227 in a:  
  	N = len(a)  
  	for i in range(N):  
  		a.append(a[0] + 1)  
  		a.append(a[0] + 5)  
  		a.append(a[0] * 3)  
  		a.pop(0)  
  	length += 1  
  	  
  print(length)  
 

Ответ: 7.

 Отправлено: 12.03.21 21:31. Заголовок: В ответе 7..

В ответе на сайте 5

 Отправлено: 12.03.21 22:36. Заголовок: Timka пишет: В ответ..

Timka пишет:

цитата:

В ответе на сайте 5

Для какой задачи ответ 5?


Для задачи № 115 ответ: 5.

Для задачи № 113 ответ: 7.

Все правильно.

 Отправлено: 13.03.21 12:56. Заголовок: polyakovss пишет: Б..

polyakovss пишет:

цитата:

Без рекурсии № 113:

Мне кажется, это тоже переборное решение. Само задание 23 про динамическое программирование. Как это решить динамически?

 Отправлено: 12.03.21 15:39. Заголовок: задача 23 из варианта 53522

у исполнителя Калькулятор две команды:
1 прибавь 1
2 умножь на 1,5???

Необычное условие - подскажите, пожалуйста, как будет выглядеть рекуррентная формула?
Спасибо.

 Отправлено: 12.03.21 22:43. Заголовок: Ответ

Рекурсивная программа, Python:

 
 def nProg( x, t ): 
     if x == t: 
         return 1 
     if x > t: 
         return 0 
     if x % 2 == 0: 
         return nProg( x+1, t ) + nProg( (x//2)*3, t ) 
     else: return nProg( x+1, t ) 
  
 print(nProg(2,22)) 
 

Без рекурсии:

 
 a=[0]*31 
 a[2]=1 
 for k in range(22): 
     a[k+1] += a[k] 
     if k % 2 == 0: 
         a[(k//2)*3] += a[k] 
 print(a[22]) 
 

 Отправлено: 17.04.21 23:48. Заголовок: Помогите, пожалуйста, с 115 задачей:

 
  def m(x,t,l): 
 	if x==t: 
 		return l 
 	elif x%3==0 and (x-5>t or x-1>t): 
 		return m(x//3,t,l+1) 
 	elif x-5>=t: 
 		return m(x-5,t,l+1) 
 	else: 
 		return m(x-1,t,l+1) 
 minl=m(111,1,0) 
 print(minl) 
  
 def f(x,t,l): 
 	if x==t and l==minl: 
 		return 1 
 	elif x>t: 
 		return False 
 	else: 
 		return f(x+1,t,l+1)+f(x+5,t,l+1)+f(x*3,t,l+1)  
 print(f(1,111,0)) 
 

Выдаёт правильно минимальную длину, не выдаёт количество. Не могу понять почему.

Спасибо!

 Отправлено: 09.05.21 20:29. Заголовок: Уррааа! Нашла решение

'''23 115) (С.С. Поляков) Исполнитель Калькулятор преобразует число на экране.
У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 5
3. Умножить на 3
Сколько существует программ минимальной длины, в результате выполнения которых
при исходном числе 1 результатом является число 111?'''

 
 from functools import lru_cache 
 def minl(x,t,l): 
     if x==t: 
         return l 
     elif x%3==0 and (x-5>t or x-1>t): 
         return minl(x//3,t,l+1) 
     elif x-5>=t: 
         return minl(x-5,t,l+1) 
     else: 
         return minl(x-1,t,l+1) 
  
 m=minl(111,1,0) 
  
 @lru_cache(None) 
 def f(x,t,l): 
     if x==t and l==m: 
         return 1 
     elif x>t: 
         return 0 
     else: 
         return f(x+1,t,l+1)+f(x+5,t,l+1)+f(x*3,t,l+1) 
 print(f(1,111,0)) 
 

 Отправлено: 09.05.21 23:13. Заголовок: Здравствуйте, Anvikm..

Здравствуйте, Anvikm!

А что Вас не устраивает в решении задачи 115, приведенном выше в (polyakovss Сообщение: 393)?

цитата:

a = [1] while not 111 in a: N = len(a) for i in range(N): a.append(a[0] + 1) a.append(a[0] + 5) a.append(a[0] * 3) a.remove(a[0]) print(a.count(111))