电平转换器基础知识

参考内容: 迷失在电平转换中 为什么芯片都是 CMOS 的呢?CMOS 和 TTL 有什么区别? 高阻态,三态门 TI 162245 用户手册 为什么需要电平转换 在电路设计中,常常会遇到一个系统中存在不同的电平信号,比如 0.9V、1.8V、3.3V、5V 等,要使系统不同模块协同工作,就需要对电平信号进行转换。 其实需要进行电平转换的本质原因是因为半导体加工工艺的不同。比如 TTL 电平 2.0V 以上表示高,0.8V 以下表示低。但是 CMOS 电平由于其物理原因,常常是将高定义为 3.5V 以上,低定义为 1.5V 以下。所以伴随着每一个新的半导体发展阶段,高和低都被改了一下,直到形成了下图这个样子。 一个 5V TTL 输出跟一个 5V TTL 输入可以没有障碍的交流,但是当一个 3V CMOS 和一个 5V CMOS 进行交流时就存在问题了。当 3V CMOS 输出高时,意味着它应用一个 2.5V 的信号在其输出引脚上,如果此时将这个输出与一个 5V CMOS 输入端进行连接,5V CMOS 只能识别超过 3.5V 的高信号和低于 1.5V 的低信号,那么 2.5V 的输入对于 5V CMOS 来说是高还是低呢? 常见电平转换电路 使用电阻分压 最直接也是最简单的办法就是使用电阻来分压来转换电平,后续芯片可以等效为一个负载电阻,通过串联一个电阻与芯片内部电阻构成分压关系。这种电路的优势是电阻器件采购方便、价格低廉,电路也很简单。但是缺点也很明显,因为两芯片引脚之间存在电压差且中间只有串联电阻,所以会有电流的流动造成两芯片相互影响。 二极管电平转换 二极管电平转换电路如下图所示。该电路由二极管和电阻组成,电路使用元件比较少,其中二极管最好用肖特基二极管,因为肖特基二极管具有开关频率高和正向压降低的优点。 当 5V TXD1 发送高电平时,二极管正极电压比负极电压低,二极管截止,RXD2 被上拉电阻拉为高电平; 当 5V TXD1 发送低电平时,二极管导通,RXD2 被钳位至二极管管压降(0.7V),所以收到低电平; 当 3.3V TXD2 发送低电平时,二极管导通,RXD1 被钳位至二极管管压降(0.7V),所以收到低电平; 当 3.3V TXD2 发送高电平时,二极管也是导通的,RXD1 电压为 3.3V 加上一个管压降,即 4.0V,所以收到高电平。 当 3.3V 端发送高电平给 5V 端时,5V 端收到的并不是 5V,同时该电路只适合单向通讯的场景,发送端和接收端不可以互换。 三极管电平转换 三极管电平转换电路其实就是模电中的共射极放大电路,也就是 TTL 的前身,原来的 RTL(Resistor Transistor Logic),以下图左边 5V 转 3.3V 为例。 当 TXD1 发送高电平时,第一个三极管导通,导致其集电极电位为低电平,所以第二个三极管基极为低电平,第二个三极管处于截止状态,RXD2 被上拉电阻拉高至 3.3V; 当 TXD1 发送低电平时,第一个三极管截止,第二个三极管导通,RXD2 相当于接地,输出低电平信号。 3V 转 5V 类似则不再赘述。 如果接收端可以接受反相信号,则可以去掉电路中一个三极管,电路会简单一些,如下图所示。 MOS 管电平转换 使用三极管搭建的逻辑电路的优点是速度快,但是其缺点也很明显,就是静态电流损耗很大,所以无法进行大规模的集成。MOS 管的导通电阻很小,其静态功耗可以忽略不计。MOS 管搭建的逻辑电路相比三极管的速度要慢,原因在于三极管是电流控制型器件,而 MOS 管是电压控制型器件,打开 MOS 管会涉及到给 MOS 管寄生电容充电,这个充电过程即是导致速度慢的原因。以 MOS 管搭建的如下电平转换电路可双向传输。 5V 电路发送高电平时,MOS 管 D 极电压被拉至 5V,但是 MOS 管的状态和 D 极电压无关,由 VGS 决定导通程度,所以 MOS 管截止,S 极被上拉电阻拉高为 3.3V; 5V 电路发送低电平时,MOS 管 D 极电压为 0V,S 极电压为 3.3V,由于 MOS 管存在体二极管,所以 3.3V 电路被钳位在 0.7V,为低电平; 3.3V 发送高电平时,MOS 管 G 极和 S 极电压都为 3.3V,MOS 管截止,D 极被上拉电阻拉高至 5V; 3.3V 发送低电平时,MOS 管 G 极为 3.3V,S 极为 0V,MOS 管导通,D 极为低电平。 电平转换芯片 在介绍集成好的电平转换芯片之前,我们需要先了解高阻态、三态门等基本的概念,最后再将三态门等进行组合形成电平转换芯片。 高阻态 高阻态是数字电路中常见的术语,表示电路中的某个节点具有相对电路中其它点更高的阻抗,它是电路的一种特殊的输出状态,但是这个状态既不是高电平也不是低电平。如果用万用表进行测试,可能测到高电平也可能测到低电平,它的状态取决于其后面的电路。 在电路分析时可以将高阻态作开路理解,理论上高阻态是不悬空的,它对地和对电源的电阻都非常大,但实际应用时与引脚悬空几乎一致,因此高阻态的极限可以认为就是悬空。 那么高阻态又是如何造成的呢?通常是由于三态门或三态缓冲器的存在而导致的,当三态门的使能端为低电平时,门电路输出上拉管和下拉管都截止,输出端就处于浮空状态,即没有电流的流动。此时相当于门电路放弃了对输出端电路的控制,其实际电平就由外部电平来决定。 三态门 那么什么又是三态门呢?三态门允许输出端除了高电平和低电平之外呈现高阻态。可以理解为除了输出输出端口外,三态门另外加了一个 EN 引脚,若没有对三态门进行使能,则其输出为高阻态,否则输出由输入决定。 三态门常常用于总线连接结构。在总线上有多个设备连接到同一条数据线上,但是在特定时间内只有一个设备是有效的,不活动的设备处于高阻态,因此不会对总线上其它设备产生影响。一般来说需要双向数据传输,我们再增加一个三态门即可实现此功能。 三态门输出结构 三态门输出端由上 PMOS 管、下 NMOS 管和一个输出供电电压构成,当上管导通时输出低电平,当下管导通时输出为高电平。 但是仔细观察会发现输出和输入是反相的,因此为了保证输入与输出同相,我们还需要在输入端加一级反相器。神奇的事情发生了,这不是施密特触发器吗?而且实际应用时为加强电路的抗干扰能力,使用的就是施密特触发器。 我们在上文的基础上再加入 EN 使能逻辑,即可实现完整的三态门输出结构,在排故障时可通过该等效电路对现象进行分析。 集成芯片 在实际应用中肯定不能一位一位的传输,我们假设一次传输一个字节(8 bit),为了简化电路我们把同一个方向的 EN 信号接到一起,如此即只需要两个信号即可控制数据的传输方向了。 通过控制 EN1 和 EN2 的使能与否,即可控制数据的传输方向。需要注意的是应该避免 EN1 和 EN2 同时都使能的状态,因为在此种状态下左右两侧的数据传输会打架,谁也不知道接收到的信号到底是自己发出去的还是别人发过来的。 EN1 EN2 左侧 右侧 输出状态 H H 使能 使能 无效状态 H L 使能 高阻态 数据由左至右 L H 高阻态 使能 数据由右至左 L L 高阻态 高阻态 隔离,不传输数据 为了避免上述同时使能的状态,我们对电路做一点改进,以保证芯片不会出现稀奇古怪的现象。 OE DIR 左侧 右侧 输出状态 H H 使能 高阻态 数据由左至右 H L 高阻态 使能 数据由右至左 L H 高阻态 高阻态 隔离,不传输数据 L L 高阻态 高阻态 隔离,不传输数据
Read More ~

LDO 基础知识

参考内容: ADI 公司 LDO 电容选型指南 线性和低压降 (LDO) 稳压器 BUCK 电路通过控制占空比来达到降压的目的,添加 LC 二阶低通滤波器将高频部分滤除,即可达到稳定输出直流的目的。但是滤波不能完全滤除高频分量,BUCK 从原理上就决定了其纹波不容易做到很小,其固有的开关频率会导致电源噪声很大,用来给噪声敏感的元器件供电就不合适。 相比 BUCK 来说,LDO(Low Dropout Regulaor:低压差线性稳压器)输出的电压会更加平稳,可以弥补 BUCK 输出纹波大的缺点。 总体框图 线性稳压器主要由四部分组成,基准源用于提供精准的电压基准、导通器件用于控制从 VIN 到 VOUT 的电流大小、误差放大器将强制反馈节点与基准电压匹配、反馈电阻用于调整以改变输出电压。 从框图中也可以看到线性稳压器只能用于降压,因此输入电压必须高于输出电压。当然其名字中本身带了低压差的,低压差就意味着少的发热,意味着电源转化效率的提升。线性则是指器件的工作状态,器件的内部模块工作在放大区,放大状态呈线性关系。 工作原理 线性稳压器的工作可以模拟为两个电阻器和一个用于 VIN 的电源,其中电源用于给负载供电,通过调整可变电阻(导通器件)的阻值来控制负载电阻所获得的电压,整个系统中唯一不变的恒定的参数就是输出电压 VOUT。 其稳压过程如下图所示,当负载电压升高/降低时,采样电路所采到的电压就跟着升高/降低,传递给误差放大器后通过调节导通器件的导通程度来调节输出电压。 导通器件 导通器件常见的有 PMOS、NMOS、BJT 等。BJT 应用于大电流的场景。PMOS 不需要额外的电源轨即可控制其导通程度,但是相比 NMOS 其 RDSon 更大,即 PMOS 架构的 LDO 在芯片本身所消耗的能量会更大。 使用 NMOS 作为导通器件时,需要添加辅助电源轨或者使用电荷泵才能将 NMOS 打开。当然电荷泵也有其缺点,虽然电荷泵可以提升 VIN,但是也带来了额外的噪声影响。若采用辅助电源轨时则需要注意,VBIAS 会影响 NMOS 的导通程度,进而影响输出电压的大小。 PSRR PSRR(Power Supply Rejection Ratio)量化了 LDO 抑制任何电源变化传递到其输出信号的能力,也就是 PSRR 决定了输入耦合到输出的噪声有多少。除了 LDO 本身的设计影响 PSRR 外,也可以通过调整 VIN 与 VOUT 之间的差值、输出电容来提高在特定应用(频率)下的 PSRR。 输入输出电容 为了确保 LDO 稳定工作,会在 LDO 输入输出端增加旁路电容,并且旁路电容的 ESR 需要很小,即在符合最小电容和最大 ESR 的要求下,使用任何质量良好的电容都可采用。在选择电容时还需要注意由于直流电压偏置、温度变化、制造商容差等需要对电容进行一定的降额。 输出电容除了可以进行滤波外,还会影响负载电流的变化的瞬态响应,采用较大的输出电容可以改善 LDO 对大负载电流变化的瞬态响应。输入电容则可以降低电路对 PCB 布局的敏感性,尤其是在长输入走线或者高源阻抗的情况下。 多层陶瓷电容、固态钽点解电容、铝电解电容通常用作输入和输出旁路电容。多层陶瓷电容具备 ESR 和 ESL 低、工作温度范围宽的优点,但是陶瓷电容中的介质材料具备压电性,振动或机械冲击可能会转化为电容上的交流噪声电压,在极端情况下可能会产生 mV 级的噪声。 压电性是在某些固体材料(晶体、陶瓷、骨头、DNA、蛋白质等)受到机械应力作用后,在材料中聚集电荷的现象。「压电」即由压力产生的电。 钽电容的优点是单位体积电容最高(CV 乘积),并且不太容易受到温度、偏执电压、震动效应的影响,在无法容忍压电效应的低噪声应用中,钽电容基本是唯一可行的选择。与陶瓷电容相比,钽电容的泄漏电流要比等值的陶瓷电容大很多倍,不适合超低电流应用。 铝电解电容往往体积较大、ESR 和 ESL 较高,漏电流相对较高,与钽电容一样不受压电效应影响,适合要求低噪声的应用场合,但是铝电解电容在航天应用中禁止使用。
Read More ~

半导体功率器件

