解析算法

解析算法（精选6篇）

解析算法 篇1

摘要：电力系统有功优化, 从20世纪30年代开始就一直广受人们关注, 电力系统运行的任务是保证系统安全、可靠、持续供电, 在保证电能质量的前提下, 提高电能生产输送的效率, 尽量降低燃料使用费或供电成本。

关键词：有功优化,遗传算法,基本流程

最优潮流, 就是当系统的结构参数及负荷情况给定时, 通过控制变量的优选, 找到能满足所有指定的约束条件, 并使系统的一个或多个性能指标达到最优潮流分布。最优潮流问题本身是一个非线性规划问题。最优潮流 (Optimal Power Flow.OPF) 作为经济调度理论的发展与延伸, 将经济性和安全性完美的结合在一起, 它在电力系统的安全运行、经济调度、电网规划、复杂电力系统的可靠性分析、传输阻塞的经济控制、能量管理系统等方面得到了广泛的应用。

1 基于遗传算法电力系统有功优化运行

遗传算法起源于对生物系统所进行的计算机模拟研究。美国Michigan大学的J·Holland教授及其学生受到生物模拟技术的启发, 创造了一种基于生物遗传和进化机制的适合于复杂系统优化的自适应概率优化技术一遗传算法。遗传算法与传统的算法不同。大多数古典的优化算法是基于一个单一的度量函数 (评估函数) 的梯度或较高次统计, 以产生一个确定性的试验解序列;遗传算法不依赖于梯度信息, 而是通过模拟自然进化过程来搜索最优解, 它利用某种编码技术, 作用于叫染色体的数字串, 模拟由这些串组成的群体的进化过程。遗传算法通过有组织、随机的信息交换来重新组合成那些适应性好的串, 生成新的群体。并适用于处理传统搜索方法难于解决的复杂问题和非线性问题, 可广泛用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域, 是21世纪有关智能计算中的关键之一。

对于工程和科学中的许多实际问题, 找到一个最优解的唯一可靠的方法是穷举法, 即搜索问题的整个参变量空间。在许多情况下, 由于参变量空间太大, 以致在限定的时间内只可能搜索其中极小的一部分。而遗传算法像撒网一样, 在参变量空间中进行搜索, 由染色体组成的群体在遗传算子的作用下, 同时对空间中不同的区域进行采样计算, 从而构成一个不断进化的群体序列。与传统的优化算法相比, 遗传算法主要有以下几个优点。

(1) 遗传算法处理对象不是参数本身, 而是参数集编码所得到的基因个体。这一特点使得遗传算法具有广泛的应用领域。

(2) 遗传算法不是采用单点搜索法, 而是同时处理群体中多个个体的方法, 即同时对搜索空间中的多个解进行评估。这一特点使遗传算法具有较好的全局搜索性能, 也使得遗传算法本身易于并行化。

(3) 遗传算法仅用适应度值信息来评估基因个体, 并在此基础上进行遗传操作。遗传算法的适应度函数不仅不受连续可微的约束, 而且其定义域可以任意设定。对适应度函数的唯一要求是:编码必须与可行解空间对应, 不能有死码。由于限制条件的缩小, 使得遗传算法的应用范围大大扩展。

(4) 遗传算法么有采用确定性规则, 而是利用概率转移规则来指导它的搜索方向。概率仅是作为一种工具来引导其搜索过程并朝着搜索空间的更优化的解区域移动的。虽然看起来它是一种盲目搜索方法, 实际上它有明确的搜索方向, 具有内在的并行搜索机制。

但是遗传算法也有其自身的缺点, 表现在以下几个方面。

(1) 编码不规范及编码存在表示的不准确性; (2) 单一的遗传算法编码不能全面地将优化问题的约束表示出来; (3) 遗传算法的效率通常比其它传统的优化方法低; (4) 遗传算法容易出现过早收敛; (5) 遗传算法对算法的精度、可信度、计算复杂性等方面, 还没有有效的定量分析方法。

2 遗传算法基本流程

2.1 编码

解空间中的解数据x, 作为遗传算法的表现型形式, 从表现型到基因的映射称为编码。利用遗传算法进行问题求解时, 首先确定问题的目标函数和变量, 然后对变量进行编码。这样做主要是因为在遗传算法中, 问题的解是用数字串表示的, 而且遗传算子也是直接对串进行操作。编码方式可分为二进制编码和实数编码。以二进制编码为例说明编码的过程:设变量x的区间是[-3.0, 12.1], 要求的精度是小数点后4位, 则对每个变量应该被分成至少 (121.- (-.30) ) ×104=151000个部分, 接着确定一个变量的二进制串位数 (染色体长度) 因为217<151000<218所以可以确定染色体的长度为17位。遗传算法的创始人Holland认为:采用二进制编码与计算机码一致, 适合于计算机用;在染色体中的每一位只有1和0两个编码值, 在交叉和变异等操作中原理清晰, 操作简单;表示的变t范围大, 适合于表示离散变量, 而对于连续变量, 只要群体总取足够大, 就可以达要求的精度。

2.2 初始群体的生成

随机产生个初始串结构数据, 每个串结构数据称N为一个个体, 个个体构成了一个群体。基本遗传算法以N这个个体作为初始点开始迭代。设置进化N代数计数器t=0;设置最大进化代数T;随机生成M个个体作为初始群体P (0) 。

在实际应用遗传算法解决问题时, 由于问题解的空间大小可能有很大的差别, 种群数目对遗传算法性能影响不容忽视:一方面太小的种群数目容易产生较大的采样误差, 另一方面太大的种群数目会影响遗传算法的收敛时间导致计算资源的浪费。实际上, 初始群体的选取, 应根据实际问题来权衡。

2.3 适应度函数值的评价

适应度函数值是对解的质量的度量, 它通常依赖于解的行为环境 (即种群) 的关系。适应度函数是用来区分群体中个体好坏的标准, 是遗传算法的驱动力, 是进行自然选择的唯一标准。改变群体内部结构的操作皆通过适应度值加以控制。

