设计一个求n!(n的阶乘)的快速算法,n是任意正数
如上, 其实是关于算法的, 但是我写了个多线程来玩。
由于数会很大, 所以直接用python来写, 就不用处理高精度啦。
#!/usr/bin/python # -*- coding: utf-8 -*- import string, Queue, threading, time THREADCOUNT=8 ANS=1 ans_lock=threading.Lock() class ThreadF(threading.Thread): def __init__(self, queue): threading.Thread.__init__(self) self.queue=queue def run(self): s,e=self.queue.get() ans_lock.acquire() global ANS ANS *= F(s, e) ans_lock.release() #print('%s - %s done.' % (s,e)) self.queue.task_done() def main(): a=raw_input() a=string.atoi(a) #i=a start = time.time() ans=magicF(a) print("Elapsed Time: %s" % (time.time() - start)) print(ans) def F(s,e): ans=1 a=e while a>=s: ans *= a a -= 1 return ans def magicF(n): global ANS ANS=1 queue=Queue.Queue() list=[] if n<3750: #神奇常数 大约在3750的时候多线程开始比单线程循环要快 5700开始,多线程大多数比单线程快 ANS=F(1,n) else: for i in range(THREADCOUNT): t = ThreadF(queue) t.setDaemon(True) t.start() x=int(n/THREADCOUNT) for i in range(0,THREADCOUNT-2): list.append((x*i+1, x*(i+1))) list.append((x*(THREADCOUNT-2)+1, n)) #print(list) for l in list: queue.put(l) queue.join() return ANS def test(): for i in range(1,10000): start = time.time() F(1,i) ta=time.time() - start #print("%s(F) Elapsed Time: %s" % (i, ta)) start = time.time() magicF(i) tb=time.time() - start #print("%s(magicF) Elapsed Time: %s" % (i, tb)) print("%s TF > TmagicF: %s" % (i, ta>tb)) if __name__=='__main__': main()
话说输出结果的时间比计算时间长好多啊啊啊
话说最高只占用了12%CPU, 为什么不是100%
话说可以加入网络来使用好几个计算机来计算
话说Mathematica是用的什么算法呢
发表评论