用Python解决计数原理问题的方法
前几天遇到这样一道数学题：
用四种不同颜色给三棱柱六个顶点涂色,要求每个点涂一种颜色,且每条棱的两个端点涂不同颜色,则不同的涂色方法有多少种？
当我看完题目后，顿时不知所措。于是我拿起草稿纸在一旁漫无目的地演算了一下，企图能找到解决方法。结果一无所获。于是打算通过程序算法解决这个问题。经过2个多小时的研究，终于完成了代码，并求得了答案。
由于Python写起来比较方便而且本人比较喜欢Python的语法，所以研究算法时我通常采用Python，此次也不例外。以下就是整个算法的实现过程。
两种算法
我一共想出了两种用于解决本题的算法：
算法一：将所有的涂色情况通过程序的循环计算出来，然后通过程序的条件判断去除掉不合题意的所有情况，最后得到最终结果。
算法二：从其中任意一个端点（p0）入手，由于其它所有端点都没有涂色，所以它可以涂四种颜色。将这四种颜色通过循环分别涂在这个端点上，每涂上一种颜色后，获取与它相临的一个端点（p1），并获取它可以涂上的颜色，然后通过循环将可用颜色涂上（及不能涂上与p0相同的颜色），每涂上一种颜色，又将p1相邻的未涂色的点涂色（及除p0外其他的相邻端点）。每个点被涂色后都采用同样的方法将相邻的点涂色，以此类推，涂完最后一个点，就记一次情况。所有的递归都完成后，就获得了所有情况。
算法一很直接很粗暴，所以我采用了算法二来解决上述问题。接下来就是具体的代码了。
算法实现
我写了大约90行Python代码来实现这个算法：
colorList = [0, 1, 2, 3]
pointList = []
amount = 0
class Point(object):
def __init__(self):
super(Point, self).__init__()
self.neibors = []
self.color = None
def paint(self, c):
self.color = c
def clean(self):
self.color = None
def getLeftOverColors(self):
copyOfColorList = colorList[0 : 4]
for neibor in self.neibors:
nc = neibor.color
if nc in copyOfColorList:
copyOfColorList.remove(nc)
return copyOfColorList
def main():
global pointList
p0 = Point()
p1 = Point()
p2 = Point()
p3 = Point()
p4 = Point()
p5 = Point()
p0.neibors = [p1, p2, p4]
p1.neibors = [p0, p2, p5]
p2.neibors = [p0, p1, p3]
p3.neibors = [p2, p4, p5]
p4.neibors = [p0, p3, p5]
p5.neibors = [p4, p3, p1]
pointList = [p0, p1, p2, p3, p4, p5]
paintPoint(p0)
print(amount)
def paintPoint(p):
global amount
colors = p.getLeftOverColors()
lastOne = isLastOne()
for c in colors:
p.paint(c)
if lastOne:
amount += 1
else:
for currentNeibor in p.neibors:
if currentNeibor.color == None:
paintPoint(currentNeibor)
break
p.clean()
def isLastOne():
global pointList
paintedNum = 0
for p in pointList:
if p.color != None:
paintedNum += 1
return paintedNum == 5
if __name__ == "__main__":
main()
以下是对各段代码的介绍。
全局变量
colorList：颜色列表
pointList：存放六个点的列表
amount : 涂色方案的种数
Point类
用于储存各个点的信息，如点的颜色（color属性，None代表无颜色）、相邻的点（'neibors'属性）。以及提供paint方法用于将点标记颜色；clean方法用于去除颜色；getLeftOverColors方法用于获取可用颜色，及获取相邻点没有使用的颜色。
main函数
程序开始运行时调用的函数，其中构造了所需的六个点，以及分别为这六个点明确了相邻的三个点。注意，由于这里的点只有相邻和不相邻的位置关系，所以不需要在意这些点到底在三棱柱里对应哪个位置，任意设定这些点的位置对结果来说并没有影响，只需注意它们之间的相邻关系即可。
isLastOne函数
判断是不是最后一个未涂色的点。
paintPoint函数
用于对作为参数传入的点进行着色。其中首先通过调用该点的getLeftOverColors方法获取可用颜色，然后按照上文算法中介绍的，通过遍历可用颜色列表，为该点着色，如果该点不是最后一个点（通过isLastOne函数判断），就递归调用paintPoint函数为相邻的一个未着色的点着色，如果是，则将记下一次涂色方案。
运行代码，得到结果 - 264：
Ok，于是这道题就在我们的计算机的帮助下，被成功解决掉了～如果大家有更好的方案解决这一算法问题，欢迎留言进行交流～希望本文对大家学习Python和计数原理都能有所帮助。
相关推荐
-
Python的Django框架中消息通知的计数器实现教程
故事的开始:.count() 假设你有一个Notification Model类,保存的主要是所有的站内通知: class Notification(models.Model): """一个简化过的Notification类,拥有三个字段: - `user_id`: 消息所有人的用户ID - `has_readed`: 表示消息是否已读 """ user_id = models.IntegerField(db_index=True) has_re
-
Python闭包实现计数器的方法
本文实例讲述了Python闭包实现计数器的方法.分享给大家供大家参考.具体实现方法如下: 先来看看专业的解释:闭包(Closure)是词法闭包(Lexical Closure)的简称,是引用了自由变量的函数.这个被引用的自由变量将和这个函数一同存在,即使已经离开了创造它的环境也不例外.所以,有另一种说法认为闭包是由函数和与其相关的引用环境组合而成的实体. 代码如下: #!/usr/bin/env python #coding=utf-8 def generate_counter(): CNT =
-
python计算书页码的统计数字问题实例
本文实例讲述了python计算书页码的统计数字问题,是Python程序设计中一个比较典型的应用实例.分享给大家供大家参考.具体如下: 问题描述:对给定页码n,计算出全部页码中分别用到多少次数字0,1,2,3,4...,9 实例代码如下: def count_num1(page_num): num_zero = 0 num_one = 0 num_two = 0 num_three = 0 num_four = 0 num_five = 0 num_six = 0 num_seven = 0 nu
-
python中的字典详细介绍
一.什么是字典? 字典是Python语言中唯一的映射类型. 映射类型对象里哈希值(键,key)和指向的对象(值,value)是一对多的的关系,通常被认为是可变的哈希表. 字典对象是可变的,它是一个容器类型,能存储任意个数的Python对象,其中也可包括其他容器类型. 字典类型与序列类型的区别: 1.存取和访问数据的方式不同. 2.序列类型只用数字类型的键(从序列的开始按数值顺序索引): 3.映射类型可以用其他对象类型作键(如:数字.字符串.元祖,一般用字符串作键),和序列类型的键不同,映射类型的
-
python算法学习之计数排序实例
python算法学习之计数排序实例 复制代码 代码如下: # -*- coding: utf-8 -*- def _counting_sort(A, B, k): """计数排序,伪码如下: COUNTING-SORT(A, B, k) 1 for i ← 0 to k // 初始化存储区的值 2 do C[i] ← 0 3 for j ← 1 to length[A] // 为各值计数 4 do C[A[j]] ← C[A
-
Python列表计数及插入实例
本文实例讲述了Python列表计数及插入的用法.分享给大家供大家参考.具体如下: 复制代码 代码如下: word=['a','b','c','d','e','f','g']//首个元素为元素0,word[0]=a a=[num1:num2] //从num1到num2的元素(不包括元素num2) //若为负数,则代表倒数第几个 在对list进行操作时,append 追加,word.append(elements)
-
python计数排序和基数排序算法实例
一.计数排序 计数排序(Counting sort)是一种稳定的排序算法 算法的步骤如下:找出待排序的数组中最大和最小的元素统计数组中每个值为i的元素出现的次数,存入数组C的第i项对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加)反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1当输入的元素是 n 个 0 到 k 之间的整数时,计数排序的时间复杂度为O(N+K),空间复杂度为O(N+K).当K不是很大时,这是一个很有效的线性排序算法. 以下是测试代
-
python strip()函数 介绍
函数原型 声明:s为字符串,rm为要删除的字符序列 s.strip(rm) 删除s字符串中开头.结尾处,位于 rm删除序列的字符 s.lstrip(rm) 删除s字符串中开头处,位于 rm删除序列的字符 s.rstrip(rm) 删除s字符串中结尾处,位于 rm删除序列的字符 注意: 1. 当rm为空时,默认删除空白符(包括'\n', '\r', '\t', ' ') 例如: 复制代码 代码如下: >>> a = ' 123'>>
-
Python入门教程 超详细1小时学会Python
为什么使用Python 假设我们有这么一项任务:简单测试局域网中的电脑是否连通.这些电脑的ip范围从192.168.0.101到192.168.0.200. 思路:用shell编程.(Linux通常是bash而Windows是批处理脚本).例如,在Windows上用ping ip 的命令依次测试各个机器并得到控制台输出.由于ping通的时候控制台文本通常是"Reply from ... " 而不通的时候文本是"time out ... " ,所以,在结果中进行
-
用Python解决计数原理问题的方法
前几天遇到这样一道数学题: 用四种不同颜色给三棱柱六个顶点涂色,要求每个点涂一种颜色,且每条棱的两个端点涂不同颜色,则不同的涂色方法有多少种? 当我看完题目后,顿时不知所措.于是我拿起草稿纸在一旁漫无目的地演算了一下,企图能找到解决方法.结果一无所获.于是打算通过程序算法解决这个问题.经过2个多小时的研究,终于完成了代码,并求得了答案. 由于Python写起来比较方便而且本人比较喜欢Python的语法,所以研究算法时我通常采用Python,此次也不例外.以下就是整个算法的实现过程. 两种算法 我
-
python单向循环链表原理与实现方法示例
本文实例讲述了python单向循环链表原理与实现方法.分享给大家供大家参考,具体如下: 单向循环链表 单链表的一个变形是单向循环链表,链表中最后一个节点的next域不再为None,而是指向链表的头节点. 操作 is_empty() 判断链表是否为空 length() 返回链表的长度 travel() 遍历 add(item) 在头部添加一个节点 append(item) 在尾部添加一个节点 insert(pos, item) 在指定位置pos添加节点 remove(item) 删除一个节点 se
-
简单了解python装饰器原理及使用方法
这篇文章主要介绍了简单了解python装饰器原理及使用方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 如果你接触 Python 有一段时间了的话,想必你对 @ 符号一定不陌生了,没错 @ 符号就是装饰器的语法糖. 装饰器的使用方法很固定: 先定义一个装饰函数(帽子)(也可以用类.偏函数实现) 再定义你的业务函数.或者类(人)最后把这顶帽子带在这个人头上 Python装饰器就是用于拓展原来函数功能的一种函数,目的是在不改变原函数名(或类名)的
-
Python双链表原理与实现方法详解
本文实例讲述了Python双链表原理与实现方法.分享给大家供大家参考,具体如下: Python实现双链表 文章目录 Python实现双链表 单链表与双链表比较 双链表的实现 定义链表节点 初始化双链表 判断链表是否为空 双链表尾部添加元素 双链表头部添加节点: 双链表表头删除 双链表按位置插入 双链表删除指定节点 完整代码 单链表与双链表比较 双链表比单链表多一个前驱指针位置,空间效率不占优势 由于双链表中的节点既可以向前也可以向后,相比单链表在查找方面效率更高(可使用二分法) 双链表的实现 定
-
Python单链表原理与实现方法详解
本文实例讲述了Python单链表原理与实现方法.分享给大家供大家参考,具体如下: Python实现单链表 关于链表 链表(Linked List)是由许多相同数据类型的数据项按照特定顺序排列而成的线性表. 链表中个数据项在计算机内存中的位置是不连续且随机的,数组在内存中是连续的. 链表数据的插入和删除很方便,但查找数据效率低下,不能像数组一样随机读取数据. 单链表的实现 一个单向链表的节点由数据字段和指针组成,指针指向下一个元素所在内存地址 定义一个链表节点类,self.value实例属性表示节
-
python 解决selenium 中的 .clear()方法失效问题
最近在使用selenium做一个数字货币的自动化脚本时,遇到一个问题就是okex网站的input使用clear()方法居然无法清空,但是后来试了好多次发现方法是可以使用的,而且这个网站修改input的value也没用,必须在文本框里修改才行,本次的目的就是要清除输入框的默认值,然而clear()没有反应,最后还是用了别的方法解决了问题,那就是使用鼠标双击事件,全选后输入内容. from selenium.webdriver.common.action_chains import ActionCh
-
Python Mock模块原理及使用方法详解
一.mock是什么? 英译中含义有:虚假的; 不诚实的; 模仿的; 模拟的 这个意思 这个库的主要功能就是模拟一些事务 官方解释:Mock是Python中一个用于支持单元测试的库,它的主要功能是使用mock对象替代掉指定的Python对象,以达到模拟对象的行为 二.为什么要用mock? 举例: 假设你开发一个项目,里面包含了一个登录模块,登录模块需要调用身份证验证模块中的认证函数,该认证函数会进行值的返回,然后系统根据这个返回值来做判断是否能进行登录.但是身份证验证模块中的认证函数只有在正式上线
-
Python模块zipfile原理及使用方法详解
zipfile是python里用来做zip格式编码的压缩和解压缩的,由于是很常见的zip格式,所以这个模块使用频率也是比较高的 zipfile里有两个非常重要的class, 分别是ZipFile和ZipInfo, 在绝大多数的情况下,我们只需要使用这两个class就可以了. ZipFile是主要的类,用来创建和读取zip文件 ZipInfo是存储的zip文件的每个文件的信息的. 比如要读取一个zipfile,这里假设filename是一个文件的路径: import zipfile z = zip
-
Python timeit模块原理及使用方法
Python 中的 timeit 模块可以用来测试一段代码的执行耗时,如一个变量赋值语句的执行时间,一个函数的运行时间等. timeit 模块是 Python 标准库中的模块,无需安装,直接导入就可以使用.导入时直接 import timeit ,可以使用 timeit() 函数和 repeat() 函数,还有 Timer 类.使用 from timeit import ... 时,只能导入 Timer 类(有全局变量 __all__ 限制). timeit 模块的源码总共只有 300 多行,主
-
简单了解python shutil模块原理及使用方法
shutil --High-level file operations 高级的文件操作模块 os模块提供了对目录或者文件的新建/删除/查看文件属性,还提供了对文件以及目录的路径操作.比如说:绝对路径,父目录-- 但是,os文件的操作还应该包含移动 复制 打包 压缩 解压等操作,这些os模块都没有提供. 而本章所讲的shutil则就是对os中文件操作的补充.--移动 复制 打包 压缩 解压 shutil 功能: 1 shutil.copyfileobj(fsrc,fds+[,length=16*1