精华内容
下载资源
问答
  • 目录 一、分布式事物:本地...(2)阶段提交协议3PC (二)对于微服务,传统分布式事务存在的问题 二、CAP理论和BASE思想 1.CAP理论 一致性Consistency: 可用性Availability: 分区容错性PartitionToler...

    目录

    一、分布式事物:本地事务和分布式事务(2PC+3PC)+传统分布式事务的问题

    (一)本地事务和分布式事务(2PC+3PC)

    (1)两阶段提交协议2PC

    (2)三阶段提交协议3PC

    (二)对于微服务,传统分布式事务存在的问题

    二、CAP理论和BASE思想

    1.CAP理论

    一致性Consistency:

    可用性Availability:

    分区容错性PartitionTolerance:

    2.BASE思想

    BasicallyAvailiable(基本可用):

    SoftState(软状态):

    EventualConsistency(最终一致性):

    3.CAP理论和BASE思想的关联性

    三、可靠事件模式

    1.基本思路

    (1)用户下单

    (2)交易支付

    (3)订单更新

    2.关键点

    3.解决方案

    4.实现策略

    (1)事件确认组件

    (2)事件恢复组件

    (3)实时消息传递组件

    四、补偿模式

    1.基本思路

    2.关键点

    3.解决方案

    五、Sagas长事务模式--错误管理模式,同时用于控制复杂事务的执行和回滚

    1.基本思路

    2.解决方案

    六、TCC模式

    1.基本思路

    2.解决方案

    3.实现策略

    七、最大努力通知模式

    1.基本思路

    2.解决方案

    八、人工干预模式

    1.基本思路

    2.解决方案

    九、数据一致性模式总结

    参考书籍、文献和资料:


    一、分布式事物:本地事务和分布式事务(2PC+3PC)+传统分布式事务的问题

    (一)本地事务和分布式事务(2PC+3PC)

    传统单体应用一般都会使用一个关系型数据库,好处是使用ACID事务特性,保证数据一致性只需要开启一个事务,然后执行更新操作,最后提交事务或回滚事务。更方便的是可以以借助于Spring等数据访问技术和框架后只需要关注引起数据改变的业务本身即可。

    但是随着组织规模不断扩大、业务量不断增加,单块应用不足以支持庞大业务量和数据量,就需要对服务和数据进行拆分,拆分后就会出现两个或两个以上的数据库的情况,此时不能依靠本地事务得以解决,需要借助于分布式事务来保证一致性,常说的就是保持强一致性的两阶段提交协议和三阶段提交协议。

    (1)两阶段提交协议2PC

    准备阶段:由协调者提议并收集其他节点参与者的反馈(提议的节点为协调者,参与决议的节点为参与者)。

    执行阶段:根据反馈决定提交或中止事务。

    如图,协调者发起一个提议分别询问各参与者是否接受场景,然后协调者根据参与者的反馈,提交或中止事务。

    注意:只有当所有参与者都同意才提交,否则只有有一个不同意就中止。            

    但是,2PC有其固有的三大问题:

    问题一:同步阻塞问题

    执行过程中,所有参与者都是事务阻塞型的。当参与者占用公共资源时,其他第三方节点访问公共资源就不得不处于阻塞状态。

    问题二:单点故障

    一旦协调者发生故障,参与者会一直阻塞下去。特别是在第二阶段,协调者发生故障,则所有参与者还处于锁定资源的状态中,但是无法完成后续的事务操作。

    问题三:数据不一致

    当协调者向参与者发送提交请求后发生了局部网络异常,或者在发送提交请求过程中协调者发生了故障,就会导致只有一部分参与者接收到了提交请求,这部分参与者接到请求后就会执行提交操作,而未接收到提交请求的机器就无法执行事务提交,于是就出现了数据不一致的问题。

    (2)三阶段提交协议3PC

    与2PC相比,3PC主要有两个改动点:在协调者和参与者之间都引入了超时机制+把准备阶段一分为二

    3PC:CanCommit + PreCommit + DoCommit,具体操作如下

    CanCommit阶段:协调者向参与者发送提交请求,参与者如果可以提交就返回Yes响应,否则返回No响应。

    PreCommit阶段:协调者根据参与者的响应情况来决定是否可以进行事务的PreCommit操作。

    如果协调者从所有参与者获得反馈都是Yes响应,那么就执行事务的预执行;

    如果有任何一个参与者向协调者发送了No响应,或者等待超时后没有收到参与者的响应,那么就执行事务的中断。

    DoCommit阶段:执行提交或中断事务。当协调者没有收到参与者发送的ACK响应,就会执行中断事务。

    可见,3PC主要解决了2PC的单点问题和同步阻塞问题。

    (二)对于微服务,传统分布式事务存在的问题

    在微服务架构中,传统分布式事务并不是实现数据一致性的最佳选择,主要有三大问题:

    问题一:对于微服务架构来说,数据访问变得更加复杂,为达到微服务间的松耦合和高度独立,数据是微服务私有的,唯一可访问的方式就是通过API,采用2PC/3PC难度太大。

    问题二:不同的微服务经常使用不同的数据库,但是在微服务架构中,服务会产生不同类型的数据,关系数据库不一定是最佳选择,很多微服务会采用SQL和NoSQL结合模式,如搜索引擎、图数据库等NoSQL数据库大多数都不支持2PC/3PC。

    问题三:当数据被拆分了或者在不同的数据库存在重复数据的时候,锁定资源和序列化数据来保证一致性就会变成一个非常昂贵的操作,会给系统的吞吐量以及扩展性带来巨大的挑战。

    对于微服务架构,建议采用一种更为松散的方式来维护一致性,也就是所谓的最终一致性,对于开发者而言,实现最终一致性的方案可以根据不同的业务场景做不同的选择。

    二、CAP理论和BASE思想

    1.CAP理论

    指的是在一个分布式系统中,无法同时实现一致性Consistency、可用性Availability和分区容错性PartitionTolerance。

    对于典型分布式系统而言,如图所以,这三个概念可以做以下解释:

    一致性Consistency:

    指分布式系统中的所有数据备份在同一时刻是否拥有同样的值。

    可用性Availability:

    指在集群中一部分节点故障后,集群整体是否还能正常响应请求。

    分区容错性PartitionTolerance:

    相当于通信的时限要求,系统如果不能在一定时限内达到数据一致性,就意味着发生了分区情况,也就是说整个分布式系统就不在互联了。

    由于当前网络硬件肯定会出现延迟丢包等通信异常问题,三态性不可避免,所以分区容错性必须实现。

    2.BASE思想

    BASE=BasicallyAvailiable(基本可用)+SoftState(软状态)+EventualConsistency(最终一致性)

    BASE理论是对CAP理论的延伸,基本思想是即使无法做到强一致性,应用可以采用适合的方式达到最终一致性。

    BasicallyAvailiable(基本可用):

    指分布式系统在出现故障的时候,可以损失部分可用性,需要保证和核心可用。服务限流和降级就是其基本表现。

    SoftState(软状态):

    指允许系统存在中间状态,而中间状态不会影响整体可用状态。分布式存储中一般一份数据都有有若干个副本,允许不同节点间副本同步的延时就是软状态的体现。

    EventualConsistency(最终一致性):

    指系统中所有的数据副本经过一定时间后,最终能够达到一致的状态。

    CAP的一致性就是强一致性,这种一致性级别是最符合用户直觉的,用户体验好,但实现起来对系统性能影响较大弱一致性正好相反。BASE中的最终一致性可以看做是弱一致性的一种特殊情况。

    3.CAP理论和BASE思想的关联性

    CAP理论和BASE思想实际上是有关联的,基本关系如图所示:                                                          

    CAP理论和BASE思想讨论的意义在于即使无法做到强一致性,我们也可以采用合适的方式达到最终一致性,这点对微服务架构很重要。最终一致性的方法重要有以下六种分别讲解。

    在微服务架构中,比如,对于一个完整的下单操作而言,订单服务和支付服务都是业务闭环中的一部分,在一个完整的业务操作流程中需要保证各自数据的正确性和一致性。

    三、可靠事件模式

    1.基本思路

    尝试将订单和支付两个微服务进行分别管理,并需要一个媒介用于这两个微服务之间进行数据传递,一般而言,消息中间件MOM适合扮演数据传递媒介的角色。引入消息中间件后下单操作流程可以拆分为如下三个步骤:

    (1)用户下单

    当用户使用订单服务下单时,一方面订单服务需要对所产生的订单数据进行持久化操作,另一方面,也需要同时发送一条创建订单的消息到消息中间件。

    (2)交易支付

    当消息中间件接收到订单创建消息,就会把消息发送到支付服务。

    支付服务接收到订单创建消息后,同样对该消息进行业务处理并持久化。当所有关于支付相关的业务逻辑执行完成以后,支付服务需要向消息中间件发送一条支付成功的消息。

    (3)订单更新

    支付成功消息通过消息中间件传递到订单服务时,订单服务根据支付的结果处理后续业务流程,一般涉及订单状态更新、向用户发送通知内容等内容。

    2.关键点

    对于以上三个闭环管理,仔细分析整个过程,不难发现存在如下三个基本问题:

    (1)某个服务在更新了业务实体后发布消息失败;

    (2)服务发布事件成功,但是消息中间件未能正确推送事件到订阅的服务;

    (3)接受事件的服务重复消费事件。

    针对第三个问题,是最为容易解决的,一般处理方法是由业务代码控制幂等性,例如支付服务传入一个订单时,可以通过判断该订单所对应的唯一ID是否已经处理方式来避免对其再次处理。

    但是前两个问题概括起来就是要解决消息传递的可靠性问题,这个是可靠性事件模式实现数据最终一致性的关键点。要做到可靠消息传递,需要消息中间件确保至少投递一次消息,目前主流的消息中间件都支持消息持久化和至少一次投递的功能。所以,我们需要考虑的是,如何原子性的完成业务操作和发布消息。

    订单服务同时需要处理数据持久化和消息发送两个操作,这就需要考虑两个场景:

    (1)如果数据持久化操作失败,显然消息不该被发送;

    (2)如果数据持久化操作成功,但消息发送失败,那么已经被持久化的数据需要被回滚以还原到初始状态。

    对应这两个场景基本实现流程图如下:

    在逻辑上是可行的,但在运行中,需要考虑很多意想不到的场景,主要有以下两个实际问题:

    (1)实际问题一:典型的依旧是分布式环境下所固有的网络通信异常问题,消息中间件返回通信发生故障,如下图分析:              

    (2)实际问题二:订单服务投递消息后等待消息返回,当消息返回时,订单服务挂了,也会导致数据不一致,如下图分析:

    3.解决方案

    解决上面的问题可以使用一个本地事件表。

    微服务在进行业务操作时需要将业务数据和事件保存在同一个本地事务中,由本地事务保证更新业务和发布事件的原子性。

    发布的事件被保存在本地事务表中,然后该服务实时发布一个事件通知关联的业务服务,如果事件发布成功则立即删除本地事件表中的事件。      

    由于事件消息发布可能会失败或无法获取返回结果,我们需要使用一个额外的“事件恢复”服务来恢复事件,该事件恢复服务定时从事件表中恢复未发布成功的事件并重新发布,只有重新发布才删除保存在本地事件表中的事件。

    注意,事件恢复服务保证了事件一定会被发布,从而确保数据的最终一致性。

    4.实现策略

    在实现上,首先考虑在可靠事件模式中存在一个事件生产者。该事件生产者处于操作的主导地位, 并根据业务操作通过事件的方式发送业务操作的结果(在上例中,订单服务就是事件的生产者),其次,事件消费者是被动方,负责根据事件来处理自身业务逻辑(上例中的支付服务属于事件消费者)。

    有了事件生产者和事件消费者后,我们关注事件服务,事件服务的主要作用就是管理本地事件表,它能存储、确认并发送事件,同时根据不同状态查询事件信息并确定事件已被事件消费者成功消费。事件服务有三大组件:       

    (1)事件确认组件

    表现为一种定时机制,用于处理事件没有被成功发送的场景。

    例如,订单服务在完成业务操作之后需要发送事件到本地事件表,如果这个过程中事件没有发送成功,我们就需要对这些事件重新发送,这个过程为事件确认。

    (2)事件恢复组件

    同样表现为一种定时机制,根据本地事件表中的事件状态,专门处理状态为已确认但还没有成功消费且已超时的事件。

    基本的事件恢复策略就是向消费者重新发送事件,并在消费成功后更新事件状态,并在本地事件表中进行逻辑删除。

    (3)实时消息传递组件

    基于特定的消息中间件工具和框架将事件作为消息进行发送的组件。

    目前可供选择的主流消息中间件包括RabbitMQ、ActiveMQ、RocketMQ、Kafka等。

    四、补偿模式

    1.基本思路

    基本思路在于使用一个额外的补偿服务来协调各个需要保证一致性的微服务,补偿服务按顺序依次调用各个微服务,如果某个微服务调用失败就撤销之前所有已经完成的微服务,补偿服务对需要保证一致性的微服务提供补偿操作。

    举例当中涉及两个微服务,订单微服务和支付微服务,为其提供补偿操作,如果支付服务失败,就需要取消之前的下单服务。

    为降低开发的复杂性和提高效率,补偿服务通常实现为一个通用的补偿框架,补偿框架提供服务编排和自动完成补偿的能力。

    2.关键点

    对于补偿服务而言,所有服务的操作记录是一个关键点,操作记录是执行取消操作的前提。

    举例中,订单服务与支付服务需要保存详细的操作记录和日志,这些日志和记录有助于确定失败的步骤和状态,进而明确需要补偿的范围,然后获取所需补偿的业务数据。

    如果只是订单服务失败,那么只需要补偿一个服务就可以,如果支付服务也失败了,对两个服务进行回滚。

    补偿操作要求业务数据包括支付时的业务流水号、账号和金额。理论上可以根据唯一的业务流水号就能完成补偿操作,但提供更多的数据有益于微服务健壮性。

    3.解决方案

    实现补偿模式的关键要素就是记录完整的业务流水,可以通过业务流水为补偿操作提供需要的业务数据。

    补偿服务可以从业务流水的状态中知道补偿的范围,补偿过程中需要的业务数据同样可以从记录的业务流水中获取。

    补偿服务作为一个服务调用过程同样存在调用不成功的情况,需要通过一定的健壮性机制来保证补偿的成功率,补偿的相关操作本身需要具有幂等性。

    补偿服务健壮性策略:需要根据服务执行失败的原因来选择不同的重试策略,如图所示:                                         

    (1)服务重启:如果失败的原因不是暂时的,而是由业务因素导致的业务错误,需要对问题进行修正后重新执行。

    (2)立即重试:对于网络失败或数据库锁等瞬时异常,重试在很大程度上能够确保任务正常执行。

    (3)定时调用:一般会指定调用的次数上限,如果调用次数达到上限也就不再进行重试。

    如果通过服务重启、立即重试、定时调用等策略依旧不能解决问题,则需要通知相关人员进行处理,即人工干预模式。

    五、Sagas长事务模式--错误管理模式,同时用于控制复杂事务的执行和回滚

    1.基本思路

    长时间持续的事务无法简单地通过一些典型的ACID模型以及使用多段提交配合持有锁的方式来实现。Sagas用于解决这个问题,和多段式分布式事务处理不同,Sagas会将工作分成单独的事务,包含正常额操作和回滚的操作。

    对于开发者而言,不是将所有微服务都定义为分布式的ACID事务,以下单行为为例,将其定义为一个整体,其中包含如何去生成订单以及如何去取消订单,对于支付而言也需要提供同样的逻辑。

    可以将订单和支付服务组合在一起构成一个服务链,然后将整个服务链加密,这样只有该服务链的接收者才能够操控这个服务链。

    当一个服务完成后,会将完成的信息记录到一个集合中,之后可以通过这个集合访问到对应的服务。

    当一个服务失败时,服务本身将本地清理完毕并将消息发送给该集合,从而路由到之前执行成功的服务,然后回滚所有的事务。

    2.解决方案

    在Sagas事务模型中,一个长事务是由一个预定义好执行顺序的子事务集合和他们对应的补偿子事务集合所组成。

    典型的一个完整的交易由T1、T2、......、Tn等多个业务活动组成,每个业务活动可以是本地操作或者是远程操作,而每个业务活动都有对应的取消活动C1、C2、......、Cn。

    所有的业务活动在Sagas事务下要么全部成功,要不全部回滚,不存在中间状态。对于一个Sagas链路而言,各个业务活动执行过程中都会依赖上下文,每个业务活动都是一个原子操作,并提供执行和取消两个入口。

    需要设计一个存储模型来保存执行上下文并通过该存储模型来索引到对应的服务。

    存储模型中包含两个内部结构,一个是完成的任务,一个是等待执行的任务。如果成功就会将任务向前执行,如果失败就向后执行。

    实现上的一种思路可以采用队列和栈数据结构,一方面使用队列来向前执行,另一方面使用栈来向后执行。

    注意,当执行取消操作进行事务操作失败时需要记录失败事务日志,通过重试策略进行重试,对重试失败的执行定时重试,在有问题时则进行人工干预。

    六、TCC模式

    1.基本思路

    一个完整的TCC业务由一个主服务和若干个从服务组成,主服务发起并完成整个业务流程。

    从服务提供三个接口:Try、Confirm、Cancel:

    Try接口:完成所有业务规则检查,预留业务资源。

    Confirm接口:真正执行业务,其自身不做任何业务检查,只使用Try阶段预留的业务资源,同时该操作需要满足幂等性。

    Cancel接口:释放Try阶段预留的业务资源,同样也需要满足幂等性。

    举例来看,订单系统拆分成订单下单和订单支付两个场景,使用TCC模式后执行效果如下:

    (1)Try阶段:尝试执行业务。

    一方面完成所有业务检查,如针对该次订单下单操作,需要验证商品的可用性以及用户账户金额是否够。

    另一方面需要预留业务资源,如把用户账户余额进行冻结用于支付该订单,确保不会出现其他并发进程扣减账户余额导致后续支付无法进行。

    (2)Confirm阶段:执行业务。

    Try阶段一切正常,则执行下单操作并扣除用户账号中的支付金额。

    (3)Cancel阶段:取消执行业务。

    释放Try阶段预留的业务资源,如果Try阶段部分成功,如商品可用且正常下单,但账户余额不够而冻结失败,则需要对产品下单做取消操作,释放被占用的该商品。

    2.解决方案

    TCC服务框架不需要记录详细的业务流水,完成Confirm和Cancel操作的业务由业务服务提供。

    TCC模式同样有两个阶段组成

    第一阶段:

    主业务服务分别调用所有从业务的Try操作,并在活动管理器中登记所有从业务服务。当所有从业务服务的Try操作都调用成功或者某个从业务的Try操作失败,进入第二个阶段。

    第二阶段:

    主业务根据第一阶段的执行结果来执行Comfirm或Cancel操作。

    如果第一阶段所有Try操作都成功,则主业务服务调用所有从业务活动的Confirm操作。

    如果第一阶段中失败,则调用Cancel操作。

    整体上,一个完整的TCC事务参与方包括三个部分:

    (1)主业务服务

    整个业务的发起方,在订单处理场景中,订单应用系统即是主业务服务。

    (2)从业务服务

    负责提供TCC业务操作,是整个业务活动的操作方。

    从业务必须实现Try、Confirm和Cancel三个接口,供主业务服务调用。Confirm和Cancel接口需要具备幂等性,订单的下单服务与支付服务即是从业务服务。

    (3)业务活动管理

    管理控制整个业务活动,包括记录维护TCC全局事务状态和每个从业务服务的子事务状态,并在业务活动提交时确认所有从业务服务Confirm操作,在业务活动取消时调用所有从业务服务的Cancel操作。

    3.实现策略

    在实现TCC模式上,最重要的工作是设计一个稳定的、高可用的、扩展性强的TCC事务管理器。

    在一个跨服务的业务操作中,首先通过Try锁住服务中业务资源进行资源预留,只有资源预留成功了,后续的操作才能正常进行。Confirm操作是在Try之后进行的对Try阶段锁定的资源进行业务操作,Cancel在所有操作失败时用于回滚。

    TCC的操作都需要业务方提供对应的功能,在开发成本上比较高,推介TCC框架有:

    (1)http://github.com/protera/spring-cloud-rest-tcc;

    (2)http://github.com/changmingxie/tcc-transaction;

    (3)http://github.com/liuyangming/ByteTCC;

    (4)http://github.com/QNJR-GROUUP/EasyTransaction;

    (5)http://github.com/yu199195/happylifeplat-tcc;

    (6)https://www.atomikos.om/Blog/TCCForTrasationMangementAcrossMicroservices。

    七、最大努力通知模式

    1.基本思路

    本质上是一种通知类的实现方案。

    基本思路是通知发送方在完成业务处理后向通知接收方发送通知消息。

    当消息接收方没有成功消费消息时,消息的发送方还需要进行重复发送直到消费者消费成功或达到某种发送总之条件。

    消息发送方可以设置复杂的通知规则,利于采用阶梯式事件通知方式。

    通知接收方也可以使用发送方所提供的查询和对账接口获取数据,用于恢复通知失败所导致的业务数据。

    以支付宝为例,通知回调商户提供的回调接口,通过多次通知、查询对账等手段完成交易业务平台间的商户通知。

    2.解决方案

    实现上比较简单,基本系统结构中的通知服务包括三大组件:

    (1)查询组件

    通发送方处理业务并把业务记录保存起来,查询组件提供查询入口供通知接收方主动查询业务数据,避免数据丢失。

    (2)确认组件

    当通知接收方成功接收到通知时,需要与通知发送方确认通知已被正常接收。确认组件接收到确认消息之后就会更新业务记录中的状态,通知组件根据状态就不需要再发送通知。

    (3)通知组件

    通知组件根据业务记录向通知接收方发送通知,在发送通知的过程中需要保存通知记录,并根据业务记录的状态以及现有的通知记录确定下一次发送通知的策略。

    注:最大努力通知模式适合于业务最终一致性的时间敏感度比较低的场景,一般用于类似支付宝与商户集成类跨企业的业务活动。

    八、人工干预模式

    1.基本思路

    严格意义上并不是一种数据一致性的实现机制,当前面讲的各种模式都无法满足需要时,人工干预模式更多的是一种替代方案。

    对于一些重要的业务场景下,由于前面几种模式中因为网络三态性无法解决问题的情况,需要人工干预来保证真正的一致性。常用手段为定期对账等。

    2.解决方案

    实施前提是需要一个后台管理系统,提供操作不一致的基本入口。

    周期性的对账机制需求,对账机制基于业务数据,业务双方根据各自系统内所产生的订单或支付记录,相互对比发现数据不一致的情况,然后通过线下付款等形式形成一致的操作结果。

    九、数据一致性模式总结

    对于金融、支付等业务体系,数据一致性要求极高,需要保证严格的实时一致性要求。

    对于基于社交类的应用场景,可以采用局部实时一致、最终全局一致的实现思路。

    微服务架构里面建议“兜底”思维,即不管实现方案是否完美,最后都要有一个备选方案,备选方案不一定满足日常业务场景,但当出现异常情况时,可通过备选完成正常业务的闭环。

    参考书籍、文献和资料:

    【1】郑天民. 微服务设计原理与架构. 北京:人民邮电出版社,2018.05

    【2】尹吉欢. Spring Cloud微服务全栈技术与案例分析. 北京:机械工业出版社,2018.08

    展开全文
  • (2)关系模式

    万次阅读 2019-08-24 22:04:48
    目录 1.关系模式数据结构 ①关系 ②属性 ③值域 ...⑥关系模式 ...从数据模式三要素(数据结构,数据操作,数据完整性约束)来进行分析: 1.关系模式数据结构 关系模式用二维表来组织数据,这个二...

     

    目录

    1.关系模式数据结构

    ①关系

    ②属性

    ③值域

    ④元组

    ⑤分量

    ⑥关系模式

    ⑦关系数据库

    ⑧各种码以及主属性

    2.关系模型操作

    3.关系模型完整性约束

    ①实体完整性约束

    ②参照完整性

    ③用户定义完整性


    关系模式是一种组织层数据模式。从数据模式三要素(数据结构,数据操作,数据完整性约束)来进行分析:

    1.关系模式数据结构

    关系模式用二维表来组织数据,这个二维表在关系模式中称为关系,关系模式的逻辑结构是二维表。下面介绍有关概念:

    ①关系

         关系就是二维表满足以下条件:

                    

       a.关系中每一列都是不可再分的属性,不能出现如下复合属性(列不可分性):

                                                            

       b.关系行列无序(行列无序性),交换列的前后顺序(比如性别放到年龄前面并不影响关系模式的语义表达)。

       c.关系中不可能出现两个完全相同的元组(实体完整性) 。

    ②属性

    二维表中的每一列称为属性,每个属性有一个名字称为属性名,称为属性名(就是表头),某一列的值称为属性值,上表有学号姓名年龄等属性。

    ③值域

    二维表中属性的取值范围,如性别只能取男女。

    ④元组

    二维表中的一行数据称为元组(记录)。如(023904,李勇,21,男,计算机系)

    ⑤分量

    元组中的每个属性值称为元组的分量,如对应姓名属性的分量是李勇。

    ⑥关系模式

    关系的描述就是关系模式,关系模型全体数据逻辑结构的描述就是关系模式,或者说二维表的表头,设有关系R,属性A1,A2,A3,则表示为R(A1,A2,A3),关系模式是型,关系就是具体的值。

    ⑦关系数据库

    对应一个关系模型的所有关系的集合称为关系数据库。

    ⑧各种码以及主属性

    a.超码:一个或多个属性的集合,这些属性的集合可以使我们在一个关系中唯一标识一个元组

    b.候选码:候选码是最小的超码,即候选码可以唯一标识一个元组,但除去候选码中的任何一个属性均不能唯一标识元组。

    c.主码:当有多个候选码时可以选择一个作为主码,一个关系只有一个主码。主码能够唯一标识一个关系的元组且不含有多余元素。

    d.主属性:包含在任意候选码中的属性称为主属性,不包含在任意候选码中的属性叫非主属性。

    e.外码:外码用于表示两个或多个实体间的关联关系。外码实际上是关系中的一个或多个属性,这些属性引用其他关系的主码或(候选码),详见参照完整性约束。

    2.关系模型操作

    关系模式的操作对象是集合(也就是关系)而不是行。操作的数据操作的结果都是完整的表(有表头的),而不是单行。

    操作主要包括查询和更新(增,删,改)。

    3.关系模型完整性约束

    在数据库中数据的完整性是指保证数据正确性的特性。关系模型中数据完整性规则是对关系的某种约束条件。他的数据完整性约束包含三大类:实体完整性约束,参照完整性约束,用户自定义完整性约束。

    ①实体完整性约束

    实体完整性是指数据库所有表中都有主码,且表中不允许存在:

        a.无主码的记录 (数据库中所有记录主码中所有属性都不为空)   b.主码相同的记录

    ②参照完整性

    参照的完整性要求关系中不允许引用不存在的实体也称引用完整性,参照完整性描述了实体间的联系。参照完整性一般是指多个实体表之间的引用关系

                                      

    学生关系模式中的专业号引用了专业关系模式中的专业号(且专业号在专业关系模式中是主码),显然学生关系中的专业号必须是个存在的专业号(可以为空表示未分配专业)。即学生关系模式中的专业号是引用了专业关系模式中的专业号的外码

    注:主码要求非空且不重复,外码没这个要求,外码的值要么为空要么存在。

    ③用户定义完整性

    用户自定义完整性也称为域完整性和语义完整性,任何关系数据库管理系统都应支持实体完整性参照完整性,除此之外根据要求不同还需要加一些特殊的约束条件。

    用户定义完整性实际上就是指明关系中的取值范围,也就是属性的域,所以又叫域完整性,比如性别限定在男女,成绩限定在0-100.

    展开全文
  • 第二章设计模式基本要素与原则一、基本要素1) 模式名称(pattem name)一个名称用来描述模式的问题、解决方案和效果。用于和同事或朋友见相互交互我们设计思想即设计结果,所以发明一个新的设计模式名称往往比发明...

    第二章设计模式基本要素与原则

    一、基本要素

    1)        模式名称(pattem name

    一个名称用来描述模式的问题、解决方案和效果。用于和同事或朋友见相互交互我们设计思想即设计结果,所以发明一个新的设计模式名称往往比发明一个设计模式要困难的多。J

    2)        问题(problem

    描述了设计模式在何种情形使用。它解释了设计模式形成的前因后果,描述了特定的设计问题。问题往往就是模式必须满足的一系列先决条件

    3)        解决方案(solution

    描述模式的组成成分,成分之间的相互关系以及各自的指着和协作方式。因为模式好比一个模板,他它应用于不同的场合(但这些场合待解决的问题的性质是一样的)所以解决方案并不描述一个特定具体的设计或实现而是提供怎样用一个具有典型的元素组合来解决这个问题

    4)        效果(consequences

    效果用来描述设计模式的利弊,效果往往是我们权衡模式是否可用的重要因素,模式效果包括它对系统的灵活性、扩展性或可遗址性的影响(复用是面向对象设计的重要要素之一)。对我们理解和评价模式起了很重要的客观依据

    二、设计模式遵循的几个原则

    1)      开——闭 原则

    提出者:Bertrand Meyer

    英文名:OCP (Open-Closed Principle)

      容:Software entities should be open for extension,but closed for modification.(一个软件实体应当对扩展开发,对修改关闭)

      解:模块应对扩展开放,对修改关闭。我们在重构代码时尽量在不修改原来代码的情况下进行扩展。

     

    ²        扩展已有系统提供新的行为。

    ²        在扩展的同时对旧版本有很好的支持。

    ²        使得系统更加灵活和很强的适应性。

    2)      里氏代换 原则

    提出者:Bertrand Liskov

    英文名:LSP (Liskov Substitution Principle)

      容:子类型(subtype)必须能够替换他们的基类型。(如果调用父类型的话,那么换成子类也可以完成)是继承复用的基础

      解:在模块中应当尽量从抽象类中继承,而不是从具体的类中继承。里氏代换只能子类代换父类,反过来是决对不可以的。

     

    ²        衍生类可以替换掉基类,软件不受到影响。

    ²        在扩展的同时对旧版本有很好的支持。

    ²        软件代码复用的重要基础。

    3)      合成复用 原则

    英文名:CARP (Composition Aggregation Reference Principle)

           合成和聚合都是关联的特殊种类,聚合表示整体和部分的关系,表示“拥有”;合成则是一种更强的“拥有”,部分和整体的生命周期是一样的,合成的新的对象完全支配其组成部分,包括他们的创建和湮灭。一个合成关系的成分对象是不能与另一个合成关系共享的

      容:合成是值的聚合(Aggregation by Value,聚合是引用的聚合(Aggregation by Reference

      解:

    1.         聚合就是多个事物聚集在一起打个比方一个大型的商场有多个摊位(做生意的人都知道)每个摊位里摆放的商品集合起来吸引众多买家来购物就形成了繁华的商场,这里可以看出每个摊位的商品不属于商场,商场关门了这些商品可以拿到其他商场中去卖所以商品和商场的关系就是聚合关系;回过头来我们看下摊位和商场的关系,摊位是随着商场的建立而孕育而生的(商场就靠这个来赚钱呢)商场没有了摊位也随之消失所以摊位和商场的关系就是一种合成关系摊位伴随着商城的建立和湮灭他们的生命周期是一样的

    2.         一个合成关系的成分对象是不能与另一个合成关系共享的。我们怎么去理解呢。2个商场 中央商场和大洋百货,两个商场是独立的没有隶属关系(偶在南京),中央商场的摊位和大洋百货是不可能有任何隶属关系的我们不可以说中央商场的摊位是属于大洋百货的(你这话说出来估计有人要。。。。)很好理解吧你直接可以理解为私有财产

    3.         我们在开发中尽量使用合成/聚合,而不是使用继承。

     

    OOD中有两种基本的办法实现服用

    1.         通过合成、聚合

    ²        黑箱复用,因为成分对象的内部实现细节新的对象是看不见的。

    ²        支持包装。

    ²        复用所需的依赖较少。(这个就是我为什么首选合成聚合而不用继承的主要原因)

    ²        新类可以把焦点集中在一个任务上,不去关心类成分间的复杂关系

    ²        复用是可以在运行时间内动态进行,新对象可以动态的引用与成分对象类型相同的对象

    ²        新对象存取成分对象的唯一方法是通过成分对象的接口(这个也埋下一个缺点)

    缺点:

    ²        系统中会有很对对象需要管理。

    2.         继承(很多程序员在初始理解设计模式时复用就是继承这个是错误的,我们在设计模式时优先选择前种,继承我个人理解成合成聚合实现不了时我会用继承)

    ²        新类实现比较容易

    ²        修改和扩展继承而来的实现比较容易

    缺点:

    ²        继承复用破坏了包装,因为继承讲超类的实现细节暴露给了子类,这种复用是透明的复用,又称“白箱”复用

    ²        如果超类发生改变,那么子类的实现不得不发生改变

    ²        从超类继承来的实现是静态的,不可能在运行时间内发生改变,没有足够的灵活性

    ²        继承只能在有限的环境中使用

    何时用继承:

    ²        子类是超类的一个特殊种类。而不是超类的一个角色,区分“Has-A”和“Is-A”。只有“Is-A(……)关系才符合继承关系,“Has-A”()关系应当用聚合来描述

    补充:

    错误的理解“Has-A”和“Is-A

    真确理解“Has-A”和“Is-A

    ²        永远不会出现需要将子类换成另外一个类的子类的情况。如果不能肯定就不要用继承

    ²        子类扩展了超类的责任,而不是具有换调(override)或注销掉(Nulify)超类的责任。如果子类需要大量的置换草类的行为,那么这个类就不因该是超类的子类

    4)      依赖倒转 原则

    英文名:DIP(Dependence Inversion Principle)

      容:抽象不应该依赖与细节,细节应当依赖与抽象;要针对接口编程,不要针对实现编程;传递参数,或者在组合聚合关系中,尽量引用层次高的类;

      解:程序在需要引用一个对象时,应当尽可能的使用抽象类型作为变量的静态方法,这个就是针对接口编程的含义。是达到“开-闭”原则的途径。针对接口编程和抽象类就是要做到一个具体的类应当只实现类的几口和抽象类中声明的方法,而没有多余的方法。做到DIP关键是抽象耦合,LSPDIP的基础

    5)      接口隔离 原则

    英文名:ISP(Interface Segregation Principle)

      容:使用多个专门的接口比使用单一接口要好,过于臃肿的接口是对就口的污染。

      解:一个类对另一个类的依赖性应当是建立在最小的接口上。不应该强迫客户依赖于他们不用的方法。我们在OOD时恰当的划分角色和角色对应的接口是非常重要的。讲没有关系的接口合并在一期是对角色和接口的一种污染,如果把一些看上去差不多的几口合并成一个几口,貌似是对代码的优化,其实是错误的。原则要求我们在不同的角色要给不同的接口,而不能交给一个接口。向客户提供的接口就像你对客户提供的承诺,承诺越少越好(那些生产厂家天天就琢磨这个了,没想到吧)

    :

    ²        系统可维护性高(我承诺的少当然维护性高了哇哈哈)

    6)      抽象   原则

    英文名:AP(Abstract Principle)

      容:抽象类不会有实例,一般作为父类被其他类继承,包含了子类的共同属性和方法

      解:OOD是好的抽象类是尽可能多的包含共同代码,具体类是不被其他类所继承的。换句话说子类继承了抽象类后,这个子类不应被其他类所继承

    7)      迪米特法则

    英文名:LoD(Law of Demeter)

      容:又叫最少知识原则(Least Knowledge Principle  LKP)。一个对象应当对其他对象尽可能的少了解。

      解:俗话说了解的越多,越烦恼这就体现出来了。每个人都听过妈妈的一句“不要跟陌生人说话”。这里的最少知道原则就是让每个类专心的做自己的事情而不去关心其他的事情这样的好处就是尽量的减少了耦合度。

          点:

    ²        减少类见的耦合度

     

     

    总结

          通过以上的学习我们基本上把所有设计模式用到的准则都梳理了一遍,细心的朋友可以发现这些原则有不同的层次分类我把他们分成 设计目标和设计细则

    7个原则的内容中他们其实都在解决一个问题,怎样尽可能的封装变化,哪里有变化我们就封装哪里,所以设计模式就是一个封装变化的过程

     

     
    展开全文
  • 递归的要素

    千次阅读 2019-10-03 11:13:51
    递归的要素 第一要素:明确你这个函数想要干什么 对于递归,我觉得很重要的一个事就是,这个函数的功能是什么,他要完成什么样的一件事,而这个,是完全由你自己来定义的。也就是说,我们先不管函数里面的代码...


    链接:https://www.zhihu.com/question/31412436/answer/683820765
    来源:知乎

    递归的三大要素

    第一要素:明确你这个函数想要干什么

    对于递归,我觉得很重要的一个事就是,这个函数的功能是什么,他要完成什么样的一件事,而这个,是完全由你自己来定义的。也就是说,我们先不管函数里面的代码什么,而是要先明白,你这个函数是要用来干什么。

    例如,我定义了一个函数

    // 算 n 的阶乘(假设n不为0)
    int f(int n){
    
    }

    这个函数的功能是算 n 的阶乘。好了,我们已经定义了一个函数,并且定义了它的功能是什么,接下来我们看第二要素。

    第二要素:寻找递归结束条件

    所谓递归,就是会在函数内部代码中,调用这个函数本身,所以,我们必须要找出递归的结束条件,不然的话,会一直调用自己,进入无底洞。也就是说,我们需要找出当参数为啥时,递归结束,之后直接把结果返回,请注意,这个时候我们必须能根据这个参数的值,能够直接知道函数的结果是什么。

    例如,上面那个例子,当 n = 1 时,那你应该能够直接知道 f(n) 是啥吧?此时,f(1) = 1。完善我们函数内部的代码,把第二要素加进代码里面,如下

    // 算 n 的阶乘(假设n不为0)
    int f(int n){
        if(n == 1){
            return 1;
        }
    }

    有人可能会说,当 n = 2 时,那我们可以直接知道 f(n) 等于多少啊,那我可以把 n = 2 作为递归的结束条件吗?

    当然可以,只要你觉得参数是什么时,你能够直接知道函数的结果,那么你就可以把这个参数作为结束的条件,所以下面这段代码也是可以的。

    // 算 n 的阶乘(假设n>=2)
    int f(int n){
        if(n == 2){
            return 2;
        }
    }

    注意我代码里面写的注释,假设 n >= 2,因为如果 n = 1时,会被漏掉,当 n <= 2时,f(n) = n,所以为了更加严谨,我们可以写成这样:

    // 算 n 的阶乘(假设n不为0)
    int f(int n){
        if(n <= 2){
            return n;
        }
    }

    第三要素:找出函数的等价关系式

    第三要素就是,我们要不断缩小参数的范围,缩小之后,我们可以通过一些辅助的变量或者操作,使原函数的结果不变。

    例如,f(n) 这个范围比较大,我们可以让 f(n) = n * f(n-1)。这样,范围就由 n 变成了 n-1 了,范围变小了,并且为了原函数f(n) 不变,我们需要让 f(n-1) 乘以 n。

    说白了,就是要找到原函数的一个等价关系式,f(n) 的等价关系式为 n * f(n-1),即

    f(n) = n * f(n-1)。

    这个等价关系式的寻找,可以说是最难的一步了,如果你不大懂也没关系,因为你不是天才,你还需要多接触几道题,我会在接下来的文章中,找 10 道递归题,让你慢慢熟悉起来

    找出了这个等价,继续完善我们的代码,我们把这个等价式写进函数里。如下:

    // 算 n 的阶乘(假设n不为0)
    int f(int n){
        if(n <= 2){
            return n;
        }
        // 把 f(n) 的等价操作写进去
        return f(n-1) * n;
    }

    至此,递归三要素已经都写进代码里了,所以这个 f(n) 功能的内部代码我们已经写好了。

    这就是递归最重要的三要素,每次做递归的时候,你就强迫自己试着去寻找这三个要素。

    案例1:斐波那契数列

    斐波那契数列的是这样一个数列:1、1、2、3、5、8、13、21、34....,即第一项 f(1) = 1,第二项 f(2) = 1.....,第 n 项目为 f(n) = f(n-1) + f(n-2)。求第 n 项的值是多少。

    1、第一递归函数功能

    假设 f(n) 的功能是求第 n 项的值,代码如下:

    int f(int n){
    
    }

    2、找出递归结束的条件

    显然,当 n = 1 或者 n = 2 ,我们可以轻易着知道结果 f(1) = f(2) = 1。所以递归结束条件可以为 n <= 2。代码如下:

    int f(int n){
        if(n <= 2){
            return 1;
        }
    }

    第三要素:找出函数的等价关系式

    题目已经把等价关系式给我们了,所以我们很容易就能够知道 f(n) = f(n-1) + f(n-2)。我说过,等价关系式是最难找的一个,而这个题目却把关系式给我们了,这也太容易,好吧,我这是为了兼顾几乎零基础的读者。

    所以最终代码如下:

    int f(int n){
        // 1.先写递归结束条件
        if(n <= 2){
            return 1;
        }
        // 2.接着写等价关系式
        return f(n-1) + f(n - 2);
    }

    搞定,是不是很简单?

    零基础的可能还是不大懂,没关系,之后慢慢按照这个模式练习!好吧,有大佬可能在吐槽太简单了。

    案例2:小青蛙跳台阶

    一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

    1、第一递归函数功能

    假设 f(n) 的功能是求青蛙跳上一个n级的台阶总共有多少种跳法,代码如下:

    int f(int n){
    
    }

    2、找出递归结束的条件

    我说了,求递归结束的条件,你直接把 n 压缩到很小很小就行了,因为 n 越小,我们就越容易直观着算出 f(n) 的多少,所以当 n = 1时,你知道 f(1) 为多少吧?够直观吧?即 f(1) = 1。代码如下:

    int f(int n){
        if(n == 1){
            return 1;
        }
    }

    第三要素:找出函数的等价关系式

    每次跳的时候,小青蛙可以跳一个台阶,也可以跳两个台阶,也就是说,每次跳的时候,小青蛙有两种跳法。

    第一种跳法:第一次我跳了一个台阶,那么还剩下n-1个台阶还没跳,剩下的n-1个台阶的跳法有f(n-1)种。

    第二种跳法:第一次跳了两个台阶,那么还剩下n-2个台阶还没,剩下的n-2个台阶的跳法有f(n-2)种。

    所以,小青蛙的全部跳法就是这两种跳法之和了,即 f(n) = f(n-1) + f(n-2)。至此,等价关系式就求出来了。于是写出代码:

    int f(int n){
        if(n == 1){
            return 1;
        }
        ruturn f(n-1) + f(n-2);
    }

    大家觉得上面的代码对不对?

    答是不大对,当 n = 2 时,显然会有 f(2) = f(1) + f(0)。我们知道,f(0) = 0,按道理是递归结束,不用继续往下调用的,但我们上面的代码逻辑中,会继续调用 f(0) = f(-1) + f(-2)。这会导致无限调用,进入死循环

    这也是我要和你们说的,关于递归结束条件是否够严谨问题,有很多人在使用递归的时候,由于结束条件不够严谨,导致出现死循环。也就是说,当我们在第二步找出了一个递归结束条件的时候,可以把结束条件写进代码,然后进行第三步,但是请注意,当我们第三步找出等价函数之后,还得再返回去第二步,根据第三步函数的调用关系,会不会出现一些漏掉的结束条件。就像上面,f(n-2)这个函数的调用,有可能出现 f(0) 的情况,导致死循环,所以我们把它补上。代码如下:

    int f(int n){
        //经过分析,f(2)=2也是一个临界条件。
        if(n <= 2){
            return n;
        }
        ruturn f(n-1) + f(n-2);
    }

    有人可能会说,我不知道我的结束条件有没有漏掉怎么办?别怕,多练几道就知道怎么办了。

    看到这里有人可能要吐槽了,这两道题也太容易了吧??能不能被这么敷衍。少侠,别走啊,下面出道难一点的。下面其实也不难了,就比上面的题目难一点点而已,特别是第三步等价的寻找

    案例3:反转单链表。

    反转单链表。例如链表为:1->2->3->4。反转后为 4->3->2->1

    链表的节点定义如下:

    class Node{
        int date;
        Node next;
    }

    虽然是 Java语言,但就算你没学过 Java,我觉得也是影响不大,能看懂。

    还是老套路,三要素一步一步来。

    1、定义递归函数功能

    假设函数 reverseList(head) 的功能是反转但链表,其中 head 表示链表的头节点。代码如下:

    Node reverseList(Node head){
    
    }

    2. 寻找结束条件

    当链表只有一个节点,或者如果是空表的话,你应该知道结果吧?直接啥也不用干,直接把 head 返回呗。代码如下:

    Node reverseList(Node head){
        if(head == null || head.next == null){
            return head;
        }
    }

    3. 寻找等价关系

    这个的等价关系不像 n 是个数值那样,比较容易寻找。但是我告诉你,它的等价条件中,一定是范围不断在缩小,对于链表来说,就是链表的节点个数不断在变小,所以,如果你实在找不出,你就先对 reverseList(head.next) 递归走一遍,看看结果是咋样的。例如链表节点如下

     

     

    我们就缩小范围,先对 2->3->4递归下试试,即代码如下

    Node reverseList(Node head){
        if(head == null || head.next == null){
            return head;
        }
        // 我们先把递归的结果保存起来,先不返回,因为我们还不清楚这样递归是对还是错。,
        Node newList = reverseList(head.next);
    }

    我们在第一步的时候,就已经定义了 reverseLis t函数的功能可以把一个单链表反转,所以,我们对 2->3->4反转之后的结果应该是这样:

     

     

    我们把 2->3->4 递归成 4->3->2。不过,1 这个节点我们并没有去碰它,所以 1 的 next 节点仍然是连接这 2。

    接下来呢?该怎么办?

    其实,接下来就简单了,我们接下来只需要把节点 2 的 next 指向 1,然后把 1 的 next 指向 null,不就行了?,即通过改变 newList 链表之后的结果如下:

     

     

    也就是说,reverseList(head) 等价于 reverseList(head.next) + 改变一下1,2两个节点的指向。好了,等价关系找出来了,代码如下(有详细的解释):

    //用递归的方法反转链表
    public static Node reverseList2(Node head){
        // 1.递归结束条件
        if (head == null || head.next == null) {
                 return head;
             }
             // 递归反转 子链表
             Node newList = reverseList2(head.next);
             // 改变 1,2节点的指向。
             // 通过 head.next获取节点2
             Node t1  = head.next;
             // 让 2 的 next 指向 2
             t1.next = head;
             // 1 的 next 指向 null.
            head.next = null;
            // 把调整之后的链表返回。
            return newList;
        }

    这道题的第三步看的很懵?正常,因为你做的太少了,可能没有想到还可以这样,多练几道就可以了。但是,我希望通过这三道题,给了你以后用递归做题时的一些思路,你以后做题可以按照我这个模式去想。通过一篇文章是不可能掌握递归的,还得多练,我相信,只要你认真看我的这篇文章,多看几次,一定能找到一些思路!

    接下来我讲讲有关递归的一些优化。

    有关递归的一些优化思路

    1. 考虑是否重复计算

    告诉你吧,如果你使用递归的时候不进行优化,是有非常非常非常多的子问题被重复计算的。

    啥是子问题? f(n-1),f(n-2)....就是 f(n) 的子问题了。

    例如对于案例2那道题,f(n) = f(n-1) + f(n-2)。递归调用的状态图如下:

     

     

    看到没有,递归计算的时候,重复计算了两次 f(5),五次 f(4)。。。。这是非常恐怖的,n 越大,重复计算的就越多,所以我们必须进行优化。

    如何优化?一般我们可以把我们计算的结果保证起来,例如把 f(4) 的计算结果保证起来,当再次要计算 f(4) 的时候,我们先判断一下,之前是否计算过,如果计算过,直接把 f(4) 的结果取出来就可以了,没有计算过的话,再递归计算。

    用什么保存呢?可以用数组或者 HashMap 保存,我们用数组来保存把,把 n 作为我们的数组下标,f(n) 作为值,例如 arr[n] = f(n)。f(n) 还没有计算过的时候,我们让 arr[n] 等于一个特殊值,例如 arr[n] = -1。

    当我们要判断的时候,如果 arr[n] = -1,则证明 f(n) 没有计算过,否则, f(n) 就已经计算过了,且 f(n) = arr[n]。直接把值取出来就行了。代码如下:

    // 我们实现假定 arr 数组已经初始化好的了。
    int f(int n){
        if(n <= 1){
            return n;
        }
        //先判断有没计算过
        if(arr[n] != -1){
            //计算过,直接返回
            return arr[n];
        }else{
            // 没有计算过,递归计算,并且把结果保存到 arr数组里
            arr[n] = f(n-1) + f(n-1);
            reutrn arr[n];
        }
    }

    也就是说,使用递归的时候,必要 须要考虑有没有重复计算,如果重复计算了,一定要把计算过的状态保存起来。

    2. 考虑是否可以自底向上

    对于递归的问题,我们一般都是从上往下递归的,直到递归到最底,再一层一层着把值返回。

    不过,有时候当 n 比较大的时候,例如当 n = 10000 时,那么必须要往下递归10000层直到 n <=1 才将结果慢慢返回,如果n太大的话,可能栈空间会不够用。

    对于这种情况,其实我们是可以考虑自底向上的做法的。例如我知道

    f(1) = 1;

    f(2) = 2;

    那么我们就可以推出 f(3) = f(2) + f(1) = 3。从而可以推出f(4),f(5)等直到f(n)。因此,我们可以考虑使用自底向上的方法来取代递归,代码如下:

    public int f(int n) {
           if(n <= 2)
               return n;
           int f1 = 1;
           int f2 = 2;
           int sum = 0;
    
           for (int i = 3; i <= n; i++) {
               sum = f1 + f2;
               f1 = f2;
               f2 = sum;
           }
           return sum;
       }

    这种方法,其实也被称为动态规划

    最后总结

    其实,递归不一定总是从上往下,也是有很多是从下往上的,例如 n = 1 开始,一直递归到 n = 1000,例如一些排序组合。对于这种从下往上的,也是有对应的优化技巧,不过,我就先不写了,后面再慢慢写。这篇文章写了很久了,脖子有点受不了了,,,,颈椎病?害怕。。。。

    说实话,对于递归这种比较抽象的思想,要把他讲明白,特别是讲给初学者听,还是挺难的,这也是我这篇文章用了很长时间的原因,不过,只要能让你们看完,有所收获,我觉得值得!

     

    展开全文
  • E-R图关系模式的转换

    千次阅读 热门讨论 2015-10-15 15:33:32
    引言:  E-R图关系模式的转换在大题中必要的考点。...我们都知道E-R图是由实体、属性和联系三要素构成的,上图中我们可以看出有两种向关系模式的转换,一是实体,二是联系。下面我们就来看一下具体转换方法
  • 设计模式的四个基本要素

    千次阅读 2013-07-19 21:44:28
    设计模式的四个基本要素: 1、模式名称(pattern name) 一个助记名,它用一两个词来描述模式的问题、解决方案和效果。 2、问题(problem) 描述了应该在合适使用模式。它解决了设计问题和问题存在的前后因果,它可能...
  • 模式 的四个基本要素

    千次阅读 2011-03-23 13:08:00
    模式的四个基本要素,我相信学习任何东西都是有模式的,虽然我不是太相信任何专门知识花个月都能入门的说法。   1. 模式名称 一个助记名,用一两个词来描述模式的问题,解决方案和效果。命名一...
  • 数据模型的三要素

    万次阅读 2017-05-04 23:09:09
    数据模型通常由个部分组成:数据结构、数据操作、完整性约束。 数据结构是描述一个数据模型性质最重要的方面。具体来说,它描述了两类内容: 一是数据库对象的类型、内容等(一个模型中有什么样的对象,对象的内容...
  • 数据库系统原理------ER图转化成关系模式

    千次阅读 多人点赞 2021-03-06 17:45:39
    ​ E-R图是由实体、实体的属性和实体之间的联系要素组成的。将E-R图转换为关系模型实际上就是要将实体、实体的属性和实体之间的联系转化为关系模式 。 实体集向关系模式的转换 一般转换遵循的原则 实体集的...
  • 正 文 声学漫谈之一:声音三要素

    千次阅读 2018-01-03 11:12:48
    声学漫谈之一:声音三要素 (2016-5-30 20:09) 标签:声学,三要素 声学三要素是指:音调、音色、响度。任何复杂的声音都可以用此个属性来描述,其分别对应声压的个物理量:频率、相位、幅度。 音调:人耳对于...
  • 数据模型要素

    万次阅读 2018-08-27 11:26:07
    它从语法角度表述了客观世界中数据对象本身的结构和数据对象之间的关联关系,是对系统静态特征的描述。 (2)数据操作 数据操作时对数据库中对象的实例允许执行的操作的集合,主要是指检索和更新(插入、删除、...
  • 1. 关系模式的相关概念: 域: 域是一组具有相同数据类型的值的集合 笛卡尔积: 域上的一种集合运算 其中每一个元素(d1,d2,d3,……dn)叫做一个元祖,元祖中的每一个值叫做一个分量。 【一个域允许的不同取值个数...
  • 颜色的三要素:色调,饱和度,和亮度。 The3 colour directories: hue,saturation, and brightness. danci.911cha.com 2 在同时使用色调、饱和度和亮度值的组合的情况下这些区域中的每一个是可定义的。 Each of ...
  • C#之十八 简单工厂设计模式

    千次阅读 2016-06-01 20:22:54
    从设计模式的类型上来说,简单工厂模式是属于创建型模式,又叫做静态工厂方法(Static Factory Method)模式,但不属于23种GOF设计模式之一。简单工厂模式是由一个工厂对象决定创建出哪一种产品类的实例
  • 颜色的三要素:色调,饱和度,和亮度。 The3 colour directories: hue, saturation, and brightness. danci.911cha.com 2 在同时使用色调、饱和度和亮度值的组合的情况下这些区域中的每一个是...
  • 一、设计模式(Design Patterns)    设计模式(Design pattern)是一套被反复使用、多数人知晓的、经过分类编目的、代码设计经验的总结。使用设计模式是为了可重用代码、让代码更容易被他人理解、保证代码可靠性...
  • 软件系统概要设计的要素

    万次阅读 2017-08-05 22:29:00
    当然也不是模块划分的越小越好,因为小粒度的模块虽然降低了模块自身的维护成本,但过多的模块会增加模块间关系维护的成本以及系统管理的复杂性。  通常来看,模块划分要符合开闭原则和高内聚和低耦合的原则。开...
  • 设计模式——设计模式概述

    万次阅读 多人点赞 2019-10-12 08:07:49
    软件设计模式(Design pattern),又称设计模式,是一套被反复使用、多数人知晓的、经过分类编目的、代码设计经验的总结。设计模式主要是为了解决某类重复出现的问题而出现的一套成功或有效的解决方案。设计模式提供...
  • 关系模型

    千次阅读 2018-07-11 18:31:41
    关系模型组成的三要素 关系数据结构 基本概念 关系 关系模式 什么是关系模式 关系模式(Relation Schema)是型 关系是值 关系模式是对关系的描述 关系数据库 关系操作集合 关系完整性约束 关系...
  • 在一定前提下,代码要以容易理解的方式实现。这个课题包括的内容太广,此文仅...下面代码的背景是有种unit,每种unit有相同种类的多个documentType;代码实现的是获取每种unit下每种documentType数量。代码如下所示:
  • 企业经营核心要素框架

    千次阅读 2014-03-18 15:37:58
    企业管理我已经有不少积累了,所以最近我发文章、研究提炼各个企业经营案例、重复阅读陈春花《经营的本质》,都直指企业商业模式、盈利模式、经营框架核心要素,希望能总结出一套企业经营核心要素分析框架。...
  • 在关系数据模型中把 记录类型 称为关系模式。(题库) 数据库管理系统中用于定义和描述数据库逻辑结构的语言称为 数据描述语言。(题库) 数据模型的种类型:概念模型、逻辑模型、物理模型 逻辑模型包括:...
  • 【Java设计模式】设计模式学习引导

    千次阅读 多人点赞 2019-10-06 11:29:21
    其实关于UML、7种软件设计原则和23种设计模式相关的文章,我之前都已经写过了,但是因为创作仓促,质量没有达到我的预期,都被我设置成了私密,接下来的日子里,打算再依次打磨打磨,发表出来。 截止目前,唯一放...
  • 设计模式大分类

    千次阅读 2014-01-13 00:21:03
    1.2 设计模式是什么  俗话说:站在别人的肩膀上,我们会看得更远。设计模式的出现可以让我们站在前人的肩膀上,通过一些成熟的设计方案来指导新项目的开发和设计,以便于我们开发出具有更好的灵活性和可扩展性,也...
  • 设计模式之结构型模式

    千次阅读 2020-08-21 15:58:19
    结构型模式 一、适配器模式 ...()构成要素: 二、桥接模式 (一)定义:桥接模式是用于把抽象化与实现化解耦,使得二者可以独立变化,它通过提供抽象化和实现化之间的桥接结构,来实现二者的解耦。
  • 设计模式

    千次阅读 多人点赞 2019-05-15 20:52:02
    2.设计模式的基本要素 模式名称:模式名称通过一两个单词来描述模式的问题、解决方案和效果。 问题:问题描述了应该在何时使用模式,它包含了设计中存在的问题以及问题存在的原因。 解决方案:解决方案描述了设计...
  • 产品读书《用户体验要素

    万次阅读 2018-08-06 14:04:05
    《用户体验要素》是一本讲产品的好书,作者为我们清晰地介绍了关于用户体验的五个要素,五个要素是按照产品的整个生命过程来描述的。 产品设计五要素分别是:战略层、范围层、结构层、框架层、表现层。 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 62,885
精华内容 25,154
关键字:

关系模式三要素