nbhkdz.com冰点文库

信息学奥赛基本算法


第0讲:算法设计概论
时间复杂度 空间复杂度 调试方法与技巧

时间复杂度
? ? ?

?
? ?

O(1)常数阶 O(log N)对数阶 O(N)线性阶 O(N^2)平方阶 O(N^3)立方阶 ……………………

空间复杂度
? ? ?

r />?
? ?

O(1)常数阶 O(log N)对数阶 O(N)线性阶 O(N^2)平方阶 O(N^3)立方阶 ……………………

调试方法与技巧
? ? ?

?
?

Break Point Watch Table Data Check Code

问题分析
? ? ?

?
?

分析题目的模型 考虑要用的算法 分析算法的时空复杂度 如果符合要求即可 Coding

第一讲:递归

什么是递归?
?

?

递归就是指一个函数直接或者间接地调用 自身。 问题的求解过程?划分成相同性质的子问 题的求解,而小问题的求解过程可以很容 易的求出,这些子问题的解就构成里原问 题的解。

总体思想
? ? ?

待求解问题的解?输入变量x的函数f(x) 通过寻找函数g( ),使得f(x) = g(f(x-1)) 且已知f(0)的值,就可以通过f(0)和g( ) 求出f(x)值

推广
?

扩展到多个输入变量x,y,z等,x-1也可以 推广到 x - x1,只要递归朝着“出口”的 方向即可

递归的三个要点
? ?

递归式:如何划分子问题
递归边界:递归的终止条件,也就是最小 的子问题

?

界函数:问题规模变化的函数,保证递归 向边界靠拢

求 n!
? ? ? ? ?

#include <iostream.h> int F(int n) {
if (n == 0) return 1; else return n * F(n - 1); }

?
? ?


?

递归的实现是需要栈的,这里所使用的栈 是系统自带的栈
栈是一种数据结构,它符合先入后出的原 则

?

解决递归问题的关键
?

?

?

找出递推公式:即如何将问题划分为小规 模的问题 找到边界条件 NOTICE:由于函数中的局部变量是存在系 统的栈上的,如果你的局部变量过大,如 较大的数组,将有可能栈溢出,这个时候 要考虑全局变量和人工栈的使用。

汉诺塔问题
?

现在有三根相邻的柱子,标号为A,B,C,A 柱子上从下到上按金字塔状叠放着n个不同 大小的圆盘,现在把所有盘子一个一个移 动到柱子B上,并且每次移动同一根柱子上 都不能出现大盘子在小盘子上方,请问至 少需要多少次移动,并输出步骤。

汉诺塔问题
?

?
? ? ? ? ? ? ? ?

?
? ? ?

void hanoi(int n,char A,char B,char C) { if(n==1) { printf("Move disk %d from %c to %c\n",n,A,C); } else { hanoi(n-1,A,C,B); printf("Move disk %d from %c to %c\n",n,A,C); hanoi(n-1,B,A,C); } }

前序中序求后序
? ? ?

树中已知先序和中序求后序。 如先序为:abdc,中序为:bdac . 则程序可以求出后序为:dbca 。

前序中序求后序
?

算法思想:先序遍历树的规则为中左右, 则说明第一个元素必为树的根节点,比如 上例中的a就为根节点,由于中序遍历为:左 中右,再根据根节点a,我们就可以知道, 左子树包含元素为:db,右子树包含元素: c,再把后序进行分解为db和c(根被消去 了),然后递归的进行左子树的求解(左 子树的中序为:db,后序为:db),递归 的进行右子树的求解(即右子树的中序为: c,后序为:c)。如此递归到没有左右子树 为止。

前序中序求后序
? ? ? ? ? ? ?

?
? ? ? ? ? ?

