Colorful Life2010

PYTHON实现阶乘算法
Weather:忘了啥了,反正挺舒服

今天看到FoxPro的一道题,要写出P = N!的程序及结果,这不就是个求阶乘吗?

一般程序弄个双循环就可以了,不过PYTHON就比较方便,循环一次就可以了。

  def f(n):
    c = 1
    for i in range(n+1):
        c  *= i
    return c

或者是用递归的方法也比较方便。

def f(n):
 if n > 1:
  return n*f(n-1)
 else:
  return 1



def f(n):
 p = 1
 if n > 1:
  p = n*f(n-1)
 return p

再后来一想,PYTHON有lambda方法,会不会有更好的方法,于是找到下面一篇,还真是有。一句话搞定阶乘。

用PYTHON的reduce方法

def foo(n):
    return reduce(lambda x,y: x*y, range(1,n+1))

----------------------我是转载分隔线----------------------

 

问题:
我有这样的一个列表:
['a.b.c.d11u.e.f.g', 'e.f88.g', 'caa3.z.brr', 'z.48.ff.ee']
需要找节点最多的一个(节点间由.分割)

看似简单的工作,要用pythonic的方法来做,还是要对python的内置函数有一定程度的熟悉,比如这里可以用最熟悉不过的max,但是会用到它并不常用的可选参数:key

node_list = ['a.b.c.d11u.e.f.g', 'e.f88.g', 'caa3.z.brr', 'z.48.ff.ee']
max_node = max(node_list, key=lambda n: n.count('.'))
 

在这里,使用key参数改变了max比较列表元素的方法,达到了完成任务的目的。

顺便再温习一下另一个用的不是很多的内置函数:reduce,使用它来解决这个问题

node_list = ['a.b.c.d11u.e.f.g', 'e.f88.g', 'caa3.z.brr', 'z.48.ff.ee']
max_node = reduce(lambda a,b: a.count('.') >= b.count('.') and a or b, node_list)

reduce接受两个必选参数,第一个参数是一个函数,这个函数接受两个参数,返回一个值;第二个参数是一个序列(比如列表); reduce首先把序列的前两个元素作为参数传递给参数函数,然后把参数函数的返回值和序列的第三个参数一起再传递给参数函数,依次类推,最终只剩下一个值。这么解释似乎更晕啦,哈哈,还是python自己的help说的好:For example, reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) calculates ((((1+2)+3)+4)+5)

历史上的今天: [2011/04/10]江西 婺源 油菜花
[2005/04/10]做了个雨中疯子,终于有了同居对象

[PYTHON实现阶乘算法]的回复

re 于 2009-04-10 01:09:23 发表 | IP:114.93.108.*
Python不支持尾递归吧?写这种玩意需要换个思路,和一般的不一样。
柠檬园主 于 2009-04-10 01:28:53 发表 | IP:119.109.24.*
PYTHON弱类型,定义的函数没有明确类型,所以在这儿没办法递归.... :(
柠檬园主 于 2009-04-10 09:35:22 发表 | IP:116.3.197.*

奇怪了。昨天晚上在家试递归的时候不好用,现在上班一试好用了。

分特。上面说错了,2楼的。

4#   quake0day 于 2010-03-11 03:30:21 发表 | IP:219.232.107.*
1 def f(n):
  2     c = 1
  3    for i in range(1,n+1):
4 c *= i
5 return c

应该是这么写吧?
柠檬园主 2010-03-11 21:30:00 回复:

嗯,对,从1开始,从0开始就全是0了。

5#   any 于 2015-05-25 11:24:36 发表 | IP:221.222.242.*
python是支持尾递归的,不过要把acc累计 放入其他fun
6#   any 于 2015-05-25 11:25:05 发表 | IP:221.222.242.*
def f(n):
    return k(n-1,acc)


def k(i,acc):
    if i ==1:
    return j
return k(i-1,acc*i)
柠檬园主 2015-06-03 11:59:21 回复:

哈哈哈,好大的一坑,这么久的东西被挖出来了,我都不记得我还写过这个。

你上面的代码里有个变量[j]是写错了吧

按你的写法,其实也完全可以写一个函数,同样把acc累计放到fun里

 def f(n, acc=1):
if n == 0:
return acc
return f(n-1, acc * n)

 

能用尾递归就不要用普通递归,能用循环就不要用递归,比如比较流行的面试中要面的斐波纳契函数

def f(n, ret1=0, ret2=1):
    if n < 2:
        return ret1
    return f(n-1, ret2, ret1+ret2)

一般的应聘者比较常见的递归写法却是下面的

def f1(n):
    if n < 2:
        return n
    return f1(n-1) + f1(n-2)

那么在算到f(100)的时候,尾递归可以很快算出结果,而非尾递归算到f1(40)就要卡死了。

 但是如果直接用循环写的话,即使是和尾递归比起来,也会有“飞”一般的感觉

def f2(num):
    a, b = 0, 1
    for n in xrange(num):
        L = a
        a, b = b, a+b
    return L
Post a Comment~