一般以目标函数或费用函数的形式来表示适应度函数, 对于不同的问题, 适应度函数的定义方式不同。根据具体问题和定义, 计算群体P (t) 中各个个体的适应度值。

2.4 选择

选择的目的是为了从当前群体中选出优良的个体, 使它们有机会作为父代为下一代繁殖子孙。根据各个个体的适应度值, 按照一定的规则或方法从上一代群体中选择出一些优良个体遗传到下一代群体中。遗传算法通过选择运算体现这一思想, 进行选择的原则是适应强的个体为下一代贡献一个或多个后代概率大。这样就体现了达尔文的适者生存原则。最常见的方法就是比例选择法:利用比例于各个个体适应度的概率决定其子孙遗留的可能性。若设种群数为M, 个体i的适应度为fi, 则个体i被选取的概率为:

遗传算法模拟了自然选择和遗传中发生的复制、交叉和变异等现象, 从任一初始种群 (Population) 出发, 通过随机选择、交叉和变异操作, 产生一群更适应环境的个体, 使群体进化到搜索空间中越来越好的区域, 这样一代一代地不断繁衍进化, 最后收敛到一群最适应环境的个体 (Individual) , 求得问题的最优解。基本遗传算法 (Simple Genetic Algorithm, 简称SGA) 的总流程如下。

当个体选择的概率给定后, 产生[0, 1]之间的均匀随机数来决定哪个个体参加交配。若个体的选择概率大, 则能被多次选中, 它的遗传基因就会在种群中扩大:若个体的选择概率小, 则可能被淘汰。除了适应度比例方法, 常见的还有最佳个体保存方法, 队列选择方法, 锦标赛选择方法, 确定性抽样选择方法, 剩余随机抽样选择方法, 随机整体抽样选择方法等。

2.5 交叉

交叉又称重组, 是按较大的概率cP从群体中选择两个个体, 交换两个个体的单个或多个基因。交叉运算产生子代, 子代继承父代的基本特征。交叉算子的设计包括如何确定交叉点位置和如何进行部分基因交换两个方面的内容。遗传算法中所谓的交叉运算, 是指两个相互配对的染色体按某种方式相互交换其部分基因, 从而形成两个新的个体。交叉运算是遗传算法区别于其他进化运算的重要特征, 它在遗传算法中起着关键作用, 是产生新个体的主要方法。在交叉运算之前还必须先对群体中的个体进行配对, 目前最常的配对策略是随机配对, 即将群体中的个个体以随机的方式组成对配对个体组, []表示不大于X的最大整数2。交叉点的位置则X是由交叉率决定的。常见的交叉方法有:单点交叉、两点P交c叉、均匀交叉、算术交叉等。图1是单点交叉的示意图。

2.6 变异

变异是以较小的概率Pm (变异概率) 对群体中染色体的某个或某些基因值进行改变, 如二进制编码中“0”变为“1”, “1”变为“0”, 从而可以生成新的个体。

变异运算本身也是一种随机算法, 但与选择和交叉算子结合后, 能够避免由于选择和交叉运算而造成的某些信息丢失, 保证遗传算法的有效性。交叉运算是产生新个体的主要方法, 它决定了遗传算法的全局搜索能力:而变异可以提供初始种群中不含有的基因, 或找回选择过程中丢失的基因, 为种群提供新的内容, 它决定了遗传算法的局部搜索能力。交叉算子与变异算子相互配合, 共同完成对搜索空间的全局搜索和局部搜索, 从而使得遗传算法能够以良好的搜索性能完成最优化问题的寻优过程。

2.7 终止条件准则

收敛判别对算法有着重大影响而且是一个不容易确定的问题。可以采用在线性能不发生变化即前后几代适应度值不发生变化, 也可以采用最大迭代次数作为收敛判据。若采用适应度值作为收敛判据, 对新一代的母体群, 重复 (3) ～ (6) 的操作, 直到满足:

式中:fi为第i代最佳母体的适应度, 对最后得到的母体群, 选取适应度最大的母体作为最优解。若采用迭代次数作为收敛判据, 取i为一定代数时停止运算。

3 结语

短期有功负荷分配是在满足系统总负荷的前提下, 在调度周期内充分、合理地利用有限的水资源在各电厂间分配有功负荷, 以减少火电厂的总运行费用。由于水电厂运行的灵活性和梯级水电厂间的补偿协调作用, 即上级水电厂的发电用水或弃水经一定延时将会影响下级各水电厂的发电和弃水, 而下级水电厂的水库调节能力又反过来影响上级水电厂的用水计划。因此, 水火电力系统的短期有功负荷分配是一个具有复杂约束条件的大型、动态、有时滞的非线性优化问题, 处理起来比较复杂。

解析算法 篇2

一、 困惑呈现：下一步路在何方

一线教师在课堂上出示两位数乘两位数28×12的算式后，直接依据教材中的提示，机械地教给学生进行竖式计算的方法，学生在教师的带领下轻松地完成了28×12竖式计算过程。此时教师自认为学生已经掌握了两位数乘两位数的笔算方法，继而顺势出示两道练习题62×41和13×72，让学生独立练习。练习结束后，教师带领学生进行集体交流时，学生的竖式书写过程令教师惊诧不已，优秀学生是“望而却步”，中、下等生是瞎写一通。仔细观察学生的竖式书写：

左题中“4×6”得“24”，学生不知道在竖式中如何书写、“24”写在哪儿。同样，右题中“7×3”得“21”，学生也不清楚在竖式中的正确书写位置，不知道是直接写下“21”，还是写“1”进“2”。学生在计算这两道竖式时，其错误及困惑聚焦为：十位上的数乘下来，得数何时可以直接写下来，何时需要向前一位进位？此时学生在笔算认知上已无法确定下一步路在何方。

二、 学情解析：忽视了学生的认知现实

