Love, and to be Loved.

我愛你,你是自由的。

Fibonacci序列, 乘法表與求素數的算法

1. 不同算法實現Fibonacci數列

1) 遞歸:

fib=lambda n:1 if n<=2 else fib(n-1)+fib(n-2)  

2) 迭代:

def fib(n):
    x,y=0,1
     while(n):
        x,y,n=y,x+y,n-1
    return x

3) 尾遞歸(SICP):

def fib(n):
    def fib_iter(n,x,y):
        if n==0 : return x
        else : return fib_iter(n-1,y,x+y)
    return fib_iter(n,0,1)

Origin

4-1) yield生成器(尾數不大於1000的序列):

def fibonacci():
a, b = 0, 1
while True:
    yield a
    a,b = b,a+b

for i in fibonacci():
if i > 1000:
    break
print i

4-2) yield生成器(生成10個元素的序列):

def fibonacci(max):
a, b, n = 0, 1, 0
while n < max:
    yield a
    a, b = b, a + b
    n += 1

for i in fibonacci(10):
print i

2. 九九乘法表

for i in range(1,10):
  for j in range(1,i+1):
    print(" %d*%d=%d" % (j,i,i*j)),
  print '\n'

3. 求素數

01)

lis = []
for obj in range(1,10):
if obj>2:
    for x in range(2,obj):
        if obj % x == 0:
            lis.append(obj)
lis = list(set(lis))
primes = [obj for obj in range(1,10) if obj not in lis]
print primes

02) 利用python的數學函數

import math  

def isPrime(n):  
if n <= 1:  
return False 
for i in range(2, int(math.sqrt(n)) + 1):  
if n % i == 0:  
    return False 
return True 

03) 單行程序掃描素數

from math import sqrt  
N = 100 
[ p for p in   range(2, N) if 0 not in [ p% d for d in range(2, int(sqrt(p))+1)] ]  

04) 運用python的itertools模塊

from itertools import count  
def isPrime(n):  
if n <= 1:  
    return False 
for i in count(2):  
    if i * i > n:  
        return True 
    if n % i == 0:  
        return False

05)

def isPrime(n):  
if n <= 1:  
    return False 
i = 2 
while i*i <= n:  
    if n % i == 0:  
        return False 
    i += 1 
return True 

4. 從Python求素數到list與dict的比較(轉)

原理:
素數,指在一個大於1的自然數中,除了1和此整數自身外,不能被其他自然數整除的數。在加密應用中起重要的位置,比如廣為人知的RSA算法中,就是基於大整數的因式分解難題,尋找兩個超大的素數然後相乘作為密鑰的。一個比較常見的求素數的辦法是埃拉托斯特尼篩法(the Sieve of Eratosthenes),說簡單一點就是畫表格,然後刪表格,如圖所示:

從2開始依次往後面數,如果當前數字一個素數,那麽就將所有其倍數的數從表中刪除或者標記,然後最終得到所有的素數。

實現:
01)
首先用dic存儲n範圍內的元素,然後依次標記,最後從頭掃描一次dic,把合適的元素放在list中返回結果

def prime(n):
lis = {}
for i in xrange(2,n+1):     
    if not i in lis:
        lis[i] = 1
        k = i*2
        while k <= n:
            lis[k] = 0
            k = k+i
ans = []    
for i in lis:
    if lis[i] == 1:
        ans.append(i)
return ans

測試以後得到的結果是:求一千萬以內的素數用了9.68秒。
可是我覺得使用1個dict和1個list存會很浪費空間(其實不然,一千萬以內的素數只有66萬個,相對一千萬來說可以忽略不計),所以想改進一下算法。

02)
這次只用一個list存數字,然後遍歷刪除

def primeC(n):
lis = range(2,n+1)
for i in xrange(2,n+1):
    if i in lis:
        k = i+i
        while k<=n:
            if k in lis:
                lis.remove(k)
            k = k+i
return lis

因為無法在for中刪除list,所以使用一個xrange,然後每次判斷k是否在lis中再做刪除,結果:求十萬以內的素數一共花了186.79秒。

比較:
在時間上,第一個方法遠遠比第二個辦法有效率,dict是哈希實現,查詢的速度是常數級的,所以在標記合數的時候所花費的時間非常少,但是list是順序表,不知道內部是怎麽實現in 和 remove的,從時間上可以大概推測出應該是順序查找實現的,所以用如下代碼做了測試:

import random
import time
def find(source,test):
for each in test:
    each in source

def remove(liss,test):
for each in test:
    if each in liss:
        liss.remove(each)

def removeDic(dicc,test):
for each in test:
    if each in dicc:
        dicc[each] = 1

n = 100000
m = 1000
liss = range(n)
dicc = {i:0 for i in xrange(n)}
test = []
for i in xrange(m):
test.append(random.randint(0,n))

s = time.clock()
find(liss,test)
print time.clock()-s

s = time.clock()
find(dicc,test)
print time.clock()-s

s = time.clock()
remove(liss,test)
print time.clock()-s

s = time.clock()
removeDic(dicc,test)
print time.clock()-s

結果是:

1.10526960281
0.00036479383832

2.11714318396
0.000374692766596

可以看出,在查找方面list是遠遠不如dict的,說明list不應該是哈希查找,而remove的時間也遠遠大於哈希的賦值時間。
不過由此判斷第二種方法是一無是處的話未免言之過早了。因為第二種方法裏面的實現是先申請了一段空間,然後再運算,而實現一的空間是動態增長的(在給哈希表賦值的那邊體現),所以如果漲到一半發現內存不夠用的話就會報錯(測試1億數據的時候就出現了這個問題),而實現二一開始就會報錯,而不用做前面的一系列無用功。
總之就是空間換時間,時間換空間的那些戲碼。不過挺有意思。

Origin