Выражение целого числа в виде последовательности множителей - PullRequest
11 голосов
/ 25 апреля 2009

Прокрутите вниз, чтобы увидеть последние изменения, я оставил весь этот текст здесь только для того, чтобы не аннулировать ответы, полученные на данный вопрос!


У меня есть следующая головоломка, для которой я хотел бы найти решение, я пытался решить эту проблему, но математически я не намного выше среднего (, то есть я думаю, что я очень близок в среднем ) Я не могу обернуться вокруг этого.

Проблема: данное число 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.

Я пытался решить эту проблему следующим образом:

  1. , а x >= y, хранить y до multipliers, затем x = x - y
  2. при 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 о распределении щедрости, которое связано с этим вопросом, если вы считаете, что мы сможем распространить его среди нескольких ответы.


Спасибо всем, что нашли время и ответили!

Ответы [ 13 ]

16 голосов
/ 29 апреля 2009

Обновление

Я не удержался, пытаясь придумать свое собственное решение для первого вопроса, даже если оно не сжимает. Вот решение Python, использующее сторонний алгоритм факторизации pyecm.

Это решение, вероятно, в несколько раз более эффективно, чем решение Евгения. Вычисления занимают секунды вместо часов или даже недель / лет для разумных значений y. Для x = 2 ^ 32-1 и y = 256 для моего основного дуэта потребовалось 1,68 секунды 1,2 ГГц.

>>> import time
>>> def test():
...     before = time.time()
...     print factor(2**32-1, 256)
...     print time.time()-before
...
>>> test()
[254, 232, 215, 113, 3, 15]
1.68499994278
>>> 254*232*215*113*3+15
4294967295L

А вот и код:

def factor(x, y):
    # y should be smaller than x. If x=y then {y, 1, 0} is the best solution
    assert(x > y)

    best_output = []

    # try all possible remainders from 0 to y 
    for remainder in xrange(y+1):
        output = []
        composite = x - remainder
        factors = getFactors(composite)

        # check if any factor is larger than y
        bad_remainder = False
        for n in factors.iterkeys():
            if n > y: 
                bad_remainder = True
                break
        if bad_remainder: continue

        # make the best factors
        while True:
            results = largestFactors(factors, y)
            if results == None: break
            output += [results[0]]
            factors = results[1]

        # store the best output
        output = output + [remainder]
        if len(best_output) == 0 or len(output) < len(best_output):
            best_output = output

    return best_output

# Heuristic
# The bigger the number the better. 8 is more compact than 2,2,2 etc...

# Find the most factors you can have below or equal to y
# output the number and unused factors that can be reinserted in this function
def largestFactors(factors, y):
    assert(y > 1)
    # iterate from y to 2 and see if the factors are present.
    for i in xrange(y, 1, -1):
        try_another_number = False
        factors_below_y = getFactors(i)
        for number, copies in factors_below_y.iteritems():
            if number in factors:
                if factors[number] < copies:
                    try_another_number = True
                    continue # not enough factors
            else:
                try_another_number = True
                continue # a factor is not present

        # Do we want to try another number, or was a solution found?
        if try_another_number == True:
            continue
        else:
            output = 1
            for number, copies in factors_below_y.items():
                remaining = factors[number] - copies
                if remaining > 0:
                    factors[number] = remaining
                else:
                    del factors[number]
                output *= number ** copies

            return (output, factors)

    return None # failed




# Find prime factors. You can use any formula you want for this.
# I am using elliptic curve factorization from http://sourceforge.net/projects/pyecm
import pyecm, collections, copy

getFactors_cache = {}
def getFactors(n):
    assert(n != 0)
    # attempt to retrieve from cache. Returns a copy
    try:
        return copy.copy(getFactors_cache[n])
    except KeyError:
        pass

    output = collections.defaultdict(int)
    for factor in pyecm.factors(n, False, True, 10, 1):
        output[factor] += 1

    # cache result
    getFactors_cache[n] = output

    return copy.copy(output)

