锐客网

  1. 首页 > 睿知 > >

分治法概述与分析

经验分享睿知

【分治法概述与分析】分治方法的基本概念很好理解 。动态规划算法和分治方法有什么相似之处？如果用分治的方法来解决这类问题，另一种方法就是用分而治之的方法，如何解决溅仙树的问题by 分治方法你好！分治方法和动态规划方法有什么异同？利用分治方法解决华水淑贤问题可以分为以下几个步骤:1 .把整个问题分成几个子问题，每个子问题都比原问题?。?这样就可以有效地利用分治 method 。

1、 分治法所能解决的问题一般具有以下特征: 分治 method所能解决的问题一般有以下特点:a .问题的规模如果缩小到一定程度就很容易解决 。这个问题可以分解成几个更小的相同的子问题 。c .这个问题分解的子问题的解可以合并到这个问题的解中 。d .这个问题分解出来的子问题是相互独立的 。e .这个问题的规模够大 。正确答案:如果这个问题的规模缩小到一定程度，就很容易解决 。这个问题可以分解成几个更小的相同的子问题 。

2、阐述一个生活中您所了解的用 分治法解决问题的案例 。生活中分治解决问题的案例如下:找出假币，给你一个装有16枚硬币的袋子 。16枚硬币中有一枚是假币，假币比真币轻 。你的任务是找到这枚伪币 。为了帮助你完成这个任务，会提供一个仪器来比较两组硬币的重量 。用这个仪器可以知道两组硬币的重量是否相同 。比较硬币1和硬币2的重量 。如果硬币1比硬币2轻，硬币1就是假币；如果硬币2比硬币1轻 ， 硬币2就是假币 。

如果两个硬币重量相等，比较硬币3和硬币4 。同样，如果一枚硬币比较轻，那么发现假币的任务就完成了 。如果两个硬币重量相等，继续比较硬币5和6 。这样，最多通过8次比较，就可以判断假币的存在，找到假币 。另一种方法是使用分而治之的方法 。如果把16个硬币的例子当成大问题 。第一步 ， 把这个问题分成两个小问题 。随机抽取8枚硬币作为第一组称为A组，其余8枚硬币作为第二组称为B组..

3、简述动态规划算法和 分治法有什么相同点?有什么异同点Description分治方法和动态规划方法有什么异同？答案如下:相似之处:基本思想是把要解决的问题分解成几个子问题，先解决子问题，然后从这些子问题的解中得到原问题的解；区别在于:(1)适用于动态规划法求解的问题，分解得到的子问题往往不是相互独立的 。如果用分治方法求解这类问题，分解得到的子问题数量太大，以至于最终求解原问题需要指数级的时间；(2)不同子问题的数目往往只有多项式，

    推荐阅读


    上一篇：matlab怎么分析数据,如何用matlab分析数据

    下一篇：分析带宽定义,低通滤波器带宽的定义