`
810364804
  • 浏览: 773608 次
文章分类
社区版块
存档分类
最新评论

数据结构和算法设计专题之---24点游戏(穷举法和递归法)

 
阅读更多

一个简单的24点程序

下面本文将通过两个题目实例,分别给出用递归方法和循环方法的解决方案以及解题思路,便于读者更好地掌握两种方法。首先是一个简单的计算24点的问题(为了简化问题,我们假设只使用求和计算方法):

19中任选四个数字(数字可以有重复),使四个数字的和刚好是24

题目很简单,数字都是个位数,可以重复且之用加法,循环算法的核心就是使用四重循环穷举所有的数字组合,对每一个数字组合进行求和,判断是否是24。使用循环的版本可能是这个样子:

8constunsignedintNUMBER_COUNT=4;//9

9constintNUM_MIN_VALUE=1;

10constintNUM_MAX_VALUE=9;

11constunsignedintFULL_NUMBER_VALUE=24;//45;

40voidPrintAllSResult(void)

41{

42inti,j,k,l;

43intnumbers[NUMBER_COUNT]={0};

44

45for(i=NUM_MIN_VALUE;i<=NUM_MAX_VALUE;i++)

46{

47 numbers[0]=i;/*确定第一个数字*/

48 for(j=NUM_MIN_VALUE;j<=NUM_MAX_VALUE;j++)

49 {

50 numbers[1]=j;/*确定第二个数字*/

51 for(k=NUM_MIN_VALUE;k<=NUM_MAX_VALUE;k++)

52 {

53 numbers[2]=k;/*确定第三个数字*/

54 for(l=NUM_MIN_VALUE;l<=NUM_MAX_VALUE;l++)

55 {

56 numbers[3]=l;/*确定第四个数字*/

57 if(CalcNumbersSum(numbers,NUMBER_COUNT)==FULL_NUMBER_VALUE)

58 {

59 PrintNumbers(numbers,NUMBER_COUNT);

60 }

61 }

62 }

63 }

64}

65}

这个PrintAllSResult()函数看起来中规中矩,但是本人的编码习惯很少在一个函数中使用超过两重的循环,更何况,如果题目修改一下,改成9个数字求和是45的组合序列,就要使用9重循环,这将使PrintAllSResult()函数变成臭不可闻的垃圾代码。

现在看看如何用递归方法解决这个问题。递归方法的解题思路就是对题目规模进行分解,将四个数字的求和变成三个数字的求和,两个数字的求和,当最终变成一个数字时,就达到了递归终止条件。这个题目的递归解法非常优雅:

67voidEnumNumbers(int*numbers,intlevel,inttotal)

68{

69inti;

70

71for(i=NUM_MIN_VALUE;i<=NUM_MAX_VALUE;i++)

72{

73 numbers[level]=i;

74 if(level==(NUMBER_COUNT-1))

75 {

76 if(i==total)

77 {

78 PrintNumbers(numbers,NUMBER_COUNT);

79 }

80 }

81 else

82 {

83 EnumNumbers(numbers,level+1,total-i);

84 }

85}

86}

87

88voidPrintAllSResult2(void)

89{

90intnumbers[NUMBER_COUNT]={0};

91

92 EnumNumbers(numbers,0,FULL_NUMBER_VALUE);

93}

如果题目改成“9个数字求和是45的组合序列”,只需将NUMBER_COUNT的值改成9FULL_NUMBER_VALUE的值改成45即可,算法主体部分不需做任何修改。

分享到:
评论

相关推荐

    C++数据结构知识点与经典算法整理

    一、数据结构知识点总结整理 3 2.数据结构的定义: 4 3.数据结构的知识: 9 二、数据结构的实现 16 1、二叉树三种遍历的非递归算法 16 1.先序遍非递归算法 16 2.中序遍历非递归算法 17 3.后序遍历非递归算法 18 4....

    数据结构与算法综合资料库

    数据结构与算法综合资料库.CHM 介绍 何谓数据结构 算法综合知识 用递归中序遍历二叉树 BRESENHAM高效画线算法 C++的沉迷与爱恋 C++复习题一 C++复习题 二 DES加密算法破解方法 DES算法及其应用误区 N皇后问题 采用...

    数据结构与算法综合资料库.CHM

    数据结构与算法综合资料库.CHM 介绍 何谓数据结构 算法综合知识 用递归中序遍历二叉树 BRESENHAM高效画线算法 C++的沉迷与爱恋 C++复习题一 C++复习题 二 DES加密算法破解方法 DES算法及其应用误区 N皇后问题 采用...

    C语言算法1-3章 算法,递归算法 模拟算法

    1.6.分治算法.wmv 1.5.递归算法.wmv 1.4.枚举(穷举)算法.wmv 3.2.网状关系:图(2).wmv 3.2.网状关系:图(1).wmv 3.1.层次关系结构:树(3).wmv ...1.1.编程的灵魂:数据结构.算法.wmv 3.1.层次关系结构:树(3).wmv

    C语言算法视频教程集合(递推、枚举、递归、分治、贪婪、试探法、模拟、数据结构)

    5、在实际编程中,这些算法和数据结构的知识对于设计高效的程序和解决复杂的问题至关重要。 内容目录如下: 1.1.编程的灵魂:数据结构.算法.wmv 1.2.算法的作用:猜价格游戏.wmv 1.3.递推算法.wmv 1.4.枚举(穷举)...

    常用算法设计方法常用算法设计方法

    算法设计是一件非常困难的工作,经常采用的算法设计技术主要有迭代法、穷举搜索法、递推法、贪婪法、回溯法、分治法、动态规划法等等。另外,为了更简洁的形式设计和描述算法,在算法设计时又常常采用递归技术,用...

    数据结构及算法编程(阿蒙工作室)

    数据结构及算法编程 ☆ “二分法”求二元方程的解 ☆ Bresenham高效画线算法 ☆ C++的沉迷与爱恋 ☆ C++复习题 二 ☆ C++复习题一 ☆ DES加密算法破解方法 ☆ DES算法及其应用误区 ☆ N皇后问题 ☆ 采用循环双向...

    数据结构 算法设计初步

    10.1迭代法与穷举法 10.2 递归与分治法 10.3 回溯法 10.4 倒推法 10.5 贪心法 10.6 分枝限界法 10.7 动态规划法

    数据结构与算法视频总结-1

    1.3 递推算法 1.4 枚举(穷举)算法 1.5 递归算法 1.6 分治算法 1.7 贪婪算法 1.8 试探法算法 1.9 模拟算法 4.1 排序概述 4.2 冒泡排序法 4.3 快速排序法 4.4 简单选择排序法 4.5 堆排序法 4.6 直接插入排序法 4.7 ...

    数据结构与算法视频总结-4

    1.3 递推算法 1.4 枚举(穷举)算法 1.5 递归算法 1.6 分治算法 1.7 贪婪算法 1.8 试探法算法 1.9 模拟算法 4.1 排序概述 4.2 冒泡排序法 4.3 快速排序法 4.4 简单选择排序法 4.5 堆排序法 4.6 直接插入排序法 4.7 ...

    史上最全经典数据结构算法c语言实现代码合集

    数据结构3.txt 数组完全单元.txt 数组操作.txt 数组递归退出.txt 数组递归退出2.txt 文件加密.txt 文件复制.txt 文件连接.txt 无向图.txt 时间陷阱.txt 杨辉三角形.txt 栈单元加.txt 栈操作.txt 桃子...

    各种数据结构算法例子

    C#算法(一)冒泡排序 C#算法(二)选择排序 C#算法(三)插入排序 C#算法(四)希尔排序 穷举搜索法 递归法 回溯法

    经典数据结构算法c语言实现代码(大全)

    数据结构3.txt 数组完全单元.txt 数组操作.txt 数组递归退出.txt 数组递归退出2.txt 文件加密.txt 文件复制.txt 文件连接.txt 无向图.txt 时间陷阱.txt 杨辉三角形.txt 栈单元加.txt 栈操作.txt 桃子...

    数据结构 课程设计 八皇后问题(C语言源程序 + Word版课程设计说明书)

    本次设计旨在通过学习各种数据结构及算法的同时,训练对基础知识和基本方法的综合运用及变通能力,增强对算法的理解能力,提高软件设计能力。在实践中培养独立分析问题和解决问题的作风和能力。

    数据结构及算法C语言实现代码集[推荐下载]

    数据结构 数组 文件程序 求进制 汉诺塔 硬币情况 逆阵 链串.c 链栈.c 链队列.c 问题算法 顺序栈.c 顺序表.c 顺序队列.c ./其它&#58; c语言窗体实例.zip 傻瓜递归.c 冒泡法改进.c 小字库DIY-.c 小字库DIY.c 小白鼠钻...

    算法设计与分析之回溯算法ppt

    算法设计与分析 目录 动态规划 贪心算法 状态空间搜索法 分治法 随机算法 模拟算法 递归算法 数论算法 回溯算法 对于有些最优解问题,没有任何的理论也无法采用精确的数学公式来帮助我们找到最优解,我们只能用...

    数据结构经典问题和算法分析

    递归是设计和描述算法的一种有力的工具,由于它在复杂算法的描述中被经常采用,为此在进一步介绍其他算法设计方法之前先讨论它。 能采用递归描述的算法通常有这样的特征:为求解规模为N的问题,设法将它分解成...

    IOI国家集训队论文集1999-2019

    陈 宏 -《数据结构的选择与算法效率——从IOI98试题PICTURE谈起》 来煜坤 -《把握本质,灵活运用——动态规划的深入探讨》 齐 鑫 -《搜索方法中的剪枝优化》 邵 铮 -《数学模型的建立、比较和应用》 石润婷 -...

    C/C++常用算法手册.秦姣华(有详细书签).rar

    “第2篇算法基本应用篇”详细讲解了算法在排序、查找、数值计算、数论、经典趣题和游戏中的应用;“第3篇算法高级应用篇”讲解了算法的一些高级应用技术,包括在密码学和数据压缩/解压缩中的应用。 《C/C++常用算法...

Global site tag (gtag.js) - Google Analytics