高中时候我们在化学课程中学过元素周期表,「氢氦锂铍硼、碳氮氧氟氖......」倒背如流,在元素周期表的中间三、四、五族元素定义为半导体元素,所谓半导体是根据其导电能力来定义的,我们可以通过一定的半导体工艺来改变其导电能力。 以硅(Si)为例,硅是处在第四族的元素,它的外部有 4 个电子,所以硅的稳定结构是形成下图所示的及其稳定的共价键结构。 硅的两侧对应的是三族和五族的元素,三族的元素意味着外层有 3 个电子,五族的元素意味着外层有 5 个电子。如果把三族元素插入到四族的硅当中,由于硅想形成稳定的四个共价键结构,所以会存在一个空置的位置,我们称之为空穴,这个空穴是具备一定的正电荷的能力的,如此就形成了 P 型半导体。 同理,若使用五族元素与硅进行掺杂,就会多出一个可移动的电子,即存在自由电荷,形成了 N 型半导体。 PN 结(普通二极管) 当我们把 P 型半导体和 N 型半导体进行组合后,即可得到最基本的二极管(PN 结)。在 P 型半导体中存在高浓度的空穴(正电荷),在 N 型半导体中存在高浓度的电子,浓度高的载流子会自然而然向浓度低的区域进行扩散。 由于载流子扩散,最终会形成一个势垒,这是一个空间电荷区,也称之为耗尽层。可以发现 PN 结存在 P 区、耗尽层、N 区三个区域,这几个区域都是呈现电中性的,不管是空穴还是电子想要到达另一个区域,都必须要穿过耗尽层,即耗尽层会阻碍空穴和电子的运动,因此整个 PN 结在没有外界干扰的情况下,是不具备导电能力的。 当我们从外界施加 N 到 P 的电场时,即 PN 结反偏。此时外界电场与耗尽层电场是同向的,所以在外部电场的作用下,耗尽层的宽度会被加强,于是 PN 结的导电能力就变得更弱,因此就呈现了一个无导电能力的特性。 当然导电只是一种相对情况,即便空间电荷区变宽了,也不能百分百保证说就完全没有导电能力,因为还是有一定的空间电荷浓度,在这样的情况下会有微弱的电流流经 PN 结,意味着系统存在一个反向电流,这就是二极管一个比较重要的漏电流参数。 当外部施加的电场是从 P 到 N 时,即 PN 结正偏。外界电场的效果是使耗尽层变窄,加强了 P 区内空穴往 N 区内移动的能力,扩散电流远大于漂移电流,形成了一个正向导通电流。 最终二极管将呈现如下的导通特性,当正向电压大于势垒电压时,二极管开始导通。当施加反向电压时,二极管将截止,当反向电压大到一定程度后,二极管就会被反向击穿,即二极管损坏的过程。 功率二极管 既然谈到了「功率」二字,那么更加关注的就是二极管承载电流、电压的能力了。如何把二极管承载电流、电压的能力加强呢?根据上文关于二极管的介绍可以知道,将耗尽层加宽可以承载更大的电压。 图中中间 n- 为轻度参杂区域,下面 n+ 为重度参杂区域,这个参杂就导致了耗尽层的加宽,当然也导致导通损耗更大,不过也正因为如此,功率二极管才更加能耐压。 我们以非同步 BUCK 电路为载体,来说明一下功率二极管的变化过程。 图中(1)部分指二极管导通,有一个小小的二极管导通压降,因此曲线没有贴着 x 轴; 图中(2)的位置由于二极管承受的是反向电压,此时它关断了,所以电压为负; 图中(3)二极管需要经历一个从没有电压到有外加电压的变化,当电压加到二极管上时,二极管中的载流子流动的趋势逐渐增大,宏观表现出来是电阻慢慢变小的过程,但是电流保持不变,所有会有一个小尖峰,这一小段时间也会导致整体功率的损耗,开关频率越高,这个导通过程导致的损耗越多; 图中(4)处伴随系统从通到断的状态变化,大规模载流子需要进行重新分配,这个重新分配表现出来就是电流,而且这个电流与主电流相反,所以会看到一个反向的电流,而且这个反向电流会施加在主电路里面。这一段反向电流又分为两部分,下降阶段是之前外加电压时,PN 结中从 P 区域移动到 N 区域的载流子移除(恢复)过程,即从正偏到反偏的过程,正偏时空间电荷区非常非常窄,此时要进入反偏状态,空间电荷区需要加强,载流子需要重新分配,外部激励会移除不必要的空间电荷。电流上升的过程,即二极管又变成一个耐压器件了,也就是空间电荷区加宽,更多的载流子会不均匀的分布在两端。整个过程不可避免的需要移动电荷,而电荷的聚集效应可以认为就是一个电容的效应,当我们需要施加电压时,电压的增加就会需要额外的电荷,电荷不断聚集提供相反电荷,使其电压不断增加,以致增加到刚好截止输出电压为止。 MOS 管 以 NMOS 为例,它以 P 型半导体衬底,以 N 型半导体作为导电沟道,金属部分作为栅极(Gate),氧化部分(SiO2)作为绝缘层,两端分别为源极(Source)和漏极(Drain),从物理结构可以看出 MOS 管的源极和漏极是可以互换的,不像三极管有严格的顺序。 在栅极和源极施加电压,随着电压的不断增大,导电沟道将逐渐形成,当导电沟道刚好形成时的电压,称之为开启电压。外加电压继续增大,导电沟道将变得越来越宽,即导电能力越来越强。 PMOS 相比 NMOS 更加容易驱动,只需要 VGS 小于一定值即可导通。但是 PMOS 的导通电阻比 NMOS 要大,并且成本也比 NMOS 要高,所以比 NMOS 的实际应用场景要少许多。 功率 MOS 管 对比前文普通 MOS 管,可以看到源极、栅极、漏极是分开的,顶上那个灰色的板子是金属板。而功率 MOS 管在这个基础上做了一点创新,下图中的阴影部分就是金属板,可以发现总共只有两个金属板,上面的金属板把 N 区和 P 区都给连起来了,所以即使在栅极没有加电压的时候,也会存在一个天然的二极管通道,但是普通 MOS 管是没有体二极管通道存在的。同时由于是功率 MOS 管,所以也会想办法将耗尽层加宽,以增加其耐压能力。 体二极管和耐压能力的加强是功率 MOS 和普通 MOS 的区别。 功率 MOS 管的正向导通能力就是涉及「场效应」了,所谓的场效应即意味着外部可以通过电场来控制其内部载流子的浓度,在栅极施加正电压时就会产生一个电子的导电沟道,由于整体是 N 型半导体衬底,所以整体也就形成了一个电子的导电沟道,并且该沟道支持电子的双向移动。 如下图所示是功率 MOS 管的等效电路模型。其主要损耗由三部分组成,分别为导通损耗、开关损耗(开通损耗和关断损耗)、驱动损耗。其中导通损耗与开关损耗容易理解,驱动损耗作何理解呢?MOS 并不像二极管是一个被动型器件,MOS 管开或关的行为都需要能量作为代价,就好比要打开机械开关需要用手去按压,这个过程所消耗的能量就是驱动损耗。 晶体管 二极管只有一个 P 型半导体和一个 N 型半导体结合,如果再加一个 N 型半导体(或 P 型半导体)即构成了晶体管(三极管),晶体管有集电极、发射极、基极三个极。 需要注意的是三极管的集电区和发射区掺杂浓度是不一样的,其中基区多子少且做的很薄,而发射区的多子浓度很高,集电区多子浓度相对较低但面积大。不管三极管是正接还是反接,三极管都处于截止状态,这是因为三极管可以看作两个二极管反向相连,不论如何接都会有一个二极管处于截止状态。 为了能让三极管导通,我们在基极和发射极再施加一个电压,此时二极管开始导通,发射区的自由电子就可以源源不断的流向基区,但是基区的掺杂浓度很低且很薄,基区短时间内吸收不了太多的电子,只有一少部分电子能与空穴复合形成基极电流,而大部分被吸引到了集电区,形成集电极电流,也就是三极管的输出电流。 流过基极的电流越大,流到基区的自由电子也就越多,相应的被吸引到集电区的电子也就更多,这就是三极管小电流控制大电流的原理。基区做的很薄是为了让发射区的电子更容易进入集电区,浓度很低视为了形成更小的基极电流,这样才会有更多的自由电子流向集电区。 IGBT 三极管工作时涉及载流子的注入和抽离所以会很慢,由于其性能的关系正在逐步退出历史舞台,因此需要对其进行改进,改进后的器件就是 IGBT,如下图所示。 可以发现 IGBT 是一个受 MOS 管控制的 BJT,即同时继承了 MOS 管快速和 BJT 大电流的优点。当然,它也有缺点,并且缺点主要来自于 BJT 关断较慢的问题,因为当 MOS 管门级信号撤出时,并不能立马把电流都抽走,所以电流会经历一段下降时间。
Read More ~

BUCK 电路基础知识

