C语言,是否阶乘之和?

Apria 发布于 2017/02/19 20:34
阅读 613
收藏 0
输入一个整数N,判断其是否可以表示成一个正整数阶乘的形式或者几个不同正整数的阶乘之和。
输入一个整数N。
对应该整数N,若可以表示,输出YES,否则输出NO
4
-1
0
6
NO
NO
NO
YES
加载中
0
Knapd
Knapd

可以直接用一个循环直接累加一下就能判定是否能表示成一个整数的阶乘,用贪心算法可以两个都判断,时间复杂度是O(n!)

0
MikeManilone
MikeManilone

这个很简单,先把所有能表示成阶乘和的整数放到列表里面,以后输入的时候直接查表就行了。每次查询时间复杂度是O(1)。

0
烟雨三月
烟雨三月

设函数f(N)判断N是否可以表示成一个或几个不同整数的阶乘和。

当N<=0时,f(N)=NO。

当N=1时,f(N)=YES。

当N=2时,f(N)=YES。

当N为大于2的奇数时,因为只有1的阶乘是奇数,其他正整数的阶乘都是偶数,所以必然需要分成1的阶乘和其他整数的阶乘之和,所以f(N)=f(N-1)。

当N为大于2的偶数时,假设N最终可分成n1、n2、n3、……、nk(n1、n2、n3、……nk各不相同,且n1<n2<n3<……<nk)的阶乘和,即N=n1!+n2!+n3!+……+nk!,提取公因子,N=n1!*(1 + (n1+1)*(n1+2)*……*n2 + (n1+1)*(n1+2)*……*n3 + …… + (n1+1)*(n1+2)*……*nk),所以仅需判断N是否可以表示成该公式,如果N不能表示成n1的阶乘,则为NO,接下来判断剩余部分(用N1表示)能否表示成1 + (n1+1)*(n1+2)*……*n2 + (n1+1)*(n1+2)*……*n3 + …… + (n1+1)*(n1+2)*……*nk,如果N1为1则为YES,否则N1减去1后,能否表示成 (n1+1)*(n1+2)*……*n2 + (n1+1)*(n1+2)*……*n3 + …… + (n1+1)*(n1+2)*……*nk,首先能否提取公因子 (n1+1)*(n1+2)*……*n2,以此类推……

// 判断整数n是否为一个或多个不同整数的阶乘和,如果是则返回1,如果不是则返回0。
int isFactorialSum(int n) {
  if (n <= 0) {
    return 0;
  }

  if (n == 1 || n == 2) {
    return 1;
  }

  if (n % 2 == 1) {
    return isFactorialSum(n - 1);
  }

  int k = 2;
  while (1) {
    if (n % k != 0) {
      break;
    }

    while (n % k == 0) {
      n /= k;
      k++;
    }

    if (n == 1) {
      return 1;
    }

    if (n < k) {
      break;
    }
    n--;
  }
  return 0;
}

 

返回顶部
顶部