两位数乘两位数对于学生来说，是计算学习过程中的一次新“跨越”。然而，由于教师在教学实践中忽视了学生的计算现实，竖式计算书写过程中两次乘积的计算步骤和方法以及书写格式未能成为学生有效探索笔算方法过程中所应理解的“数学概念”。这说明两位数乘两位数竖式书写格式及其计算方法的建构未能源于学生的思维特点和认知水平，如此知识结构的形成不是基于学生认知现实而得以自然建构与生长，因而学生无法吸收与理解。

为什么当学生直接计算62×2和13×7时，学生能正确计算和规范书写，而学到两位数乘两位数时，反而把两位数乘一位数的已有知识与计算技能遗忘了，是什么因素干扰了学生的思维？为什么已有知识经验不能促进新知识的形成与建立，反而阻碍了新知的生成与建构？

笔者以为，教师在教学实践中忽视了学生的已有学习经验与认知现实，未能引领学生经历新知识的形成过程，未能从学生的认知现实出发，去体验新知识的“来龙去脉”，去触摸新知识形成的“源头”，而是“照搬”教材，机械地把教材中的方法“灌输”给学生。教材中直接呈现方法提示 ■，接下去怎样算呢？这一过程直接呈现在学生面前，学生一定感到很突然、很迷茫，不知道“56”是哪儿来的，或无法理解为什么可以这样得出“56”。如此告知，未能遵循儿童的认知经验和思维现实。沿着儿童的思维不难体会，只要将两位数乘两位数竖式■呈现在学生面前，无论是儿童的思维直觉，还是对竖式运算的直观感觉，学生尝试练习■一定会认为个位上8与2相乘，十位上2与1相乘，因为学生已经积累了个位上数相加、减和十位上数相加、减的两位数加减法运算经验。所以，教材中第一步呈现“56”，学生一下子无法理解“56”是怎么算出来的、为什么这么算，脱离了儿童的认知现实，断裂了数学知识的前后联系，忽视了知识的起源与发展。

回顾学生对两位数乘法笔算的已有知识经验理应是两位数乘一位数的笔算方法，应该引领学生从两位数乘一位数乘法笔算的经验与方法逐步向两位数乘两位数乘法笔算进行迁移与转化，让学生在两位数乘一位数的基础上逐步建构起两位数乘两位数的乘法笔算的计算方法与书写格式。在日常教学实践中，教师如果未能从儿童的认知现实出发，而是机械地教教材，直接以告知的口吻告诉学先用2乘8，再用2乘2，然后用1乘8，再用1乘2，那么，中等偏下的学生就无法记住这样的计算方法和运算顺序，需要经过几节课的强化训练，学生才可能记住。

而教材中是从口算的角度引导学生向笔算进行迁移。28×10=280，28×2=56，280+56=336。如此呈现不仅忽视了学生的认知现实，也脱离了知识间的应然联系。因为这样的口算方法本身并不符合儿童的认知现实和情感现实，在平时的教学中也未发现有如此口算方法的学生。首先，这一口算过程所支撑的计算算理涉及乘法分配律，此阶段的学生思维还未触及此规律，而且此运算律是小学阶段学生最难以掌握与理解的运算规律，三年级学生的运算思维还未能达到如此抽象的思维水平。其次，从学生的情感上分析，学生总是希望在解决问题的过程中能找到简单、直观、明了的计算方法，但三步计算中同时伴随着乘法进位与加法进位，这是计算过程中的复杂因素，也是学生在计算过程中容易出错的因子。再次，口算与笔算的算理与算法所凸显出来的运算思维不在同一思维水平上，因为笔算知识是在口算知识不能适应人在社会中的生存发展需要而自然产生的。即当人们在生活应用中不能直接通过口算得出结果时，新的一种计算方法——笔算即竖式计算便应运而生。因此，从口算算理向笔算方法进行迁移不符合新知识的形成结构和学生的认知特点，它对笔算计算方法不能自然形成有效的迁移与建构作用。因此，两位数乘两位数的笔算需要从两位数乘一位数的笔算方法进行转化，应该由“笔算引出新的笔算”，而不是由口算引出笔算。

三、 算法建构：由笔算走向新的笔算

想要让学生能自然地掌握并理解两位数乘两位数竖式计算的方法及算理，教师须要从知识的“生长性”出发，以“儿童的方式”设计教学，引领学生这种经历知识“生长”的过程，遵循儿童的认知现实，顺应儿童的思维方式。所以，教学时需要教师设计出如下“儿童化”的实践探索，促使学生以儿童的认知方式吸纳新知，内化新知。

1.出示■并设问：这是几位数乘几位数？

2.两位数乘两位数可以拆成几个两位数乘一位数的算式？

3.■你会拆成哪两个两位数乘一位数竖式计算的算式？

4.由于学生已经积累了两位数乘一位数的经验，而且学生已经形成了当两位数乘一位数时，写竖式总是把两位数写在上面，一位数写在下面的计算技能，所以课堂上学生会很快把拆成这两个竖式（观察发现学生拆时有意把十位上的1还写在十位上）。

5.学生分别算出这两道两位数乘一位数的结果：。这是学生已学的知识，所以无论是计算还是书写，学生都能轻松完成。

6.引导学生思考：现在拆成进行计算，怎样把它们的计算过程合并在的竖式计算的过程中呢？

7.学生尝试竖式合并，大部分学生合并成这种形式。学生这种错误是符合学生计算现实的，这是学生在学习过程中真实的一面。

8.教师化学生的错误资源为有效教学资源：（1）“56“是怎么得到的？（2）“28”是怎么得到的？这里的“1”表示什么？所以28乘1个十实际上得到28个什么？（3）因此，“28”书写时，应如何对齐数位？这样设计教学，不仅让学生经历了两位数乘两位数竖式计算方法的形成过程，也有效突破了学生的认知难点，不会出现前面的两种困惑现象。

综上所述，无论是教学内容的选择，还是学习方法的运用，都必须贴近儿童实际、尊重儿童学习现实，这样才能有效促进儿童体验与探索、思考与理解，数学课堂才会由被动走向主动，由低效走向高效。

常用C语言排序算法解析 篇3

