The Zen of Python(Python之禅)
自己写的眼保程序(pynotify,pygtk)

号码球

dcy posted @ 2009年6月08日 05:12 in Python with tags 算法 , 1945 阅读

现有十个分别标有1-10号码的球,十个分别标有1-10号码的罐子。每个球放进一个罐子里,现要求每一个球都不能放在同一号码的罐子中,请问有多少种放法?

思路:

假设n个球时,号码不重复的放法有F(n)个,这时又来了一个罐子和一个球在n+1位置,我们利用球n+1和其它球交换来得到新的放法。

有两种情况适合:

  第一种情况:就是原来n个球是不重复的,我加入第n+1球和位置n+1,开始我把球n+1放在位置1,其余n个球不重复放在n个位置的方法有F(n)种,以此类推我把球放在2,3,4……n各有F(n)种,所以第一种情况的方法共有n*F(n)

  第二种情况:就是原来n个球有一个球号码重复放在一起,所以原始情况方法是F(n-1),之后我新加入的球n+1和重复号码的那个球交换,重复号码从1到n有n个符合情况,所以第二种情况共有方法n*F(n-1)

所以综上:F(n+1)=n*(F(n)+F(n-1)).

代码:

 

  1. #!/usr/bin/env python
  2.  
  3. def F(n):
  4.     if n == 1: return 0
  5.     if n == 2: return 1
  6.  
  7.     Fn, Fn_1 = 1, 0
  8.     for i in xrange(2, n):
  9.         Fn, Fn_1 = i * (Fn + Fn_1), Fn
  10.     else:
  11.         return Fn
  12.  
  13. print F(10)

如果8,9行有点难理解,可以看下面C风格的代码,不过那样不pythonic

    for i in xrange(2, n):
        current=i * (Fn + Fn_1)
        Fn_1=Fn
        Fn=current

参考于http://wiki.woodpecker.org.cn/moin/PyProgramGames/CodeBall

Avatar_small
dcy 说:
2009年6月09日 01:08

不知道专业名词叫什么,呵呵……


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter