现在的位置: 首页 > 综合 > 正文

python解号码球问题

2013年09月17日 ⁄ 综合 ⁄ 共 5973字 ⁄ 字号 评论关闭

题目描述:

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

 

1.1. codeball.py

Toggle line numbers
   1 # -*- coding: utf-8 -*-
   2 
   3 #号码球问题
   4 
   5 #求排列,这里采用迭代算法而非递归,
   6 #是为了得到更好的效率
   7 def P(x, y = None):
   8         """
   9         求排列数P(x, y),y默认值为x,此时取P(x),即x!
  10         """
  11         if x == 0 or y == 0:
  12                 return 1
  13 
  14         re = x
  15         i = x - 1
  16         if y == None:
  17                 l = 1
  18         else:
  19                 l = x - y
  20 
  21         while i > l:
  22                 re *= i
  23                 i -= 1
  24         return re
  25 
  26 #求组合
  27 def C(x, y):
  28         """
  29         求组合数C(x, y)
  30         """
  31         if x == y:
  32                 return 1
  33         else:
  34                 return P(x, y)/P(y)
  35 
  36 #求号码球(Code Ball)问题,CB1使用递归算法:
  37 #1、CB1算法只考虑取出所有球的情况
  38 #       即每一个罐子都有一个球对应,没有空罐。
  39 #2、CB1(0)时,视作有1种解(这种情况下没
  40 #有罐子与球对应);
  41 #3、CB1(1)时,没有解(罐子必然与球对应);
  42 #4、CB1(2)时,有一种解(罐子与球要么完全)
  43 #对应,要么完全不对应;
  44 #5、CB1(n), n>=3可以分解为用所有可能的排列减去
  45 #不合要求的组合。包含有m(m <= n)个重复对应的排
  46 #列数为C(n, m)*CB1(n - m)。m取遍n到1,
  47 #P(n)与C(n, m)*CB1(n - m)之积加和之差,即为所求。
  48 #故:
  49 #CB1(3) = P(3) - C(3, 3)*CB1(3 - 3) - C(3, 2)*CB1(3 - 2) - C(3, 1)*CB1(3 - 1) 
  50 #CB1(n) = P(n) - C(n, n)*CB1(n - n) - C(n, n - 1)*CB1(n - n + 1) - ... - C(n, 1)*CB1(n - 1)
  51 #               = P(n) - C(n, n)*CB1(0) - C(n, n - 1)*CB1(1) - ... - C(n, 1)*CB1(n - 1)
  52 #由C(n, n)==1,CB1(0)==CB1(2)==1,CB1(1)==0,CB1(n)可以简化为:
  53 #CB1(n)=P(n) - 1 - C(n, n - 2) - C(n, n - 3)*CB1(3) - ... - n*CB1(n-1)
  54 def CB1(x):
  55         if x == 0 or x == 2:
  56                 return 1
  57         elif x == 1:
  58                 return 0
  59         else:
  60                 re = P(x) - 1
  61                 for i in range(2, x):
  62                         re -= C(x, x-i)*CB1(i)
  63                 return re
  64 
  65 print "CB1算法解得CB1(10) = ", CB1(10)

2. Zoom.Quiet

坚决使用暴力!

使用"一切从游戏开始 - ChinesePython Wiki"的技巧来优化

2.1. codeBall.py

Toggle line numbers
   1 # -*- coding: gbk -*-
   2 # file codeBall.py
   3 #/*********************************
   4 # /class codeBall
   5 # /brief        [python-chinese] 趣味问题——号码分配试解
   6 # /version 2.0  04427   16:22 liux@gdcn.com fixed
   7 # /version 1.0  04427   liux@gdcn.com 原始提出,现在以最笨方式解决
   8 # /author Zoom Quiet (zoomq at itcase.com)
   9 # /attention    Released under GNU Lesser GPL library license
  10 #*********************************/
  11 
  12 import sys, os,string
  13 import PnC
  14 
  15 class playCodeBall:
  16     def __init__(self):
  17         self.log=""
  18     def __repr__(self):# 类自述定义
  19         print("Zoom.Quiet 最笨方式进行正确解答输出/n 可以作为其它解的验证")
  20         return self.log
  21     def filter(self,seq,order):
  22         seqCB = []
  23         length = len(order)
  24         tag = 0
  25         for item in seq:
  26             for i in range(length):
  27                 #if(i == int(item[i-1])):
  28                 # 0427;16:22 liux@gdcn.com fixed
  29                 if(i == int(item[i]) - 1):
  30                     #print "bad CodeBall> %s at [%s] = %s"%(item,i,item[i-1])
  31                     break
  32                 else:
  33                     if(i+1==length):
  34                         tag = 1
  35             if(1==tag):
  36                 seqCB.append(item)
  37                 #print item
  38                 tag = 0
  39         return seqCB
  40 
  41 if __name__ == '__main__':      # 自测试
  42     tryPnC = PnC.permutation()            # imported by other programs as well
  43     if(tryPnC):
  44         #建立序列
  45         import timer
  46         watch= timer.timer()
  47         watch.start()
  48         order="12345678"
  49         seq = list(order)
  50         #生成排列
  51         p = tryPnC.permute(seq)
  52         #玩——过滤出切题的
  53         CB = playCodeBall()
  54         result = CB.filter(p,order)
  55         print(watch.stop())
  56         #print result
  57         #输出正确的序列到文件
  58         import outputLog
  59         exp = outputLog.exporter()
  60         exp.exportArrayCB(result)
  61         exp.writeInFile("CodeBall.log")
  62         #print "当罐有 %s 个时,全部 %s 种排列中,合题的为:%s 种!"%(len(order),len(p),len(result))
  63     else:
  64         print("/"<!--/n   数码球Zq试解模块 实例创建失败退出!-->/"")

