Как проверить, нет ли факториала или нет?

Question

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

ВХОД 24, ВЫХОДНОЙ верно
ВХОД 25, ВЫХОДНОЙ ложные
я написал следующую программу для него: -

int factorial(int num1) 
    { 
     if(num1 > 1) 
     { 
      return num1* factorial(num1-1) ; 
     } 
     else 
     { 
      return 1 ; 
     } 
    } 

    int is_factorial(int num2) 
    { 
     int fact = 0 ; 
     int i = 0 ; 
     while(fact < num2) 
     { 
      fact = factorial(i) ; 
      i++ ; 
     } 
     if(fact == num2) 
     { 
      return 0 ; 
     } 
     else 
     { 
      return -1; 
     } 
    } 

Обе эти функции, кажется, правильно работать.
Когда мы их много раз поставляем для больших входов, тогда is_factorial будет многократно звонить factorial, что будет действительно пустой тратой времени.
Я также пытался поддерживать таблицу для факториалов

Итак, мой вопрос, есть ли какой-то более эффективный способ, чтобы проверить, является ли число факторным или нет?

Answer 1

Это является расточительных счетные факториалов непрерывно, как, что, так как вы дублируя работу в x!, когда вы делаете (x+1)!, (x+2)! и так далее.

---

Один из подходов заключается в поддержании список факториалов в пределах заданного диапазона (например, все 64-битных беззнаковых факториалов) и просто сравнить его с этим. Учитывая, насколько быстрые факториалы увеличивают стоимость, этот список не будет очень большим. На самом деле, вот C мета-программа, которая на самом деле генерирует функцию для вас:

#include <stdio.h> 

int main (void) { 
    unsigned long long last = 1ULL, current = 2ULL, mult = 2ULL; 
    size_t szOut; 

    puts ("int isFactorial (unsigned long long num) {"); 
    puts (" static const unsigned long long arr[] = {"); 
    szOut = printf ("  %lluULL,", last); 
    while (current/mult == last) { 
     if (szOut > 50) 
      szOut = printf ("\n  ") - 1; 
     szOut += printf (" %lluULL,", current); 
     last = current; 
     current *= ++mult; 
    } 
    puts ("\n };"); 
    puts (" static const size_t len = sizeof (arr)/sizeof (*arr);"); 
    puts (" for (size_t idx = 0; idx < len; idx++)"); 
    puts ("  if (arr[idx] == num)"); 
    puts ("   return 1;"); 
    puts (" return 0;"); 
    puts ("}"); 

    return 0; 
} 

При запуске, что вы получаете функцию:

int isFactorial (unsigned long long num) { 
    static const unsigned long long arr[] = { 
     1ULL, 2ULL, 6ULL, 24ULL, 120ULL, 720ULL, 5040ULL, 
     40320ULL, 362880ULL, 3628800ULL, 39916800ULL, 
     479001600ULL, 6227020800ULL, 87178291200ULL, 
     1307674368000ULL, 20922789888000ULL, 355687428096000ULL, 
     6402373705728000ULL, 121645100408832000ULL, 
     2432902008176640000ULL, 
    }; 
    static const size_t len = sizeof (arr)/sizeof (*arr); 
    for (size_t idx = 0; idx < len; idx++) 
     if (arr[idx] == num) 
      return 1; 
    return 0; 
} 

, который является довольно коротким и эффективным, даже для 64-битные факториалы.

---

Если вы после чисто программным способом (без таблиц поиска), вы можете использовать свойство, что факторный число является:

1 x 2 x 3 x 4 x ... x (n-1) x n 

для некоторого значения n.

Следовательно, вы можете просто начать делиться своим тестовым номером на 2, затем 3 затем 4 и так далее. Будет одна из двух вещей.

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

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

Предполагая, что ваши подразделения являются неотъемлемой частью, следующий код будет хорошей отправной точкой:

int isFactorial (unsigned long long num) { 
    unsigned long long currDiv = 2ULL; 
    while (num != 1ULL) { 
     if ((num % currDiv) != 0) 
      return 0; 
     num /= currDiv; 
     currDiv++; 
    } 
    return 1; 
} 

