24点扑克牌游戏.ppt

第第1313章章 24 24点扑克牌游戏点扑克牌游戏前面学前面学习了了C语言各方面的知言各方面的知识，本章通，本章通过经典游典游戏“24点扑克牌点扑克牌”的的设计与与实现来提高来提高读者的学者的学习兴趣，能趣，能够对相关知相关知识有有较强的的综合运用能力。合运用能力。编写程序写程序实现的的“24点扑点扑克牌克牌”游游戏，就是利用，就是利用计算机模算机模拟随机随机发给用用户4个数，用个数，用户尽量将尽量将这4个数利用加减乘除四个数利用加减乘除四则运算最后得到运算最后得到24。本章本章讲述的知述的知识点包括：点包括：将中将中缀表达式表达式转换为后后缀表达式的算法的表达式的算法的实现。对后后缀表达式的求表达式的求值算法的算法的实现。栈的概念及其基本操作。的概念及其基本操作。随机数随机数产生的算法的生的算法的实现。13.1 13.1 游戏描述游戏描述“24点扑克牌游点扑克牌游戏”是一个很多人从小到大都在玩的游是一个很多人从小到大都在玩的游戏，作，作为老少皆宜的大众游老少皆宜的大众游戏，很多人都将它作，很多人都将它作为孩子学孩子学习数学和开数学和开发智力的工具。智力的工具。最初是几个人使用一副扑克牌来玩此游最初是几个人使用一副扑克牌来玩此游戏，基本的游，基本的游戏规则是：随便从一副扑克牌中拿出四是：随便从一副扑克牌中拿出四张牌，参与游牌，参与游戏的人将的人将这四四张扑克牌上的数字（其中扑克牌上的数字（其中J算算11、Q算算12、K算算13）用）用加、减、乘、除、四加、减、乘、除、四则运算（包括括号）将四个数运算（包括括号）将四个数组成一个成一个表达式，使表达式的表达式，使表达式的结果果为24。看。看谁算得最快，算得最快，谁就就赢了。了。使用使用计算机模算机模拟该游游戏，就是随机，就是随机产生生4个个113之之间的的整数，由用整数，由用户输入它入它们组合后的表达式，合后的表达式，计算机算机计算算该表达表达式的式的值，判断是否，判断是否为24。13.2 13.2 游戏解析游戏解析知道了游知道了游戏的基本的基本规则，下面开始分析，下面开始分析设计了。大家都了。大家都知道，我知道，我们直接通直接通过键盘输入算入算术表达式，表达式，计算机系算机系统是不是不会会给我我们算出表达式的算出表达式的结果的。那么，如何果的。那么，如何计算出表达式的算出表达式的值呢呢?经过分析，分析，实现这个游个游戏有两个关有两个关键点，一个是如何点，一个是如何处理用理用户输入的表达式，以便入的表达式，以便为计算表达式的算表达式的值作准作准备，另，另外一个就是外一个就是对表达式如何求表达式如何求值。13.2.1 13.2.1 处理用户输入得表达式处理用户输入得表达式现在，将我在，将我们平平时输入的表达式称入的表达式称为中中缀表达式，而表达式，而计算机存算机存储一般都是后一般都是后缀表达式。所以，我表达式。所以，我们要将用要将用户输入的入的中中缀表达式表达式转换为后后缀表达式后存表达式后存储。1算算术表达式的形式表达式的形式2将中将中缀表达式表达式转换为后后缀表达式表达式13.2.2 13.2.2 对后缀表达式求值对后缀表达式求值由于后由于后缀表达式中没有括号，不需判表达式中没有括号，不需判别优先先级，计算算严格从左向右格从左向右进行，故行，故计算一个后算一个后缀表达式要比表达式要比计算机一个中算机一个中缀表达式表达式简单得多。在我得多。在我们的程序中就是的程序中就是对转换成的后成的后缀表表达式达式进行行计算，算，这样比比较方便。方便。对后后缀表达式表达式进行求行求值计算的算法思想是：算的算法思想是：（1）建立一个）建立一个栈（STACK类型）；型）；（2）从左到右）从左到右读后后缀表达式，表达式，读到数字就将它到数字就将它转换为数数值压入入栈中，中，读到运算符到运算符则从从栈中依次中依次弹出两个数分出两个数分别到到num2和和num1，然后以然后以“num1 运算符运算符 num2”的形式的形式计算出算出结果，再将果，再将结果果压加加栈中；中；（3）如果后）如果后缀表达式未表达式未读完，就重复上面完，就重复上面过程（程（2），），直到直到读到到结束符束符“0”为止，最后止，最后输出出栈顶的数的数值则为最后表最后表达式的达式的结果。果。13.3 13.3 两个重要函数的实现两个重要函数的实现通通过前面的分析，那么下面如何具体的用前面的分析，那么下面如何具体的用C语言言实现将将中中缀表达式表达式转换为后后缀表达式的和表达式的和对后后缀表达式表达式进行求行求值计算的算的这两个函数呢？两个函数呢？13.4 13.4 “2424点扑克牌游戏点扑克牌游戏”的实现的实现两个重要算法两个重要算法实现了，那么了，那么“24点扑克牌游点扑克牌游戏”的的实现基本就没有太大基本就没有太大问题了。但是了。但是为了更好的体了更好的体现游游戏并并实现其其功能，功能，还要有几部分要有几部分辅助的函数。助的函数。13.4.1 13.4.1 栈的基本操作函数的实现栈的基本操作函数的实现在代在代码13-1和代和代码13-2中，大量的用到了中，大量的用到了栈的相关操作，的相关操作，所以所以还要在程序中要在程序中编写相写相应的函数来的函数来实现栈的操作。由于的操作。由于栈的操作都是在一端的操作都是在一端进行，所以本程序行，所以本程序实现栈的存的存储使用了使用了动态存存储的的链表形式。我表形式。我们可以将可以将链表的表表的表头作作为栈顶，这样不但可以利用不但可以利用链表表头指指针就可以很方便就可以很方便实现栈的操作，的操作，还有有利于空利于空间的合理分配。的合理分配。栈的基本操作主要有判断的基本操作主要有判断栈是否是否为空、入空、入栈、出、出栈、读取取栈顶元素的元素的值和和读取取栈顶元素的元素的值并出并出栈。13.4.2 13.4.2 随机发四张扑克牌函数的实现随机发四张扑克牌函数的实现游游戏的玩法在的玩法在实际中是随便中是随便发四四张扑克牌，根据扑克牌，根据这四四张牌上的数牌上的数进行加减乘除运算行加减乘除运算结果凑成果凑成24。我我们编写的程序要模写的程序要模拟发牌的牌的过程，程，这如何解决？很如何解决？很简单，只需要要，只需要要计算机随机算机随机产生四个生四个113之之间（扑克牌上的数（扑克牌上的数是是113之之间）的整数即可。在）的整数即可。在C语言中，使用言中，使用random函数函数就可就可产生一个随机数。生一个随机数。13.4.3 13.4.3 检查输入表达式的正确性函数的实现检查输入表达式的正确性函数的实现由于由于对用用户输入的表达式有特殊的要求（在每个数字入的表达式有特殊的要求（在每个数字结束后要加一个束后要加一个“.”），也），也为了程序的完整性和安全性，在程序了程序的完整性和安全性，在程序中中编写了写了检查用用户输入的表达式是否符合要求的函数。入的表达式是否符合要求的函数。13.4.4 13.4.4 mainmain函数的实现函数的实现main函数主要完成的事情就是理清思路，将前面分析函数主要完成的事情就是理清思路，将前面分析设计的函数有机的的函数有机的组织在一起，在一起，实现真正的真正的“24点扑克牌点扑克牌”游游戏。13.5 13.5 小结小结本程序中，最主要是本程序中，最主要是实现了中了中缀表达式表达式转换成后成后缀表达表达式和后式和后缀表达式表达式计算的两个算法。在两个算法中，都使用了算的两个算法。在两个算法中，都使用了栈。虽然两个然两个栈的的类型一型一样，但是在中，但是在中缀表达式表达式转换成后成后缀表达式算法中，表达式算法中，栈是用来存放运算符和左括号的；而在后是用来存放运算符和左括号的；而在后缀表达式表达式计算的算法中算的算法中栈是用来存放参与运算的数。是用来存放参与运算的数。