在数据处理中, 数据排序是相当重要的, 它可以使数据更有条理, 方便数据的处理。排序是程序设计的常见问题, 解决排序问题也有多种算法, 常用的算法有顺序比较排序法、选择排序法、冒泡排序法、直接插入排序法、快速排序和希尔排序法等排序算法。在学习C语言程序设计过程中排序算法也是重点研究问题之一, 本文主要用C语言来描述几种常见的排序算法, 以及分析实现算法的基本思路、模拟相应算法实现排序的过程及算法性能分析。文中所涉及的排序均为升序排序。

1 顺序比较排序法

1.1 算法思想

假设数组有n个元素, 从第一个元素开始为第一趟, 第一个元素和第二个元素开始到第n个元素按顺序作比较, 如果第一个元素大于某个元素则第一个元素和该元素进行交换, 第一个元素和其后的n-1个元素一一进行两两比较结束后将是所有元素中的最小值。接下来第二趟从第二个元素开始逐一和其后的n-2个元素两两比较, 在进行n-2次比较后第二个元素将是剩下n-1个元素中的最小值。依次类推一直到第n-1趟最后两个元素进行比较并得到第n-1个元素是剩下的两个元素中的较小值。

1.2 模拟排序执行过程

假设一个整型数组有5个元素, 分别为23、12、5、16、10, 排序执行过程如下所示:

第一趟: 23 12 5 16 10 (第一趟比较前元素)

第一次: 12 23 5 16 10 (由于23>12 两元素交换)

第二次: 5 23 12 16 10 (由于12>5 两元素交换)

第三次: 5 23 12 16 10 (由于5<16 两元素不交换)

第四次: 5 23 12 16 10 (由于5<10 两元素不交换)

第二趟: 5 23 12 16 10 (第二趟比较前元素)

第一次: 5 12 23 16 10 (由于23>12 两元素交换)

第二次: 5 12 23 16 10 (由于12<16 两元素不交换)

第三次: 5 10 23 16 12 (由于12>10 两元素交换)

第三趟: 5 10 23 16 12 (第三趟比较前元素)

第一次: 5 10 16 23 12 (由于23>16 两元素交换)

第二次: 5 10 12 23 16 (由于16>12 两元素交换)

第四趟: 5 10 12 23 16 (第四趟比较前元素)

第一次: 5 10 12 16 23 (由于23>16 两元素交换)

1.3 实现顺序比较排序法核心代码

1.4 算法性能分析

有n个元素参加排序要进行n-1趟比较, 第i趟要进行n-i次两两比较。时间复杂度为O (n2) 。顺序比较排序算法稳定, 比较次数已知, 但是该算法速度慢。

2 冒泡排序法

2.1 算法思想

假设数组有n个元素, 第一趟从第一个元素开始依次比较两个相邻元素的值, 如果前一个元素的值大于后一个元素的值则两个相邻元素进行交换, 第一趟比较n-1次, 经过一趟排序n个元素中的最大值存放到最后一个数组元素中。第二趟从第一个元素开始到第n-1个元素相邻两个元素作比较, 如果前一个数大于后一个数则两个相邻的元素进行交换, 经过n-2次比较, 这一趟中最大值放在第n-1个数组元素的位置。依次类推一直到第n-1趟第一个元素和第二个元素两个元素进行比较, 两个元素中的较大值放在第二个数组元素的位置, 较小值放在第一个数组元素的位置。

2.2 模拟排序执行过程

假设一个整型数组有5个元素, 分别为23、12、5、16、10, 用变量k保存最小值的下标, 排序执行过程如下所示:

第一趟: 23 12 5 16 10 (第一趟比较前元素)

第一次: 12 23 5 16 10 (由于23>12 两元素交换位置)

第二次: 12 5 23 16 10 (由于23>5 两元素交换位置)

第三次: 12 5 16 23 10 (由于23>16 两元素交换位置)

第四次: 12 5 16 10 23 (由于23>10 两元素交换位置)

第二趟: 12 5 16 10 23 (第二趟比较前元素)

第一次: 5 12 16 10 23 (由于12>5 两元素交换位置)

第二次: 5 12 16 10 23 (由于12<16 两元素不交换位置)

第三次: 5 12 10 16 23 (由于16>10 两元素交换位置)

第三趟: 5 12 10 16 23 (第三趟比较前元素)

第一次: 5 12 10 16 23 (由于5<12 两元素不交换位置)

第二次: 5 10 12 16 23 (由于12>10 两元素交换位置)

第四趟: 5 10 12 16 23 (第四趟比较前元素)

第一次: 5 10 12 16 23 (由于5<10 两元素不交换位置)

2.3 实现冒泡排序法核心代码

2.4 算法性能分析

有n个元素参加排序要进行n-1趟比较, 第i趟要进行n-i次两两比较。时间复杂度为O (n2) 。冒泡排序算法稳定, 比较次数已知, 但是该算法速度慢, 每次只能比较和移动相邻两个数据元素, 移动数据元素的次数多。

3 改进的冒泡排序法

3.1 算法思想

冒泡排序法存在的不足之处是在排序过程中, 虽然数据序列已经按要求排序完成, 但程序无法判断是否完成排序, 程序仍然要进行下一趟的排序, 这样势必浪费了程序执行的时间, 降低了程序的执行效率。为了解决这一不足, 在程序中可以设置一个标志变量flag, 每一趟排序开始前设置flag值为1, 表示待排序的数据序列是无序的。如果在程序的执行过程中发生数据交换操作, 则修改flag值为0。当前趟排序结束后检查flag标志, 若flag的值为1, 表示在当前趟排序过程中没有进行过交换数据, 则结束排序过程, 否则继续进行下一趟排序。

3.2 实现改进冒泡排序法核心代码

3.3 算法性能分析

若数据序列的初始状态为“正序”, 则冒泡排序过程只需进行一趟排序, 在排序过程中只需进行n-1次比较, 且不移动数据元素。若数据序列的初始状态为“逆序”, 则需进行n (n-1) /2次比较和数据元素交换, 而完成两个数据元素交换需移动操作3次, 故移动次数达到最大3n (n-1) /2。改进的冒泡排序算法的时间复杂度为O (n2) , 改进的冒泡排序算法是稳定的排序算法。