void pronum(char pre[],int pre_s,int pre_e,char in[],int in_s,int in_e) { char c; int k; if(in_s>in_e) return ; /* 非法子树,完成。 */ if(in_s==in_e){printf("%c",in[in_s]); /* 子树子仅为一个节点时直接输出并完成。 */ return ; } c=pre[pre_s]; /* c储存根节点。 */ k=find(c,in,in_s,in_e); /* 在中序中找出根节点的位置。 */ pronum(pre,pre_s+1,pre_s+k-in_s,in,in_s,k-1); /* 递归求解分割的左子树。 */ pronum(pre,pre_s+k-in_s+1,pre_e,in,k+1,in_e); /* 递归求解分割的右子树。 */ printf("%c",c); /* 根节点输出。 */ }

FBI树
?

?

? ?

?

我们可以把由“0”和“1”组成的字符串分为三类:全“0” 串称为B串,全“1”串称为I串,既含“0”又含“1”的串则 称为F串。 FBI树是一种二叉树 ,它的结点类型也包括F结点,B结点 和I结点三种。由一个长度为2N的“01”串S可以构造出一棵 FBI树T,递归的构造方法如下: 1) T的根结点为R,其类型与串S的类型相同; 2) 若串S的长度大于1,将串S从中间分开,分为等长的左 右子串S1和S2;由左子串S1构造R的左子树T1,由右子串 S2构造R的右子树T2。 现在给定一个长度为2N的“01”串,请用上述构造方法构造 出一棵FBI树,并输出它的后序遍历 序列。

FBI树
?

算法思想:本题为后序,类似于前一题,我们有相似的解 法

FBI树
? ? ? ? ? ?

?

int fbi(int i,int j) { if(i<=j){ int mid=(i+j)/2 if(i!=j){ fbi(i,mid); fbi(mid+1,j);
? ?

} int I,B;

? ? ? ? ? ? ?

while(i<=j)if(a[i++]=='0')B++;else I++; if(B>0 && I>0)cout<<'F'; else if(B>0)cout<<'B'; else cout<<'I'; } return 0; }

第二讲:回溯

回溯
? ?

回溯是一种实现枚举的算法
其本质就是应用了递归这一工具所进行的 枚举

?

?

其优点在于可以加上一些剪枝,使得枚举 的效率更加的高 我们也可以将其称之为深度优先搜索 DFS

回溯框架
?

?
? ? ? ? ? ?

?
? ? ?

?

int try(……….) { if (达到目标) 记录结果; else for_each() if (满足条件) { 改变状态; try(………..); 回复状态 } }

8皇后
?

在8X8格的国际象棋上摆放八个皇后,使其 不能互相攻击,即任意两个皇后都不能处 于同一行、同一列或同一斜线上,问有多 少种摆法。

分析
?

显然,八皇后问题每行必须有一个皇后, 所以,对棋盘深搜时,第一个皇后的位置 不妨设为第一行,这样只对第一行进行搜 索,同理,第二个皇后不妨设为第二行, 以此类推。

代码
?

void try(int k){
if (k==9) { if (ok) ans++; return 0 } for (int i=1;i<=8;i++) { a[k][i]=1; try(k+1); a[k][i]=0; }

?

}

优化
? ?

用一个use[]来记录是否本列被占用 用一个Xright[],Xleft[]分别记录每条对角线是 否被占用

Fibonacci
? ? ?

F(n)=F(n-1)+F(n-2) F(0)==F(1)==1 如何解决这个问题

解法1
? ? ?

递归解法 int f(int n) {
if ((n==1)||(n==0)) return 1; return f(n-1)+f(n-2)

?

}

解法2
? ? ?

递归+记忆化 int f(int n) {
if ((n==1)||(n==0)) return 1; calc[n]=1; if (calc[n]) return f[n]; f[n]=f(n-1)+f(n-2) return f[n];

?

}

解法3
? ?

?

递推 f[0]=1; f[1]=1; for (int i=2;i<=n;i++){ f[n]=f[n-1]+f[n-2]; }

解法4
数学方法 ? 数学上可以简单推理:存在A,B使得:
?

F(n)=A*x1^n+B*x2^n 代入F(0)=0,F(1)=1,解得A=1/sqrt(5.0),B=1/sqrt(5.0),即

F(n)=(x1^n-x2^n)/sqrt(5.0) -----?时间复杂度 为O(1),但不能保证精度

解法5
?

