字符串反转和判断素数的 Python 语言算法范例

第一个是反转字符串,前两种是我出来丢人的,请直接看第三种。

方法1:

取出最大长度并 -1,以此为索引,依次递减,并将结果加入数组。

def reverse(string):
    if not string:
        return string
    str_list = []
    i = len(string) - 1
    while(i >= 0):
        str_list.append(string[i])
        i -= 1
    return ''.join(str_list)

方法2:

类似 C 中的位移操作,使用一个中间变量 t 记录临时值,然后将前后为置换,时间主要花在将字符串转换成数组上,实际遍历只需要上面方法的一半,但比上面方法要多消耗一个临时变量 t 的内存。当然,如果用 C 就可以直接指向内存,这样最节省内存,但是 Python 可能没更好办法。

但因为对 str 操作会造成 TypeError,所以还需要组成一个临时数组并在最后合并。

def reverse2(string):
    if not string:
        return string
    
    idx = 0
    length = len(string) - 1
    h_length = length / 2 # Half of length
    # 'str' object does not support item assignment for Python
    # Use C to solve it will be better.
    # So we convert it to be a list from the string.
    str_list = [x for x in string]
    
    while(idx <= h_length):
        t_idx = length - idx
        # Use varible t to store the temporary string
        t = str_list[t_idx]
        # Start to move the bit
        str_list[t_idx] = str_list[idx]
        str_list[idx] = t
        idx += 1
    
    return ''.join(str_list)

方法3:

由 @Cotton 提供,直接用数组的方式,通过本用来做间隔数的段落进行反向遍历,我只能赞叹一句,Python 太强大了!

def reverse3(string):
    return string[::-1]

另一个是求素数,没想出什么比较好的算法,只能递归,但是因为除法(求余)非常缓慢,所以我对此算法非常不满。

方法1:

这里使用一个 range 直接生成一个数组,并用 for 递归,因为我觉得一次生成数组的速度应该比多次改写一个变量速度要快,但是自然,消耗内存稍大,如果对内存有要求,也可用 while 加递减代替。

def is_prime1(num):
    # Initial to presume it's a prime
    rt = True
    # It seems every number is possible to be the one, so it have to make a range.
    for i in range(2, num):
        if num % i == 0:
            rt = False
            break
    return rt

方法2:

jyf1987 提供,双数的判断一次解决(但是 3、5 的倍数如何能更快地排除呢?),剩下的是单数的递归,同时引入平方根(很好的想法,因为大于平方根后的数的计算已经没有意义,因为另一个数必然也是之前计算过的,因为 N = a*b,所以 N=M^2),降低运算量,引入 xrange 降低内存使用量,因为是原生实现,我相信应该不会比直接用 range 生成数组更慢。

from math import sqrt

def is_prime2(num):
    # Checking the Type/value
    if type(num) != int:
       raise TypeError

    if num < 2:
       raise ValueError('The number must be great than 1')

    # Inital to presume it's a prime
    rt = True
    sq_num = int(sqrt(num))

    # First we detect is it prime for 2
    if num == 2:
        return rt

    if num % 2 == 0:
        rt = False
        return rt
    
    # Now, start to detect the odd number
    # Because all of even number could division by 2, then how about 3? -_-#
    for i in xrange(3, sq_num, 2):
        if num % i == 0:
            rt = False
            break
    return rt

冰天雪地三十六度翻转跪求更好算法~嘿嘿。。。

Posted by K*K Thu, 09 Dec 2010 20:57:01 +0800