4 选择排序法

4.1 算法思想

假设数组有n个元素, 第一趟从第一个元素开始, 第一个元素和第二个元素开始到第n个元素按顺序作比较, 按排序要求找到最小元素的位置, 然后用该位置和第一个元素的下标进行比较, 如果不相等则两元素进行交换, 这样第一个元素将是n个元素中的最小值。接下来第二趟从第二个元素开始逐一和其后的n-2个元素两两比较, 在进行n-2次比较后找到剩下n-1个元素中的最小值的位置, 然后用该位置和第一个元素的下标进行比较, 如果不相等则两元素进行交换, 第二个元素将是后n-1个元素中的最小值。依次类推一直到第n-1趟最后两个元素进行比较并得到两个元素中的较小值的位置。

4.2 模拟排序执行过程

假设一个整型数组有5个元素, 分别为23、12、5、16、10, 用变量k保存最小值的下标, 排序执行过程如下所示:

第一趟: 23 12 5 16 10 (第一趟比较前元素)

第一次: k=1 (由于23>12)

第二次: k=2 (由于 12>5)

第三次: k=2 (由于 5<16)

第四次: k=2 (由于 5<10)

第一趟比较后, 由于0!=2, 则a[0]与a[2]交换。

第二趟: 5 12 23 16 10 (第二趟比较前元素)

第一次: k=1 (由于 12<23)

第二次: k=1 (由于 12<16)

第三次: k=4 (由于 12>10)

第二趟比较后, 由于1!=4, 则a[1]与a[4]交换。

第三趟: 5 10 23 16 12

第一次: k=3 (由于 23>16)

第二次: k=4 (由于 16>12)

第三趟比较后, 由于2!=4, 则a[2]与a[4]交换。

第四趟: 5 10 12 16 23

第一次: k=4 (由于 16>23)

第四趟比较后, 由于3!=4, 则a[3]与a[4]交换。

5 10 12 16 23

4.3 实现选择排序法核心代码

4.4 算法性能分析

有n个元素参加排序要进行n-1趟比较, 第i趟要进行n-i次两两比较, 每趟最多进行一次数据交换, 其余元素的相对位置不变。时间复杂度为O (n2) 。选择排序算法稳定, 比较次数与冒泡排序一样, 数据移动次数比冒泡排序少, 算法速度还是慢。

5 直接插入排序法

5.1 算法思想

将序列分为有序序列和无序序列, 依次从无序序列中取出元素值插入到有序序列的合适位置。初始是有序序列中只有第一个数, 其余n-1个数组成无序序列, 则n个数需进行n-1次插入。初始是有序序列中只有第一个数, 其余n-1个数组成无序序列, 则n个数需进进n-1次插入。寻找在有序序列中插入位置可以从有序序列的最后一个数往前找, 在未找到插入点之前可以同时向后移动元素, 为插入元素准备空间。

假设数组有n个元素, 第一趟首先对前两个元素进行比较, 按排序要求排列好, 第二趟将第3个元素与前两个已排好序的元素做比较, 按排序要求找到其相应的位置, 将第3个元素插入到该位置上。以此类推, 直到所有的元素排好序为止。

5.2 模拟排序执行过程

待排序列: 23 12 5 16 10

第一趟: 12 23 5 16 10 (23插入12之后, 23后移)

第二趟: 5 12 23 16 10 (5插入12之前, 12、23依次后移)

第三趟: 5 12 16 23 10 (16插入23之前, 23后移)

第四趟:5 10 12 16 23 (10插入12之前, 12、16、23依次后移)

5.3实现直接插入排序法核心代码

5.4算法性能分析

有n个元素参加排序要进行n-1趟比较。时间复杂度为O (n2) 。直接插入排序算法稳定, 执行速度快, 但是该算法的数据比较次数不确定, 比较次数越多, 插入点后的数据移动次数越多, 特别是当数据总量庞大的时候。

6结语

通过对顺序比较法、选择排序法、冒泡排序法、改进的冒泡排序法和直接插入排序法的介绍, 并从排序算法的思想、模拟排序执行过程、实现排序的算法代码及算法性能分析四个方面进行了详细的解析。本文可以帮助C语言初学者轻松理解几种常用的排序算法。

摘要：排序是计算机科学中最重要的研究问题之一, 也是学习C语言程序设计过程中重点研究问题之一。主要介绍了顺序比较法、选择排序法、冒泡排序法、改进的冒泡排序法和直接插入排序法, 并从排序算法的思想、模拟排序执行过程、实现排序的算法代码及算法性能分析4个方面进行了详细的解析, 可以帮助C语言初学者轻松理解几种常用的排序算法。

关键词：C语言,排序,算法思想,数组

参考文献

[1]谭浩强.C语言程序设计[M].第3版.北京:清华大学出版社, 2005.

[2]范兴福.C程序设计[M].北京:机械工业出版社, 2008.

数据结构教学中KMP算法解析 篇4

模式匹配 (Patten Matching) 是许多计算机应用领域的基础问题, 在数据结构中模式匹配是字符串的基本运算之一。字符串模式匹配指的是, 找出特定的模式串在一个较长的字符串中出现的位置。有两个字符串S和T, 字符串S称为目标串, 字符串T称为模式串, 要求找出模式T在S中的首次出现的位置。一旦模式T在目标S中找到, 就称发生一次匹配。有些应用可能会要求找出所有的匹配位置[1]。例如, 目标串S='Shanghai', 模式串T='gha', 则匹配结果为4。

模式匹配的典型算法包括朴素匹配算法、KMP算法和BM算法等, 其中KMP算法是效率较高且经典的模式匹配算法之一[2]。在数据结构教学中, 由于KMP算法较难理解, 课堂讲授往往很难取得好的效果。本文通过对传统的朴素匹配算法与KMP算法的比较, 分析next函数的含义以及实现方法, 来帮助理解KMP算法。

