算法数据结构和算法分析Python算法之旅

算法进化历程1剪刀石头布

2020-03-27  本文已影响0人  巧若拙

算法进化历程之剪刀石头布

小美:阿福,你玩过剪刀石头布游戏吗?

阿福:这算什么问题?谁还能没玩过剪刀石头布?要知道它可是一种世界闻名的猜拳游戏。它起源于中国,然后传到日本、朝鲜等地,随着亚欧贸易的不断发展它传到了欧洲,到了近现代逐渐风靡世界。简单明了的规则(石头打剪刀,布包石头,剪刀剪布),使得剪刀石头布游戏没有任何规则漏洞可钻,单次玩法比拼运气,多回合玩法比拼心理博弈,使得剪刀石头布这个古老的游戏同时拥有“意外”与“技术”两种特性,深受世界人民喜爱。

小美:哟,你还知道的挺多。那你会编写程序和电脑玩剪刀石头布游戏吗?

阿福:这个应该不难,不就是几条分支语句吗?我今天就让你看看我扎实的基本功。


问题1:

函数功能:根据游戏规则和甲乙玩家出拳情况,输出石头剪子布游戏的结果。

函数名:rock_paper_scissors(s1:str,s2:str)->str

参数表:s1,s2-- 字符串,分别表示甲乙两个人的出拳,只可能取值在{"石头","剪刀","布"}中。

返回值:字符串,存储了游戏结果,只可能取值在{"甲胜","乙胜","平局"}中。

示例1:s1="石头",s2="剪刀",返回"甲胜";

示例2:s1="石头",s2="布",返回"乙胜";

示例3:s1="石头",s2="石头",返回"平局"。


代码1:

def rock_paper_scissors(s1:str,s2:str)->str:

   #最基础的复合条件判断语句

   if s1 == s2:

       ans = "平局"

   elif (s1 == "剪刀" and s2 == "布" or

         s1 == "石头" and s2 == "剪刀" or

         s1 == "布" and s2 == "石头"): 

       ans = "甲胜"

   else:

       ans = "乙胜"

return ans

小美:嗯,程序确实符合算法要求,思路也还算清晰。但你不觉得代码有点长吗?

阿福:这还长?

小美:是啊,特别是那个elif语句,里面条件表达式太长了,and和or交织在一起,这样容易出错。

阿福:那倒是。不过也没办法,它就是要分成3种情况来判断。难道你有更好的方法?

小美:哈哈,初中生要向小学生请教了!我给你点提示吧:利用Python里面的字典数据结构。

阿福:字典?我知道字典,它是用键值对存储元素的一种数据结构。但是它跟这道题目好像没什么关系啊。

小美:瞧瞧你这脑回路,亏你还知道键值对!我问你,本题中的出拳名称是不是各不相同,而且可以用字符串来存储?

阿福:是啊,我刚才就是这样做的。各不相同、字符串。。。。。。。哦,我明白了!我们可以使用出拳名称来作为字典元素的键,然后每种拳法的天敌作为其对应的值。例如R["石头"]="布",表示"石头"的天敌是"布",这样就可以直接利用字典的键值对来确定出拳的胜负关系了。

小美:总算开窍了。

阿福:没错,小美,今天从你这学到一招。现在我把代码写出来,你看看对不对。


代码2:

def rock_paper_scissors2(s1:str,s2:str)->str:

    #用字典存储各种手法的天敌关系

    R= {"剪刀":"石头", "石头":"布", "布":"剪刀"}

   if s1 == s2: 

       ans = "平局"

   elif s1 == R[s2]: #s1是s2的天敌

       ans = "甲胜"

   else:

       ans = "乙胜"

return ans

知识小贴士:

字典是一种可变容器模型,可存储任意类型对象,具有极快的查找速度。字典的每个元素都是一个键值对,其值可以取任何数据类型,但键必须是唯一且不可变的,如字符串,数字或元组,这种结构类型也称之为映射。


古老师:哎呀,不好意思来晚了。学如逆水行舟,不进则退。阿福你要努力啊,不然就要被小学生超过了。不过你们今天使用的方法有点意思,利用字典的键值对,可以直接设置两个对象的关系,避免复杂的条件判断,确实是解决配对类问题的好方法。

但是这道题目还可以用另外一种方法来解决。

小美:还有别的方法?

古老师:是的,听说过解析算法吗?

阿福:解析算法就是用解析的方法找出表示问题的前提条件与结果之间关系的数学表达式,并通过表达式的计算来实现问题求解的方法。

小美:这个我也听说过,解析算法的解题思路分为四步:明确问题的前提条件;明确要求的解;寻找条件与结果之间的关系式;编程描述数学关系式。

古老师:没错!基础挺扎实的。那你们能找到本题的前提条件、要求的解和关系式吗?

阿福:前提条件是甲乙玩家出拳情况,要求的解是游戏的结果。

小美:可是条件和解都是字符串,它们之间只存在逻辑关系,怎么建立二者的数学关系式呢?字符串可不能参与数学运算啊。

阿福:那我们可以把字符串和数值建立对应关系,这样就能参与数学运算了。

小美:还真是这样呢。我们可以用字典的键值对把字符串和数值对应起来。