Ответ на первый вопрос

Вы говорите, что хотите сжать числа, но из ваших примеров эти последовательности длиннее, чем неразложенные числа. Невозможно сжимать эти числа без дополнительной информации в систему, которую вы пропустили (вероятность последовательностей / есть программируемый клиент?). Не могли бы вы рассказать подробнее?

Вот математическое объяснение того, почему текущие ответы на первую часть вашей проблемы никогда не решат вашу вторую проблему. Это не имеет ничего общего с проблемой ранца.

Shannon's entropy

Это алгоритм энтропии Шеннона. Он сообщает вам теоретическое минимальное количество битов, которое вам необходимо для представления последовательности {X0, X1, X2, ..., Xn-1, Xn}, где p (Xi) - вероятность увидеть токен Xi.

Предположим, что от X0 до Xn - это диапазон от 0 до 4294967295 (диапазон целого числа). Из того, что вы описали, каждое число, как и другое, может появиться. Поэтому вероятность каждого элемента составляет 1/4294967296.

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

import math

def entropy():
    num = 2**32
    probability = 1./num
    return -(num) * probability * math.log(probability, 2)
    # the (num) * probability cancels out

Неудивительно, что энтропия равна 32. Нам требуется 32 бита для представления целого числа, где каждое число одинаково вероятно. Единственный способ уменьшить это число - увеличить вероятность некоторых чисел и уменьшить вероятность других. Вы должны объяснить поток более подробно.

Ответ на второй вопрос

Правильный способ сделать это - использовать base64 при взаимодействии с HTTP. Очевидно, в Java этого нет в стандартной библиотеке, но я нашел ссылку на бесплатную реализацию:

http://iharder.sourceforge.net/current/java/base64/

Вот "псевдокод", который отлично работает в Python и не должен быть сложным для преобразования в Java (моя Java ржавая):

def longTo64(num):
    mapping = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_"
    output = ""

    # special case for 0
    if num == 0:
        return mapping[0]

    while num != 0:
        output = mapping[num % 64] + output
        num /= 64

    return output

Если у вас есть контроль над веб-сервером и веб-клиентом, и вы можете без проблем анализировать все HTTP-запросы, вы можете выполнить обновление до base85. Согласно википедии, кодировка url допускает до 85 символов . В противном случае вам может потребоваться удалить несколько символов из сопоставления.

Вот еще один пример кода на Python

def longTo85(num):
    mapping = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_.~!*'();:@&=+$,/?%#[]"
    output = ""
    base = len(mapping)

    # special case for 0
    if num == 0:
        return mapping[0]

    while num != 0:
        output = mapping[num % base] + output
        num /= base

    return output

А вот и обратная операция:

def stringToLong(string):
    mapping = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_.~!*'();:@&=+$,/?%#[]"
    output = 0
    base = len(mapping)

    place = 0
    # check each digit from the lowest place
    for digit in reversed(string):
        # find the number the mapping of symbol to number, then multiply by base^place
        output += mapping.find(digit) * (base ** place)
        place += 1

    return output

Вот график алгоритма Шеннона в разных базах. alt text

Как видите, чем выше основание, тем меньше символов необходимо для представления числа. На base64 требуется ~ 11 символов для представления long. На base85 он становится ~ 10 символов.

6 голосов
/ 25 апреля 2009

Изменить после окончательного объяснения:

Я бы подумал, что base64 - лучшее решение, так как есть стандартные функции, которые имеют с ним дело, и варианты этой идеи не дают большого улучшения. Здесь ответили более подробно другие.

Что касается первоначального вопроса, то, хотя код работает, он не гарантированно будет запущен в любое разумное время, как было дано ответом и комментарием на этот вопрос LFSR Consulting.

Оригинальный ответ:

Вы имеете в виду что-то подобное?

Редактировать - исправлено после комментария.

shortest_output = {}