1 朴素匹配算法

朴素匹配算法如下:

在朴素匹配算法中, S和T分别为目标串和模式串, 变量i和j为两个静态指针, 分别表示S和T中当前正待比较的字符位置。算法的基本思想是:第1趟匹配:从S的第1个字符 (序号为0) 起和T的第一个字符比较之, 如果相等, 则继续逐个比较后续字符 (i++;j++) , 否则开始下一趟匹配。新的一趟匹配:i的初值为上一趟的初值+1, j的初值为1, 如果比较结果相等, 则继续逐个比较后续字符, 否则开始下一趟匹配。依次类推, 直至某一趟匹配中, T的每个字符依次和S中的一个连续的字符序列相等, 则称匹配成功, 否则称匹配不成功。当匹配成功时, 朴素匹配算法的函数返回值为最后一趟匹配的i的初值 (即S中与T相等的连续的字符序列的起始位置) , 匹配不成功时, 函数的返回值为-1。

在目标串'ababcabcacb'中匹配模式串'abcac'的过程如下, 其中i和j分别为指向目标串和模式串的指针, “=”后面表示i和j的依次取值。

从以上的例子可以看出:每当出现“失配”时, 开始新一趟的匹配, 目标串指针i的初值为上一趟i的初值加1;模式串指针j的初值返回1。在朴素匹配算法中, 指针i和j有大量重复的比较, 也就是回溯。

朴素匹配算法过程易于理解, 在很多应用场合效率也较高。此时, 算法的时间复杂度为O (n+m) 。其中n和m分别为目标串和模式的长度。然而, 当目标串中存在多个和模式串中“部分匹配”的子串时, 会引起指针i的多次回溯。因此, 在最坏情况下的时间复杂度为O (n*m) 。

2 KMP算法

2.1 算法简介

KMP算法由D.E.Knuth、V.R.Pratt和J.H.Morris同时提出。此算法可以在O (n+m) 的时间数量级上完成模式匹配操作。其改进在于:当目标串S[i]与模式串T[j]失配时, i不回溯, 而是利用已经得到的“部分匹配”的结果将j回溯到一个尽量“偏右”的位置k。在KMP算法中, 为了确定在匹配不成功时, 下次匹配时j的位置, 引入了next[]数组, next[j]的值表示T[0…j-1]中最长后缀的长度等于相同字符序列的前缀。因此KMP算法的核心问题是寻找确定k=next[j]的方法。

回顾第1节中在目标串'ababcabcacb'中匹配模式串'abcac'的过程, 当第3趟匹配结束后, i=7, j=5。这时并不需要从i=4, j=1重新开始比较, 因为从第3趟部分匹配的结果就可得出, 目标串的第4、5、6个字符必然是'b'、'c'和'a'。因为模式中的第1个字符是'a', 因此当开始新的一趟匹配时, 'a'不需要和这3个字符比较。可将T中的第2个字符与S中的第7个字符对齐 (即将T向右滑动3个字符的位置) , 继续进行字符的比较。

采用KMP算法在目标串'ababcabcacb'中匹配模式串'abcac'的过程如下:

KMP算法如下:

因此KMP算法的思想就是:在匹配过程中, 若发生不匹配的情况, 如果next[j]≥0, 则目标串的指针i不变, 将模式串的指针j移动到next[j]的位置继续进行匹配;如果next[j]=-1, 则将i右移1位, 并将j置0, 继续进行比较。

2.2 next函数的意义

next函数值的含义为:当目标串中失配点的前1个字符和模式串的第1个字符相等时, 就可以利用上次匹配的结果, 使得目标串的指针不回溯 (下一趟匹配时i的初值为上一趟的结束值) , 而模式串中少回溯1个字符 (下一趟匹配时j的初值为2) ;依此类推, 当目标串中失配点的前k个字符和模式串的前k个字符相等时, 就可以利用上次匹配的结果, 使得目标串的指针不回溯, 而模式串中少回溯k个字符 (下一趟匹配时j的初值为k+1) 。所以求next函数值就是:寻找在目标串中失配点前的k个字符和模式串前k个字符相等, 而这个k值应尽可能大, 这时next[j]=k。

例如, 设S='acabaabaabca', T='abaabc', i=7, j=5, 根据以上的讨论, 可看出k=2, 如图1所示。

推广至一般情况, 可得出结论:k为满足关系式1的最大值:

而已经得到的“部分匹配结果”是:

由上述两个等式可得到下面的结论:

由此得出next[]数组的定义如下:

以上定义也说明next[j]与目标串S无关。例如, 设T='abaabcac', 则它的各个next函数值如表1所示:

即next[j]=k>0时, 表示T[0…k-1]=T[j-k, j-1]。

2.3 next函数的求值方法

(1) 递推法。通常采用递推的方法来求next函数值。由定义知:next[0]=-1。设next[j]=k, 即:T[0…k-1]=T[j-k…j-1], 分两种情况求next[j+1]的值。

(1) 若T[j]=T[k], 则有T[0…k]=T[j-k…j], 很显然, next[j+1]=k+1=next[j]+1; (2) 若T[j]≠T[k], 则可以把其看做模式匹配的问题, 即匹配失败时, k值如何移动。由于T[j]≠T[k], 则next[j+1]

例如, 参见表1, 对模式串T='abaabcac', 已求得next[0]…next[5], 现求next[6]。因为next[5]=2, 又T[5]≠T[2], 则需比较T[5]和T[0] (因为next[2]=0) , 这相当于将模式串向右移动。由于T[5]≠T[0], 而且next[0]=-1, 所以next[6]=0, 而因为T[6]=T[0], 则next[7]=1。

求next函数值的算法如下:

(2) 直接求解法。递推法较难理解, 也可以采用直接求解的办法来实现求next函数的值。

3 结语

模式匹配是字符串的基本运算之一, 也是数据结构教学中的难点之一, 其中next数组的计算方法是KMP算法的难点和核心, 理解next函数值的含义可以更好地理解KMP算法。