参考内容: 手撕Buck!Buck公式推导过程 电力电子的基础应用 《精通开关电源设计(第二版)》 Buck电源芯片输出有问题?检查这几样 原来PWM这么简单! 为什么 DC-DC 芯片设计中都有一个自举电容? 如何克服开关电源中的最小导通时间挑战 BUCK 电路构建 根据高中所学习的物理知识可以很容易的想到,使用一个滑动变阻器即可实现降压和稳压的效果。当负载波动时,通过改变滑动变阻器的阻值,可以调节负载所获得的电压。但是使用滑动变阻器的劣势也很明显,大量的耗能会导致器件温度快速升高。 上面所提到的电路主要缺点在于导通器件(变阻器或三极管)本身存在耗能,那么有没有不会耗能的导通器件呢?首先肯定不能选导线,不然又回到最原始的问题,所有电压都被加到负载上了。有没有能不耗能且能控制加在负载电压的导通器件呢?最常见的机械开关就能做到这个效果。 当开关闭合时,负载即获得电压源输出的电压;当开关打开时,负载所获得的电压为 0V。计算平均值可以确定达到了降压的目的,通过控制开关闭合的时间长短,就可以达到调节电压的效果。但仔细想想就会发现不对劲,电路并不会帮助我们计算平均值,负载所获得的电压波形如下图所示,是完美的方波,并不是一条直线。 控制开关闭合的时间,即后文要讲的控制占空比 此时很容易就能想到利用电容两端电压不能突变的特点,给负载并联一个电容即可,电容即保证负载可以获得连续的能量流。 一旦引入了电容,就需要考虑浪涌电流的问题。根据公式 Q=CV=ItQ=CV=ItQ=CV=It 可得 I=CVtI=\frac{CV}{t}I=tCV​,开关闭合时电压在非常短的时间内升高,所以电流会突然变得很大。 我们当然可以简单的利用电阻来抑制浪涌电流,但不幸的是电阻总要消耗功率。为了最大限度的提高效率,可以考虑使用电感,电感本身不消耗任何能量,只会进行储能,且其无损限流的能力正好可以用来抑制电容的浪涌电流。 引入电感后可以发现当开关打开时,电感没有续流回路,因此需要想办法构造电感的续流回路。续流回路需要保证不论开关打开还是闭合,电流都流向负载,且开关闭合时电源正极与负极回路必须经过电感与负载。这个需求很符合二极管的特点,即只允许单向导通。 到目前为止我们构建了非同步 BUCK 电路,考虑到机械开关容易磨损、使用寿命短、有机械惯性(转换频率低)的问题,我们需要将机械开关换成转换频率高的半导体器件,此处我们选择 NMOS 管来替代开关。 选择 NMOS 和 PMOS 的主要区别在于驱动电路的设计 可以发现当 NMOS 开关管导通时,续流二极管处于截止状态;当开关管关断时,续流二极管处于导通状态。即二极管的导通和截止和开关管的截止导通是同步的,也就是说二极管起到的是一个开关的作用。而且考虑到电流从二极管流过期间,二极管两端的压降恒定为导通电压 0.7V,二极管所消耗的能量较大。因此我们也可以把二极管换为导通电阻更小的 NMOS 管。 为了提高 BUCK 电路的稳定性,防止由于输入纹波带来异常,我们在 BUCK 电路的输入端并联一个电容,用于滤除输入电压的纹波。 至此我们就搭建了一个标准的同步 BUCK 电路,我们将其简单变个样子,再加几个标签即可得到下图。在同步 BUCK 电路中需要两个开关管密切配合,以防止整个线路导通,所以它们之间需要保持一定的相位关系,即上管导通下管截止;上管截止下管导通,我们把这种关系称之为同步。 信号角度理解 LC 我们以占空比为 0.5 来进行说明,将时域下的方波转换到频域,通过傅立叶变换可以分解出一系列的频率分量。其中包含频率为 0 的分量,即直流分量,也就是我们想要保留的部分,还有频率为 n 倍 fsf_{s}fs​ 的分量。那么如何把我们不想要的部分去掉呢?从滤波角度考虑就需要加入一个低通滤波器。 通过加入低通滤波器可以把高频分量滤除,把二阶低通滤波器的截止频率设置在 0 到 fsf_{s}fs​ 之间,即可把 fsf_{s}fs​ 所有以上的部分给滤除。整体达到的效果即通过一个 LC 低通滤波器,配合一个开关网络,将一个数字化的电平重新滤出,得到一个比较平缓的电压输出,这个过程即完成了电压从高到低的转换。其中直流分量的大小受占空比 D 控制,所以通过改变占空比 D 即可改变输出电压大小。 稳态分析 我们需要先强调一下前提,此处我们说的稳态分析,即输入电压输出电压都是稳定,且纹波足够小的状态。下文的所有计算都将基于稳态进行分析,并且是在 (F)CCM(连续导通模式)下计算的。 我们将一些已知条件列出来: 输入电压:ViV_{i}Vi​ 输出电压:VoV_{o}Vo​ 负载电阻:RRR 输出电感:LLL 开关频率:fff 伏秒平衡 当上管导通下管截止时,电感右边的电压为 ViV_{i}Vi​,左边的电压为 VoV_{o}Vo​,因为同步 BUCK 电路是降压电路,所以 Vi>VoV_{i}>V_{o}Vi​>Vo​,所以电感两端电压即为 Vi−VoV_{i}-V_{o}Vi​−Vo​,也就是说是一个恒定值。由于有 Ldidt=Vi−VoL\frac{\mathrm{d} i}{\mathrm{d} t} =V_{i}-V_{o}Ldtdi​=Vi​−Vo​,所以 didt=Vi−VoL\frac{\mathrm{d} i}{\mathrm{d} t} =\frac{V_{i}-V_{o}}{L}dtdi​=LVi​−Vo​​,即电感电流的上升斜率,由于是稳态前提,所以可以确定该值是一个常数。 当上管截止下管导通时,电感右边电压为 VoV_{o}Vo​,左边电压为 000,所以电感两端电压为 0−Vo0-V_{o}0−Vo​,即 −Vo-V_{o}−Vo​。由于 Ldidt=−VoL\frac{\mathrm{d} i}{\mathrm{d} t} =-V_{o}Ldtdi​=−Vo​,所以 didt=−VoL\frac{\mathrm{d} i}{\mathrm{d} t} =-\frac{V_{o}}{L}dtdi​=−LVo​​,即电感电流的下降斜率,也是一个常数。 整个电路处于稳定状态,负载电路恒定,那么在一个周期内,电感电流增加的量肯定等于电感电流减小的量,即充了多少电就要放多少电,不然负载的电流或电压将会发生变化。 前文已有didt=UL\frac{\mathrm{d} i}{\mathrm{d} t} =\frac{{U}}{L}dtdi​=LU​,而 LLL 恒定,那么电感电流的变化速度即与电压成正比关系,即电感电流上升(下降)的斜率与电压成正比关系。而电感电流上升和下降的高度相同,那么上升时间和下降时间就自然构成反比关系。 TonToff=VoVi−Vo\frac{T_{on} }{T_{off} } = \frac{V_{o}}{V_{i}-V_{o}}Toff​Ton​​=Vi​−Vo​Vo​​,将其进行简单变换即可得到闻名江湖的伏秒平衡法则。 Ton(Vi−Vo)=ToffVoT_{on}(V_{i}-V_{o}) = T_{off}V_{o}Ton​(Vi​−Vo​)=Toff​Vo​ 占空比 已知 T=Ton+Toff=1fT=T_{on}+T_{off}=\frac{1}{f}T=Ton​+Toff​=f1​,结合伏秒平衡法则可以计算出: 开通时间:Ton=VoVi∙1fT_{on} = \frac{V_{o} }{V_{i} } \bullet \frac{1}{f}Ton​=Vi​Vo​​∙f1​ 关断时间:Toff=Vi−VoVi∙1fT_{off} = \frac{V_{i}-V_{o} }{V_{i} } \bullet \frac{1}{f}Toff​=Vi​Vi​−Vo​​∙f1​ 占空比:D=TonT=VoViD = \frac{T_{on} }{T}=\frac{V_{o} }{V_{i}}D=TTon​​=Vi​Vo​​ 纹波电流 由于输出电压不变,也就是说输出电容两端的电压没有变化,即输出电容的平均电流为 0。根据输出节点的基尔霍夫电流定律可知,输出节点电流和为 0,那么功率电感的平均电流就等于负载的平均电流,即IL=Io=VoRI_{L} = I_{o} = \frac{V_{o} }{R}IL​=Io​=RVo​​。 上文计算电感电流斜率时已经能确定电流波形是个三角波,纹波电流等于在开关导通时电感电流的增大值,也等于在关断时电感电流减小的值,计算任意一个即可得到纹波电流。我们以上管导通时增大的电感电流计算。 上管导通时电感两端电压为 Vi−VoV_{i}-V_{o}Vi​−Vo​,导通时间为 Ton=VoVi∙1fT_{on} = \frac{V_{o} }{V_{i} } \bullet \frac{1}{f}Ton​=Vi​Vo​​∙f1​,根据 U=LdidtU=L\frac{\mathrm{d} i}{\mathrm{d} t}U=Ldtdi​ 可知: △IL=di\triangle I_{L} =di△IL​=di =Ton∙UL=T_{on}\bullet \frac{U}{L}=Ton​∙LU​ =Vi−VoL∙VoVi∙1f=\frac{V_{i}-V_{o}}{L}\bullet \frac{V_{o}}{V_{i}}\bullet \frac{1}{f}=LVi​−Vo​​∙Vi​Vo​​∙f1​ 根据理论计算可以发现,电感电流的纹波和负载电流的大小没有关系,但是负载电流与平均电感电流是相等关系。 功率电感选择 根据上文的信息进一步可以计算出电感的峰值电流: ILP=Io+△IL2I_{LP} =I_{o}+\frac{\triangle I_{L}}{2}ILP​=Io​+2△IL​​ =Io+Vi−Vo2L∙VoVi∙1f=I_{o}+\frac{V_{i}-V_{o}}{2L}\bullet \frac{V_{o}}{V_{i}}\bullet \frac{1}{f}=Io​+2LVi​−Vo​​∙Vi​Vo​​∙f1​ 那么在选择功率电感时,电感的饱和电流就必须要大于这个ILPI_{LP}ILP​,并且需要留有一定的裕量。实际应用时电感的纹波电流应是平均电流的 30%30\%30% 至 50%50\%50% 为宜,我们将这个参数称之为电流纹波率 r。根据电流纹波率范围就可以计算出电感值的范围: △IL=Vi−VoL∙VoVi∙1f\triangle I_{L} =\frac{V_{i}-V_{o}}{L}\bullet \frac{V_{o}}{V_{i}}\bullet \frac{1}{f}△IL​=LVi​−Vo​​∙Vi​Vo​​∙f1​ L=Vi−Vo△IL∙VoVi∙1fL =\frac{V_{i}-V_{o}}{\triangle I_{L}}\bullet \frac{V_{o}}{V_{i}}\bullet \frac{1}{f}L=△IL​Vi​−Vo​​∙Vi​Vo​​∙f1​ =Vi−Vo(0.3至0.5)Io∙VoVi∙1f=\frac{V_{i}-V_{o}}{(0.3至0.5) I_{o}}\bullet \frac{V_{o}} {V_{i}}\bullet \frac{1}{f}=(0.3至0.5)Io​Vi​−Vo​​∙Vi​Vo​​∙f1​ =(Vi−Vo)Vo(0.3至0.5)IoVif=\frac{(V_{i}-V_{o})V_{o}}{(0.3至0.5) I_{o} V_{i} f}=(0.3至0.5)Io​Vi​f(Vi​−Vo​)Vo​​ 为何 r 为 0.3~0.5 电流纹波率即是电感电流的交流分量与其相对应的直流分量的比值,一旦 r 确定,那么输入输出滤波电容的电流、开关管的有效电流等都确定了,因此 r 的选择会影响器件选择和芯片的成本。使用公式可以表述为: r=△IIL=2×IACIDCr=\frac{\triangle I}{I_{L}}=2\times \frac{I_{AC}}{I_{DC}}r=IL​△I​=2×IDC​IAC​​ 一般认为,电感体积与其能量处理能量成正比,因为要处理更高的能量就需要更大的磁芯。选择电感磁芯的能量处理能力至少要等于其需存储量,即 E=12×L×Ipk2E=\frac{1}{2} \times L \times I_{pk}^{2}E=21​×L×Ipk2​,下图是 E 与 r 的的函数曲线,可以发现在 r=0.4r=0.4r=0.4 附近有一个拐点。 选择的 r 如果较 0.4 低很多,则所需要的电感体积越大;而若继续增大 r,则电感的体积并不会减少多少,即当 r 超过 0.4 后,通过增加 r 来减少电感体积的效果已经不明显了。 输入纹波 电源输入功率为 Pi=ViIiP_{i}=V_{i}I_{i}Pi​=Vi​Ii​,负载功率为 Pr=VoIoP_{r}=V_{o}I_{o}Pr​=Vo​Io​,不考虑开关损耗、导通损耗等等因素,那么输入功率和输出功率相等,可得输入平均电流为 Ii=VoIoViI_{i}=\frac{V_{o}I_{o}}{V_{i}}Ii​=Vi​Vo​Io​​。 输入电压纹波就是输入电容上面电压的变化,这个变化可以分为两部分。一部分为电容充放电所导致的电压变化 UqU_{q}Uq​,另一部分为电流流过电容 ESRESRESR 导致的压降 UesrU_{esr}Uesr​。即 △Vi=Uq+User\triangle V_{i} = U_{q} + U_{ser}△Vi​=Uq​+User​。 ∵Q=CiUq=Iit=IiToff\because Q = C_{i}U_{q} = I_{i}t = I_{i}T_{off}∵Q=Ci​Uq​=Ii​t=Ii​Toff​ ∴Uq=IiToffCi\therefore U_{q} = \frac{I_{i}T_{off}}{C_{i}}∴Uq​=Ci​Ii​Toff​​ ∵Toff=Vi−VoVif\because T_{off} = \frac{V_{i}-V_{o} }{V_{i}f }∵Toff​=Vi​fVi​−Vo​​ 且 Ii=VoIoViI_{i}=\frac{V_{o}I_{o}}{V_{i}}Ii​=Vi​Vo​Io​​ ∴Uq=VoIoCiVif∙Vi−VoVi\therefore U_{q} = \frac{V_{o}I_{o}}{C_{i}V_{i}f}\bullet \frac{V_{i}-V_{o}}{V_{i}}∴Uq​=Ci​Vi​fVo​Io​​∙Vi​Vi​−Vo​​ 要想知道 ESRESRESR 所造成的纹波,只需要知道流过输入电容的电流即可。当上管断开时,电源输入电流 IiI_{i}Ii​ 全部流入电容 CiC_{i}Ci​。电感电流原本从下管的体二极管续流,当上管导通后,变为了从上管续流。因为此前电感一直处于放电状态,所以切换的那一刻电感电流是最小的,为 IL−△IL2I_{L}-\frac{\triangle I_{L}}{2}IL​−2△IL​​。 在整个 TonT_{on}Ton​ 时间内,电感都被充电,电感电流一直都在增大,直到 IL+△IL2I_{L}+\frac{\triangle I_{L}}{2}IL​+2△IL​​,并且在 TonT_{on}Ton​ 时间内,电感电流都是走的上 MOS 管通路,所以上 MOS 管最大电流也是 IL+△IL2I_{L}+\frac{\triangle I_{L}}{2}IL​+2△IL​​。 根据基尔霍夫电流定律可知,输入节点的电流和为 0,那么输入电源电流 IiI_{i}Ii​ 和电容 CiC_{i}Ci​ 的放电电流就等于通过上 MOS 管的电流。所以 CiC_{i}Ci​ 的最大放电电流即为 IL+△IL2−IiI_{L}+\frac{\triangle I_{L}}{2} - I_{i}IL​+2△IL​​−Ii​。我们约定充电为正,放电为负,则放电电流为 Ii−△IL2−ILI_{i} - \frac{\triangle I_{L}}{2} - I_{L}Ii​−2△IL​​−IL​。 上管截止时 ESRESRESR 的压降为 Ii∙ESRI_{i} \bullet ESRIi​∙ESR,上管导通时压降为 (Ii−△IL2−IL)∙ESR(I_{i} - \frac{\triangle I_{L}}{2} - I_{L}) \bullet ESR(Ii​−2△IL​​−IL​)∙ESR,则可得: User=Ii∙ESR+(Ii−△IL2−IL)∙ESRU_{ser} = I_{i} \bullet ESR + (I_{i} - \frac{\triangle I_{L}}{2} - I_{L}) \bullet ESRUser​=Ii​∙ESR+(Ii​−2△IL​​−IL​)∙ESR =(IL+△IL2)∙ESR=(I_{L} + \frac{\triangle I_{L}}{2}) \bullet ESR=(IL​+2△IL​​)∙ESR ∵△IL==Vi−VoL∙VoVi∙1f\because \triangle I_{L} ==\frac{V_{i}-V_{o}}{L}\bullet \frac{V_{o}}{V_{i}}\bullet \frac{1}{f}∵△IL​==LVi​−Vo​​∙Vi​Vo​​∙f1​ 且 IL=IoI_{L} = I_{o}IL​=Io​ ∴User=(Io+(Vi−Vo)Vo2ViLf)∙ESR\therefore U_{ser} = \left ( I_{o} + \frac{\left ( V_{i}-V_{o} \right ) V_{o}}{2V_{i}Lf} \right )\bullet ESR∴User​=(Io​+2Vi​Lf(Vi​−Vo​)Vo​​)∙ESR 综上所述可得: △Vi=Uq+Uesr\triangle V_{i} = U_{q} + U_{esr}△Vi​=Uq​+Uesr​ =VoIoCiVif∙Vi−VoVi+(Io+(Vi−Vo)Vo2ViLf)∙ESR=\frac{V_{o}I_{o}}{C_{i}V_{i}f} \bullet \frac{V_{i}-V_{o}}{V_{i}} +\left ( I_{o} + \frac{\left ( V_{i}-V_{o} \right ) V_{o}}{2V_{i}Lf} \right )\bullet ESR=Ci​Vi​fVo​Io​​∙Vi​Vi​−Vo​​+(Io​+2Vi​Lf(Vi​−Vo​)Vo​​)∙ESR 输入电容选择 考虑到电容的实际使用情况,陶瓷电容的 ESRESRESR 小,容量小,所以 UqU_{q}Uq​ 对纹波起决定性作用,输入纹波可近似为 UqU_{q}Uq​。若选择铝电解电容,则 ESRESRESR 大,容量大,UesrU_{esr}Uesr​ 对纹波起到决定性作用,输入纹波可以近似为 UesrU_{esr}Uesr​,假设电路设计要求输入纹波不能大于 △Vi\triangle V_{i}△Vi​,则有: 陶瓷电容:Ci≥VoIo△ViVif∙Vi−VoViC_{i} \ge \frac{V_{o}I_{o}}{\triangle V_{i}V_{i}f} \bullet \frac{V_{i}-V_{o}}{V_{i}}Ci​≥△Vi​Vi​fVo​Io​​∙Vi​Vi​−Vo​​ 铝电解电容:ESR≤△ViIo+(Vi−Vo)Vo2fLViESR \le \frac{\triangle V_{i}}{I_{o} + \frac{(V_{i}-V_{o})V_{o}}{2fLV_{i}} }ESR≤Io​+2fLVi​(Vi​−Vo​)Vo​​△Vi​​ 输出纹波 输出纹波与输入纹波同理,亦是 △Vo=Uq+Uesr\triangle V_{o} = U_{q} + U_{esr}△Vo​=Uq​+Uesr​,我们画出负载、功率电感、输出电容三者的电流波形。其中电感的纹波电流是 △IL\triangle I_{L}△IL​,则电容的纹波电流也是 △IL\triangle I_{L}△IL​,又因为电容的平均电流为 0,所以充电电流和放电电流都是 △IL2\frac{\triangle I_{L}}{2}2△IL​​。 电容充放电的总电荷量 Q 等于电流乘以时间,即图中阴影三角形的面积,三角形底部时间为 T2\frac{T}{2}2T​,高为 △IL2\frac{\triangle I_{L}}{2}2△IL​​,所以总的放电量可以计算出来为 Q=12∙T2∙△IL2Q=\frac{1}{2} \bullet \frac{T}{2} \bullet \frac{\triangle I_{L}}{2}Q=21​∙2T​∙2△IL​​ 结合 Q=CoUqQ=C_{o}U_{q}Q=Co​Uq​ 可得: Uq=(Vi−Vo)Vo8ViCoLf2U_{q} = \frac{\left ( V_{i}-V_{o} \right ) V_{o}}{8V_{i}C_{o}Lf^{2} }Uq​=8Vi​Co​Lf2(Vi​−Vo​)Vo​​ 由前面电流波形可知,电容的充电电流最大是 △IL2\frac{\triangle I_{L}}{2}2△IL​​,放电电流最大是 −△IL2-\frac{\triangle I_{L}}{2}−2△IL​​,则可以得到 ESRESRESR 引起的总压降为: User=△IL2∙ESR−(−△IL2∙ESR)U_{ser} = \frac{\triangle I_{L}}{2} \bullet ESR - (-\frac{\triangle I_{L}}{2} \bullet ESR)User​=2△IL​​∙ESR−(−2△IL​​∙ESR) ∵△IL=Vi−VoL∙VoVi∙1f\because \triangle I_{L} = \frac{V_{i}-V_{o}}{L}\bullet \frac{V_{o}}{V_{i}}\bullet \frac{1}{f}∵△IL​=LVi​−Vo​​∙Vi​Vo​​∙f1​ ∴(Vi−Vo)VoViLf∙ESR\therefore \frac{\left ( V_{i}-V_{o} \right ) V_{o}}{V_{i}Lf} \bullet ESR∴Vi​Lf(Vi​−Vo​)Vo​​∙ESR 最终可得: △Uo=Uq+Uesr\bigtriangleup U_{o} = U_{q} + U_{esr}△Uo​=Uq​+Uesr​ =(Vi−Vo)Vo8ViCoLf2+(Vi−Vo)VoViLf∙ESR=\frac{\left ( V_{i}-V_{o} \right ) V_{o}}{8V_{i}C_{o}Lf^{2} } + \frac{\left ( V_{i}-V_{o} \right ) V_{o}}{V_{i}Lf} \bullet ESR=8Vi​Co​Lf2(Vi​−Vo​)Vo​​+Vi​Lf(Vi​−Vo​)Vo​​∙ESR =(Vi−Vo)VoViLf∙(ESR+18fCo)=\frac{\left ( V_{i}-V_{o} \right ) V_{o}}{V_{i}Lf}\bullet \left ( ESR + \frac{1}{8fC_{o}} \right )=Vi​Lf(Vi​−Vo​)Vo​​∙(ESR+8fCo​1​) 输出电容选择 与输入电容选择的方式一致,考虑是容值还是 ESRESRESR 占主导地位,假设要求输出纹波要小于 △Vo\triangle V_{o}△Vo​,则有: 陶瓷电容:Co≥(Vi−Vo)Vo8Vi△VoLf2C_{o} \ge \frac{\left ( V_{i}-V_{o} \right ) V_{o}}{8V_{i}\triangle V_{o}Lf^{2} }Co​≥8Vi​△Vo​Lf2(Vi​−Vo​)Vo​​ 铝电解电容:ESR≤△VoViLf(Vi−Vo)VoESR \le \frac{\triangle V_{o}V_{i}Lf}{\left ( V_{i}-V_{o} \right ) V_{o}}ESR≤(Vi​−Vo​)Vo​△Vo​Vi​Lf​ 电感续流模式 电感电流曲线不能断续(无突降),因为电流断续会引起实际不可能发生的能量断续现象。但是电流的变化率可以突变,比如从上升斜率(电感储能增加)变为下降斜率(电感储能释放),尽管这样电感电流也必须连续。根据稳定状态下每个周期电流是否回到零,划分为不同的导通模式,并且通过减小负载电流,可以使电路从 CCM 经过 BCM 最终转变为 DCM。 CCM(连续导通模式) 稳定状态下每个周期,电流都回到某一非零值,称之为连续导通模式(CCM:Continuous Conduction Mode)。CCM 是功率变换中最常见的工作模式,有输出纹波小但功耗高的特点。 FCCM(强制连续导通模式)只存在于同步 BUCK 中,由于使用 MOS 管将非同步拓扑的二极管取代,MOS 管的导通压降远低于二极管压降,除了显著减小了续流通路的导通损耗外,也允许电感电流反向,即从负载瞬时流出电流。 DCM(断续导通模式) 若稳定状态下每个周期中电流都会回到零,那么就称之为断续导通模式(DCM:Discontinuous Conduction Mode),DCM 由于其电感电流的不连续,计算平均电感电流就需要更加详细复杂的公式,这也是 DCM 方程看上去复杂的根本原因。 BCM(临界导通模式) BCM 是临界导通模式(Boundary Conduction Mode),由控制器监控电感电流,一旦检测到电流等于 0,功率开关立即闭合,控制器总是等电感电流「复位」来激活开关。即 BCM 处于 CCM 和 DCM 之间,可以将其视为 CCM 和 DCM 的极端情况,所以 BCM 模式下可以自由的选择 CCM 或 BCM 方程。 DC-DC 功能框图 前文所构建的 BUCK 电路只能是纸上谈兵,还需要解决诸多问题才能应用于实际电路。 基础驱动与控制 首先需要解决的问题就是 MOS 管不可能平白无故就打开,所以我们需要添加 MOS 管驱动器。 理想情况是上管关闭,下管立刻打开,中间没有任何时间差,但是 MOS 管并非理想开关,从关断到导通存在一个过渡的过程,若同时导通则电源通过上下 MOS 管直接对地短路,很容易就会导致 MOS 损坏,甚至可能会把前一级电源也损坏,所以上下管同时导通的状态必须得避免。 为了避免上下管直通的情况,实际应用会故意让上管和下管切换时多等一会儿,宁愿出现同时关断的情况,也不能出现同时导通的状态,这个等待的过程就叫做死区时间。 需要注意的是,在死区时间内虽然下管没有被导通,但是功率 MOS 管本身存在一个寄生二极管,这个寄生二极管可以像非同步 BUCK 那样帮助电感续流,而且这个时间非常的短暂,所以产生的功耗没有那么大,因此不必担心系统会出问题。 到目前为止,不知道您有没有发现我们都在自嗨,系统中并没有用来控制上下 MOS 导通和关断的信号。因此需要增加一个振荡器用来产生控制信号,注意我们在前文中使用的是占空比一词,也就是说我们要使用的是 PWM(脉冲宽度调制)。当然你也可以使用 PFM(脉冲频率调制),本文只介绍 PWM 方式。 PWM(脉冲宽度调制) PWM 的全称是脉冲宽度调制(Pulse-width modulation),是通过将有效的电信号分散成离散形式,从而来降低电信号所传递的平均功率的一种方式。其基本实现原理是通过锯齿波/三角波(载波)与所需要合成的波形(调制波)进行比较,然后确定 PWM 所需要输出的极性。因为一般都是用到开关器件上,通常是 ON 或者 OFF,具体如下图所示。 将振荡器输出的锯齿波和参考值 VthV_{th}Vth​ 进行比较,就可以输出 PWM 波形了。话不多说,上图就明白了。 上图中的锯齿波(橙色)最大为 10,但是我们希望输出平均为 5 的波形(图中紫色的水平线),那么通过比较器进行比较,当锯齿波小于 5 时,PWM 即输出低电平 OFF,当锯齿波大于 5 时,PWM 即输出高电平 ON,此时的占空比即为 50%。 若是想输出一个电压逐渐抬高的波形,即占空比逐渐增大,那只需要将调制的波形设置为斜坡输出即可达到效果。比如下图中可以看到,占空比从 0% 逐渐增大到 100%。 同样的道理,我们可以通过改变调制波形,进一步调制出来其它的波形,比如要调制一个正弦波(sin wave),也就是我们常说的 SPWM,那么就是下面的样子。 负反馈环路 有了调制信号,开关管也可以正常打开与关闭,看起来可以应用到实际电路中了,但是别忘了负载的电阻并不是恒定的,负载的变化必然会引起输出电压的波动。为了减小输出电压的波动,我们可以在输出端添加分压电阻,与误差放大器和基准电压一起构成负反馈回路,这种通过取样输出电压进行闭环反馈的方式称之为电压模式控制。 误差放大器的输入端分别为带隙基准源输出电压采样,当输出电压减小/增大时,与基准电压的细微差异都会被误差放大器放大,今儿调节脉冲宽度来达到调节调整输出电压的目的。图中 R2 接地,所以可以很容易计算出输出电压与分压电阻的关系:Vout=Vref(R1+R2)R2V_{out} = \frac{V_{ref}(R_{1}+R_{2})}{R_{2}}Vout​=R2​Vref​(R1​+R2​)​。 除了输出电压可以用作控制取样信号,还有输入电压、输出电流、输出电感电压、开关器件峰值电流可以作为控制取样信号。使用这些信号可以构成单环、双环或多环反馈系统,进而实现稳压、稳流以及恒定功率的目的,也可以实现过流、过压、均流等功能。 现在回过头来评判一下电压模式控制的优缺点。单一的反馈电压闭环设计使得调试更加容易、对输出负载的变化有比较好的响应调节、占空比的调节也不会受到什么限制等等都是它的优点,但是其缺点也很明显。由于主电路有较大的输出电容和电感的相移延时作用,输出电压的变小/变大也延时滞后,再经过误差放大器的延时,使得瞬态响应变得更慢。由于电压控制模式不采样电流,逐周期限流保护功能必须另外增加电路来实现。 峰值电流模式控制在电压模式控制的基础上又增加了电流环,所以峰值电流模式控制是一个双环反馈系统。误差电压信号与一个变化的,其峰值代表输出电感电流峰值的三角波形进行比较,然后得到 PWM 脉冲的关断时刻。所以峰值电流模式控制不是使用电压误差信息直接控制 PWM 脉冲宽度,而是直接控制峰值输出侧的电感电流大小,进而间接的控制 PWM 脉冲宽度。 峰值电流在逻辑上与平均电感电流大小变化一致,但是峰值电感电流的大小并不能与平均电感电流的大小一一对应。在占空比不同的情况下,相同的峰值电感电流大小可以对应不同的平均电感电流大小,但平均电感电流大小才是唯一决定输出电压大小的因素。 为了解决不同占空比对平均电感电流大小的扰动作用,使得所控制的峰值电感电流最后收敛于平均电感电流,需要将电感电流下斜坡斜率的至少一半以上斜率加在实际检测电流的上斜坡上,这一点可以从数学上进行证明(具体咋证明暂不讨论)。 总结一下峰值电流模式控制 PWM 是双闭环控制系统,电压外环控制电流内环。电流内环是瞬时快速按照逐个脉冲工作的。功率级石油电流内环控制的电流源,而电压外环再控制次功率级电流源。电流内环只负责输出电感的动态变化,电压外环仅需控制输出电容,所以峰值电流模式控制 PWM 具有比电压模式控制大得多的带宽。 为了防止在应用过程中可能出现的短路等异常场景,DC-DC 少不了过温保护、过流保护、过压保护等保护手段。再设定一定的辅助功能,比如 PG 状态显示、缓启动、欠压保护等即可搭建完整的 DC-DC 电路。 异常模式 参考上文中的电路图,我们把绿色部分称之为控制电路,灰色部分是功率电路,功率电路中最核心的就是上下两个 MOS 管,下文我们讨论不同的异常场景中,控制电路、上管、下管三部分应该处于什么状态,其中控制电路关闭相当于整个芯片重启。 过压保护 当输出电压偏高并且达到了过压保护的阈值。过压状态需要控制电路去调整把输出电压降下来,所以不需要重启整个芯片。可以想到输出端已经处于过压状态了,上管如果打开那会加重过压的程度,因此上管需要关闭。若下管打开,则电感、负载、下管形成回路,即电感有续流回路,会把过压状态维持的时间更长,因此下管也需要关闭。综上有:过压保护:关上管、关下管。 过温保护 温度过高的情况无非两种,一种是流过芯片的电流太大,即功率太大导致芯片自身发热达到了过温保护的阈值,此时关闭芯片肯定可以解决,另外切断电流回路也是可以解决的,即关闭上管。过温的第二种情况是由于环境温度过高而导致芯片温度过高,此时最好还是关闭芯片吧。综上有:过温保护:关闭芯片。 关闭芯片指关闭芯片中的 BUCK 部分,但是基准源部分仍然保持工作 过流保护 过流保护还需要区分是正向过流还是负向过流,因为工作在 FCCM 模式的 DC-DC 在轻载或空载时,可能会有负向过流的情况。存在负向过流的另一原因也是因为同步 BUCK 没有像非同步 BUCK 那样的整流二极管,所以当存在负向过流情况时,直接模拟非同步 BUCK 中的二极管即可。综上有:负向过流保护:关下管。 若发生正向过流时如何进行保护呢?首先考虑到电流经上管到负载,既然已经过流了那么肯定需要关上管。为了使电流减小的更快,那么就需要将电流流向地,所以需要将下管打开以构成回路。综上有:正向过流保护:关上管、开下管。 异常排查 不管系统设计的多好,在实际应用中都可能会或多或少出现问题,比如电感选用不合适、触发 min-on time、触发 min-off time、输出电容 ESR 过大等,下面我们逐一进行讨论。 min-on time 虽然 MOS 管打开速度很快,但是打开始终是一个过程,要完成一个过程就必须需要一定的时间,当高频且压差大的情况下很容易触发完成「打开」这个过程的最小时间。也就是说占空比已经是实际最小了,占空比无法再降低了,所以查看输出电压纹波可能会出现下面的波形。 出现该波形的原因在于,占空比已经无法继续降低,所以电压整体处于逐渐抬高的趋势,当抬高到一定程度时即触发过压保护,上下管都关断,所以电压快速下降。 min-off time 与 min-on time 相对应的是 min-off time,当开关频率足够高且输入和输出电压接近时即容易出现此问题,此时即达到系统所能达到的最大占空比也无法满足负载所需要的电压,表现为输出电压无法达到设定值,负反馈分压电阻电压也低于电压基准值。 电感饱和电流过小 电感电流正常是一个三角波,但是如果电感饱和电流过小,则会电感电流将会变成下图很苗条的样子。因为电感电流饱和所以电流不再线性增加,电流快速增大导致磁通率减小,会导致磁性损耗增大、芯片热耗增大,而且这是一个正反馈过程,整个系统的可靠性会大大降低。 输出电容选用不合适 当输出电容选用过小时,会导致动态响应输出出现抖动。若输出电容的等效串联电阻(ESR)过大,也会导致输出纹波异常增大,这一点从前文的理论计算即可验证。因此在实际使用过程中需要同时考虑电容容值和所选电容的 ESR。 为什么需要 min-on time 占空比 D 控制相对于输入电压的输出电压,虽然通过提高开关频率有助于减小电感尺寸,但是也必须满足最小导通时间(min-on time)才能使芯片正常工作。那么这个 min-on time 是由哪些因素引起的呢? 因为上管中电流波形前沿的电流尖峰。由于 MOS 管也是由 PN 结组成,存在 PN 结就肯定存在结电容,MOS 管的寄生电容 CgsC_{gs}Cgs​ 和 CgdC_{gd}Cgd​ 会导致上管在导通时电流突然变化,也就是说会出现电流尖峰。如果在这个电流尖峰的时间段内去检测电流的话,很可能就会触发过流保护,因此开关电路的最小导通时间必须大于电流尖峰出现的时间,这个时间我们称之为消隐时间。 另一个原因是因为上下管开关完成后,由于键合线存在寄生电感的原因会产生很大的振铃,这个振铃同样可能会导致峰值电流检测出错,需要一个 min-on time 将这个振铃隔离过去。 为什么需要 min-off time 如下图所示,最简单的需要最小关断时间(min-off time)的原因是,若下管不打开则没有办法给自举电容充电,所以需要在该时间内给自举电容充电,为下一个开关周期做准备。 另一个原因是因为没有最小关断时间,即占空比 D 增大到 100%,那么就无法对负向电流、谷值电流进行采样,也就无法实现实现相应的异常保护功能。与 min-on time 一致,电流检测也需要一个 min-off time 隔离振铃。 为什么需要自举电容 DC-DC 的上 MOS 管可以是 PMOS,也可以是 NMOS。但是一般因为生产工艺问题,PMOS 导通电流往往做不不到很大,而在相同成本下 NMOS 的导通电流可以做到更大,也就是 RdsonR_{dson}Rdson​ 可以做到相对较低,所以往往更倾向于 NMOS。 将上管换为 NMOS 后也带来了新的问题,如何打开 NMOS ?如图所示,上管的 S 极连接 PH 点,该点的电压为 +5V,要打开 NMOS 需要 VGS>0V_{GS} > 0VGS​>0,驱动 MOS 管打开的压降需要 5V,那么驱动电压就需要 +10V 才可以打开上管,但是纵观整个电路并没有能达到 +10V 级别的电压,所以需要自举电容来进行升压才能打开上 MOS 管。 所以 DC-DC 芯片是否需要自举电容是由芯片所选用的 MOS 管类型决定的,若是 PMOS 则无需自举电容。
Read More ~