foreach (int R = 0; R <= X; R++) {
    // iteration over possible remainders
    // check if the rest of X can be decomposed into multipliers
    newX = X - R;
    output = {};

    while (newX > Y) {
       int i;
       for (i = Y; i > 1; i--) {
           if ( newX  % i == 0) { // found a divider
           output.append(i);
           newX  = newX /i;  
           break;
           }
       }

       if (i == 1) { // no dividers <= Y
          break;
       }
    }
    if (newX != 1) {
        // couldn't find dividers with no remainder
        output.clear();
    }
    else {
        output.append(R);
            if (output.length() < shortest_output.length()) {
                 shortest_output = output;
            }
    }
}
5 голосов
/ 29 апреля 2009

Звучит так, как будто вы хотите сжать случайные данные - это невозможно по теоретико-информационным причинам. (См. http://www.faqs.org/faqs/compression-faq/part1/preamble.html вопрос 9.) Используйте Base64 для составных двоичных представлений ваших чисел и покончите с этим.

4 голосов
/ 30 апреля 2009

Проблема, которую вы пытаетесь решить (вы имеете дело с подмножеством проблемы, учитывая, что у вас есть ограничение y), называется Целочисленная факторизация , и это не может быть сделано эффективно, учитывая любой известный алгоритм:

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

Эта проблема делает возможным использование ряда криптографических функций (а именно RSA, который использует 128-битные ключи - длина составляет половину от этого.) На вики-странице есть несколько полезных ресурсов, которые должны направить вас в правильном направлении с вашей проблемой.

Итак, твой тизер мозгов - действительно тизер мозгов ... и если ты решаешь это эффективно, мы можем поднять твои математические навыки до уровня выше среднего!

3 голосов
/ 25 апреля 2009

Обновлено после полной истории

Base64, скорее всего, ваш лучший вариант. Если вам нужно индивидуальное решение, вы можете попробовать внедрить систему Base 65+. Просто помните, что то, что 10000 можно записать как «10 ^ 4», не означает, что все можно записать как 10 ^ n, где n - целое число. Различные базовые системы - это самый простой способ написания чисел, и чем больше основание, тем меньше цифр требуется. Плюс большинство библиотек фреймворков содержат алгоритмы для кодирования Base64. (Какой язык вы используете?).

Одним из способов дальнейшей упаковки URL-адресов является тот, который вы упомянули, но в Base64.

int[] IDs;
IDs.sort() // So IDs[i] is always smaller or equal to IDs[i-1].

string url = Base64Encode(IDs[0]);

for (int i = 1; i < IDs.length; i++) {
  url += "," + Base64Encode(IDs[i-1] - IDs[i]);
}

Обратите внимание, что вам нужен какой-то разделитель, так как начальный идентификатор может быть произвольно большим, а разница между двумя идентификаторами МОЖЕТ быть больше 63, и в этом случае одной цифры Base64 недостаточно.

Обновлено

Просто повторю, что проблема неразрешима. Для Y = 64 вы не можете написать 87681 в множителях + остаток, где каждое из них меньше 64. Другими словами, вы не можете написать ни одно из чисел 87617..87681 с множителями ниже 64. Каждое из этих чисел имеет элементарный срок свыше 64. 87616 можно записать элементарными терминами ниже 64, но тогда вам понадобятся эти + 65, и поэтому остаток будет больше 64.

Так что, если это был просто головоломка, это неразрешимо. Была ли какая-то практическая цель для этого, которая могла бы быть достигнута иным способом, чем использование умножения и остатка?

И да, это действительно должен быть комментарий, но я потерял способность комментировать в какой-то момент. : Р

Я считаю, что наиболее близким решением является решение Евгения. Также легко расширить решение Евгения, чтобы удалить предел для остатка, и в этом случае он сможет найти решение, где множители меньше Y, а остаток настолько мал, насколько это возможно, даже если больше Y.

Старый ответ:

Если вы ограничите, что каждое число в массиве должно быть ниже y, то для этого не будет никакого решения. Учитывая достаточно большой х и достаточно маленький у, вы окажетесь в невозможной ситуации. Как пример с y, равным 2, x из 12, вы получите 2 * 2 * 2 + 4, так как 2 * 2 * 2 * 2 будет 16. Даже если вы допустите отрицательные числа с abs (n) ниже y, это не работает так, как вам нужно 2 * 2 * 2 * 2 - 4 в приведенном выше примере.

И я думаю, что проблема в NP-Complete, даже если вы ограничите задачу входными данными, у которых, как известно, есть ответ, где последний член меньше y. Это звучит очень похоже на [проблему с рюкзаком] [1]. Конечно, я могу ошибаться.

Edit:

Без более точного описания проблемы трудно решить проблему, но один вариант может работать следующим образом:

  1. установить ток = х
  2. отключить ток до его условий
  3. Если один из терминов больше y, текущее число нельзя описать терминами больше y. Уменьшите одно с текущего и повторите с 2.
  4. Текущее число может быть выражено в терминах меньше чем у.
  5. Рассчитать остаток
  6. Объедините как можно больше терминов.

(Евгений Доктор имеет более сознательную (и работающую) реализацию этого, чтобы избежать путаницы, я пропустил реализацию.)

2 голосов
/ 05 мая 2009

ОП. Написал:

Моей целью изначально было придумать конкретный способ упаковать 1..n большой целые числа (иначе длинные) вместе, так что их строковое представление заметно короче, чем написание фактического число. Думайте кратно десяти, 10 ^ 6 и 1 000 000 одинаковы, однако длина представления в символы не.

Я уже шел по этому пути раньше, и как бы весело ни было выучить всю математику, чтобы сэкономить ваше время, я просто укажу вам: http://en.wikipedia.org/wiki/Kolmogorov_complexity

В двух словах некоторые строки можно легко сжать, изменив обозначение:

10^9 (4 characters) = 1000000000 (10 characters)

Другие не могут:

7829203478 = some random number...

Это большое упрощение статьи, на которую я ссылался выше, поэтому я рекомендую вам прочитать ее, а не принимать мое объяснение за чистую монету.

Edit: Если вы пытаетесь создать RESTful URL для некоторого набора уникальных данных, почему бы вам не использовать хеш, такой как MD5? Затем включите хеш как часть URL, затем ищите данные на основе хеша. Или я что-то упускаю очевидное?

1 голос
/ 05 мая 2009

По сравнению с исходным запросом алгоритма: есть ли ограничение на размер последнего числа (помимо этого оно должно храниться в 32-битном int)? (Оригинальный запрос - это все, что я могу решить, лол.)

Тот, который создает самый короткий список:

bool negative=(n<1)?true:false;
int j=n%y;
if(n==0 || n==1)
{
list.append(n);
return;
}
while((long64)(n-j*y)>MAX_INT && y>1) //R has to be stored in int32
{
y--;
j=n%y;
}
if(y<=1)
fail //Number has no suitable candidate factors. This shouldn't happen

int i=0;
for(;i<j;i++)
{
list.append(y);
}
list.append(n-y*j);
if(negative)
list[0]*=-1;
return;

Немного упрощенно по сравнению с большинством ответов, которые были даны до сих пор, но он достигает желаемой функциональности оригинального сообщения ... Это немного грязно, но, надеюсь, полезно :)

