Java八大算法思想(总结)

八大算法:枚举、递推、递归、分治、贪心、试探法、动态迭代和模拟算法思想。

一、枚举算法思想(暴力算法)

  将问题的所有可能答案一一列举,根据判断条件判断此答案是否合适,一般用循环实现。

  经典运用:百钱买百鸡、填写运算符

二、递推算法思想

  1.顺推法:从已知条件出发,逐步推算出要解决问题的方法。

  2.逆推法:从已知结果出发,用迭代表达式逐步推算出问题开始的条件,即顺推法的逆过程。

  经典运用:斐波那契数列(顺推法)、银行存款(逆推法)

三、递归算法思想

  1.递归过程一般通过函数或子过程实现;

  2.递归算法在函数或子过程的内部,直接或间接调用自己的算法

  3.递归算法实际上是把问题转化为规模缩小了的同类问题的子问题,然后再递归调用函数或过程来表示问题的解

注意:必须有一个明确的递归结束条件;如果递归次数过多,容易造成栈溢出。

  经典运用:汉诺塔问题、阶乘问题

四、分治算法思想

  将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同。只要求出子问题的解,就可得到原问题的解。

  一般步骤:

    1.分解,将要解决的问题划分成若干个规模较小的同类问题

    2.求解,当子问题划分得足够小时,用较简单的方法解决

    3.合并,按原问题的要求,将子问题的解逐层合并构成原问题的解

  经典运用:大数相乘问题、比赛日程安排

五、贪心算法思想

  从问题的某一个初始解出发,逐步逼近给定的目标,以便尽快求出更好的解。

  局限:

    不能保证最后的解是最优的;

    不能求最大最小解问题;

    只能求满足某些约束条件的可行解范围。

  基本过程:

    1.从问题的某一初始解出发

    2.while能向给定总目标前进一步

    3.求出可行解的一个解元素

    4.由所有解元素组合成问题的一个可行解

  经典运用:装箱问题、找零方案

六、试探算法(回溯法)

  在试探算法中,放弃当前候选解,并继续寻找下一个候选解的过程称为回溯。扩大当前候选解的规模,以继续试探的过程称为向前试探。

  (为求得问题的正确解,会先委婉地试探某一种可能情况。在进行试探过程中,一旦发现原来选择的假设情况是不正确的,马上会自觉地退回一步重新选择,然后继续向前试探。反复进行,直到得到解或证明无解时才死心)

  基本步骤:

    1.针对所给问题,定义问题的解空间

    2.确定易于搜索的解空间结构

    3.以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索

  经典运用:八皇后问题、29选7彩票组合

七、迭代算法(辗转法)

  是一种不断用变量的旧值递推新值的过程,解决问题时总是重复利用一种方法。

  1.确定迭代变量:直接或间接地不断由旧值递推出新值的变量

  2.建立迭代关系式:新值与旧值的公式或关系。(解决迭代问题的关系)

  3.对迭代过程进行控制:确定迭代过程什么时候结束

    所需的迭代次数是个确定值,可以计算出来:可以构建一个固定次数的循环来实现对迭代过程的控制;

    所需的迭代次数无法确定:需要进一步分析出用来结束迭代过程的条件。

  经典运用:求平方根问题

八、模拟算法思想

  对真实事物或者过程的虚拟。

  经典运用:猜数字游戏、掷骰子问题

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 216,142评论 6 498
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 92,298评论 3 392
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 162,068评论 0 351
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 58,081评论 1 291
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 67,099评论 6 388
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 51,071评论 1 295
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,990评论 3 417
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,832评论 0 273
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,274评论 1 310
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,488评论 2 331
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,649评论 1 347
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,378评论 5 343
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,979评论 3 325
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,625评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,796评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,643评论 2 368
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,545评论 2 352

推荐阅读更多精彩内容