目前数据结构教材中普遍采用递推的方式来计算next数组值, 可通过动画等形式形象地对该方法进行讲解。对于较容易理解的直接求解法, 可在上机实验中要求学生自己完成。

摘要：模式匹配是字符串的基本运算之一, 也是数据结构教学中的难点之一。分析了模式匹配KMP算法以及算法中next函数的含义, 给出了next函数的两种实现方法, 有助于在教学实践中帮助学生更好地理解该算法。

关键词：数据结构,模式匹配,KMP算法

参考文献

[1]严蔚敏, 吴伟民.数据结构:C语言版[M].北京:清华大学出版社, 2003.

输液泵工作数据准确性中算法解析 篇5

输液泵是预期通过泵产生的正压来控制流入患者体内的液体流量的设备。作为向患者体内持续或间断注入液体药物的医疗设备,输液泵工作数据的准确性既是性能指标的要求,又是安全项目的要求,所以是我们检测中的重点。GB9706.27-2005《医用电气设备第2-24部分 :输液泵和输液控制器安全专用要求》中第50章专门对工作数据的准确性的检测方法和数据处理进行了详细的规定。在实际检测中该检测项目数据量大,公式繁多,算法复杂,其中的难点就是Ep(max)和EP(min)的得出。通过我实际的工作经验,对Ep(max)和EP(min)的算法原理进行一些解析,并用Excel表举例说明。

1 几个相关的基本概念

1.1 取样间隔 S

连续的质量读数或液滴计数之间的时间。

1.2 观测窗期间 P

用于观测规定期间数据情况的一个窗口(时间段)。

1.3Ep(max)

规定期间内在观测窗中测得的最大测量误差。

1.4EP(min)

规定期间内在观测窗中测得的最小测量误差。

2 计算 Ep(max)和 EP( min)算法原理

在一分析周期T中的P期间的观测窗中计算最大Ep(max)和最小EP(min)百分比变化的算法可分为4个组成阶段。

2.1 第一阶段

计算分析周期T中的P期间观测窗的最大数量。有一个最大数量为m的观测窗。首先考虑期间S(min)的最小观测窗,一直考虑大期间T(min) 的最大观测窗。

对于最小观测窗P=Sm=T/S

对于第二个最小的观测窗P=2S

对于第K个最小的观测窗P=KS

对于最大观测窗P=T m =1

因此,对于P期间的任意观测窗,其中P是一个S的若干倍,根据下列方程式得出一个最大为m的观测窗个数

2.2 第二阶段

计算分析周期T上每一个连续取样的流量误差Ei 。由于Ep(max)和EP(min)以百分比表示,Qi 也以速度r的百分比误差表示。图(1)中显示对于W0 到Wn 的取样量,有从Q1到Qn 的流量,并且有随之的e1到en的流量误差。注意Wi 是分析周期T的第i次取样量,而不是试验周期的第i次取样量,由下列公式得出任一ei :

2.3 第三阶段

计算P期间任一观测窗上的平均流量误差,通过每一观测窗上的单一流量误差相加求和并且此结果被总数除而得到一个平均值。

对于从式(1)确定的所有m个观测窗重复此计算。式(3)计算出P期间的所有观测窗的平均流量误差Ep 。

第一个观测窗 :

第二个观测窗 :

第m个观测窗:

因此,对任一窗j从第1至最大为m的窗

最后的计算阶段确定了P期间的观测窗中最大Ep(max)和EP(min)百分比变化。这些参数是简单地从公式AA.3.3计算出的Ep(j)中取出极值,因此 :

对于最大值

类似地,对于最小值

四个计算阶段可以各自合并成一个单独的 (max)EP和 ( min)EP公式。

为了确定P期间的每 一个观测 窗中的最大Ep(max)和EP(min)百分比变化,对于每一 个新的P=1min、2min、5min、11min、19min和31min的值,应该重新用公式计算。

3 举例

上述的算法原理,可通过下述具体实例加深理解。实际测试中,选取分析周期T为试验周期的第2h。设定取样间隔S为0.5min。设定流速r为25ml/h, Qi可通过输液泵质量监测仪直接测得,单位为ml/h,共测到A列中的120个数据。B列数据用求出。C列为P=1min时每个观测窗上的平均流量误差,单元格C1的公式为,C2 为, ………,C119 为;D列为P=2min时每个观测窗上的平均流量误差,单元格D1的公式为,………,D117为;其余E列、F列、G列、H列分别为P=5min、11min、19min、31min时每个观 测窗上的平均流量误差,其对应的公式为式(3)P。最后再从C列至H列中分别选取每个P期间观测窗的极值,即为我们所求Ep(max)的EP(min)和。

4 结束语

输液泵的工作数据准确性试验既是GB9706.27中的重点,也是检测中的难点。只有在准确理解算法的基础上,并对数据进行正确处理,才能得到准确的测试结果。以上是笔者对算法和数据处理的一点浅见,希望能抛砖引玉,看到更方便有效的方法出现。

摘要：文章阐述了输液泵工作数据准确性试验中计算(max)pE和(min)PE算法原理,并举例说明数据处理过程。

解析算法 篇6

一、困惑呈现:下一步路在何方

一线教师在课堂上出示两位数乘两位数28×12的算式后,直接依据教材中的提示,机械地教给学生进行竖式计算的方法,学生在教师的带领下轻松地完成了28×12竖式计算过程。此时教师自认为学生已经掌握了两位数乘两位数的笔算方法,继而顺势出示两道练习题62×41和13×72,让学生独立练习。练习结束后,教师带领学生进行集体交流时,学生的竖式书写过程令教师惊诧不已,优秀学生是“望而却步”,中、下等生是瞎写一通。仔细观察学生的竖式书写:

左题中“4×6”得“24”,学生不知道在竖式中如何书写、“24”写在哪儿。同样,右题中“7×3”得“21”, 学生也不清楚在竖式中的正确书写位置,不知道是直接写下“21”,还是写“1”进“2”。学生在计算这两道竖式时,其错误及困惑聚焦为:十位上的数乘下来, 得数何时可以直接写下来,何时需要向前一位进位? 此时学生在笔算认知上已无法确定下一步路在何方。