1 голос
/ 29 апреля 2009

Вы женаты на использовании Java? Python имеет целый пакет, предназначенный именно для этой цели. Это даже очистит кодировку, чтобы вы были безопасны для URL.

Собственное решение Python

Стандартный модуль, который я рекомендую, - base64, который преобразует произвольные строки символов в очищенный формат base64. Вы можете использовать его вместе с модулем pickle, который обрабатывает преобразование из списков длинных (фактически произвольного размера) в сжатое строковое представление.

Следующий код должен работать на любой ванильной установке Python:

import base64
import pickle

# get some long list of numbers
a = (854183415,1270335149,228790978,1610119503,1785730631,2084495271,
    1180819741,1200564070,1594464081,1312769708,491733762,243961400,
    655643948,1950847733,492757139,1373886707,336679529,591953597,
    2007045617,1653638786)

# this gets you the url-safe string
str64 = base64.urlsafe_b64encode(pickle.dumps(a,-1))
print str64
>>> gAIoSvfN6TJKrca3S0rCEqMNSk95-F9KRxZwakqn3z58Sh3hYUZKZiePR0pRlwlfSqxGP05KAkNPHUo4jooOSixVFCdK9ZJHdEqT4F4dSvPY41FKaVIRFEq9fkgjSvEVoXdKgoaQYnRxAC4=

