我有一个问题，然后给出一些输入数n，我们必须检查是否是其他一些的否定因素。
INPUT 24，OUTPUT true INPUT 25，OUTPUT false 我为它编写了以下程序： -
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，这实际上是浪费时间。
我也试过维护一个表格来进行阶乘
那么，我的问题是，是否有更有效的方法来检查一个数字是否是阶乘的？
由于你在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;
}
但是，为了提高效率，最好的选择可能是第一个。将计算成本移至构建阶段而不是运行时。与表查找相比，计算成本显着的情况下，这是一个标准技巧。
您甚至可以通过使用查找表的二进制搜索使其均匀模式效率，但这可能不是必需的，因为其中只有20个元素。
如果数字是阶乘的，那么对于某些n，其因子是1..n。
假设n是整数变量，我们可以执行以下操作：
int findFactNum(int test){
for(int i=1, int sum=1; sum <= test; i++){
sum *= i; //Increment factorial number
if(sum == test)
return i; //Factorial of i
}
return 0; // factorial not found
}
现在将数字24传递给此功能块，它应该工作。此函数返回刚刚传递的阶乘的数字。
通过简单检查数字是奇数还是偶数（使用％2），您可以加速至少一半的情况。没有奇数（禁止1）可以是任何其他数字的阶乘
#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");
}
您可以创建一个包含阶乘列表的数组： 就像在下面的代码中我创建了一个包含最多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;
}
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 ??
* */
}