二、学情解析:忽视了学生的认知现实

两位数乘两位数对于学生来说,是计算学习过程中的一次新“跨越”。然而,由于教师在教学实践中忽视了学生的计算现实,竖式计算书写过程中两次乘积的计算步骤和方法以及书写格式未能成为学生有效探索笔算方法过程中所应理解的“数学概念”。 这说明两位数乘两位数竖式书写格式及其计算方法的建构未能源于学生的思维特点和认知水平,如此知识结构的形成不是基于学生认知现实而得以自然建构与生长,因而学生无法吸收与理解。

为什么当学生直接计算62×2和13×7时,学生能正确计算和规范书写,而学到两位数乘两位数时,反而把两位数乘一位数的已有知识与计算技能遗忘了,是什么因素干扰了学生的思维?为什么已有知识经验不能促进新知识的形成与建立,反而阻碍了新知的生成与建构?

笔者以为,教师在教学实践中忽视了学生的已有学习经验与认知现实,未能引领学生经历新知识的形成过程,未能从学生的认知现实出发,去体验新知识的“来龙去脉”,去触摸新知识形成的“源头”,而是“照搬”教材,机械地把教材中的方法“灌输”给学生。教材中直接呈现方法提示接下去怎样算呢?这一过程直接呈现在学生面前,学生一定感到很突然、很迷茫,不知道“56”是哪儿来的,或无法理解为什么可以这样得出“56”。如此告知,未能遵循儿童的认知经验和思维现实。沿着儿童的思维不难体会,只要将两位数乘两位数竖式呈现在学生面前,无论是儿童的思维直觉,还是对竖式运算的直观感觉,学生尝试练习一定会认为个位上8与2相乘,十位上2与1相乘,因为学生已经积累了个位上数相加、减和十位上数相加、减的两位数加减法运算经验。所以,教材中第一步呈现“56”,学生一下子无法理解“56”是怎么算出来的、为什么这么算,脱离了儿童的认知现实,断裂了数学知识的前后联系,忽视了知识的起源与发展。

回顾学生对两位数乘法笔算的已有知识经验理应是两位数乘一位数的笔算方法,应该引领学生从两位数乘一位数乘法笔算的经验与方法逐步向两位数乘两位数乘法笔算进行迁移与转化,让学生在两位数乘一位数的基础上逐步建构起两位数乘两位数的乘法笔算的计算方法与书写格式。在日常教学实践中,教师如果未能从儿童的认知现实出发,而是机械地教教材,直接以告知的口吻告诉学生先用2乘8,再用2乘2,然后用1乘8,再用1乘2,那么,中等偏下的学生就无法记住这样的计算方法和运算顺序,需要经过几节课的强化训练,学生才可能记住。

而教材中是从口算的角度引导学生向笔算进行迁移。28×10=280,28×2=56,280+56=336。如此呈现不仅忽视了学生的认知现实,也脱离了知识间的应然联系。因为这样的口算方法本身并不符合儿童的认知现实和情感现实,在平时的教学中也未发现有如此口算方法的学生。首先,这一口算过程所支撑的计算算理涉及乘法分配律,此阶段的学生思维还未触及此规律,而且此运算律是小学阶段学生最难以掌握与理解的运算规律,三年级学生的运算思维还未能达到如此抽象的思维水平。其次,从学生的情感上分析,学生总是希望在解决问题的过程中能找到简单、直观、明了的计算方法,但三步计算中同时伴随着乘法进位与加法进位,这是计算过程中的复杂因素,也是学生在计算过程中容易出错的因子。再次,口算与笔算的算理与算法所凸显出来的运算思维不在同一思维水平上,因为笔算知识是在口算知识不能适应人在社会中的生存发展需要而自然产生的。即当人们在生活应用中不能直接通过口算得出结果时,新的一种计算方法———笔算即竖式计算便应运而生。因此,从口算算理向笔算方法进行迁移不符合新知识的形成结构和学生的认知特点,它对笔算计算方法不能自然形成有效的迁移与建构作用。 因此,两位数乘两位数的笔算需要从两位数乘一位数的笔算方法进行转化,应该由“笔算引出新的笔算”,而不是由口算引出笔算。

三、算法建构:由笔算走向新的笔算

想要让学生能自然地掌握并理解两位数乘两位数竖式计算的方法及算理,教师须要从知识的“生长性”出发,以“儿童的方式”设计教学,引领学生这种经历知识“生长”的过程,遵循儿童的认知现实,顺应儿童的思维方式。所以,教学时需要教师设计出如下 “儿童化”的实践探索,促使学生以儿童的认知方式吸纳新知,内化新知。

1.出示并设问:这是几位数乘几位数?

2.两位数乘两位数可以拆成几个两位数乘一位数的算式?

3.你会拆成哪两个两位数乘一位数竖式计算的算式?

4.由于学生已经积累了两位数乘一位数的经验, 而且学生已经形成了当两位数乘一位数时,写竖式总是把两位数写在上面,一位数写在下面的计算技能,所以课堂上学生会很快把拆成这两个竖式(观察发现学生拆时有意把十位上的1还写在十位上)。

5.学生分别算出这两道两位数乘一位数的结果:这是学生已学的知识,所以无论是计算还是书写,学生都能轻松完成。

6.引导学生 思考 :现在拆成进行计算,怎样把它们的计算过程合并在的竖式计算的过程中呢?

7.学生尝试竖式合并,大部分学生合并成这种形式。学生这种错误是符合学生计算现实的,这是学生在学习过程中真实的一面。

8.教师化学 生的错误 资源为有 效教学资 源:(1)“56“是怎么得到的?(2)“28”是怎么得到的?这里的“1”表示什么?所以28乘1个十实际上得到28个什么?(3)因此,“28”书写时,应如何对齐数位?这样设计教学,不仅让学生经历了两位数乘两位数竖式计算方法的形成过程,也有效突破了学生的认知难点,不会出现前面的两种困惑现象。