# this unwinds it
a64 = pickle.loads(base64.urlsafe_b64decode(str64))
print a64
>>> (854183415, 1270335149, 228790978, 1610119503, 1785730631, 2084495271, 1180819741, 1200564070, 1594464081, 1312769708, 491733762, 243961400, 655643948, 1950847733, 492757139, 1373886707, 336679529, 591953597, 2007045617, 1653638786)

Надеюсь, это поможет. Использование Python, вероятно, наиболее близко к решению из 1 строки.

1 голос
/ 29 апреля 2009

Исходный метод, который вы выбрали (a * b + c * d + e), будет очень трудно найти оптимальные решения просто из-за большого пространства поиска возможностей. Вы можете факторизовать число, но это то, что "+ e" усложняет ситуацию, так как вам нужно не только , а просто это число, а сразу несколько сразу под ним.

Два метода для сжатия пружины, которые сразу же приходят на ум, оба из которых дают намного лучшую, чем 10%, экономию пространства по сравнению с числовым представлением.

64-битное число находится в диапазоне (без знака):

                         0 to
18,446,744,073,709,551,616

или (подписано):

-9,223,372,036,854,775,808 to
 9,223,372,036,854,775,807

В обоих случаях вам нужно уменьшить количество взятых 20 символов (без запятых) до значения немного меньшего.

Первый - это просто BCD-ify число, которое кодирует base64 (на самом деле это слегка измененный base64, поскольку "/" не будет кошерным в URL-адресе - вы должны использовать один из допустимых символов, например "_").

Преобразование его в BCD сохранит две цифры (или знак и цифру) в одном байте, что даст вам сокращение пространства на 50% (10 байтов). Кодирование с помощью base 64 (который превращает каждые 3 байта в 4 символа base64) превратит первые 9 байтов в 12 символов, а этот десятый байт - в 2 символа, всего 14 символов - это экономия 30%.

Единственный лучший способ - просто кодировать base64 двоичным представлением. Это лучше, потому что BCD имеет небольшое количество потерь (каждая цифра требует только 3,32 бита для хранения [log 2 10], но BCD использует 4).

Работая с двоичным представлением, нам нужно только base64 кодировать 64-битное число (8 байт). Это требует 8 символов для первых 6 байтов и 3 символа для последних 2 байтов. Это 11 символов base64 для экономии 45%.

Если требуется сжатие максимум , для кодировки URL доступно 73 символа:

ABCDEFGHIJKLMNOPQRSTUVWXYZ
abcdefghijklmnopqrstuvwxyz
0123456789$-_.+!*'(),

Технически, вы, вероятно, могли бы закодировать base-73, который, по грубым подсчетам, все равно занимал бы 11 символов, но с более сложным кодом, который, на мой взгляд, не стоит.

Конечно, это максимальное сжатие из-за максимальных значений. На другом конце шкалы (1 цифра) это кодирование фактически дает больше данных (расширение, а не сжатие). Вы можете видеть, что улучшения начинаются только для чисел свыше 999, где 4 цифры можно превратить в 3 символа base64:

