算法设计与分析总结

2016  summer &

index picture

1、递归与分治法

递归的基本思想:一个直接或间接调用自身的算法

(1)斐波那契数列:

斐波那契数列递归  以及递归优化

分治法的基本思想:将一个规模为n的问题分解为k个规模较小的子问题,这些子问题互相独立且与原问题相同。递归地解决这些子问题,然后将各子问题的解合并得到原问题的解。

(1)排列问题:

先贴出可能用到的代码:

交换两个数的模板:

交换函数

问题:已知R={1,2,3},对它产生全排列

分析:当第一个数1固定,对23进行全排列,可以分为当2固定,对3进行全排列;当3固定,对2进行全排,则可以得到123,132;其余当第一个数是2,对13进行全排列;当第一个数是3,对12进行全排列。

程序代码:

全排列

(2)整数划分问题

问题:

整数划分问题

程序代码:

整数划分

(3)二分搜索技术:

问题:给定已排好序的n个元素a[0,n-1],现要在这n个元素中找出一特定元素x

程序代码:

循环实现:

二分搜索循环

递归实现:

二分搜索递归

(4)棋盘覆盖

先贴出可能用到的代码:

动态申请一个一维数组:

动态申请一维数组

动态开辟一个二维数组:

动态开辟一个二维数组

问题:

问题
l型骨牌

分析:可以用分治法解决此问题,当k > 0时,将2^k * 2^k的棋盘分割为4个2^(k-1) * 2^(k-1)个子棋盘,如下图:

分割与填法

上图中的右图就是我们填L型骨牌的方式,使得每一个区域都有一个特殊方格。

代码一
代码二
运行结果

(5)合并排序

基本思想:当n=1时,终止排序;否则将待排序的元素分割为大小大致相同的两个子集和,分别对子集和进行排序,最终将排好序的子集和合并。

代码一
代码二

(6)快速排序

快速排序

注:若数据是基本有序的,则快速排序的效率不高,可以用随机化法解决:

随机化法

(7)线性时间选择

问题:给定线性序集中n个元素和一个整数k,要求找出这n个元素中第k小的元素。

分析:利用分治法,调用Partition函数可以对其进行划分,一次划分得到第pos个小的元素,然后判断k值与pos的大小,分别对部分重复上述步骤,最主要的是pos的求法是index-left+1

找第k小的元素




2、动态规划算法

基本思想:将待求解的问题分解为若干个子问题,先求解子问题,然后从这些子问题得到原问题的解。经动态规划法得到的子问题往往不是相互独立的,为了避免重复计算,我们可以用一个表来记录所有已解决的子问题的答案。它常用于求解具有最优子结构性质(问题的最优解包含了子问题的最优解)和子问题重叠性质(在用递归算法自顶向下的解决问题时,每次产生的子问题并不总是新问题,有些问题被反复计算多次)的问题。

基本步骤:a、找出最优解的性质,并刻画其特征;

b、递归地定义最优值;

c、以自底向上的方式计算出最优值;

d、根据计算最优值时得到的信息,构造一个最优解。

(1)矩阵连乘问题

两个矩阵相乘代码:

矩阵相乘

问题:给定n个矩阵{A1,A2,A3.........An},计算出n个矩阵连乘积的最优计算次序

分析:

a、最优解的性质:设A[1,n]是n个矩阵的连乘,则可将其划分为A[1,k]和A[k+1,n]

b、递归地定义最优值:设m[i,j]为所需的最少数乘次数,则当i=j时,m[i,j]=0;当i<j时,

m[i,j] = min(m[i,k]+m[k+1,j]+p[i-1]*p[k]*p[j]),其中k取值范围是i到j-1;

c、以自底向上计算最优值

d、构造一个最优解

(2)最长公共子序列

规定:子序列是按照下标递增的方式

问题:给定两个序列分别是:X={A,B,C,B,D,A,B},Y={B,D,C,A,B,A},假设Z是X和Y的最长公共子序列,求Z?

分析:

a、最优解的性质:若xm = yn,则zk = xm = yn,z(k-1)是x(m-1)和y(n-1)的最长公共子序列;若xm!=yn且zk!=xm,则z是x(m-1)和yn的最长公共子序列;若xm!=yn且zk!=yn,则z是xm和y(n-1)的最长公共子序列;

b、递归地定义最优值:用c[i][j]记录xi和yj最长公共子序列的长度。当i=j=0时,c[i][j]=0;当i,j>0时,若xi=yj,则c[i][j]=c[i-1][j-1]+1;若xi!=yj,则c[i][j] =max(c[i][j-1],c[i-1][j])。

c、以自底向上计算最优值

d、构造一个最优解

(3)0-1背包问题

问题:

0-1背包问题

分析:

a、最优解的性质:假设对于n元0-1向量x={x1,x2……xn},有Sum(wi xi) <= c && Max(Sum(vi xi))为最优解,则有对于x={x2……xn},有Sum(wi xi) - w1 x1 <= c && Max(Sum(vi xi)-v1 x1)为最优解

b、递归地定义最优值:设m(i,j)代表最大价值,i表示为i……n,即放入了这么些物品,j代表当前容器的容量。则有第一种情况当i==n,如果j>w[n],则返回v[n],否则返回0;第二种情况当i < n时,若jw[i],则返回Max( m(i+1,j) , (m(i+1,j-w[i]) + v[i] ) )

c、以自底向上计算最优值:

d、构造一个最优解:




3、回溯法

基本思想:它是将问题的所有解罗列出来,然后构建一颗并非真实存在的解空间树,并对这颗树进行深度优先搜索。这里介绍两种常用的解空间树,当所给的问题是从n个元素的集合中找出满足某种性质的子集时,这时的树成为子集树;当所给的问题是确定n个元素满足某种性质的排列时,这时的树成为排列树。

(1)求一个数组的子集

(2)n后问题

在一个n*n的象棋盘上摆放n个皇后,使其不可以相互攻击,即使她们不能处在同一行、同一列、统一对角线上。

递归:


非递归:

思想:一列列地填,并判断位置是否合法


结果:

拓展思维:

0———

                         ----------------end -----

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

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,712评论 0 33
  • 动态规划(Dynamic Programming) 本文包括: 动态规划定义 状态转移方程 动态规划算法步骤 最长...
    廖少少阅读 3,235评论 0 18
  • 以前写过一篇关于大订单的文章,今天把大订单和小订单的差异再详细描述一下。 首先,无论是大订单还是小订单,都要经历初...
    Up大订单销训营_张毛地阅读 1,288评论 0 1
  • 最近发现一个有趣的现象,在某个村小微信群里的女人们总是动不动的就叫群里的男人们请客。而且叫的频率还挺高,高达一...
    临界紫苏阅读 199评论 0 2