---

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

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

Answer 2

Если число является факториалом, то его коэффициенты равны 1..n для некоторого n.

Предполагая п целочисленной переменной, мы можем сделать следующее:

int findFactNum(int test){ 
    for(int i=1, int sum=1; sum <= test; i++){ 
    if(sum == test) 
     return i; //Factorial of i 
    sum *= i; //Increment factorial number 
    } 
return 0; // factorial not found 
} 

Переходим число 24 для функционального блока и он должен работать. Эта функция возвращает число, факториал которого вы только что прошли.

Answer 3

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

Answer 4

#include<stdio.h> 
main() 
{ 
     float i,a; 
     scanf("%f",&a); 
     for(i=2;a>1;i++) 
     a/=i; 
     if(a==1) 
     printf("it is a factorial"); 
     else 
     printf("not a factorial"); 
} 

Answer 5

public long generateFactorial(int num){ 
    if(num==0 || num==1){ 
     return 1; 
    } else{ 
     return num*generateFactorial(num-1); 
    } 
} 
public int getOriginalNum(long num){ 
    List<Integer> factors=new LinkedList<>(); //This is list of all factors of num 
    List<Integer> factors2=new LinkedList<>();  //List of all Factorial factors for eg: (1,2,3,4,5) for 120 (=5!) 
    int origin=1;    //number representing the root of Factorial value (for eg origin=5 if num=120) 
    for(int i=1;i<=num;i++){ 
     if(num%i==0){ 
      factors.add(i);  //it will add all factors of num including 1 and num 
     } 
    } 

    /* 
    * amoong "factors" we need to find "Factorial factors for eg: (1,2,3,4,5) for 120" 
    * for that create new list factors2 
    * */ 
    for (int i=1;i<factors.size();i++) {   
     if((factors.get(i))-(factors.get(i-1))==1){ 

      /* 
      * 120 = 5! =5*4*3*2*1*1 (1!=1 and 0!=1 ..hence 2 times 1) 
      * 720 = 6! =6*5*4*3*2*1*1 
      * 5040 = 7! = 7*6*5*4*3*2*1*1 
      * 3628800 = 10! =10*9*8*7*6*5*4*3*2*1*1 
      * ... and so on 
      * 
      * in all cases any 2 succeding factors inf list having diff=1 
      * for eg: for 5 : (5-4=1)(4-3=1)(3-2=1)(2-1=1)(1-0=1) Hence difference=1 in each case 
      * */ 

      factors2.add(i); //in such case add factors from 1st list " factors " to " factors2" 
     } else break; 
     //else if(this diff>1) it is not factorial number hence break 
     //Now last element in the list is largest num and ROOT of Factorial 
    } 
    for(Integer integer:factors2){ 
     System.out.print(" "+integer); 
    } 
    System.out.println(); 

    if(generateFactorial(factors2.get(factors2.size()-1))==num){ //last element is at "factors2.size()-1" 
     origin=factors2.get(factors2.size()-1); 
    } 
    return origin; 

    /* 
    * Above logic works only for 5! but not other numbers ?? 
    * */ 
} 

Answer 6

Вы можете создать массив, содержащий факторный список:
как в коде ниже я создал массив, содержащий факториалов до 20. теперь вы просто должны ввести номер и проверить, является ли он там в массиве или нет ..

#include <stdio.h> 
int main() 
{ 
    int b[19]; 
    int i, j = 0; 
    int k, l; 

    /*writing factorials*/ 
    for (i = 0; i <= 19; i++) { 
     k = i + 1; 
     b[i] = factorial(k); 
    } 
    printf("enter a number\n"); 
    scanf("%d", &l); 
    for (j = 0; j <= 19; j++) { 
     if (l == b[j]) { 
      printf("given number is a factorial of %d\n", j + 1); 
     } 
     if (j == 19 && l != b[j]) { 
      printf("given number is not a factorial number\n"); 
     } 
    } 
} 
int factorial(int a) 
{ 
    int i; 
    int facto = 1; 
    for (i = 1; i <= a; i++) { 
     facto = facto * i; 
    } 
    return facto; 
}