Range (bytes)  Chars  Base64 chars  Compression ratio
-------------  -----  ------------  -----------------
     < 10 (1)      1       2             -100%
    < 100 (1)      2       2                0%
   < 1000 (2)      3       3                0%
   < 10^4 (2)      4       3               25%
   < 10^5 (3)      5       4               20%
   < 10^6 (3)      6       4               33%
   < 10^7 (3)      7       4               42%
   < 10^8 (4)      8       6               25%
   < 10^9 (4)      9       6               33%
  < 10^10 (5)     10       7               30%
  < 10^11 (5)     11       7               36%
  < 10^12 (5)     12       7               41%
  < 10^13 (6)     13       8               38%
  < 10^14 (6)     14       8               42%
  < 10^15 (7)     15      10               33%
  < 10^16 (7)     16      10               37%
  < 10^17 (8)     17      11               35%
  < 10^18 (8)     18      11               38%
  < 10^19 (8)     19      11               42%
  <  2^64 (8)     20      11               45%
1 голос
/ 29 апреля 2009

Обновление: Я не получил все, поэтому переписал все это в стиле Java. Я не думал о случае простых чисел, который больше делителя. Это исправлено сейчас. Я оставляю оригинальный код, чтобы получить идею.

Обновление 2: Теперь я рассматриваю случай большого простого числа другим способом. Таким образом, результат получается в любом случае.

public final class PrimeNumberException extends Exception {

    private final long primeNumber;

    public PrimeNumberException(long x) {
        primeNumber = x;
    }

    public long getPrimeNumber() {
        return primeNumber;
    }
}

public static Long[] decompose(long x, long y) {
    try {
        final ArrayList<Long> operands = new ArrayList<Long>(1000);
        final long rest = x % y;
        // Extract the rest so the reminder is divisible by y
        final long newX = x - rest;
        // Go into recursion, actually it's a tail recursion
        recDivide(newX, y, operands);            
    } catch (PrimeNumberException e) {
        // return new Long[0];
        // or do whatever you like, for example
        operands.add(e.getPrimeNumber());
    } finally {
        // Add the reminder to the array
        operands.add(rest);
        return operands.toArray(new Long[operands.size()]);
    }
}

// The recursive method
private static void recDivide(long x, long y, ArrayList<Long> operands)
    throws PrimeNumberException {
    while ((x > y) && (y != 1)) {
        if (x % y == 0) {
            final long rest = x / y;
            // Since y is a divisor add it to the list of operands
            operands.add(y);
            if (rest <= y) {
                // the rest is smaller than y, we're finished
                operands.add(rest);
            }
            // go in recursion
            x = rest;
        } else {
            // if the value x isn't divisible by y decrement y so you'll find a 
            // divisor eventually
            if (--y == 1) {
                throw new PrimeNumberException(x);
            }
        }
    }
}

Оригинал: Вот некоторый рекурсивный код, который я придумал. Я бы предпочел кодировать его на каком-то функциональном языке, но это было необходимо в Java. Я не потрудился преобразовать числа в целое, но это не должно быть так сложно (да, я ленивый;)

public static Long[] decompose(long x, long y) {
    final ArrayList<Long> operands = new ArrayList<Long>();
    final long rest = x % y;
    // Extract the rest so the reminder is divisible by y
    final long newX = x - rest;
    // Go into recursion, actually it's a tail recursion
    recDivide(newX, y, operands);
    // Add the reminder to the array
    operands.add(rest);
    return operands.toArray(new Long[operands.size()]);
}

// The recursive method
private static void recDivide(long newX, long y, ArrayList<Long> operands) {
    long x = newX;
    if (x % y == 0) {
        final long rest = x / y;
        // Since y is a divisor add it to the list of operands
        operands.add(y);
        if (rest <= y) {
            // the rest is smaller than y, we're finished
            operands.add(rest);
        } else {
            // the rest can still be divided, go one level deeper in recursion
            recDivide(rest, y, operands);
        }
    } else {
        // if the value x isn't divisible by y decrement y so you'll find a divisor    
        // eventually
        recDivide(x, y-1, operands);
    }
}
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...