转载请注明:@小五义 http://www.cnblogs.com/xiaowuyi
题目:借书方案
内容:小明有五本新书,要借给A、B、C三位小朋友,若每人每次只能借一本,则可以有多少种不同的借法。
问题分析和算法设计:
本问题实际上就是一个排列问题,即求从5个中取3个进行排列的方法有多少。首先对五本书从1至5进行编号,然后使用穷举的方法,假设三个人分别借这五本书中的一本,当三个人所借的书的编号都不相同时,就满足题意。
具体代码:
# -*- coding: cp936 -*- ##@小五义 http://www.cnblogs.com/xiaowuyi ''' 借书方案:小明有五本新书,要借给A、B、C三位小朋友,若每人每次只能借一本,则可以有多少种不同的借法。 ''' count=0 #记录第几种分法 print "假设五本书分别为1,2,3,4,5,主要借法有" for a in range(1,6): for b in range(1,6): if a!=b: for c in range(1,6): if c!=a and c!=b: count+=1 print "第%d种:A分到书%d,B分到书%d,C分到书%d"%(count,a,b,c)
运行结果为:
假设五本书分别为1,2,3,4,5,主要借法有
第1种:A分到书1,B分到书2,C分到书3
第2种:A分到书1,B分到书2,C分到书4
第3种:A分到书1,B分到书2,C分到书5
第4种:A分到书1,B分到书3,C分到书2
第5种:A分到书1,B分到书3,C分到书4
第6种:A分到书1,B分到书3,C分到书5
第7种:A分到书1,B分到书4,C分到书2
第8种:A分到书1,B分到书4,C分到书3
第9种:A分到书1,B分到书4,C分到书5
第10种:A分到书1,B分到书5,C分到书2
第11种:A分到书1,B分到书5,C分到书3
第12种:A分到书1,B分到书5,C分到书4
第13种:A分到书2,B分到书1,C分到书3
第14种:A分到书2,B分到书1,C分到书4
第15种:A分到书2,B分到书1,C分到书5
第16种:A分到书2,B分到书3,C分到书1
第17种:A分到书2,B分到书3,C分到书4
第18种:A分到书2,B分到书3,C分到书5
第19种:A分到书2,B分到书4,C分到书1
第20种:A分到书2,B分到书4,C分到书3
第21种:A分到书2,B分到书4,C分到书5
第22种:A分到书2,B分到书5,C分到书1
第23种:A分到书2,B分到书5,C分到书3
第24种:A分到书2,B分到书5,C分到书4
第25种:A分到书3,B分到书1,C分到书2
第26种:A分到书3,B分到书1,C分到书4
第27种:A分到书3,B分到书1,C分到书5
第28种:A分到书3,B分到书2,C分到书1
第29种:A分到书3,B分到书2,C分到书4
第30种:A分到书3,B分到书2,C分到书5
第31种:A分到书3,B分到书4,C分到书1
第32种:A分到书3,B分到书4,C分到书2
第33种:A分到书3,B分到书4,C分到书5
第34种:A分到书3,B分到书5,C分到书1
第35种:A分到书3,B分到书5,C分到书2
第36种:A分到书3,B分到书5,C分到书4
第37种:A分到书4,B分到书1,C分到书2
第38种:A分到书4,B分到书1,C分到书3
第39种:A分到书4,B分到书1,C分到书5
第40种:A分到书4,B分到书2,C分到书1
第41种:A分到书4,B分到书2,C分到书3
第42种:A分到书4,B分到书2,C分到书5
第43种:A分到书4,B分到书3,C分到书1
第44种:A分到书4,B分到书3,C分到书2
第45种:A分到书4,B分到书3,C分到书5
第46种:A分到书4,B分到书5,C分到书1
第47种:A分到书4,B分到书5,C分到书2
第48种:A分到书4,B分到书5,C分到书3
第49种:A分到书5,B分到书1,C分到书2
第50种:A分到书5,B分到书1,C分到书3
第51种:A分到书5,B分到书1,C分到书4
第52种:A分到书5,B分到书2,C分到书1
第53种:A分到书5,B分到书2,C分到书3
第54种:A分到书5,B分到书2,C分到书4
第55种:A分到书5,B分到书3,C分到书1
第56种:A分到书5,B分到书3,C分到书2
第57种:A分到书5,B分到书3,C分到书4
第58种:A分到书5,B分到书4,C分到书1
第59种:A分到书5,B分到书4,C分到书2
第60种:A分到书5,B分到书4,C分到书3
下面我们把这个问题扩展一下,做一个更加通用的程序,就是将m本书分给n个小朋友,共中n<=m,要求每人每次只能分到一本。排列组合这个古老的问题解法有很多,这里我们用的方法是先从m本书中取出n本,然后对n本进行排列。于是我们分步实现:
第一步,从m本书中取出n本,具体代码:
# -*- coding: cp936 -*- ''' 对m个数中取n个的取法 ''' ##@小五义 http://www.cnblogs.com/xiaowuyi def combination(lst,n): rst = [] if n == 1: for i in lst: l = [] l.append(i) rst.append(l) else: for i in combination(lst,n-1): for j in range(lst.index(i[-1])+1,len(lst)): l = i[:] l.append(lst[j]) rst.append(l) return rst if __name__ == "__main__": rst = []#记录书的组合 lst=[]#将书编号 numlist=[]#记录数组合后的数字 num=raw_input('输入数的本数m:') for i in range(1,int(num)+1): lst.append(str(i)) print lst i=raw_input('输入小朋友数量n:') ivrst = combination(lst,int(i)) rst = rst + ivrst for i in rst:#将得到的组合读出 print i numstr='' for j in i:#将组合组成数字 numstr=numstr+j numlist.append(numstr) print numlist
第二步,对n本书进行排列,具体代码:
# -*- coding: cp936 -*- ''' 对m个数进行排列 ''' ##@小五义 http://www.cnblogs.com/xiaowuyi import time,sys def permute(num): l = len(num) if l <= 2: if l == 2: return [num,num[1],num[0],num[1]+num[0]] else: return [num] else: list = [] for i in range(len(num)): li = num[:i]+num[i+1:] #print 'li=',li for x in permute(li): p=num[i:i+1]+x list.append(p) return list num = raw_input('the number:') list1 = permute(num) list1= [''.join(x) for x in list1 if len(x)==len(num)] print list1
最后,将前两步合并,并将程序进行完善。
# -*- coding: cp936 -*- ##@小五义 http://www.cnblogs.com/xiaowuyi ''' 借书方案:小明有m本新书,要借给n位小朋友,若每人每次只能借一本,则可以有多少种不同的借法。 ''' def combination(lst,n):#将lst中取出n个进行组合 rst = [] if n == 1: for i in lst: l = [] l.append(i) rst.append(l) else: for i in combination(lst,n-1): for j in range(lst.index(i[-1])+1,len(lst)): l = i[:] l.append(lst[j]) rst.append(l) return rst def permute(num):#将书进行排列 l = len(num) if l <= 2: if l == 2: return [num,num[1],num[0],num[1]+num[0]] else: return [num] else: list = [] for i in range(len(num)): li = num[:i]+num[i+1:] #print 'li=',li for x in permute(li): p=num[i:i+1]+x list.append(p) return list if __name__ == "__main__": count=0 #记录第几种分法 rst = []#记录书的组合 lst=[]#将书编号 numlist=[]#记录数组合后的数字 num_bool=True #用来判断小朋友数不大于书的数量 book_list=[]#记录最后组合数 ##判断小朋友数不大于书的数量 while num_bool: try: books=int(raw_input('小明一共有书的数量:')) baby=int(raw_input('要分给的小朋友数量(不大于书的数量)')) if baby>books or books==0 or baby==0: print'输入错误,请重新输入。' num_bool=True else: num_bool=False except: print'输入错误,请重新输入。' num_bool=True for i in range(1,books+1): lst.append(str(i)) books_com=combination(lst,baby) rst=rst+books_com for i in rst:#将得到的组合读出 numstr='' for j in i:#将组合组成数字 numstr=numstr+j numlist.append(numstr) ##print numlist for i in numlist: list1=permute(i) ##book_list=[''.join(x) for x in list1 if len(x)==len(i)] for x in list1: if len(x)==len(i): book_list.append(x) for i in book_list: count+=1 print "第%d种:%s"%(count,i)
运行结果为:
小明一共有书的数量:5
要分给的小朋友数量(不大于书的数量)3
第1种:123
第2种:132
第3种:213
第4种:231
第5种:312
第6种:321
第7种:124
第8种:142
第9种:214
第10种:241
第11种:412
第12种:421
第13种:125
第14种:152
第15种:215
第16种:251
第17种:512
第18种:521
第19种:134
第20种:143
第21种:314
第22种:341
第23种:413
第24种:431
第25种:135
第26种:153
第27种:315
第28种:351
第29种:513
第30种:531
第31种:145
第32种:154
第33种:415
第34种:451
第35种:514
第36种:541
第37种:234
第38种:243
第39种:324
第40种:342
第41种:423
第42种:432
第43种:235
第44种:253
第45种:325
第46种:352
第47种:523
第48种:532
第49种:245
第50种:254
第51种:425
第52种:452
第53种:524
第54种:542
第55种:345
第56种:354
第57种:435
第58种:453
第59种:534
第60种:543
可以看出,下面的这个程序对第一程序进行了扩展,更加具有通用性。