注意到Fibonacci数列是二阶递推数列,所以存在 一个2*2的矩阵A,使得:

(F[n] F[n-1])=(F[n-1] F[n-2])*A,

求解得到A = { {1,1}, {1,0}},然后通过递推式
(Fn Fn-1) = (Fn-1 Fn-2)*A = (Fn-2 Fn-3)*A2 = .... = (F1 F0)*An-1, 然后只要计算An-1,再与矩阵 (F1 F0)相乘,就可以的得到 Fn的值
?

快速指数相乘法求An-1: n = ak*2^k + ak-1*2^k-1 + ... + a1*2 + a0,其中ai = 0 或1 ,i = 0,1,2... k.所以我们只需要进行logn次的运算

第三讲:分治

分治概念
?

分治算法的基本思想是将一个规模为N的问 题分解为K个规模较小的子问题,这些子问 题相互独立且与原问题性质相同。求出子 问题的解,就可得到原问题的解。

分治步骤
?

分解,将要解决的问题划分成若干规模较 小的同类问题;
求解,当子问题划分得足够小时,用较简 单的方法解决; 合并,按原问题的要求,将子问题的解逐 层合并构成原问题的解。

?

?

分治
? ? ?

?

分治也是运用递归方法进行的算法 将大问题化为若干小问题 再解决小问题 最后由小问题得出大问题的解

分治例子
?

例1[找出伪币] 给你一个装有1 6个硬币的袋 子。1 6个硬币中有一个是伪造的,并且那 个伪造的硬币比真的硬币要轻一些。你的 任务是找出这个伪造的硬币。为了帮助你 完成这一任务,将提供一台可用来比较两 组硬 币重量的仪器,利用这台仪器,可以 知道两组硬币的重量是否相同。

解法1
?

比较硬币1与硬币2的重量。假如硬币1比硬币2轻, 则硬币1是伪造的;假如硬币2比硬币1 轻,则硬币 2是伪造的。这样就完成了任务。假如两硬币重量 相等,则比较硬币3和硬币4。同样,假如有一个 硬币轻一些,则寻找伪币的任务完成。假如两硬 币重 量相等,则继续比较硬币5和硬币6。按照这 种方式,可以最多通过8次比较来判断伪币的存在 并找出这一伪币。

解法2
?

另外一种方法就是利用分而治 之方法。假如把1 6硬币的 例子看成一个大的问题。第一步,把这一问题分成两个小 问题。随机选择8个硬币作为第一组称为A组,剩下的8个 硬币作为第二组称为B组。这样,就把 1 6个硬币的问题分 成两个8硬币的问题来解决。第二步,判断A和B组中是否 有伪币。可以利用仪器来比较A组硬币和B组硬币的重量。 假如两组硬币重量相等,则 可以判断伪币不存在。假如两 组硬币重量不相等,则存在伪币,并且可以判断它位于较 轻的那一组硬币中。最后,在第三步中,用第二步的结果 得出原先1 6个硬币问题的答案。若仅仅判断硬币是否存在, 则第三步非常简单。无论A组还是B组中有伪币,都可以 推断这1 6个硬币中存在伪币。因此,仅仅通过一次重量的 比较,就可以判断伪币是否存在。

分治应用:归并排序
? ? ?

?
?

?
?

排序的方法: 冒泡排序 选择排序 快速排序 桶排序 基数排序 归并排序

归并排序
?

归并(Merge)排序法是将两个(或两个以 上)有序表合并成一个新的有序表,即把 待排序序列分为若干个子序列,每个子序 列是有序的。然后再把有序子序列合并为 整体有序序列。

归并排序
?

我们可以在O(n)的时间内将两个有序的序列 合并
每次我们将一个序列平均分成两半,分别 进行排序,之后再将其合并

?

复杂度分析
? ? ? ? ?

时间复杂度为O(nlogn) 这是该算法中最 好、最坏和平均的时间性能。 空间复杂度为 O(n) 比较操作的次数介于(nlogn) / 2和nlogn - n + 1。 赋值操作的次数是(2nlogn)。归并算法 的空间复杂度为:0 (n) 归并排序比较占用内存,但却效率高 且稳定的算法。