并查集详解及相关例题解析

参考内容: 图论——并查集(详细版) 并查集(Disjoint-set)是一种精巧的树形数据结构,它主要用于处理一些不相交集合的合并及查询问题。一些常见用途,比如求联通子图、求最小生成树的 Kruskal 算法和求最近公共祖先(LCA)等。 并查集的理念是只关注个体属于哪个阵营,并不关心这个阵营中个体内部的关系,比如我们常说的张三是李家沟的,王二是王家坝的。同时并查集借助个体代表集体的思想,用一个元素代表整个群体,就像我们开学都会有学生代表、教师代表讲话一样,在台上讲话的那一个学生就代表了学校所有的学生。 并查集基本操作 并查集的基本操作主要有初始化 init、查询 find和合并 union操作。 初始化 在使用并查集的时候,常常使用一个数组fa来存储每个元素的父节点,在一开始的时候所有元素与其它元素都没有任何关系,即大家相互之间还不认识,所以我们把每个元素的父节点设为自己。 #define ARR_LEN 6000 int fa[ARR_LEN]; void init(int n) { for(int i = 1; i <= n; i++) fa[i] = i; } 查询 查询即找到指定元素的祖先。需要注意的是,这里我们需要找到指定元素的根祖先,不能找到爸爸或者爷爷就停止了,而是要找到查找不下去了为止,所以要不断的去递归下去,直到找到父亲为自己的结点才结束。 int find(int i) { if(i == fa[i]) // 递归出口 return i; else return find(fa[i]); // 不断向上查找祖先 } 考虑下面的场景,假如第一次我们需要查询元素5的祖先,第二次需要查询元素4的祖先,会发现第一次查询包含了第二次查询的计算过程,但我们的程序却傻傻的计算了两次,有没有办法去来优化查询过程,让每一次查询都能利用到此前查询计算的便利? 考虑到并查集并不关心某个元素的爸爸、爷爷是谁,只关心最终的祖先是谁,所以我们可以在查询的过程中顺便做一些修改,比如在查询5的过程中,顺便就把4和2的父亲给修改为1,即我们在查找过程中进行路经压缩 int find(int i) { if(i == fa[i]){ return i; } else { fa[i] = find(fa[i]); // 进行路径压缩 return fa[i]; } } 合并 合并操作即介绍两个人相互认识,将他们纳入同一个帮派,只需要将俩元素的父亲修改为同一个即可。 void union(int i, int j) { int fa_i = find(i); int fa_j = find(j); fa[fa_i] = fa_j; } 相关练习题目 洛谷 P1551 亲戚 题目连接:https://www.luogu.com.cn/problem/P1551 题目描述 若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,现在给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系。 规定:xxx 和 yyy 是亲戚,yyy 和 zzz 是亲戚,那么 xxx 和 zzz 也是亲戚。如果 x,yx,yx,y 是亲戚,那么 xxx 的亲戚都是 yyy 的亲戚,yyy 的亲戚也都是 xxx 的亲戚。 输入格式 第一行:三个整数 n,m,p,(n,m,p≤5000)n,m,p,(n,m,p≤5000)n,m,p,(n,m,p≤5000) 分别表示有 nnn 个人,mmm 个亲戚关系,询问 ppp 对亲戚关系。 以下 mmm 行:每行两个数 Mi,Mj,1≤Mi,Mj≤nM_i,M_j,1≤M_i,M_j≤nMi​,Mj​,1≤Mi​,Mj​≤n,表示 MiM_iMi​ 和 MjM_jMj​ 具有亲戚关系。 接下来 ppp 行:每行两个数 Pi,PjP_i,P_jPi​,Pj​,询问 PiP_iPi​ 和 PjP_jPj​ 是否具有亲戚关系。 输出格式 ppp 行,每行一个Yes或No。表示第 iii 个询问的答案为“具有”或“不具有”亲戚关系。 输入输出样例 # 输入 6 5 3 1 2 1 5 3 4 5 2 1 3 1 4 2 3 5 6 # 输出 Yes Yes No 题目解析 可以发现这是一个非常标准的并查集问题,简直和并查集模版如出一辙,因此直接将所有关系读取后进行合并,然后直接查询父亲是否为同一个即可。 #include<bits/stdc++.h> using namespace std; #define ARR_LEN 6000 int fa[ARR_LEN]; void init(int n) { for(int i = 1; i <= n; i++) fa[i] = i; } int find(int i) { if(i == fa[i]){ return i; } else { fa[i] = find(fa[i]); return fa[i]; } } void union(int i, int j) { int fa_i = find(i); int fa_j = find(j); fa[fa_i] = fa_j; } int main() { int n, m, p; int a, b; cin>> n >> m >> p; init(n); for(int i = 0; i < m; i++){ cin >> a >> b; union(a, b); } for(int i = 0; i < p; i++){ cin >> a >> b; int fa_a = find(a); int fa_b = find(b); if(fa_a == fa_b) cout<<"Yes"<<endl; else cout<<"No"<<endl; } } 杭电 OJ1213 How Many Tables 题目连接:https://acm.hdu.edu.cn/showproblem.php?pid=1213 题目描述 Today is Ignatius' birthday. He invites a lot of friends. Now it's dinner time. Ignatius wants to know how many tables he needs at least. You have to notice that not all the friends know each other, and all the friends do not want to stay with strangers. One important rule for this problem is that if I tell you A knows B, and B knows C, that means A, B, C know each other, so they can stay in one table. For example: If I tell you A knows B, B knows C, and D knows E, so A, B, C can stay in one table, and D, E have to stay in the other one. So Ignatius needs 2 tables at least. 输入格式 The input starts with an integer T(1<=T<=25)T(1<=T<=25)T(1<=T<=25) which indicate the number of test cases. Then TTT test cases follow. Each test case starts with two integers NNN and M(1<=N,M<=1000)M(1<=N,M<=1000)M(1<=N,M<=1000). NNN indicates the number of friends, the friends are marked from 111 to NNN. Then MMM lines follow. Each line consists of two integers AAA and B(A!=B)B(A!=B)B(A!=B), that means friend AAA and friend BBB know each other. There will be a blank line between two cases. 输出格式 For each test case, just output how many tables Ignatius needs at least. Do NOT print any blanks. 输入输出样例 # 输入 2 5 3 1 2 2 3 4 5 5 1 2 5 # 输出 2 4 题目解析 分析可以发现,这个问题要我们做的是统计在所有元素合并之后,统计总共有多个和集合。很轻松就能写出下面的 AC 代码。类似的问题还有杭电 OJ1232 畅通工程。 读者大人可以在此基础上继续进行延伸,我们实际生活中每个桌子只能坐 8 个人,假设还需要考虑每桌人数的容量,又如何进行改进呢? #include<bits/stdc++.h> using namespace std; #define ARR_LEN 6000 int fa[ARR_LEN]; void init(int n) { for(int i = 1; i <= n; i++) fa[i] = i; } int find(int i) { if(i == fa[i]){ return i; } else { fa[i] = find(fa[i]); return fa[i]; } } void union(int i, int j) { int fa_i = find(i); int fa_j = find(j); fa[fa_i] = fa_j; } int main() { int n, m, a, b, t; cin>>t; for(int i = 0; i < t; i++){ cin>>n>>m; int ans = 0; init(n); for(int i = 0; i < m; i++) { cin>>a>>b; union(a, b); } for(int i = 1; i <= n; i++) { // 如果父亲是自己,那么就表示一个独立的集合 if(find(i) == i) ans++; } cout<<ans<<endl; } } 杭电 OJ1272 小希的迷宫 题目连接:https://acm.hdu.edu.cn/showproblem.php?pid=1272 题目描述 小希设计了一个迷宫让 Gardon 玩,首先她认为所有的通道都应该是双向连通的,就是说如果有一个通道连通了房间 A 和 B,那么既可以通过它从房间 A 走到房间 B,也可以通过它从房间 B 走到房间 A,为了提高难度,小希希望任意两个房间有且仅有一条路径可以相通(除非走了回头路)。小希现在把她的设计图给你,让你帮忙判断她的设计图是否符合她的设计思路。比如下面的例子,前两个是符合条件的,但是最后一个却有两种方法从 5 到达 8。 输入格式 输入包含多组数据,每组数据是一个以 0 0 结尾的整数对列表,表示了一条通道连接的两个房间的编号。房间的编号至少为 1,且不超过 100000。每两组数据之间有一个空行。整个文件以两个 -1 结尾。 输出格式 对于输入的每一组数据,输出仅包括一行。如果该迷宫符合小希的思路,那么输出Yes,否则输出No。 输入输出样例 # 输入 6 8 5 3 5 2 6 4 5 6 0 0 8 1 7 3 6 2 8 9 7 5 7 4 7 8 7 6 0 0 3 8 6 8 6 4 5 3 5 6 5 2 0 0 -1 -1 # 输出 Yes Yes No 题目解析 其实这个问题就是让我们判断一个连通图中是否存在环,那么问题就转换为寻找出现环的条件。其实不难发现出现下面两种情况时,连通图即存在环。 在查找过程中,发现两个不同元素的父亲是相同的; 若不存在环,则边的数量一定比顶点数量少 1。 #include<bits/stdc++.h> using namespace std; #define ARR_LEN 100010 int fa[ARR_LEN]; bool visited[ARR_LEN]; // 用于辅助记录顶点的数量 int edges, points; // 记录顶点和边的数量 bool hascycle; // 是否存在环 void init() { hascycle = false; edges = 0; points = 0; for(int i = 1; i < ARR_LEN; i++) fa[i] = i, visited[i] = false; } int find(int i) { if(i == fa[i]){ return i; } else { fa[i] = find(fa[i]); return fa[i]; } } void union(int i, int j) { int fa_i = find(i); int fa_j = find(j); // 两个元素祖先相同,存在环 if(fa_i == fa_j) { hascycle = true; } else { visited[i] = true; visited[j] = true; edges++; fa[fa_i] = fa_j; } } int main() { int a, b; init(); while(cin>>a>>b) { if(a == 0 && b == 0) { cout<<"Yes"<<endl; continue; } if(a == -1 && b == -1) { return 0; } union(a, b); while(cin>>a>>b){ if(a == 0 && b == 0) { break; } union(a, b); } if(hascycle) { cout<<"No"<<endl; continue; } for(int i = 1; i < ARR_LEN; i++){ if(visited[i]) { points++; } } if(points == edges + 1) { cout<<"Yes"<<endl; } else { cout<<"No"<<endl; } init(); } }
Read More ~