阿福:也可以用列表或者元组存储字符串,这样它的下标(又称索引)值就是数值了。

古老师:分析的很到位。那你们打算如何存储出拳情况和游戏结果呢?

小美:我打算定义两个字典:num = {"剪刀":1, "石头":2,"布":3}; 

ans = {0:"平局", 1:"甲胜", -2:"甲胜", -1:"乙胜", 2:"乙胜"},把字符串和数值建立对应关系。

我们可以对数值做减法运算,当出拳相同时,结果为0,对应“平局”。

若甲出“石头”乙出“剪刀”,相当于1-0=1,我们可以用数值1代表“甲胜”;若甲出“布”乙出“石头”,相当于2-1=1,也是“甲胜”;若甲出“剪刀”乙出“布”,相当于0-2=-2,也是“甲胜”。

同理我们也可以得到“乙胜”结果对应的数值。这样直接返回字典的值就行了,代码非常简单。


代码3:

def rock_paper_scissors(s1:str,s2:str)->str:

    #用字典存储各种手法的序号、数值差对应的结果,再直接返回结果

   num = {"剪刀":1, "石头":2,"布":3}

   ans = {0:"平局", 1:"甲胜", -2:"甲胜", -1:"乙胜", 2:"乙胜"}

   return ans[num[s1] - num[s2]]

阿福:用字典存储各种手法的序号我一百个同意,可是你用字典存储游戏结果时,“甲胜”和“乙胜”都存在两种情形,我觉得不够简明。

小美:不简明?可对序号求差就是会出现两种结果啊,难道还能简化成一种情况吗?

古老师:没错,确实可以转化成同一个值。你们听说过模运算吗?

小美:模运算我知道,就是求余数嘛。我们在判断某个数的奇偶性时就是使用模运算来处理的,还有求最大公约数也要使用模运算。

阿福:“模”是指一个计量系统的计数范围。如时钟,12个整点为计算范围,则模为12。所以我们也称14点为下午2点,2就是14%12的结果;我们也称24点为0点,因为24%12结果为0。

模运算和取余运算不完全一致,它们在对负整数进行除法运算时操作不同,当运算数为负整数时,不能简单地以为先将运算数取绝对值再求余数。模运算计算公式为r = a - b * (a // b)。例如14 % 6、-14 % 6和14 % -6的结果分别是2、4和-4。

古老师:没错,阿福的理论基础很扎实。取模主要是用于计算机术语中;取余则更多是数学概念。请大家思考,在对局结果只有3种情况的前提下,怎样通过模运算把1和-2整合成同一个值?

小美;对局结果只有3种情况,那是不是意味着以3为模?难道1%3和-2%3的结果相同?

阿福:是的,结果都是1。如果你不太习惯运算数为负值的话,也可以先对它们都做加3的处理,即(1+3)%3==(-2+3)%3。

小美:转化成正数以后确实更能接受了。这样代码更简洁了。


代码4:

def rock_paper_scissors(s1:str,s2:str)->str:

    #用字典存储各种手法的序号,用元组存储结果,再使用模运算解析式求解结果

   num = {"剪刀":1, "石头":2,"布":3}

   ans = ("平局", "甲胜", "乙胜")

   return ans[(num[s1] - num[s2]) % 3]#或ans[(num[s1] -num[s2] + 3) % 3]

古老师:非常棒!能够利用字典或元组把字符串跟数值建立对应关系,并且熟练使用模运算解析式求解游戏结果,思路非常灵活啊!Python的字典是一种常见的数据结构,可以非常方便地建立某种对应关系。我再给你们提供一个拓展练习,巩固一下今天学习的内容吧。


问题2:

碱基链配对:脱氧核糖核酸(DNA)由两条互补的碱基链以双螺旋的方式结合而成。而构成DNA的碱基共有4种,分别为腺嘌呤(A)、鸟嘌呤(G)、胸腺嘧啶(T)和胞嘧啶(C)。我们知道,在两条互补碱基链的对应位置上,A总是和T配对,G总是和C配对。你的任务就是根据一条单链上的碱基序列,给出对应的互补链上的碱基序列。

函数功能:根据输入的一条单链上的碱基序列,给出对应的互补链上的碱基序列。

函数名:match(chain:str)-> str

参数表:chain-- 字符串,表示一条碱基链。这个字符串只含有大写字母A、T、G、C。

返回值:一个只含有大写字母A、T、G、C的字符串,为与输入的碱基链互补的碱基链。

示例1:chain='ATATGGATGGTGTTTGGCTCTG',返回'TATACCTACCACAAACCGAGAC'。


彩蛋:

阿福:小美啊,古老师出的这个题目和你出给我的几乎一模一样,我就不做重复的练习了。今天的话题是你挑起来的,这个光荣而艰巨的任务就交给你吧。

小美:不就是为4种碱基设置配对关系吗?这有何难!看我的。


代码5:

def match(chain:str) -> str:

    #用字典存储各种碱基的配对关系

    R= {'A':'T', 'T':'A', 'G':'C', 'C':'G'}

    a= []

   for c in chain:

       a.append(R[c])

   return ''.join(a)

上一篇下一篇

猜你喜欢

热点阅读