优点
?

归并排序是稳定的排序。即相等的元素的 顺序不会改变。如输入记录 1(1) 3(2) 2(3) 2(4) 5(5) (括号中是记录的关键字)时输出的 1(1) 2(3) 2(4) 3(2) 5(5) 中的2 和 2 是按输入的 顺序。这对要排序数据包含多个信息而要 按其中的某一个信息排序,要求其它信息 尽量按输入的顺序排列时很重要。这也是 它比快速排序优势的地方。

例子
? ?

? ? ?

?

如 设有数列{6,202,100,301,38,8,1} 初始状态: [6] [202] [100] [301] [38] [8] [1] 比较 次数 i=1 [6 202 ] [ 100 301] [ 8 38] [ 1 ] 3 i=2 [ 6 100 202 301 ] [ 1 8 38 ] 4 i=3 [ 1 6 8 38 100 202 301 ] 4 总计: 11次

代码
?

?
? ?

?
? ? ? ? ? ?

void MergeSort(int array[], int first, int last) { int mid = 0; if(first<last) { mid = (first+last)/2; MergeSort(array, first, mid); MergeSort(array, mid+1,last); Merge(array,first,mid,last); } }

code
void merge(int s,int t) ?{ int mid=(s+t) / 2; int i=s; { i 是左边子序列的指针} int j=mid+1; { j 是右边子序列的指针} int k=s; { k 是临时队列的指针}
?

while (k<=t) { if ( (i<=mid) && ((j>t)||(a[i]<=a[j])) ) {左边子序列不空,右边 子序列已空或左边的元素小于右边的元素} { now[k]=a[i]; i++ } else { now[k]=a[j]; j++; } k++; } for (int i=s;i<=t;i++) a[i]=now[i]; }

?

?

在合并的过程中,我们分别拿出两个有 序子序列的一个值进行比较,选择一个较 小(或较大)的值,也就是这两个有序子 序列中较小(或较大)的值,加入一个临时 的队列之中。 当其中的有一个子序列空了的时候,另 一个子序列中剩下的元素就可以直接加入 临时队列中。

瑞士轮
?

2*N 名编号为1~2N 的选手共进行R 轮比赛。 每轮比赛开始前,以及所有比赛结束后, 都会按照总分从高到低对选手进行一次排 名。选手的总分为第一轮开始前的初始分 数加上已参加过的所有比赛的得分和。总 分相同的,约定编号较小的选手排名靠前。

瑞士轮
?

?

每轮比赛的对阵安排与该轮比赛开始前的排名有 关:第 1 名和第2 名、第3 名和第4 名、……、第2K – 1 名和第2K 名、…… 、第 2N – 1 名和第2N 名,各进行一场比赛。每 场比赛胜者得1 分,负者得0 分。也就是说除了首 轮以外,其它轮比赛的安排均不能事先确 定,而是要取决于选手在之前比赛中的表现。 现给定每个选手的初始分数及其实力值,试计算 在 R 轮比赛过后,排名第Q 的选手编号是多少。 我们假设选手的实力值两两不同,且每场比赛中 实力值较高的总能获胜。 N<=100000 R<=50

瑞士轮
? ? ?

直接每次都进行快速排序必然超时 需要找到每次排序O(n)的方法 归并排序

瑞士轮
? ?

每次将胜利者和失败者分成两个有序序列
胜利者每人加一场胜场,所以依然是有序 的 将两个序列合并,可以做到O(n)

?

逆序对
?

?

所谓的逆序对是对于一个包含N个非负整数 的数组A[1..n],如果有i < j,且A[ i ]>A[ j ], 则称(A[ i] ,A[ j] )为数组A中的一个逆序对。 例如,数组(3,1,4,5,2)的逆序对有 (3,1),(3,2),(4,2),(5,2),共4个。

求逆序对个数
?