《算法竞赛进阶指南》165 小猫爬山题解

参考内容: [洛谷][noip][算法竞赛进阶指南]小猫爬山 《算法竞赛进阶指南》小猫爬山 小猫爬山 题目描述 题目链接:https://www.acwing.com/problem/content/167/ ​Freda 和 Rainbow 饲养了 N 只小猫。这天,小猫们要去爬山。经历了千辛万苦,小猫们终于爬上了山顶,但是疲倦的它们再也不想徒步走下山了(呜咕>_<)。 Freda 和 Rainbow 只好花钱让它们坐索道下山。索道上的缆车最大承重量为 W,而 N 只小猫的重量分别是C1、C2……Cn。当然,每辆缆车上的小猫的重量之和不能超过 W。每租用一辆缆车,Freda 和 Rainbow 就要付 1 美元,所以他们想知道,最少需要付多少美元才能把这 N 只小猫都运送下山? 输入格式 ​第一行包含两个用空格隔开的整数,N 和 W。接下来 N 行每行一个整数,其中第 i+1 行的整数表示第 i 只小猫的重量 Ci。 输出格式 输出一个整数,最少需要多少美元,也就是最少需要多少辆缆车。 分析解答 贪心 经过思考发现,我们只需要尽可能的在每辆车上都放更多的小猫,就能以最经济的方式把所有小猫都送下山。所以是一个非常明显的贪心题目,我们将所有小猫按重量排序,尽可能把肥猫先送下山即可。具体实现代码如下: #include<bits/stdc++.h> using namespace std; void cin_arr(int *num, int len) { for(int i = 0; i < len; i++){ cin>>num[i]; } } int slove(int *num, int n, int w) { int ans = 0; int remain = 0; int load = 0; sort(num, num+n); while(true){ for(int i = 0; i < n; i++){ // 连当前最小的猫都装不下,那么就新开一辆车 if(num[i] != -1 && remain < num[i]){ ans++; remain = w; break; } } for(int i = n-1; i >= 0; i--){ // 从大到小查找,尽可能装肥猫 if(num[i] != -1 && remain >= num[i]){ remain -= num[i]; // 运送走的小猫重量以 -1 表示 num[i] = -1; load++; break; } } // 如果所有小猫都运走了,那么当前 ans 就是答案 if(load >= n) return ans; } } int main() { int n, w; int cat[1000000]; cin>>n>>w; cin_arr(cat, n); cout<<slove(cat, n, w)<<endl; } 经过实际测试发现,盲目使用贪心思想的算法并不正确,例如如下测试用例。 6 16 9 5 5 5 4 3 贪心的结果是使用 3 辆车,分别为9+5、5+5+4、3;而正确的结果却是使用 2 辆车,分别为9+4+3和5+5+5。 深度优先搜索 既然贪心思想在这里行不通,那么我们就采用暴力搜索,即小猫可以放在现有任意一辆车上。具体实现代码如下: #include<bits/stdc++.h> using namespace std; #define N 2000 int n, w; int cat[N]; int sum[N] = {0}; // 第 i 辆车当前重量 int ans = N; void cin_arr(int *num, int len) { for(int i = 0; i < len; i++){ cin>>num[i]; } } void dfs(int cur_cat, int cur_car) { if(cur_car > ans) // 求最小值,不符合直接返回 return ; if(cur_cat == n) { // 所有小猫都上车了 ans = cur_car; return ; } for(int i = 0; i < cur_car; i++) { if(sum[i] + cat[cur_cat] <= w) { // 当前猫能放进去 sum[i] += cat[cur_cat]; // 当前猫占用重量 dfs(cur_cat+1, cur_car); // 继续放下一只猫 sum[i] -= cat[cur_cat]; // 把已经放进去的猫拿出来,因为是循环,所以放入下一辆车里面 } } // 新开一辆车,把当前这只猫放到新的车里面 sum[cur_car] = cat[cur_cat]; dfs(cur_cat+1, cur_car+1); sum[cur_car] = 0; // 把猫拿出来 } int main() { cin>>n>>w; cin_arr(cat, n); dfs(0, 0); cout<<ans<<endl; } 搜索优化 考虑到每次都是在车数量固定的情况下进行搜索的,那么少满足一次(sum[i] + cat[cur_cat] <= w)条件,就会少一次递归的调用,也即少一次搜索。那么如何能尽快使得程序尽快不满足该条件呢? 让sum[i]减小的速度加快就会减少搜索分支,即每次放更重一点的猫进去,就能达到效果。所以我们可以在进行搜索前将小猫的重量进行降序排序,这样从肥猫开始搜索就会减少分支。 #include<bits/stdc++.h> using namespace std; #define N 2000 int n, w; int cat[N]; int sum[N] = {0}; // 第 i 辆车当前重量 int ans = N; void cin_arr(int *num, int len) { for(int i = 0; i < len; i++){ cin>>num[i]; } } bool cmp(int a, int b) { return a > b; } void dfs(int cur_cat, int cur_car) { if(cur_car > ans) // 求最小值,不符合直接返回 return ; if(cur_cat == n) { // 所有小猫都上车了 ans = cur_car; return ; } for(int i = 0; i < cur_car; i++) { if(sum[i] + cat[cur_cat] <= w) { // 当前猫能放进去 sum[i] += cat[cur_cat]; // 当前猫占用重量 dfs(cur_cat+1, cur_car); // 继续放下一只猫 sum[i] -= cat[cur_cat]; // 把已经放进去的猫拿出来,因为是循环,所以放入下一辆车里面 } } // 新开一辆车,把当前这只猫放到新的车里面 sum[cur_car] = cat[cur_cat]; dfs(cur_cat+1, cur_car+1); sum[cur_car] = 0; // 把猫拿出来 } int main() { cin>>n>>w; cin_arr(cat, n); sort(cat, cat+n, cmp); // 反排序优化搜索 dfs(0, 0); cout<<ans<<endl; }
Read More ~

