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

K*K posted @ Thu, 09 Dec 2010 20:57:01 +0800 in 技术 with tags Algorithm python , 6118 readers

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

方法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

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

Cotton said:
Dec 09, 2010 10:33:19 PM

print "1234"[::-1] == "4321"

Head_small
K*K said:
Dec 09, 2010 10:48:43 PM

@Cotton: Great! 太强大了。

jyf1987 said:
Dec 10, 2010 07:12:14 AM

对于一个数字 N 要用穷举法判断其是否素数 不需要从 2 -> N
只需要找到 一个整数 M M <= N的平方根即可 所以这样一样 你的运算量会蹭蹭的下降
如果你需要证明 为何只需要算到 M
简单 架设 N是合数 并且 刚好 N = M^2 则对于N的其他因子 总有 N = a*b
如果 a > M 则必然 b < M 所以我们不需要考虑 a是否能被 N 整除 只需b能被 N整除即可
而 b 刚好处于 2 -> M 之间

如果你不想要大内存占用 可以用 xrange代替range 这个是生成一个 iterator 所以对于你例子里的倒数第2个数那个级别的数字非常有用,但很显然,你举的那个例子不用判断 因为无论的n的多少次方都必然是合数而非素数

如果可以接受一定的内存消耗,并且要求快速的时间,可以考虑查表法
因为我们不需要判断 一个数是否能被合数整除,我们只需要判断其是否能被素数整除就可以了

所以从 2 -> M 里 我们的运算量又会猛跌,必经素数是比较少的

据说印度人搞了一个快速的素数判断公式,额是 O(1)的
不过我没看懂

Head_small
K*K said:
Dec 10, 2010 07:25:49 PM

@jyf1987: 平方根是很好的想法。

查表发我考虑过,但是因为素数本身太多,最担心的问题是 素数 * 素数 的情况。

我回头去找下那个快速素数判断公式。

jyf1987 said:
Dec 10, 2010 07:29:04 PM

@K*K: 我曾经用lua算过1e以内的素数 结果并不大都放一个表里 呵呵 如果你要从一段连续的数中提取素数 特别是大量的,用查表真的不错 很节省运算量

Head_small
K*K said:
Dec 10, 2010 08:41:37 PM

@jyf1987: 嘿嘿,好,我回头用你提供的方法,也可以做一个表,但是因为素数无穷大,我还是担心某个某某人试个异常大的数。

不过在程序可处理的范围内,这个是可以考虑的。

Avatar_small
依云 said:
Dec 16, 2010 12:26:48 AM

以下是我用来生成指定范围的素数的(注意是 Python3 代码),方法差不多。有一些公式,能够以很高的正确率迅速判断一个数是否为素数的。

def primes(start, stop):
'''生成质数'''
if start > stop:
start, stop = stop, start
if start <= 1:
start = 2
if start == 2:
yield 2
start += 1

while start <= stop:
for i in range(3, int(start**0.5), 2):
if start % i == 0:
break
else:
yield start
start += 2

Avatar_small
依云 said:
Dec 16, 2010 12:51:34 AM

这可是Python啊,缩进都没了。。。试试在评论里包含代码:

def primes(start, stop):
  '''生成质数'''
  if start > stop:
    start, stop = stop, start
  if start <= 1:
    start = 2
  if start == 2:
    yield 2
    start += 1

  while start <= stop:
    for i in range(3, int(start**0.5), 2):
      if start % i == 0:
        break
    else:
      yield start
    start += 2

 

Head_small
K*K said:
Dec 18, 2010 01:07:49 AM

@依云: 嗯,也很简洁,看起来在 Python 2 里应该也可以执行,不过我觉得 Robust 方面还可以继续加强一下。

嘿嘿,Python 3 啊,还是遥不可及的梦(因为 Django 还没对它支持)。。。

freiz said:
Jan 05, 2011 09:35:35 PM

http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test,判断大质数会比较快,但同时有误判率。如果要查表的话,用筛法生成质数表比对每个数字进行判断更好

Avatar_small
逍遥云 said:
Jan 23, 2011 10:23:27 PM

@jyf1987: 同意此法,就像你计算1+..N一样,可以使用通项公式而不必太在意那个循环是否优雅。

Avatar_small
逍遥云 said:
Jan 23, 2011 10:26:34 PM

翻转字符,python对中文好像处理得不成,先前微博上面郑渊洁反着写微博,我用js写了一个,考虑了中英文混合的情况。可以看看:http://www.itamt.org/reverse.htm


Login *


loading captcha image...
(type the code from the image)
or Ctrl+Enter