Question

C语言 取一数的阶乘的不为0的最高位的数

如：输入5，它的阶乘是120，输出2。这个题的难点在于如何避免溢出（合法输入是0-9999）。之前写过一个可以得到正确的数据，但是在学校的系统上交上后却提示“超时”，具体的代码可以看这个链接：http://zhidao.baidu.com/question/401713022.html?quesup2&oldq=1
之后我为了避免超时的问题，求阶乘改为递归，但是这时又难以实现去除阶乘尾部的0了：下面是自己可以写出的代码，求指教：
#include<stdio.h>
#include<stdlib.h>
int jiecheng(int a)
{
if (a==1||a==0)
return 1;
else
// while(jiecheng(a-1)>10 && jiecheng(a-1)%10 != 0){
// jiecheng(a-1) = (a-1)*jiecheng(a-2)/10;
// }
//这部分少了去零取尾数的功能，数据可能溢出
return (a*jiecheng(a-1));
}

int main()
{
int k, n,t;
char s[10];
while(1){
scanf("%s",s);
k=0;
t=0;
while(s[k]){
if(s[k]<'0' || s[k]>'9')
return 0;
t=t*10+(s[k]-'0');
k++;
}
printf("%5d -> %ld\n",t,jiecheng(t));

}
return 0;
}

Answer 1

我是采用了去掉因子2和因子5，只记录最后一位非零位，将因子5与因子2抵消，多出来的因子2，根据2^n末位规律2，4，8，6在最后乘上去就可以了。时间复杂度为O(nlgn)，空间复杂度为O(1)，不可能存在溢出……

#include<stdio.h>
#include<stdlib.h>

int JC(int n);

int main()
{
int n;
scanf("%d",&n);
do {
printf("%d -> %d\n", n, JC(n));
scanf("%d",&n);
} while (n>=0 || n<10000);
system("pause");
return 0;
}

int JC(int n)
{
int n2=0,s=1; //n2记录当前阶段2的幂次，s记录当前阶乘值的末位，不包括因子2和5
int i,j;
if (n==0||n==1)
return 1;
for (i=2; i<=n; i++)
{
j=i;
while (j%2==0) //去掉所有因子2
{
j=j/2;
n2++;
}
while (j%5==0) //去掉所有因子5
{
j=j/5;
n2--; //一个5和一个2抵消
}
s=(s*j)%10;
}
//因子2的幂次末尾循环规律为2、4、8、6...
switch(n2%4)
{
case 0: s=s*6; break;
case 1: s=s*2; break;
case 2: s=s*4; break;
case 3: s=s*8; break;
}
s=s%10;
return s;
}

追问

高才啊。。。请问按我的思路可以实现吗？就是在递归中实现对数的处理。。。可以的话告下，非常感谢!

追答

递归的话会有一个问题，函数调用是需要消耗栈空间的，你如果递归很多次的话容易造成栈溢出。
另外采纳一下，谢谢~~~

Answer 2

你标题写错了吧，这不是求阶乘结果的最 “低” 一位非0数字吗？

每次乘的时候都只取最后一位非0数字即可。
int n; //n阶乘
int result=1; //存结果
...
for (int i=1; i<n;++n)
{
result *= (i%10); //只乘 i 的个位

//取result的最低非0数字
while(result%10==0)
result /= 10;
result %= 10;
}