算法设计与分析 第一章 递推算法 1.概述 2.斐波那切数列前n项 Fibonacci 数列:0,1,1,2,3,5,8,13,21,34,…… f0 = 0 f1 = 1 fn = fn-1 + fn-2 ( n >= 2 ) 分析 : 可以用迭代方法求解 2.N层汉诺塔的移动次数 递推关系分析 f(n)=2*f(n-1)+1 边界条件:f(1)=1. 3.猴子...

本次博客,直接简述核心动态规划部分,需要先对动态规划以及什么是最长公共子序列有简单了解,可以参考下博客, 最长公共子序列 (LCS) 详解+例题模板(全) https://blog.csdn.net/lxt_Lucia/article/details/81209962 动态规划解最长公共子序列(LCS)(附详细填表过程) https://blog.csdn.net/weixin_40673608/...

第5天 设计语法分析器 5.1 Stone语言的语法 代码清单 5.1 Stone 语言的语法定义 5.2 使用解析器和组合子 Parser库: 一种解析器组合子类型的库 工作是将BNF写成的语法规则改写成Java语言程序 在书中第十七章有详细解说 代码清单 5.2 Stone 语言的语法分析器BasicParser.java Parser类与Operators类都是由库提供的类。 rule方法是...

第9天 设计面向对象语言 目标:为Stone语言添加类和对象的支持。仅支持单一继承 9.1 设计用于操作类与对象的语法 添加的类与对象的处理功能后,下面的Stone语言就能被正确执行了 首先定义一个Position类,方法由def语句定义。类中字段通过变量表示,并赋了初始值。上面的例子定义了move方法以及字段x与y。 类名后接.new组成的代码表示创建一个对象。为简化实现,这里规定Stone语言...

第11天 优化变量读写性能 以变量值的读写为例,向读者介绍基于这种理念的语言处理器性能优化方式。 11.1 通过简单数组来实现环境 假如函数包含局部变量x与y,程序可以事先将x设为数组的第0个元素,将y设为第1个元素,以此类推。这样一来,语言处理器引用变量时就无需计算哈希值。也就是说,这是一个通过编号,而非名称来查找变量值的环境 为了实现这种设计,语言处理器需要在函数定义完成后遍历对应的抽象语法树...

算法——归并排序 一.归并排序的原理 原理:使用递归方法来实现归并排序时,核心思想是两个有序子序列的合并,注意这里是有序子序列的合并,因此下面要做两件事: (1)将待排序序列从中间一分为二,对左右两边再进行递归分割操作,得到n个相互独立的子序列; (2)对n个独立的子序列递归的执行合并操作,最终得到有序的序列。 二.归并排序的java实现...

题号 15 题目描述 给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。 注意:答案中不可以包含重复的三元组。 示例: 链接:leetcode #15 三数之和 注意:以下三种解题思路,只有第三种AC了,可以直接查看第三种。 解题思路1【暴力法】: 最直观的想法就是采用三层for循环,依...

STL的代码从广义上分为三类:Algorithm(算法)、Container(容器)、Iterator(迭代器) 栈 向量 映射 列表 集合 栈 头文件 定义一个栈 成员函数 向量 STL容器Vector是一个动态数组,随机存取任何元素都能在常数时间完成。 可以通过迭代器随机的存取,当往其插入新的元素时,如果在结尾插入,将会执行效率比较高,而如果往中间的某个位置插入,其插入位置之后的元素都要后移,...

老规矩步入正题之前先说点儿题外话,今天老师讲的东西感觉没什么需要记录的,所以今天就把之前老师布置的一个作业拿出来分析一下吧,水一篇文章,毕竟好几天没更新了,话不多说,上题 Question 整数划分问题。把正整数n表示成一系列正整数的和,n=n1+n2+n3+…+ni,这种表示成为n的划分,不同的划分个数称为正整数n的划分数,如6有11种划分。设计算法,输出n的划分数和具体的划分方法...

分治 总体思想 使用条件 基本步骤 案例 覆盖残缺棋盘 大整数的乘法 Strassen矩阵乘法 分治 总体思想 将要求解的较大规模的问题分割成k个更小规模的子问题 对这k个子问题分别求解。如果子问题的规模仍然不够小,则再划分为k为子问题,如此递归进行下去,直到问题规模足够小,很容易求出其解为止 将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原来的问题的解 使用条件 该问题的...

文章目录 前言 算法分析 算法思想 代码分析 JavaScript代码 准备代码 普通版 代码分析 测试实例 优化版 代码分析 测试实例 C语言代码 算法效率分析 后记 前言 快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为较小和较大的2个子序列,然后递归地排序两个子序列。 ——维基百科 快速排序与归并排序相同,都是使用了分治法的思...

动态规划 算法总体思想 基本步骤 矩阵连乘问题 问题描述 分析 解决方法 具体步骤 案例 Java代码实现 动态规划 History does not occur again 算法总体思想 与分治算法类似 子问题往往不是互相独立的, (分治会重复计算) 保存已解决的子问题的答案,需要时找出即可(空间换时间) 基本步骤 找出最优解的性质并刻划其结构特征 递归地定义最优值 以自底向上的方式计算出最优值...

递归算法 递归算法是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数(或过程)来表示问题的解。 一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函数) 递归算法特点: (1) 递归就是在过程或函数里调用自身。 (2) 在使用递归策略时,必须有一个明确的递归结束条件,称为递归出口。 (3) 递归算法解题通常显得很简洁,但递归算法解题的运行效率较低。所以一般不提倡用...

问题描述 Gray码是一个长度为2n的序列。序列中无相同的元素,每个元素都是长度为n位的串,相邻元素恰好只有一位不同。用分治策略设计一个算法对任意的n构造相应的Gray码。 编程任务 利用分治策略试设计一个算法对任意的n构造相应的Gray码。 数据输入 由文件input.txt提供输入数据n。 实现提示 把原问题分解为两个子问题,分别对两个子问题的每个数组后一位加0和1 解决思路: ①根据输出结果...