二叉树的前序、中序、后序、层序遍历

参考内容: 五分钟让你彻底理解二叉树的非递归遍历 Python实现二叉树的非递归遍历 二叉树遍历——深度优先(前中后序)+广度优先(层序遍历) 构造二叉树 定义二叉树结构如下 struct node { int data; node *left; node *right; }; 构造如下形态二叉树 node *init_tree() { node *node1 = (node *)malloc(sizeof(node)); node *node2 = (node *)malloc(sizeof(node)); node *node3 = (node *)malloc(sizeof(node)); node *node4 = (node *)malloc(sizeof(node)); node *node5 = (node *)malloc(sizeof(node)); node *node6 = (node *)malloc(sizeof(node)); node *node7 = (node *)malloc(sizeof(node)); node *node8 = (node *)malloc(sizeof(node)); node1->data = 1; node2->data = 2; node3->data = 3; node4->data = 4; node5->data = 5; node6->data = 6; node7->data = 7; node8->data = 8; node1->left = node2; node1->right = node3; node2->left = node4; node2->right = node5; node3->right = node6; node5->left = node7; node5->right= node8; return node1; } 前序遍历(递归) 前序遍历顺序为根左右。要遍历整个二叉树我们就需要遍历二叉树的每一个子树,对于任何一个子树它的遍历方式均为根左右顺序遍历。即所有子问题均与父问题除规模大小不同外,其余均相同。所以可以采用递归方式实现前序遍历。 // 前序遍历 根左右 void pre_order_traversal(node *root) { if(root) { cout<<root->data<<" "; pre_order_traversal(root->left); pre_order_traversal(root->right); } } 遍历结果为:1 2 4 5 7 8 3 6 中序遍历(递归) 中序遍历顺序为左根右。其与前序遍历仅顺序不同,其余均相同。 // 中序遍历 左根右 void in_order_traversal(node *root) { if(root) { in_order_traversal(root->left); cout<<root->data<<" "; in_order_traversal(root->right); } } 遍历结果为:4 2 7 5 8 1 3 6 后序遍历(递归) 后序遍历顺序为左右根。其与前序、中序遍历仅顺序不同,其余均相同。 // 后序遍历 左右根 void post_order_traversal(node *root) { if(root) { post_order_traversal(root->left); post_order_traversal(root->right); cout<<root->data<<" "; } } 遍历结果为:4 7 8 5 2 6 3 1 前序遍历方法一(非递归) 因为递归实际上是由系统帮我们进行压栈,所以理论上所有递归算法都可以改为循环+栈实现,那么我们先照着上述前序遍历的样子修改为循环+栈的形态。需要注意的是由于栈先进后出的特性,为了保证左孩子在右孩子前被访问,所以应该先右孩子入栈,再左孩子入栈。 // 前序遍历 根左右 void pre_order_traversal(node *root) { stack<node *> s; s.push(root); while(!s.empty()) { node *cur = s.top(); s.pop(); if(cur) { cout<<cur->data<<" "; s.push(cur->right); s.push(cur->left); } } } 遍历结果为:1 2 4 5 7 8 3 6 前序遍历方法二(非递归) 现在我们换一种思路来实现前序非递归遍历,仔细观察前序遍历的递归调用过程。 先把从根结点开始的所有左子树放入栈中; 弹出栈顶元素 如果栈顶元素有右子树,那么右子树入栈 重复上述过程直到栈为空 因此我们可以写出遍历代码 // 前序遍历 根左右 void pre_order_traversal(node *root) { stack<node *> s; node *cur = root; while(cur || !s.empty()) { // 将左子树全部入栈 while(cur) { cout<<cur->data<<" "; s.push(cur); cur = cur->left; } if(!s.empty()) { cur = s.top(); s.pop(); cur = cur->right; } } } 遍历结果为:1 2 4 5 7 8 3 6 中序遍历(非递归) 有了前面的基础,我们再来考虑中序遍历,会发现中序遍历与前序遍历只是打印结点的位置不一样。前序遍历是在结点入栈时打印,中序遍历只需要替换为在结点出栈时打印即可。 // 中序遍历 左根右 void in_order_traversal(node *root) { stack<node *> s; node *cur = root; while(cur || !s.empty()) { // 将左子树全部入栈 while(cur) { s.push(cur); cur = cur->left; } if(!s.empty()) { cur = s.top(); cout<<cur->data<<" "; s.pop(); cur = cur->right; } } } 遍历结果为:4 2 7 5 8 1 3 6 后序遍历方法一(非递归) 后序遍历相对来说显得更加复杂了。在前序和中序遍历中,只要左子树处理完毕实际上栈顶元素就可以出栈了,但后序遍历需要把左子树和右子树都处理完毕才能出栈,显然我们需要某种方法记录遍历的过程。 实际上我们只需要记录下遍历的前一个结点就能解决问题,因为通过前一个结点我们可以做如下判断: 如果前一个结点是当前结点的右子树,那么说明右子树已经遍历完毕可以出栈了 如果前一个结点是当前结点的左子树而且当前结点没有右子树,那么说明可以出栈了 如果当前结点即没有左子树也没有右子树,即为叶子结点,那么说明可以出栈了 若不属于上述情况,则依次将当前结点的右孩子和做孩子入栈,这样就能保证每次取栈顶元素时,左孩子都在右孩子前面被访问,左孩子和右孩子都在父结点前面被访问。 // 后序遍历 左右根 void post_order_traversal(node *root) { stack<node *> s; node *pre = NULL; node *cur = root; s.push(cur); while(!s.empty()) { cur = s.top(); // 叶子结点 if((!cur->left && !cur->right) // 叶子结点 || pre == cur->right // 前一个结点为当前结点右子树 || (pre == cur->left && !cur->right)) { // 前一个结点为当前结点左子树,且没有右子树 cout<<cur->data<<" "; pre = cur; s.pop(); } else { if(cur->right) s.push(cur->right); if(cur->left) s.push(cur->left); } } } 遍历结果为:4 7 8 5 2 6 3 1 后序遍历方法二(非递归) 后序遍历的顺序是左右根,如果把这个顺序倒过来就是根右左,是不是发现和前序遍历很像?那么我只需要按照根右左的方式遍历完,然后将遍历结果掉一个个儿就可以,而栈就具备掉个儿的功能,因此可写出如下代码。 // 后序遍历 左右根 void post_order_traversal(node *root) { stack<node *> s; stack<int> ans; node *cur = root; while(cur || !s.empty()) { // 将左子树全部入栈 while(cur) { ans.push(cur->data); s.push(cur); cur = cur->right; } if(!s.empty()) { cur = s.top(); s.pop(); cur = cur->left; } } while(!ans.empty()) { cout<<ans.top()<<" "; ans.pop(); } } 遍历结果为:4 7 8 5 2 6 3 1 层序遍历 层序遍历即广度优先遍历,使用队列即可实现。 // 层序遍历 void breadth_first_order_traversal(node *root) { queue<node *> q; q.push(root); while(!q.empty()){ node *cur = q.front(); q.pop(); if(cur){ cout<<cur->data<<" "; q.push(cur->left); q.push(cur->right); } } } 遍历结果为:1 2 3 4 5 6 7 8
Read More ~

