Это было вдохновлено математической проблемой, которую я видел где-то в Интернете, но не помню, где (ОБНОВЛЕНИЕ: оригинальная проблема была найдена в subreddit математических загадок с доказательством при условии, что это возможно, также см. Этот пост Math SE ), прося доказательство того, что следующий процесс возможен для любой произвольной пары целых чисел (насколько я помню, это было возможно для любой данной пары):
Для пары целых чисел j и k удвоьте одно из них и добавьте одно к другому, в результате чего получится пара новых целых чисел, т. Е. (J, k) -> (j + 1, k * 2) или (j * 2, к + 1). Затем повторите этот процесс с этими целыми числами с целью получения равных пары целых чисел.
Эти приведенные примеры не обязательно являются оптимальными, но показывают, как этот процесс может быть выполнен для любых целых чисел, положительных, отрицательных или нулевых:
(2, 5) -> (3, 10) -> (6, 11) -> (12, 12)
(5, 6) -> (6, 12) -> (7, 24) -> (14, 25) -> (28, 26) -> (56, 27) -> (112, 28) -> (113, 56) -> (226, 57) -> (227, 114) -> (228, 228)
(0, 2) -> (1, 4) -> (2, 5) -> (3, 10) -> (6, 11) -> (12, 12)
(-4, 0) -> (-3, 0) -> (-2, 0) -> (-1, 0) -> (0, 0)
(3, -1) -> (6, 0) -> (12, 1) -> (13, 2) -> (14, 4) -> (15, 8) -> (16, 16)
(-4, -3) -> (-8, -2) -> (-16, -1) -> (-32, 0) -> (-31, 0) -> ... -> (0, 0)
Вызов
Создайте программу, которая дает два целых числа, выводит список шагов, необходимых для того, чтобы сделать эти числа равными, многократно увеличивая одно и удваивая другое
Характеристики
- Решение не обязательно должно быть оптимальным, но оно должно решать конечное число шагов для любой произвольной пары
Ввод должен быть двух целых
Выходными данными могут быть любые разумные выходные данные, которые четко обозначают результирующие целые числа каждого шага, например:
- строка с двумя различными разделителями (любой символ, пробел и т. д.), один для каждого целого числа в паре и один для каждой пары
- например, вход j, k: 2, 5 -> выход: 3,10; 6,11; 12,12
- список списков целых чисел
- например, вход j, k: 2, 5 -> выход: [[3, 10], [6, 11], [12, 12]]
- строка с двумя различными разделителями (любой символ, пробел и т. д.), один для каждого целого числа в паре и один для каждой пары
Если вход представляет собой пару равных чисел, вы можете вывести что угодно, если это согласуется с другими нетривиальными ответами
- например
- если вход [2, 5] имеет выход [[3, 10], [6, 11], [12, 12]], который не включает входную пару, то вход [4, 4] ничего не должен выводить.
- если вход [2, 5] имеет выход [[2, 5], [3, 10], [6, 11], [12, 12]], который включает входную пару, то вход [4, 4] должен вывод [[4, 4]].
- например
Применяются стандартные методы ввода-вывода и запрещаются стандартные лазейки
Это код гольф, поэтому самый короткий ответ в байтах выигрывает
источник
[(12,12),(6,11),(3,10),(2,5)]
для ввода(2,5)
?Ответы:
JavaScript (ES6),
1119083 байтаПопробуйте онлайн!
комментарии
источник
Haskell,
7069 байтовПопробуйте онлайн!
Простая БФС. Отслеживает шаги в списке из списка пар.
источник
Python 3 ,
907472 байта-2 байта благодаря Денису .
Попробуйте онлайн!
Принимает ввод в виде одноэлементного списка .
Ungolfed
источник
Pyth, 41 байт
Попробуй здесь
объяснение
Это довольно простой поиск в ширину. Сохраняйте очередь возможных последовательностей (
J
), и пока мы не получим подходящую пару, возьмем следующую последовательность, закрепим каждый из возможных ходов и поместим их в конец очереди.Для краткости мы определяем функцию
y
(используя лямбда-выражениеL
) для выполнения одного из шагов и применяем ее как вперед, так и назад.источник
Желе , 20 байт
Попробуйте онлайн!
источник
[[2,5]]
)05AB1E ,
252220 байтПринимает дважды вложенный список в качестве входных данных и выводит зубчатый список с каждым шагом на одну глубину вложения.
Попробуйте онлайн!
объяснение
источник
Сетчатка , 72 байта
Попробуйте онлайн! Всего два теста из-за ограничений унарной арифметики. Объяснение:
Преобразовать в одинарный.
Пока на входе нет пары идентичных чисел ...
... соответствует последней паре в каждой строке ...
... и превратить строку в две строки, одна с суффиксом с увеличением первого числа, вторая с удвоением, другая с суффиксом первого числа, удвоенного и второго с увеличением.
Держите линию с соответствующей парой.
Конвертировать обратно в десятичную.
8988-байтовая десятичная арифметическая версия без знака (работает также с 0):Попробуйте онлайн!
источник
MATL , 24 байта
Время выполнения является случайным, но оно конечно с вероятностью 1.
Код очень неэффективен. Входы, требующие более 4 или 5 шагов, имеют большую вероятность истечения времени ожидания в онлайн-переводчике.
Попробуйте онлайн!
объяснение
источник
Stax ,
2926 байтЗапустите и отладьте его
Это поиск в ширину. Это кажется достаточно быстрым.
Требуется пара целых чисел с двойным массивом. Результатом является разделенный пробелами список значений. Каждые два значения представляют одну пару на пути к решению.
источник
Haskell , 95 байт
Попробуйте онлайн! Выходы в обратном порядке, например,
h(2,5)
доходность[(12,12),(6,11),(3,10),(2,5)]
.источник
Красный , 142 байта
Принимает входные данные как дважды вложенный блок пары целых чисел в формате Red
(2, 5)
->2x5
Например, возвращает результат в виде списка красных пар
2x5 3x10 6x11 12x12
. Включает начальную пару.Попробуйте онлайн!
Строгий ввод:
Ввод двух чисел, например
2 5
Красный , 214 байт
Попробуйте онлайн!
Объяснение:
источник