Прокрутите вниз, чтобы увидеть последние изменения, я оставил весь этот текст здесь только для того, чтобы не аннулировать ответы, полученные на данный вопрос!
У меня есть следующая головоломка, для которой я хотел бы найти решение, я пытался решить эту проблему, но математически я не намного выше среднего (, то есть я думаю, что я очень близок в среднем ) Я не могу обернуться вокруг этого.
Проблема: данное число x должно быть разделено на серию multipliers, где каждый multiplier <= y, y является константой, равной 10 или 16 или чем-то еще. В серии (технически array of integers) последнее число должно быть добавлено вместо умножения, чтобы иметь возможность преобразовать множители обратно в исходное число.
В качестве примера, давайте предположим x=29 и y=10. В этом случае ожидаемый массив будет {10,2,9}, что означает 10*2+9. Однако, если y=5, это будет {5,5,4}, что означает 5*5+4, или если y=3, это будет {3,3,3,2}, что тогда будет 3*3*3+2.
Я пытался решить эту проблему следующим образом:
- , а
x >= y, хранить y до multipliers, затем x = x - y
- при
x < y, хранить x до multipliers
Очевидно, что это не сработало, я также пытался сохранить «оставшуюся» часть отдельно и добавить ее после всего остального, но это тоже не сработало. Я считаю, что моя главная проблема заключается в том, что я пытаюсь думать об этом слишком сложным образом, в то время как решение очевидно и просто.
Повторим, вот ограничения, которые должен иметь этот алгоритм:
- должен работать с 64-битной длиной
- должен вернуть массив 32-битных целых чисел (... ну, шорты тоже в порядке)
- в то время как поддержка чисел со знаком (как +, так и -) была бы хороша, если бы это помогало заданию, только числа без знака являются обязательными
И хотя я делаю это с использованием Java, я предпочел бы использовать любые возможные примеры кода в качестве псевдокода, я специально НЕ хочу получать готовые ответы, мне просто нужно подтолкнуть (ну, более сильный удар), чтобы Я могу решить это, по крайней мере, частично сам. Заранее спасибо.
Редактировать: Дополнительные разъяснения
Чтобы избежать путаницы, думаю, мне следует перефразировать это немного:
- Каждое целое число в массиве результатов должно быть меньше или равно y, включая последнее число.
- Да, последний номер - просто магическое число.
- Нет, это не модуль, поскольку в большинстве случаев второе число будет больше, чем y.
- Да, есть несколько ответов на большинство доступных чисел, однако я ищу тот, у которого наименьшее количество математических операций. Что касается моей логики, это означает, что нужно найти максимальное количество как можно больших множителей, например,
x=1 000 000,y=100 равно 100*100*100, хотя 10*10*10*10*10*10 одинаково правильный ответ по математике.
Мне нужно пройти через приведенные ответы с некоторой мыслью, но если у вас есть что добавить, пожалуйста, сделайте! Я высоко ценю интерес, который вы уже проявили к этому, спасибо всем за это.
Редактировать 2: дополнительные объяснения + щедрость
Ладно, похоже, то, к чему я стремился, просто не может быть сделано так, как я думал. Я был слишком двусмысленен с моей целью, и, подумав немного, я решил просто рассказать вам полностью, что я хотел бы сделать, и посмотреть, что вы можете придумать.
Первоначально моя цель состояла в том, чтобы придумать конкретный метод для упаковки больших целых чисел (больше длинных) 1..n так, чтобы их представление String было заметно короче, чем запись действительного числа. Представьте, что кратные десяти, 10 ^ 6 и 1 000 000 одинаковы, однако длина представления в символах не совпадает.
Для этого я хотел как-то объединить числа, так как ожидается, что числа несколько близки друг к другу. Сначала я подумал, что представление 100, 121, 282 как 100+21+161 может быть подходящим способом, но экономия длины строки в лучшем случае пренебрежимо мала и действительно не работает так хорошо, если числа не очень близки друг к другу. В основном я хотел больше, чем ~ 10%.
Так что мне пришла в голову мысль, что если я сгруппирую числа по общему свойству, такому как множитель, и разделю оставшуюся часть числа на отдельные компоненты, которые я затем смогу представить в виде строки. Вот где эта проблема возникает, я думал, что, например, 1 000 000 и 100 000 можно выразить как 10 ^ (5 | 6), но из-за контекста моего целевого использования это было слишком ненадежно:
Контекст - веб. RESTful URL: для конкретности. Вот почему я упоминал о том, чтобы подумать об использовании 64 символов (веб-безопасных буквенно-цифровых незарезервированных символов, а затем и некоторых) с тех пор, как я мог создать кажущиеся случайными URL-адреса, которые можно было бы распаковать в список целых чисел, выражающих набор номеров идентификаторов. В этот момент я подумал о создании базовой 64-подобной системы счисления для выражения базовых чисел 10/2, но, поскольку я не гений математики, я не знаю, как это сделать.
Щедрость
Теперь, когда я написал всю историю (извините, что она длинная), я открываю награду за этот вопрос. Все, что касается требований к предпочтительному алгоритму, указанному ранее, остается в силе. Я также хочу сказать, что я уже благодарен за все ответы, которые я получил до сих пор, мне нравится быть доказанным неправильно, если это сделано так, как вы, люди.
Заключение
Ну, щедрость теперь дается. Я выкладываю несколько комментариев к ответам, в основном для дальнейшего использования, и вы можете также проверить мое предложение SO Uservoice о распределении щедрости, которое связано с этим вопросом, если вы считаете, что мы сможем распространить его среди нескольких ответы.
Спасибо всем, что нашли время и ответили!