动态规划实例——01 背包详解

题目描述 有 n 件物品,每件物品有一个重量和一个价值,分别记为 w1,w2,…,wn 和 c1,c2,…,cn。现在有一个背包,其容量为 wk,要从 n 件物品种任取若干件。要求:(1)重量之和小于或等于 wk;(2)价值之和最大。 输入: 共 3 行,第一行 2 个整数,表示 n 和 wk;第二行 n 个整数表示每一个物品的重量,第三行 n 个整数表示每一个物品的价值。 输出: 一行一个整数,表示符合背包容量的最大价值。 样例: 8 200 79 58 86 11 28 62 15 68 83 14 54 79 72 52 48 62 暴力枚举 我们以只有 A、B、C 三件物品的情况为例,对于每一个物品都存在拿和不拿两种情况。以0表示不拿当前物品,以1表示拿当前物品,可以有如下分析结果。 可能上面的图看起来不够清晰,我们从左至右逐一列举出来观察,一眼就可以看出来规律。其实就是十进制的 0、1、2、3、4、......可枚举的最大值即 2n-1。 000 001 010 011 100 101 110 111 根据上面的分析,我们可以写出如下代码。 #include<bits/stdc++.h> using namespace std; int main() { int n, wk; int w[10000], c[10000]; cin>>n>>wk; for(int i = 0; i < n; i++){ cin>>w[i]; } for(int i = 0; i < n; i++){ cin>>c[i]; } int ans = 0; int max_val = 1 << n; // 逐一枚举 for(int i = 0; i < max_val; i++){ int ww = 0, cc = 0; int index = 0; // 转二进制 int cur = i; while(cur){ int bit = cur % 2; // 若拿第 index 个物品,则累加其重量和价值 if(bit){ ww += w[index]; cc += c[index]; } cur = cur >> 1; index++; } //计算最大值 if(ww <= wk && ans < cc){ ans = cc; } } //输出最大值 cout<<ans<<endl; } 递归求解 我们把背包容量为wk,有n个物品可以选择的问题表示为slove(wk, n)。那么在背包剩余容量可以装下第 n 个物品时,该问题可以表示为求如下两个问题的最大值 选第 n 个物品:c[n-1] + slove(wk-w[n-1], n-1) 不选第 n 个物品:slove(wk, n-1) 在背包剩余容量无法装下第 n 个物品时,问题直接变为 不选第 n 个物品:slove(wk, n-1) 可以发现上述三个子问题可以继续向下拆分为规模更小,但类型一致的子子问题。于是可以写出如下递归求解代码。 #include<bits/stdc++.h> using namespace std; int w[30]={0}, c[30]={0}; // wk 背包剩余重量 // ch 可选项 int slove(int wk, int ch) { if(wk <= 0 || ch <= 0){ return 0; } // 若背包剩余容量无法装下 w[ch-1],则直接丢弃第 ch 个物品 if(w[ch-1] > wk){ return slove(wk, ch-1); } // 若背包剩余容量能装下 w[ch-1],则计算装和不装的最大值 int a = c[ch-1] + slove(wk-w[ch-1],ch-1); int b = slove(wk, ch-1); return a > b ? a : b; } int main() { int n, wk; cin>>n>>wk; for(int i = 0; i < n; i++){ cin>>w[i]; } for(int i = 0; i < n; i++){ cin>>c[i]; } cout<<slove(wk, n); } 动态规划 递归在执行过程中会存在重复计算相同子问题的情况,我们可以将其改为用循环实现,即动态规划的写法。dp[i][j]的含义即为:在背包容量为i,可选物品数量为j的情况下,符合背包容量的最大值。具体代码如下所示: #include<bits/stdc++.h> using namespace std; int w[30]={0}, c[30]={0}; int main() { int n, wk; cin>>n>>wk; for(int i = 0; i < n; i++){ cin>>w[i]; } for(int i = 0; i < n; i++){ cin>>c[i]; } int dp[1000001][21] = { 0 }; for(int i = 1; i <= wk; i++) { for(int j = 1; j <= n; j++) { // 若背包剩余容量无法装下 w[j-1],则直接丢弃第 j 个物品 if(w[j-1] > i) { dp[i][j] = dp[i][j-1]; } else { // 若背包剩余容量能装下 w[j-1],则计算装和不装的最大值 int a = c[j-1] + dp[i-w[j-1]][j-1]; int b = dp[i][j-1]; dp[i][j] = a > b ? a : b; } } } cout<<dp[wk][n]; }
Read More ~

Oracle 安装及 Spring 使用 Oracle

参考内容: docker安装oracle数据库史上最全步骤(带图文) Mac下oracle数据库客户端 Docker安装Oracle docker能安装oracle吗 Batch script for add a auto-increased primary key for exist table with records Docker 安装 Oracle11g 注意:下列安装方式仅适用于x86架构服务器,不适用于arm架构服务器。 # 拉取 oracle11,镜像有点大,需要花一些时间 docker pull registry.cn-hangzhou.aliyuncs.com/helowin/oracle_11g # 查看镜像是否拉取成功 docker images # 给镜像重新打 tag,原来的名字太长了 docker tag registry.cn-hangzhou.aliyuncs.com/helowin/oracle_11g oracle11g:latest # 启动 oracle11g 容器 docker run --name=oracle11g -itd -p 1521:1521 # 进入容器进行配置 docker exec -it oracle11g /bin/bash # 切换到 root 用户,密码为:helowin su root # 编辑配置文件 编辑/etc/profile,在其中增加如下内容: export ORACLE_HOME=/home/oracle/app/oracle/product/11.2.0/dbhome_2 export ORACLE_SID=helowin export PATH=$ORACLE_HOME/bin:$PATH 编辑完成后,需要刷新上述环境变量才能使用。 # 刷新环境变量 source /etc/profile # 创建软链接 ln -s $ORACLE_HOME/bin/sqlplus /usr/bin # 切换到 oracle 用户 su - oracle # 登陆 sqlplus sqlplus /nolog conn /as sysdba # 修改 system 用户密码 alter user system identified by system; # 修改 sys 用户密码 alter user sys identified by system; # 创建内部管理员账号 create user test identified by test; # 将 dba 权限授权给内部管理员账号和密码 grant connect,resource,dba to test; # 修改密码规则策略为密码永不过期 ALTER PROFILE DEFAULT LIMIT PASSWORD_LIFE_TIME UNLIMITED; # 修改数据库最大连接数据 alter system set processes=1000 scope=spfile; 修改上述信息后,需要重新启动数据库才会生效。 conn /as sysdba # 关闭数据库 shutdown immediate; # 启动数据库 startup; # 退出软链接 exit; 客户端连接 Oracle 以 Navicat 客户端为例,新建连接时按下图方式填写连接信息即可,密码即为system。需要注意的是,在 Windows 下选择 SID 或是服务名均可连接成功,但是在 Mac 下需要选择 SID 方式才能连接成功。 Oracle 实现主键自增 Oracle 在创建表的时候,不能像 MySQL 那样选择主键直接自增,但是我们可以通过给表创建序列和触发器去实现自增。下文以创建 USER 表为例。 -- 删除原有 USER 表 DROP TABLE "TEST"."USER"; -- 创建 USER 表 CREATE TABLE "TEST"."USER" ( "id" NUMBER NOT NULL, "gmt_create" DATE NOT NULL, "gmt_modified" DATE NOT NULL, "is_deleted" NUMBER NOT NULL, "login" NVARCHAR2(255) NOT NULL, "passwd" NVARCHAR2(255) NOT NULL, "nick" NVARCHAR2(255) NOT NULL, "phone" NVARCHAR2(255), "head_img" NVARCHAR2(255), "status" NVARCHAR2(255), "remark" NCLOB ); -- 删除原有序列 DROP SEQUENCE "TEST"."USER_SEQ"; -- 创建 USER_SEQ 序列,最小值为 1 CREATE SEQUENCE "TEST"."USER_SEQ" -- 最小值为 1 MINVALUE 1 -- 最大值为 9999999999999999999999999999 MAXVALUE 9999999999999999999999999999 -- 每次增加 1 INCREMENT BY 1 -- 将 20 个序列值放入缓存 CACHE 20; -- 创建触发器 CREATE TRIGGER "TEST"."USER_TRIGGER" -- 在插入数据前执行 BEFORE INSERT ON "TEST"."USER" -- 命名老数据为 OLD,新数据为 NEW REFERENCING OLD AS "OLD" NEW AS "NEW" -- 针对表的每一行都执行触发器 FOR EACH ROW -- 将序列值赋值给 id BEGIN :NEW."id" := USER_SEQ.NEXTVAL; END; / 需要注意的是,上面的/符号不能少。执行插入语句时可以发现,id会自动增加。 INSERT INTO "TEST"."USER" ("gmt_create", "gmt_modified", "is_deleted", "login", "passwd", "nick", "phone", "head_img", "status", "remark") VALUES (TO_DATE('2023-04-01 00:00:00', 'SYYYY-MM-DD HH24:MI:SS'), TO_DATE('2023-04-01 17:04:30', 'SYYYY-MM-DD HH24:MI:SS'), '0', 'user', '123', 'Jack', '1111', 'head.jpg', '激活', '测试'); Java Spring+Mybatis 使用 Oracle 及配置分页 application.properties文件配置信息: # mybatis spring.datasource.driver-class-name=oracle.jdbc.driver.OracleDriver spring.datasource.url=jdbc:oracle:thin:@8127.0.0.1:1521:helowin spring.datasource.username=system spring.datasource.password=system mybatis.mapper-locations=classpath*:mybatis/*.xml mybatis.configuration.log-impl=org.apache.ibatis.logging.stdout.StdOutImpl # pageHelper pagehelper.helperDialect=oracle pagehelper.reasonable=true pagehelper.supportMethodsArguments=true pagehelper.params=count=countSql pom.xml配置文件关键信息。 <?xml version="1.0" encoding="UTF-8"?> <project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 https://maven.apache.org/xsd/maven-4.0.0.xsd"> <properties> <java.version>1.8</java.version> <maven.compiler.target>1.8</maven.compiler.target> <maven.compiler.source>1.8</maven.compiler.source> <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding> <project.reporting.outputEncoding>UTF-8</project.reporting.outputEncoding> <spring.boot-version>2.1.3.RELEASE</spring.boot-version> </properties> <dependencyManagement> <dependencies> <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-dependencies</artifactId> <version>${spring.boot-version}</version> <type>pom</type> <scope>import</scope> </dependency> <dependency> <groupId>org.mybatis.spring.boot</groupId> <artifactId>mybatis-spring-boot-starter</artifactId> <version>2.1.0</version> </dependency> <dependency> <groupId>com.oracle.ojdbc</groupId> <artifactId>ojdbc8</artifactId> <version>19.3.0.0</version> </dependency> <dependency> <groupId>com.github.pagehelper</groupId> <artifactId>pagehelper-spring-boot-starter</artifactId> <version>1.4.3</version> </dependency> <dependency> <groupId>com.github.pagehelper</groupId> <artifactId>pagehelper-spring-boot-starter</artifactId> </dependency> </dependencies> </dependencyManagement> </project>
Read More ~

