Определите функцию f (n) для натурального числа n следующим образом:
- n / 2 , если n четное
- 3 * n + 1 , если n нечетно
Если вы неоднократно применяете эту функцию к любому n, большему 0, результат всегда кажется сходящимся к 1 (хотя пока никто не смог доказать это). Это свойство известно как гипотеза Коллатца .
Определите время остановки целого числа как количество раз, которое вы должны пройти через функцию Коллатца f, прежде чем оно достигнет 1. Вот время остановки первых 15 целых чисел:
1 0
2 1
3 7
4 2
5 5
6 8
7 16
8 3
9 19
10 6
11 14
12 9
13 9
14 17
15 17
Давайте назовем любой набор чисел с одинаковым временем остановки двоюродных братьев Коллатц . Например, 5 и 32 - двоюродные братья Коллатц, время остановки 5.
Ваша задача: написать программу или функцию, которая принимает неотрицательное целое число и генерирует набор двоюродных братьев Коллатц, время остановки которых равно этому целому числу.
вход
Неотрицательное целое число S, заданное через STDIN, ARGV или аргумент функции.
Выход
Список всех чисел, время остановки которых S, отсортировано в порядке возрастания . Список может быть выведен вашей программой или возвращен или выведен вашей функцией. Формат вывода гибкий: разделенный пробелами, разделенный новой строкой или любой стандартный формат списка вашего языка подходит, если числа легко отличимы друг от друга.
Требования
Ваше представление должно давать правильные результаты для любого S ≤ 30. Оно должно заканчиваться в секундах или минутах, а не часах или днях.
Примеры
0 -> 1
1 -> 2
5 -> 5, 32
9 -> 12, 13, 80, 84, 85, 512
15 -> 22, 23, 136, 138, 140, 141, 150, 151, 768, 832, 848, 852, 853, 904, 906, 908, 909, 5120, 5376, 5440, 5456, 5460, 5461, 32768
Вот суть вывода для S = 30 .
Это код-гольф : выигрывает самая короткая программа в байтах. Удачи!
Ответы:
Pyth,
262421 байтЭтот код работает мгновенно для
S=30
. Попробуйте сами: демонстрацияСпасибо @isaacg за сохранение 5 байтов.
объяснение
Мой код начинается с
1
отмены функции Collatz. Он отображает все номераd
наS-1
шаг к2*d
и(d-1)/3
. Последний в не всегда действителен все же.источник
-F
.- ... 1
сумму в сумму уменьшения, вам не нужно уменьшать, чтобы быть.u
, ни-F
снаружи. Спасает 2 персонажа.q4%d6
эквивалентно!%hhd6
, но на 1 символ короче.Mathematica,
989289 байтЭто решение решает
S = 30
сразу:Это безымянная функция, принимающая в
S
качестве единственного параметра и возвращающая список двоюродных братьев Коллатц.Алгоритм - это простой поиск в ширину. Двоюродными братьями Коллатц для данного
S
являются все целые числа, которые могут быть получены из двоюродных братьев Коллатц дляS-1
через2*n
или нечетных чисел, которые могут быть достигнуты через(n-1)/3
. Нам также нужно убедиться, что мы производим только те целые числа, которые были достигнуты впервые послеS
шагов, поэтому мы отслеживаем всех предыдущих двоюродных братьевp
и удаляем их из результата. Так как мы делаем это в любом случае, мы можем сэкономить несколько байтов, вычисляя шаги от всех предыдущих двоюродных братьев (не только от двоихS-1
), чтобы сохранить несколько байтов (что делает его немного медленнее, но не заметно для требуемогоS
).Вот немного более читаемая версия:
источник
Python 2,
8683757371 байтЗвоните как
f(30)
.n = 30
почти мгновенно(Спасибо @DLosc за идею рекурсивного преобразования
k
в число, а не в список двоюродных братьев и сестер и несколько байтов. Спасибо @isaacg за удаление~-
.)Этот вариант намного короче, но, к сожалению, занимает слишком много времени из-за экспоненциального ветвления:
источник
f=lambda d,n=1:d and sorted(sum((c(d-1,x)for x in[n*2]+[~-n/3][:n>4==n%6]),[]))or[n]
. Это менее эффективно с вызовами функций, но все равно работаетn = 30
менее чем за секунду.f=lambda n,k=1:sorted([k][n:]or(k>4==k%6and f(n-1,~-k/3)or[])+f(n-1,k*2))
~-
это не нужно, потому что вы используете целочисленное деление.CJam,
2926 байтБлагодарность принадлежит @isaacg за его идею удалять 1 после каждой итерации, что позволило мне сэкономить два байта напрямую и один косвенно.
Попробуйте онлайн в интерпретаторе CJam (должен закончиться менее чем за секунду).
Как это устроено
источник
CJam, 35 байт
Объяснение в ближайшее время. Это гораздо более быстрая версия, чем «довольно прямой» подход (см. Его в истории редактирования).
Попробуйте онлайн здесь, для
N = 30
которого в считанные секунды запускается онлайн-версия и мгновенно в компиляторе Javaисточник
It should finish in seconds or minutes, not hours or days.
S=15
не работает.Java 8, 123
Когда
x
30, программа занимает 15 минут и 29 секунд.расширенный
источник
javac 1.7.0_79
в Ubuntu дало мне много синтаксических ошибок.i > 1 && ++n <= x
(вы также можете отброситьn++
) кажется еще более быстрым только для 5 дополнительных символов ... около 3 минут для S = 30 для меня. Это будет безопасно выбрито за минуту, если я.parallel()
тожеPython 2, 118 байт
Что ж, я подумал, что не достигну лучшего результата Python, увидев решение @ Sp3000. Но это выглядело как забавная маленькая проблема, поэтому я все равно хотел попробовать независимое решение:
То же самое перед удалением пробелов:
Это очень прямая реализация поиска в ширину. На каждом шаге мы имеем набор с временем остановки
k
и получаем набор с временем остановкиk + 1
, добавляя возможных предшественников каждого значенияt
в наборе из шагаk
:2 * t
всегда возможный предшественник.t
можно записать как3 * u + 1
, гдеu
нечетное число, которого нет1
, тоu
и предшественник тоже.N = 30
На моем MacBook Pro требуется около 0,02 секунды .источник
s.add(x)
в гольфе нет необходимости, так как вы можете сделать этоs|={x}
вместо этого. Кроме того, использование~-x
вместо(x+1)
сохранения на скобках. Но в остальном хорошая работа :)s.add()
потому что оно становится присваиванием и больше не может быть частью выражения. Это работает для первого. Вfor
петле на основе счетчиков всегда вид многословный , а также. Я думал, что смогу сократить его, используяwhile
цикл, но он оказался точно такой же длины.for
цикла, так как вы не используете ввод каким-либо другим способом, вы, вероятно, можете использоватьexec"..."*input()
вместо этого :)PHP 5.4+, 178 байт
Функция
Тест и вывод
S (30) выполняется за 0,24 секунды * , возвращает 732 элемента. Пара
* Чтобы сэкономить на байтах, мне приходилось добавлять
ksort
иarray_keys
на каждом шагу. Единственный другой выбор, который у меня был, - сделать небольшую функцию-обертку, которая вызывает,c()
а затем вызываетarray_keys
иksort
один раз результат. Но из-за времени, которое все еще было прилично быстрым, я решил взять удар производительности за малое количество байтов. Без надлежащей сортировки и обработки время в среднем составляет 0,07 секунды для S (30).Если у кого-нибудь есть какие-нибудь умные способы получить правильную обработку только один раз без слишком большого количества дополнительных байтов, пожалуйста, дайте мне знать! (Я храню свои числа в виде ключей массива, поэтому я использую
array_keys
иksort
)источник
Язык C
источник
{}
кнопку, чтобы отформатировать ваш код, что я и сделал для вас. Но, как говорит Алекс, пожалуйста, добавьте название языка (C?) И попробуйте сыграть в гольф :) Но добро пожаловать!f
не работает должным образом. Сs=5
, я получаю кучу неверных результатов.if (r == s)return true;
должно бытьreturn (r==s)
, такf
как не вернет ничего значащего, когда(r < s)
. Кроме того , я думаю , вы должны объявитьi
вf
качествеlong
, так как он будет переполнение довольно быстро для некоторых значений.return (r==s);