python趣味编程:借书方案(排列组合)

简介: 转载请注明:@小五义 http://www.cnblogs.com/xiaowuyi 题目:借书方案内容:小明有五本新书,要借给A、B、C三位小朋友,若每人每次只能借一本,则可以有多少种不同的借法。问题分析和算法设计:本问题实际上就是一个排列问题,即求从5个中取3个进行排列的方法有多少。

转载请注明:@小五义 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

可以看出,下面的这个程序对第一程序进行了扩展,更加具有通用性。

目录
相关文章
|
1天前
|
机器学习/深度学习 Linux Python
Python编程教学
Python教学
24 13
|
1天前
|
机器学习/深度学习 数据挖掘 开发者
探索Python编程:从基础到实战
【9月更文挑战第34天】在这篇文章中,我们将一起踏上Python编程的旅程。无论你是初学者还是有一定经验的开发者,这篇文章都将为你提供有价值的信息。我们将从Python的基础语法开始,逐步深入到更复杂的主题,如面向对象编程和网络应用开发。我们还将探讨如何在实际项目中应用这些知识,以及如何通过持续学习和实践来提高你的编程技能。让我们一起探索Python的世界,发现它的无限可能!
|
2天前
|
机器学习/深度学习 人工智能 数据可视化
Python比较适合哪些场景的编程?
Python比较适合哪些场景的编程?
14 7
|
2天前
|
大数据 Python
Python 高级编程:深入探索高级代码实践
本文深入探讨了Python的四大高级特性:装饰器、生成器、上下文管理器及并发与并行编程。通过装饰器,我们能够在不改动原函数的基础上增添功能;生成器允许按需生成值,优化处理大数据;上下文管理器确保资源被妥善管理和释放;多线程等技术则助力高效完成并发任务。本文通过具体代码实例详细解析这些特性的应用方法,帮助读者提升Python编程水平。
20 5
|
1天前
|
程序员 数据库 开发者
探索Python编程之旅:从基础到进阶
【9月更文挑战第34天】本文将引导你踏上Python编程的奇妙旅程,从最初的安装和运行第一个程序开始,逐步深入到面向对象编程、文件操作和网络编程等高级主题。我们将通过代码示例和清晰的步骤解释,帮助你构建起对Python语言的深刻理解,并鼓励你在遇到问题时主动寻找解决方案,培养解决问题的能力。无论你是初学者还是有一定经验的开发者,都能在这篇文章中找到有价值的内容和启发。
|
7天前
|
数据挖掘 索引 Python
Python数据挖掘编程基础3
字典在数学上是一个映射,类似列表但使用自定义键而非数字索引,键在整个字典中必须唯一。可以通过直接赋值、`dict`函数或`dict.fromkeys`创建字典,并通过键访问元素。集合是一种不重复且无序的数据结构,可通过花括号或`set`函数创建,支持并集、交集、差集和对称差集等运算。
15 9
|
3天前
|
存储 数据处理 开发者
深入浅出:Python编程基础与实战技巧
【9月更文挑战第32天】本文将引导读者从零开始,掌握Python编程语言的核心概念,并通过实际代码示例深入理解。我们将逐步探索变量、数据结构、控制流、函数、类和异常处理等基本知识,并结合实用案例,如数据处理、文件操作和网络请求,提升编程技能。无论您是初学者还是有一定经验的开发者,这篇文章都能帮助您巩固基础,拓展视野。
|
3天前
|
数据采集 机器学习/深度学习 人工智能
Python编程之旅:从基础到精通
【9月更文挑战第32天】本文将带你进入Python的世界,从基础语法到高级特性,再到实战项目,让你全面掌握Python编程技能。无论你是初学者还是有一定基础的开发者,都能在这篇文章中找到适合自己的学习路径和方法。让我们一起踏上Python编程之旅,开启一段充满挑战和乐趣的学习历程吧!
|
6天前
|
存储 开发者 Python
探索Python编程的奥秘
【9月更文挑战第29天】本文将带你走进Python的世界,通过深入浅出的方式,解析Python编程的基本概念和核心特性。我们将一起探讨变量、数据类型、控制结构、函数等基础知识,并通过实际代码示例,让你更好地理解和掌握Python编程。无论你是编程新手,还是有一定基础的开发者,都能在这篇文章中找到新的启示和收获。让我们一起探索Python编程的奥秘,开启编程之旅吧!
|
7天前
|
Python
Python编程的循环结构小示例(二)
Python编程的循环结构小示例(二)
下一篇
无影云桌面