Ну, мы все знаем, что если N задано, легко вычислить N!. Но как насчет обратного?
N! дается, и вы собираетесь найти N - возможно ли это? Мне любопытно.
Обратный факториал
Ответ 1
- Установите
X=1. - Создать
F=X! - Является ли F = вход? Если да, то
X- N. - Если нет, то установите
X=X+1, затем снова запустите на # 2.
Вы можете оптимизировать, используя предыдущий результат F, чтобы вычислить новый F (new F = new X * old F).
Это так же быстро, как движение в противоположном направлении, если не быстрее, учитывая, что разделение обычно занимает больше времени, чем умножение. Гарантируется, что для данного факториала A! все целые числа меньше A в качестве факторов в дополнение к A, поэтому вы потратили бы столько времени на факторинг, как вы просто вычисляли бы факториал.
Ответ 2
Если у вас Q = N! в двоичном выражении, подсчитывают конечные нули. Назовите этот номер J.
Если N равно 2K или 2K + 1, то J равно 2K минус число 1 в двоичном представлении 2K, поэтому добавьте 1 снова и снова до тех пор, пока количество добавленных вами 1 не будет равно числу 1 в результате.
Теперь вы знаете 2K, а N - 2K или 2K + 1. Чтобы рассказать, какой из них он, подсчитайте коэффициенты наибольшего простого (или любого простого, действительно) в 2K + 1 и используйте это для проверки Q = (2K + 1)!.
Например, пусть Q (в двоичном выражении)
1111001110111010100100110000101011001111100000110110000000000000000000
(Извините, это так мало, но у меня нет инструментов, которые можно манипулировать большими числами.)
Есть 19 конечных нулей, которые
10011
Теперь increment:
1: 10100
2: 10101
3: 10110 bingo!
Итак, N равно 22 или 23. Мне нужен простой коэффициент 23, и, ну, я должен выбрать 23 (бывает, что 2K + 1 является простым, но я не планировал это, и он не нужен). Таким образом, 23 ^ 1 должен делить 23!, он не делит Q, поэтому
N=22
Ответ 3
int inverse_factorial(int factorial){
int current = 1;
while (factorial > current) {
if (factorial % current) {
return -1; //not divisible
}
factorial /= current;
++current;
}
if (current == factorial) {
return current;
}
return -1;
}
Ответ 4
Да. Позвольте называть ваш вход x. При малых значениях x вы можете просто попробовать все значения n и посмотреть, будет ли n!= x. Для больших x вы можете бинарно искать по n, чтобы найти правильное n (если оно существует). Обратите внимание, что у нас есть n! ≈ e ^ (n ln n - n) (это приближение Стирлинга), поэтому вы знаете примерно, где искать.
Проблема, конечно, в том, что очень мало чисел - факториалы; поэтому ваш вопрос имеет смысл только для небольшого набора входов. Если ваш вход мал (например, подходит для 32-разрядного или 64-битного целого), то наилучшим решением будет поисковая таблица.
(Конечно, вы могли бы рассмотреть более общую проблему обращения Gamma function. И снова бинарный поиск, вероятно, был бы лучшим способом, а не что-то аналитическое. Я был бы рад, если бы меня здесь показали неправильно.)
Изменить. На самом деле, в случае, если вы точно не знаете, что x является факториальным номером, вы можете не получить столько (или что-либо) с бинарным поиском с использованием приближения Стирлинга или гамма-функции, над простыми решениями. Обратный факториал растет медленнее, чем логарифмический (это потому, что факториал является суперэкспоненциальным), и вам нужно делать арифметику произвольной точности, чтобы найти факториалы и умножить эти числа.
Например, см. ответ Драко Атера за идею о том, что (при расширении до арифметики произвольной точности) будет работать для всех x. Даже проще и, вероятно, даже быстрее, потому что умножение быстрее, чем деление, является ответом Dav, который является наиболее естественным алгоритмом... эта проблема - еще один триумф простоты.: -)
Ответ 5
Хорошо, если вы знаете, что M действительно является факториалом какого-то целого числа, то вы можете использовать
n! = Gamma(n+1) = sqrt(2*PI) * exp(-n) * n^(n+1/2) + O(n^(-1/2))
Вы можете решить эту проблему (или, действительно, решить ln(n!) = ln Gamma(n+1)) и найти ближайшее целое число.
Он по-прежнему нелинейный, но вы можете получить приблизительное решение путем итерации (на самом деле, я ожидаю, что коэффициент n^(n+1/2) достаточен).
Ответ 6
Несколько способов. Используйте таблицы поиска, используйте двоичный поиск, используйте линейный поиск...
Таблицы поиска являются очевидными:
for (i = 0; i < MAX; ++i)
Lookup[i!] = i; // you can calculate i! incrementally in O(1)
Вы можете реализовать это, используя хэш-таблицы, или, если вы используете С++/С#/Java, у них есть своя хэш-таблица - как контейнеры.
Это полезно, если вам нужно делать это много раз и каждый раз, когда он должен быть быстрым, но вы можете позволить себе потратить некоторое время на создание этой таблицы.
Двоичный поиск: предположим, что число m = (1 + N!) / 2. Является ли m! больше, чем N!? Если да, уменьшите поиск между 1 и m!, в противном случае уменьшите его между m! + 1 и N!. Рекурсивно применяйте эту логику.
Конечно, эти цифры могут быть очень большими, и вы можете сделать много нежелательных операций. Лучше всего искать между 1 и sqrt(N!) с помощью двоичного поиска или пытаться найти еще более удобные аппроксимации, хотя это может быть нелегко. Изучите функцию гаммы .
Линейный поиск: возможно, лучший в этом случае. Вычислите 1*2*3*...*k, пока продукт не будет равен N! и не будет выводить k.
Ответ 7
Вот код clojure:
(defn- reverse-fact-help [n div]
(cond (not (= 0 (rem n div))) nil
(= 1 (quot n div)) div
:else (reverse-fact-help (/ n div) (+ div 1))))
(defn reverse-fact [n] (reverse-fact-help n 2))
Предположим, что n = 120, div = 2. 120/2 = 60, 60/3 = 20, 20/4 = 5, 5/5 = 1, возврат 5
Предположим, что n = 12, div = 2. 12/2 = 6, 6/3 = 2, 2/4 =.5, return 'nil'
Ответ 8
int p = 1,i;
//assume variable fact_n has the value n!
for(i = 2; p <= fact_n; i++) p = p*i;
//i is the number you are looking for if p == fact_n else fact_n is not a factorial
Я знаю, что это не псевдокод, но довольно легко понять
Ответ 9
inverse_factorial( X )
{
X_LOCAL = X;
ANSWER = 1;
while(1){
if(X_LOCAL / ANSWER == 1)
return ANSWER;
X_LOCAL = X_LOCAL / ANSWER;
ANSWER = ANSWER + 1;
}
}
Ответ 10
Эта функция основана на последовательных приближениях! Я создал его и реализовал его в Advanced Trigonometry Calculator 1.7.0
double arcfact(double f){
double result=0,precision=1000;
int i=0;
if(f>0){
while(precision>1E-309){
while(f>fact(result+precision)&&i<10){
result=result+precision;
i++;
}
precision=precision/10;
i=0;
}
}
else{
result=0;
}
return result;
}
Ответ 11
Если вы не знаете, является ли число M N! или нет, то достойный тест должен проверить, делится ли он всеми малыми штрихами, пока приближение Sterling этого числа больше, чем M. В качестве альтернативы, если у вас есть таблица факториалов, но она не подходит достаточно высоко, вы можете выбрать самый большой фактор в своей таблице и убедиться, что M делится на это.
Ответ 12
Проверьте обратные гамма-функции отсюда http://functions.wolfram.com/GammaBetaErf/InverseGammaRegularized/ Они имеют несколько аппроксимаций
Ответ 13
В C из моего приложения Advanced Trigonometry Calculator v1.6.8
double arcfact(double f) {
double i=1,result=f;
while((result/(i+1))>=1) {
result=result/i;
i++;
}
return result;
}
Что вы думаете об этом? Правильно работает для целых чисел факториалов.
Ответ 14
Код C/С++ для what the factorial (r является результирующим факториалом):
int wtf(int r) {
int f = 1;
while (r > 1)
r /= ++f;
return f;
}
Примеры тестов:
Call: wtf(1)
Output: 1
Call: wtf(120)
Output: 5
Call: wtf(3628800)
Output: 10
Ответ 15
Просто разделите на положительные числа, то есть: 5!= 120 → > 120/2 = 60 || 60/3 = 20 || 20/4 = 5 || 5/5 = 1
Итак, последнее число перед результатом = 1 - ваш номер.
В коде вы можете сделать следующее:
number = res
for x=2;res==x;x++{
res = res/x
}
или что-то в этом роде. Этот расчет нуждается в улучшении для неточных чисел.
Ответ 16
Большинство номеров не находятся в диапазоне выходов факториальной функции. Если это то, что вы хотите проверить, легко получить приближение с использованием формулы Стирлинга или количество цифр целевого номера, как упомянуто другими, затем выполнить двоичный поиск для определения факториалов выше и ниже заданного числа.
Более интересным является построение обратной функции Гамма, которая расширяет факториальную функцию до положительных действительных чисел (и для большинства комплексных чисел тоже). Оказывается, что построение обратного является трудной задачей. Тем не менее, он был определен явно для большинства положительных реальных чисел в 2012 году в следующем документе: http://www.ams.org/journals/proc/2012-140-04/S0002-9939-2011-11023-2/S0002-9939-2011-11023-2.pdf. Явная формула приведена в следствии 6 в конце статьи.
Обратите внимание, что он включает в себя интеграл в бесконечной области, но при тщательном анализе я считаю, что разумная реализация может быть построена. То, что лучше, чем простая схема последовательного приближения на практике, я не знаю.
Ответ 17
п! очень легко учитывать. Так что продолжайте делиться на 2,3,5,7... и проверьте экспоненты, сколько раз вы могли бы разделить.
Теперь вопрос в том, что у вас есть n! что представляет собой показатель простого p в нем?
Во-первых, n! может иметь только простые числа вплоть до n, включая n, если он является простым.
Вы добавляете один за каждый раз простой p или любая его сила находится в пределах n. Сколько раз вы увидите p. Ну, это должно быть самое большое k, для которого
Значение
то же самое из простых степеней
Далее следует алгоритм.
Предположим, что у нас есть 10888869450418352160768000000
Мы можем разделить на
2, 23 раза
3, 13 раз
5, 6
7, 3
11, 2
13, 2
17, 1
23, 1
не делится на 29
Это означает, что это число между 23 и 29. (Обычно диапазон намного больше, но этот пример по-прежнему полезен.)
Теперь мы можем использовать бинарный поиск между 23 и 29, чтобы получить набор, который может быть делимым на 2, 23 раза. Обратите внимание, что может быть только два таких числа. Мы попробуем 26 и легко найдем, что это
Если это не так, мы продолжим сегмент 23-26 или 26-29 в зависимости от результата.
Итак, это либо 26, либо 27. Мы делаем то же самое для 3, а остальные - до тех пор, пока не получим совпадение ни с одним из двух возможных чисел. Цифры будут иметь разные результаты для хотя бы одного из заданных простых чисел.
Итак, если вышеперечисленное является факториалом, то это факторный показатель 27. Проверка того же, что и выше для 5,7,11,13,17,19 и 23, показывает, что все нормально, и что это действительно 27.