主题:快给答案!
Matodied
[专家分:7560] 发布于 2007-04-16 16:54:00
我们这里的考试题中有一道这样的题:
输入一个数N(10000<N<10^10),求出N!最后一位非0的数字。
(别看这道题只要会高精度就行,因为N过大,要算很长很长时间,现要求2分钟内出结果)
回复列表 (共3个回复)
沙发
mickeyice [专家分:200] 发布于 2007-04-17 10:43:00
弱弱的问下 n!是n 的阶乘
阶乘怎么算?
是不是 n*(n-1)*(n-2)........*2?
那恭喜了...10^6无论算法怎么样都会超过2min
板凳
Matodied [专家分:7560] 发布于 2007-04-21 15:03:00
哈哈!如果你用高精度阶乘就惨了,这道题就是耍你……
3 楼
Matodied [专家分:7560] 发布于 2007-04-21 15:26:00
真没想到,你们人人都做不出来……我已经做出来了,结掉吧!
CLS
DIM n AS DOUBLE, m AS DOUBLE, q AS DOUBLE
INPUT n
m = INT(n / 10): q = n - INT(n / 10) * 10
SELECT CASE m - INT(m / 4) * 4
CASE 0 AND m > 0: s = 6
CASE 1: s = 8
CASE 2: s = 4
CASE 3: s = 2
CASE ELSE: s = 1
END SELECT
a$ = LTRIM$(STR$(s)): DIM a(a), b(b), s(s)
FOR i = 1 TO q
b$ = LTRIM$(STR$(m * 10 + i))
ERASE a, b, s
GOSUB gjdmult
j = 0
a$ = s$
NEXT i
FOR i = LEN(a$) TO 1 STEP -1
IF MID$(a$, i, 1) <> "0" THEN PRINT MID$(a$, i, 1): END
NEXT i
END
gjdmult:
la = LEN(a$): lb = LEN(b$): DIM a(la), b(lb), s(la + lb)
FOR k = 1 TO la: a(k) = VAL(MID$(a$, la + 1 - k, 1)): NEXT k
FOR k = 1 TO lb: b(k) = VAL(MID$(b$, lb + 1 - k, 1)): NEXT k
FOR k = 1 TO la: FOR l = 1 TO lb
d = a(k) * b(l): v = k + l - 1
s(v) = s(v) + d MOD 10: s(v + 1) = s(v + 1) + s(v) \ 10 + d \ 10: s(v) = s(v) MOD 10
NEXT l, k
IF s(la + lb) = 0 THEN ls = la + lb - 1 ELSE ls = la + lb
s$ = ""
FOR k = ls TO 1 STEP -1
s$ = s$ + RTRIM$(LTRIM$(STR$(s(k))))
NEXT k
RETURN
我来回复