动态规划实例——换零钱的方法数(C++详解版)

原写了 Java 版本的如何求解换钱的方法数,近期进行了一些细节上的补充,以及部分错误更正,将语言换为了 C++ 语言。 基础题目 假设你现在拥有不限量的 1 元、5 元、10 元面值纸币,路人甲希望找你换一些零钱,路人甲拿出的是一张 100 元面值的纸币,试求总共有多少种换零钱的方法? 分析:因为总共只有 3 种面值小额纸币,所以将所有可能进行枚举,直接暴力解决即可。 #include<bits/stdc++.h> using namespace std; int slove() { int ans = 0; // 10 元张数 for(int i = 0; i <= 10; i++) { // 5 元张数 for(int j = 0; j <= 20; j++) { // 1 元张数 for(int k = 0; k <= 100; k++) { int cur = i*10 + j*5 + k*1; if(cur == 100) { ans++; } } } } return ans; } int main() { cout<<slove(); } 递归求解 基础题目中是拥有固定种类的小额纸币,即使再多几种小额纸币也没关系,大不了在嵌套几个循环就能解决。现在需要将题目的难度加大一点,改为小额纸币的种类和需要换零钱的总额由用户输入,即小额纸币种类和总额都不在固定,那么如何解决? 输入共有三行: 第一行:小额纸币种类数量 第二行:不同小额纸币的面值 第三行:需要换零钱的总额 分析:虽然现在种类和总额都是变量了,但是上文中的基础版本还是被包含在此问题中,所以我们还是以上文中的 1 元、5 元、10 元换 100 元进行分析,找一找除了枚举是否还有其他方法解决。 我们先固定一种零钱的数量,剩下的钱用剩余零钱去兑换,即: 用 0 张 1 元换,剩下的用 5、10 元换,最终方法数为 count0; 用 1 张 1 元换,剩下的用 5、10 元换,最终方法数为 count1; ...... 用 100 张 1 元换,剩下的用 5、10 元换,最终方法数为 count100; 那么最终换钱的方法综述即为count0 + count1 + count2 + ... + count100。 上面的分析中,我们把原来的大问题拆为了 101 个小问题,且每一个小问题都有很相似的地方,即: 求用 5、10 元换 100 元的方法数 求用 5、10 元换 95 元的方法数 ...... 求用 5、10 元换 0 元的方法数 如果我们对这 101 个小问题再进行同样思路的分析,即再固定 5 元零钱的数量,那么就能把问题划分成了规模更小,但问题类型一样的小小问题。即递归的思路,可以写出如下代码。 #include<bits/stdc++.h> using namespace std; int money[1000]; // money 表示所有小额纸币的面值 int len; // len 表示 money 数组的长度,即:小额纸币种类 // index 表示上文分析中的当前固定第几张 // target 表示现在要兑换的钱的总额 int slove(int index, int target) { int ans = 0; if(index == len) { ans = target == 0 ? 1 : 0; } else { for(int i = 0; i*money[index] <= target; i++) { // 剩余待换零钱的总额 int cur_total = target-(i * money[index]); ans = ans + slove(index+1, cur_total); } } return ans; } int main() { int target; cin>>len; // 零钱种类 for(int i = 0; i < len; i++){ cin>>money[i]; } cin>>target; // 兑换总额 cout<<slove(0, target); } 优化递归 可以发现上文所写的递归代码存在大量的重复过程,比如下面两种情况,后面所求的子问题是完全一样的,导致程序运行时间的浪费。 已经使用了 5 张 1 元、0 张 5 元,剩下的 95 元用 5 元和 10 元兑换 已经使用了 0 张 1 元、1 张 5 元,剩下的 95 元用 5 元 和 10 元兑换 既然前面已经求解过相同的子问题了,那么我们是否可以在第一次求解的时候,将计算结果保存下来,这样下次遇到相同子问题的实际,直接查出来用就可以,省去再次求解的时间。 #include<bits/stdc++.h> using namespace std; int money[1000]; // money 表示所有小额纸币的面值 int len; // len 表示 money 数组的长度,即:小额纸币种类 // 用于存储子问题的解 int val_map[1000][1000] = { 0 }; // 0 表示该子问题没有算过 // -1 表示算过,但该子问题无解 // 其它值,即此子问题的方法数 int slove(int index, int target) { int ans = 0; if(index == len) { ans = target == 0 ? 1 : 0; } else { for(int i = 0; i*money[index] <= target; i++) { // 剩余待换零钱的总额 int cur_total = target-(i * money[index]); int pre_val = val_map[index+1][cur_total]; // 如果 val 为 0,说明该子问题没有被计算过 if(pre_val == 0) { ans = ans + slove(index+1, cur_total); } else { ans += pre_val == -1 ? 0 : pre_val; } } } // 存储计算结果 val_map[index][target] = ans == 0 ? -1 : ans; return ans; } int main() { int target; // 零钱种类 cin>>len; for(int i = 0; i < len; i++){ cin>>money[i]; } cin>>target; cout<<slove(0, target); } 动态规划 上面对递归的优化方案已经能看出来动态规划的影子了,沿着前文先计算再查表的思路继续思考,我们能否提前把所有子问题都计算出答案,对每个子问题都进行查表解决。也即将最初的递归方案改为循环的实现。 所有的递归都能改为循环实现 #include<bits/stdc++.h> using namespace std; int money[1000]; // money 表示所有小额纸币的面值 int len; // len 表示 money 数组的长度,即:小额纸币种类 // 用于存储子问题的解 // val_map[i][j] 表示用 money[0...i] 的小面额零钱组成 j 元的方法数 int val_map[1000][1000] = { 0 }; int slove(int target) { // 第一列表示组成 0 元的方法数,所以为 1 for (int i = 0; i < len; i++) { val_map[i][0] = 1; } // 第一行表示只使用 money[0] 一种钱币兑换钱数为i的方法数 // 所以是 money[0] 的倍数的位置为 1,否则为 0 for (int i = 1; money[0]*i <= target; i++) { val_map[0][money[0]*i] = 1; } for (int i = 1; i < len; i++) { for (int j = 1; j <= target; j++) { for (int k = 0; j >= money[i]*k; k++) { /* val_map[i][j] 的值为: 用 money[0...i-1] 的零钱组成 j 减去 money[i] 的倍数的方法数 因为相比 val_map[i-1][j],只是多了一种零钱的可选项 */ val_map[i][j] += val_map[i-1][j-money[i]*k]; } } } return val_map[len-1][target]; } int main() { int target; cin>>len; for(int i = 0; i < len; i++){ cin>>money[i]; } cin>>target; cout<<slove(target); } 动归优化 在上文第一版动态规划代码的优化中已经能发现,其实val_map[i][j]的值由两部分组成,分别为: 用 money[0...i-1] 的零钱组成换 j 元的方法数 用 money[0...i-1] 的零钱换 j-money[i]*k(k=1,1,2,3....)元的方法数之和 对于第二种情况来说,其累加值实际上就是val_map[i][j-money[i]],即用money[0...i]的零钱换 j-money[i]元的方法数。至于具体为什么累加值与val_map[i][j-money[i]]相等,我们可以借助递归方法时的分析方式进行理解。 用 money[0...i-1] 的零钱组成换 j 元的方法数对应: 用 0 张 money[i] 换,剩下的用 money[0...i-1] 换 用 money[0...i-1] 的零钱换 j-money[i]*k(k=1,1,2,3....)元的方法数之和对应: 用 1 张 money[i] 换,剩下的用 money[0...i-1] 换 用 2 张 money[i] 换,剩下的用 money[0...i-1] 换 ...... 所以第二部分的值即为val_map[i][j-money[i]]。依据此处的分析,我们可以在原有基础上去掉第三层循环,减少程序运行所花费的时间。 #include<bits/stdc++.h> using namespace std; int money[1000]; int len; int val_map[1000][1000] = { 0 }; int slove(int target) { for (int i = 0; i < len; i++) { val_map[i][0] = 1; } for (int i = 1; money[0]*i <= target; i++) { val_map[0][money[0]*i] = 1; } for (int i = 1; i < len; i++) { for (int j = 1; j <= target; j++) { val_map[i][j] = val_map[i-1][j]; // 此处需要比较 j 的大小,防止数组越界 // 注意条件时 >= ,否则少计算 j 刚好为 money[i] 的情况 if(j >= money[i]) { val_map[i][j] += val_map[i][j-money[i]]; } } } return val_map[len-1][target]; } int main() { int target; cin>>len; for(int i = 0; i < len; i++){ cin>>money[i]; } cin>>target; cout<<slove(target); } 空间压缩 仔细观察能发现,每一次更新val_map[i][j]的值时,它只依赖于上一行和当前这一行前面的元素。对于我们所求解的问题来说,它仅要求我们给出最终的答案即可,那么前面存储中间结果的那些元素实际上就会空间的浪费,因此我们可以思考一下如何在空间上进行压缩。 实际上我们只需要定义一个一维的数组,采用一些技巧对该数组进行滚动更新,按照合适的方向去更新数组,同样可以达到上面使用二维数组的效果。 #include<bits/stdc++.h> using namespace std; int money[1000]; int len; int val_map[1000] = { 0 }; int slove(int target) { // 第一行,只用 money[0] 换零钱 // 所以只能换 money[0] 倍数的钱 for (int i = 0; money[0]*i <= target; i++) { val_map[money[0] * i] = 1; } for (int i = 1; i < len; i++) { for (int j = 1; j <= target; j++) { if(j >= money[i]) { // 在进行下面一步前 val_map[j] 的值就已经是 val_map[i-1][j] 了 val_map[j] += val_map[j-money[i]]; } } } return val_map[target]; } int main() { int target; cin>>len; for(int i = 0; i < len; i++){ cin>>money[i]; } cin>>target; cout<<slove(target); }
Read More ~