2.1.1. 伺候程序

Toggle line numbers
   1 # -*- coding: gbk -*-
   2 # file PnC.py
   3 #/*********************************
   4 # /class PnC
   5 # /brief        permutation and combination 排列组合 输出
   6 # /version 1.0  04427   使用"一切从游戏开始 - ChinesePython Wiki"的技巧
   7 # /author Zoom Quiet (zoomq at itcase.com)
   8 # /attention    Released under GNU Lesser GPL library license
   9 # /par
  10 # /return
  11 # /sa
  12 #*********************************/
  13 
  14 import sys, os,string
  15 import outputLog
  16 
  17 class permutation:
  18     def __init__(self):
  19         self.log=""
  20         self.export=""
  21     def __repr__(self):# 类自述定义
  22         return self.log
  23     def P(self,x, y = None):
  24         """
  25                 Liux的自然 求排列数P(x, y),y默认值为x,此时取P(x),即x!
  26         """
  27         if x == 0 or y == 0:
  28                 return 1
  29         re = x
  30         i = x - 1
  31         if y == None:
  32                 l = 1
  33         else:
  34                 l = x - y
  35         while i > l:
  36                 re *= i
  37                 i -= 1
  38         return re
  39     def permute_O_n(self,seq,index):
  40         seqc = seq[:]
  41         seqn = [seqc.pop()]
  42         divider = 2
  43         while seqc:
  44             index, new_index = divmod(index,divider)
  45             seqn.insert(new_index, seqc.pop())
  46             divider += 1
  47         return ''.join(seqn)
  48 
  49     def permute(self,seq):
  50         seqn = [seq.pop()]
  51         while seq:
  52             newseq = []
  53             new = seq.pop()
  54             #print "seq:",seq,'seqn', seqn ,'new', new
  55             for i in range(len(seqn)):
  56                 item = seqn[i]
  57                 for j in range(len(item)+1):
  58                     newseq.append(''.join([item[:j],new,item[j:]]))
  59             seqn = newseq
  60             #print 'newseq',newseq
  61         return  seqn
  62 
  63 if __name__ == '__main__':      # 自测试
  64     PnC = permutation()            # imported by other programs as well
  65     if(PnC):
  66         seq = list("1234")
  67         for i in range(30):
  68             print PnC.permute_O_n(seq, i)
  69         print(PnC.P(4))
  70     else:
  71         print("/"<!--/n   排列组合 输出模块 实例创建失败退出!-->/"")


Toggle line numbers
   1 # -*- coding: gbk -*-
2 # file outputLog.py
3 #/*********************************
4 # /class outputLog
5 # /brief 结果数据输出支持
6 # /version 1.1 04427 数组的数码球输出辅助 exportArrayCB ...
7 # /version 1.0 04427 支持字串,和数组输出!
8 # /author Zoom Quiet (zoomq at itcase.com)
9 # /attention Released under GNU Lesser GPL library license
10 # /par
11 # /return
12 # /sa
13 #*********************************/
14
15 import sys, os,string
16
17 class exporter:
18 def __init__(self):
19 self.log=""
20 def __repr__(self):# 类自述定义
21 return self.log
22 def writeInFile(self,fname):
23 open(fname,"w").write(self.log)
24 print("成功输出数据到文件:%s"%fname)
25
26 def exportArrayCB(self,seq):
27 foo = ""
28 for i in range(len(seq[0])):
29 foo +=str(i+1)
30 self.log += foo
31 self.log +="/n"+"~"*27+"/n"
32 for i in seq:
33 self.log += i+"/n"
34

【上篇】
【下篇】

抱歉!评论已关闭.