利用归并排序求逆序对的过程主要是根据, 归并排序中元素的位置是稳定的,并且每 两个子序 列中也是有序的,当左边的子序 列中的元素大于右边的子序列的元素时, 那么左边子序列中该元素后面的所有元素 都要大于右边的那个元素,也就是有这么 多的逆序 对。因此我们在归并排序的加一 句话就可以完成。

? ?

{
} { now[k]=a[i]; i++

else
now[k]=a[j]; j++; if (i<=mid) ans+=mid-i+1;

?

}

表达式的计算
?

输入一个由0~9 + - * \ 运算符及括号组成 的表达式,比如(17+18)*(12-(3+6)*9) 。表达式 中的数字及计算结果都不超过长整型数。请编 一个程序计算表达式的值, 输入样例:6+8\3 输出样例1:8

表达式计算
? ?

本题的解法有很多 我们采用分治的思想来解决

表达式计算
?
?

首先我们计算出每个运算符的优先级,即 哪一个运算符需要先计算
(17+18)*(12-(3+6)*9)

?
? ? ?

我们令加减号优先级为1 乘除为 2 每加一层括号 优先级加 2 则 优先级为 3 2 3 5 4 符合我们对表达式计算的顺序

分治
?
?

接下来我们按照优先级顺序从低到高进行 分治
(17+18) * (17 + 18) (17 + 18) (17 + 18) (12-(3+6)*9) * (12 (3+6)*9) * (12 - (3+6) * 9 * (12 (3 + 6) * 9)

?
? ?

分治
? ? ?

?
?

(17 + (17 + (17 + (35) -2415

18) 18) 18) *

* * * (-69)

(12 (12 (12

-

(3 + 6) * 9) (9) * 9) 81)

棋盘覆盖
?

? ?

在一个2^k×2^k个方格组成的棋盘中,若有一个方 格与其他方格不同,则称该方格为一特殊方格,且称 该棋盘为一个特殊棋盘.显然特殊方格在棋盘上出 现的位置有4^k种情形.因而对任何 k≥0,有4^k种不同的特殊棋盘. 下图中的特殊棋盘是当k=2时16个特殊棋盘中 的一个:

棋盘覆盖
?

特殊方格必位于4个较小子棋盘之一中,其余3个 子棋盘中无特殊方格.为了将这3个无特殊方格的 子棋盘转化为特殊棋盘,可以用一个L型骨牌覆盖 这3个较小棋盘的会合处。

棋盘覆盖
?

如下图所示,这3个子棋盘上被L型骨牌覆盖 的方格就成为该棋盘上的特殊方格,从而原 问题转化为4个较小规模的棋盘覆盖问题. 递归地使用这种分割,直至棋盘简化为1×1 棋盘

普通递归、回溯、分治区别
?

?
?

一般的递归是建立在递推函数与边界条件 上的,它是将一个子问题化成另一个子问 题(或若干)的方法 回溯则是利用递归的枚举法
分治是将问题按一定的方式划分成若干小 问题的方法(一般大于一个)

第四讲:贪心

贪心
?

仅仅由当前的状态导出当前所需决策的算 法,我们称之为贪心算法
能够应用贪心算法解决的问题,每次必然 都是选择最优的策略 如果我们可以证明这样做是全局最优的话, 那么贪心算法是一种十分高效的算法

?

?

贪心
?

?

正如人的思考一般,贪心就是针对局部最 优情况的决策,无需考虑之后的决策会受 到怎样的影响 简单的例子:现有10元、7元、2元、1元四 种纸币,使用的张数不限,需要用这四种 纸币凑成x元钱,怎样用最少的张数达到此 要求。

贪心思路
? ? ?

每次取最大的纸币 当x=14 贪心算法14=10+2+2 最优:14=7+7 但是当纸币种类为10元、5元、1元时贪心明 显是正确的
这就促使我们思考如何证明贪心算法的正 确性

?

三值排序问题
?

有一个由N个数值均为1、2或3的数构成的 序列(N<= 1000),其值无序,现要求你 用最少的交换次数将序列按升序顺序排列。

贪心算法
?

排序后的序列分为三个部分:排序后应存 储1的部分,排序后应存储2的部分和排序后 应存储3的部分,贪心排序法应交换尽量多 的交换后位置正确的(2,1)、(3,1)和 (3,2)数对。当这些数对交换完毕后,再 交换进行两次交换后位置正确的(1,2,3) 三个数。

贪心
?

分 析:很明显,每一次交换都可以改变两 个数的位置,若经过一次交换以后,两个 数的位置都由错误变为了正确,那么它必 定最优。同时我们还可发现,经过两次交 换 后,我们可以随意改变3个数的位置。那 么如果存在三个数恰好为1,2和3,且位置 都是错误的,那么进行两次交换使它们位 置正确也必定最优。有由于该题具有 最优 子结构性质,我们的贪心算法成立。

拼点游戏
?

C和S两位同学一起玩拼点游戏。有一堆白 色卡牌和一堆蓝色卡牌,每张卡牌上写了 一个整数点数。C随机抽取n张白色卡牌,S 随机抽取n张蓝色卡牌,他们进行 n回合拼 点,每次两人各出一张卡牌,点数大者获 得三颗巧克力,小者获得一颗巧克力,如 果点数相同,每人各得二颗巧克力,使用 过的卡牌不得重复使用。已知C 和S取到的 卡牌点数,请编程计算S最多和最少能得到 多少颗巧克力。

田忌赛马
? ?

其实本题就是田忌赛马的翻版 如果3匹马变成1000匹,齐王仍然让他的马 按从优到劣的顺序出赛,田忌可以按任意 顺序选择他的赛马出赛。赢一局,田忌可 以得到200两银子,输一局,田忌就要输掉 200两银子,平局的话不输不赢。 请问田忌最多能赢多少银子?

解题思路
? ? ?

本题可以用DP来解 可以连边进行匹配算法 但是最简单的是贪心算法

贪心
? ?

当田忌最慢的马比齐王最慢的马快,赢一场先
当田忌最慢的马比齐王最慢的马慢,和齐王最快 的马比,输一场 当田忌最快的马比齐王最快的马快时,赢一场先。 当田忌最快的马比齐王最快的马慢时,拿最慢的 马和齐王最快的马比,输一场。

? ?

?

当田忌最快的马和齐王最快的马相等时,拿最慢 的马来和齐王最快的马比.

证明
? ?

?
?

?

?

当田忌最慢的马比齐王最慢的马快,赢一场先。因为始终 要赢齐王最慢的马,不如用最没用的马来赢它。 当田忌最慢的马比齐王最慢的马慢,和齐王最快的马比, 输一场。因为田忌最慢的马始终要输的,不如用它来消耗 齐王最有用的马。 当田忌最慢的和齐王最慢的马慢相等时,分4和5讨论。 当田忌最快的马比齐王最快的马快时,赢一场先。因为最 快的马的用途就是来赢别人快的马,别人慢的马什么马都 能赢。 当田忌最快的马比齐王最快的马慢时,拿最慢的马和齐王 最快的马比,输一场,因为反正要输一场,不如拿最没用 的马输。 当田忌最快的马和齐王最快的马相等时,这就要展开讨论 了,贪心方法是,拿最慢的马来和齐王最快的马比.

电池的寿命
?

小S新买了一个掌上游戏机,这个游戏机由两节5号电池供 电。为了保证能够长时间玩游戏,他买了很多5号电池, 这些电池的生产商不同,质量也 有差异,因而使用寿命也 有所不同,有的能使用5个小时,有的可能就只能使用3个 小时。显然如果他只有两个电池一个能用5小时一个能用3 小时,那么他只能玩 3个小时的游戏,有一个电池剩下的 电量无法使用,但是如果他有更多的电池,就可以更加充 分地利用它们,比如他有三个电池分别能用3、3、5小时, 他可以先 使用两节能用3个小时的电池,使用半个小时后 再把其中一个换成能使用5个小时的电池,两个半小时后 再把剩下的一节电池换成刚才换下的电池(那个电池还能 用 2.5个小时),这样总共就可以使用5.5个小时,没有一 点浪费。 现在已知电池的数量和电池能够使用的时间,请你找一种 方案使得使用时间尽可能的长。

思路
? ? ?

设最大的电池电量为x 其余的电量和为S 如果x>=S ; ans=2*S 这个好理解 否则ans=x+S

思路
? ? ?

?

当x<S 时我们取 最大的两个电池进行消耗 消耗到他们不是最大的为止 此时 x<S 重复进行前两步则S必然趋于0 故x趋于0 所以可以全部消耗

活动安排问题
?

设有n个活动的集合e={1,2,…,n},其中每个 活动都要求使用同一资源,如演讲会场等,而在 同一时间内只有一个活动能使用这一资源。每个 活动i都有 一个要求使用该资源的起始时间si和一 个结束时间fi,且si<fi。如果选择了活动i,则它在 半开时间区间[si,fi]内占用资源。若区间 [si,fi]与 区间[sj,fj]不相交,则称活动i与活动j是相容的。 也就是说,当si≥fi或sj≥fj时,活动i与活动j相容。 活动安排问题就是 要在所给的活动集合中选出最 大的相容活动子集合。

设待安排的11个活动的开始时间和结束时间按结束时间的 非减序排列如下:
i 1 2 3 3 0 4 5 5 3 6 5 7 6 8 8 9 8 10 2 11 12

Star 1 ti End 4 i

5

6

7

8

9

10 11

12 13

14

算法的计算过程如下图所示。图中每行相应 于算法的一次迭代。 阴影长条表示的活动是已选入集合的活动, 而空白长条表示的活 动是当前正在检查相容性的活动。

贪心
?

?

?

? ?

我们先证明 排序后的第一个活动一定在解 集中 假设我们有一个最有解 A 他不包含 活动1 那么我们必然可以将A中end时间最早的替 换成 活动1 得证 以此类推,可以证明贪心算法的最优性

旅行家的预算
?

一个旅行家想驾驶汽车以最少的费用从一个城市 到另一个城市(假设出发时油箱是空的)。给定 两个城市之间的距离D1、汽车邮箱的容量C(以 升为单位)。每升汽油能行使距离D2、出发点的 每升汽油价格P和沿途油站数(N可以是0)、油 站I离出发点的距离Di、油站I每升汽油价格Pi (I=1,2,3……N)。 编程找出一种加油方案,使费用最少,输出 这个最少的费用值,计算结果四舍五入至小数点 后两位。如果无法到达目的地,则输出“No Solution”。

?

旅行家的预算
?

我们可以假设每次都装满油箱,只有当要 用油时才对其付款。
可以很明确的看到,但我们发现油箱里的 油比当前可以买的油贵时,就用便宜的油 来替代,这样一定最优。

?

贪心算法的基本要素
?

对于一个具体的问题,怎么知道是否可用 贪心算法解此问题,以及能否得到问题的 最优解呢?这个问题很难给予肯定的回答。 但是,从许多可以用贪心算法求解的问题 中看到这类问题一般具有2个重要的性质: 贪心选择性质和最优子结构性质。

?

贪心选择性质
?

?

?

所谓贪心选择性质是指所求问题的整体最优解可 以通过一系列局部最优的选择,即贪心选择来达 到。这是贪心算法可行的第一个基本要素,也是 贪心算法与动态规划算法的主要区别。 动态规划算法通常以自底向上的方式解各子问题, 而贪心算法则通常以自顶向下的方式进行,以迭 代的方式作出相继的贪心选择,每作一次贪心选 择就将所求问题简化为规模更小的子问题。 对于一个具体问题,要确定它是否具有贪心选择 性质,必须证明每一步所作的贪心选择最终导致 问题的整体最优解。

最优子结构性质
?

当一个问题的最优解包含其子问题的最优 解时,称此问题具有最优子结构性质。问 题的最优子结构性质是该问题可用动态规 划算法或贪心算法求解的关键特征。

Bridge
?

?

n个人要过河,有一桥,一盏灯,每次桥上 可以过两人,但是一定要带灯。 现给出n个人过桥时间,问最短时间可以过 完桥。

Bridge
? ? ? ? ? ?

当人数等于1,2,3的时候:答案很容易得出; 当人数大于等于4时:
若设过桥速度最快的那个人过桥时间为a,第二快为 b;过桥第二慢的那个人过桥时间为y,最慢为z; 此时有两种过桥方案: 最快和次快的人先过,然后最快的回来,然后最 慢与次慢的人再过,次快的回来; 最快的和最慢的过,快的回来,在和次慢的过, 快的再回来;

Bridge
? ? ? ?

?
? ?

第一种方法时间为b*2+a+z 第二种方法时间为y+z+2*a 如果第一种大于第二种 有2*b+a+z>y+z+2*a 化简得 2*b>y+a; 此时只要比较2*b和a+y的大小即可知道那种方法 更优 每次遵循局部最优策略即可

最优数对
?

按递增的顺序告诉你N个正整数和一个实数 P,要求求出求出该数列中的比例最接近P 的两个数(保证绝对没有两个数使得其比 值为P)。

最优数对
?

定义两个指针i和j,然后进行如下操作:当 code[j]/code[i]>p时i++,当code[j]/code[i]<p 时j++,然后记录其中产生的最优值即可。

连续数之和最大值
?

给你N个数,要求求出其中的连续数之和的 最大值

连续数之和最大值
?

定义一个统计变量tot,然后用循环进行如 下操作:tot+=item 其中如果出现tot<0的情 况,则将tot赋值为0。在循环过程之中tot出 现的最大值即为答案。


2014 NOIP信息学奥赛——算法快速入门教程(中国计算机学会出版)

2014 NOIP信息学奥赛——算法快速入门教程(中国计算机学会出版)_学科竞赛_高中教育...33 中国计算机学会 2014 算法基础篇学习过程序设计的人对算法这个词并不陌生,从...

noip信息竞赛100个基本算法

noip信息竞赛100个基本算法_理学_高等教育_教育专区。算法noip 信息竞赛 100 个...信息竞赛复习资料3--算法... 45页 2下载券 (NOIP)信息学竞赛 贪心算... ...

信息学奥赛基础算法教案

79 基础算法教案 第 0 页共 81 页 第一课 算法简介 算法是一组(有限个)规则,它为某个特定问题提供了解决问题的运算序列。在信息学竞赛中,就 是计算机解题的...

信息学奥赛(NOIP)必看经典书目汇总

(欢迎大家查漏补缺) 基础篇 1、 《全国青少年信息学奥林匹克分区联赛初赛培训...6、 《算法竞赛入门经典》 (推荐指数:5 颗星) 刘汝佳著,算法必看经典。 7、...

信息学奥赛经典算法C语言经典例题100例

信息学奥赛经典算法 C 语言经典例题 100 例 经典C源程序 100 例 题目:有 1、2、3、4 个数字,能组成多少个互不相同且无重复数字的三位数?都是多少? 1....

信息学奥赛算法教程_Pascal

信息学奥赛算法教程_Pascal_初中教育_教育专区。信息学奥赛辅导教程第3章 算法与...A.执行算法程序所需要的时间 B.算法程序的长度 C.算法执行过程中所需要的基本...

信息学奥赛三要素

全国青少年信息学奥林匹克竞赛(noi)和联赛(noip)(简称信息学奥赛,下同)是由...简单算法基本结束)再多进行几次校内测验,从中挑 选优秀者,这些便是最终的奥赛...

信息学奥赛经典算法

信息学奥赛经典算法_计算机软件及应用_IT/计算机_专业资料。信息学奥赛经典算法一、 排序算法 1.1 选择算法 选择排序是一种简单而有效的排序算法, 在问题规模不是...

edu_ecologychuanke132010

初学算法的学生学习搜索的应用。视频教程,幼狮精英学馆全套教学,在线学习高中其他课程,信息学奥赛算法入门——搜索(中)视频下载

edu_ecologychuanke139885

算法初学者并查集的认识和应用。视频教程,幼狮精英学馆全套教学,在线学习高中其他课程,信息学奥赛算法入门——并查集(1)视频下载