Определить, сколько возможно построить различных программ для исполнителя, которые преобразуют число х в у

@Iosif · Регистрация: 27.08.2014

Студворк — интернет-сервис помощи студентам

У некоторого исполнителя, обрабатывающего числа, есть три команды: +1, +2, *3. Исполнитель получает на вход некоторое число и программу, представляющую собой некоторую последовательность вышеназванных команд. На выходе он выдает новое число - результат применения программы к исходному числу. Вам предлагается написать программу - анализатор данного исполнителя. На вход программе подаются два числа х и у, каждое из которых лежит в диапазоне от 0 до 200 (включая границы) и при этом гарантируется, что х меньше, либо равно у. Ваша программа должна подсчитать, сколько возможно построить различных программ для исполнителя, которые преобразуют число х в у. В качестве ответа нужно вывести одно целое число.

Добавлено через 37 секунд
Буду рад оперативной помощи, заранее спасибо!

@catr · 11.03.2015, 08:03

хорошая задача

@JuriiMW · 11.03.2015, 08:49

Проще всего рекурсией:

Pascal
1
2
3
4
5
…
vars := 0;
FindVariant(X, Y);
WriteLn(vars);
…

Pascal
1
2
3
4
5
6
7
8
9
10
procedure FindVariants(A, B : Integer);
begin
  if A > B then Exit
  else if A = B then Inc(vars)
  else begin
    FindVariants(A +1, B);
    FindVariants(A +2, B);
    FindVariants(A *3, B);
  end;
end;

@Yakoe · 23.03.2016, 16:37

JuriiMW, А можно подробнее, а желательно программу целиком

@a1d4r · 23.03.2016, 19:38

Решение методом динамического программирования.

Что показывает элемент: a[i] - кол-во способов получить i из x
Начальные значения: a[x] = 1
Рекурентное соотношение: a[i] = a[i - 1] + a[i - 2] + (если i кратное трем) a[i div 3]
Ответ: a[y]

Pascal
1
2
3
4
5
6
7
8
9
10
var
  x, y, i, j: integer;
  a: array[0..200] of int64;
begin
  read(x, y);
  a[x] := 1;
  for i := x + 1 to y do
    a[i] := a[i - 1] + a[i - 2] + a[i div 3] * ord(i mod 3 = 0);
  write(a[y])
end.

UPD: Для отдаленных чисел x и y придется использовать длинную арифметику

@capricornus CF · 23.03.2016, 20:49

Yakoe, это и есть программа , практически целиком. С позволения:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var x,y,vars:integer;
 
procedure FindVariants(A, B : Integer);
begin
  if A > B then Exit
  else if A = B then Inc(vars)
  else begin
    FindVariants(A +1, B);
    FindVariants(A +2, B);
    FindVariants(A *3, B);
  end;
end;
begin
vars := 0;
readln(x,y);
FindVariants(X, Y);
WriteLn(vars);
end.

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Программа принимает математическое выражение в виде строки и выдаёт его производную в виде строки и вычисляет значение производной при заданном х Логарифм записывается как: (x-2)log(x^2+2) -. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

@Iosif 0 / 0 / 0 Регистрация: 27.08.2014 Сообщений: 12

	Определить, сколько возможно построить различных программ для исполнителя, которые преобразуют число х в у 10.03.2015, 19:09. Показов 6774. Ответов 5 Метки нет (Все метки) У некоторого исполнителя, обрабатывающего числа, есть три команды: +1, +2, 3. Исполнитель получает на вход некоторое число и программу, представляющую собой некоторую последовательность вышеназванных команд. На выходе он выдает новое число - результат применения программы к исходному числу. Вам предлагается написать программу - анализатор данного исполнителя. На вход программе подаются два числа х и у, каждое из которых лежит в диапазоне от 0 до 200 (включая границы) и при этом гарантируется, что х меньше, либо равно у. Ваша программа должна подсчитать, сколько возможно построить различных программ для исполнителя, которые преобразуют число х в у. В качестве ответа нужно вывести одно целое число. Добавлено через 37 секунд* Буду рад оперативной помощи, заранее спасибо! 0

@catr 12 / 12 / 6 Регистрация: 27.11.2013 Сообщений: 73
	11.03.2015, 08:03
	хорошая задача 0

@Yakoe 0 / 0 / 0 Регистрация: 23.10.2015 Сообщений: 9
	23.03.2016, 16:37
	JuriiMW, А можно подробнее, а желательно программу целиком 0