《算法设计与分析》递归算法典型例题
算法递归典型例题
实验一：递归策略运用练习
三、实验项目
1．运用递归策略设计算法实现下述题目的求解过程。
题目列表如下：
（1）运动会开了N天，一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚，第二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。到了第N天刚好还有金牌N枚，到此金牌全部发完。编程求N和M。
（2）国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份，然后给第一个儿子一份，再加上剩余财产的1/10；给第二个儿子两份，再加上剩余财产的1/10；……；给第i 个儿子i份，再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱，孰不知国王是“一碗水端平”的。请用程序回答，老国王共有几个儿子？财产共分成了多少份？
源程序：
（3）出售金鱼问题：第一次卖出全部金鱼的一半加二分之一条金鱼；第二次卖出乘余金鱼的三分之一加三分之一条金鱼；第三次卖出剩余金鱼的四分之一加四分之一条金鱼；第四次卖出剩余金鱼的五分之一加五分之一条金鱼；现在还剩下11条金鱼，在出售金鱼时不能把金鱼切开或者有任何破损的。问这鱼缸里原有多少条金鱼？
（4）某路公共汽车，总共有八站，从一号站发轩时车上已有n位乘客，到了第二站先下一半乘客，再上来了六位乘客；到了第三站也先下一半乘客，再上来了五位乘客，以后每到一站都先下车上已有的一半乘客，再上来了乘客比前一站少一个……，到了终点站车上还有乘客六人，问发车时车上的乘客有多少？
（5）猴子吃桃。有一群猴子摘来了一批桃子，猴王规定每天只准吃一半加一只（即第二天吃剩下的一半加一只，以此类推），第九天正好吃完，问猴子们摘来了多少桃子？
（6）小华读书。第一天读了全书的一半加二页，第二天读了剩下的一半加二页，以后天天如此……，第六天读完了最后的三页，问全书有多少页？
（7）日本著名数学游戏专家中村义作教授提出这样一个问题：父亲将2520个桔子分给六个儿子。分完后父亲说：“老大将分给你的桔子的1/8给老二；老二拿到后连同原先的桔子分1/7给老三；老三拿到后连同原先的桔子分1/6给老四；老四拿到后连同原先的桔子分1/5给老五；老五拿到后连同原先的桔子分1/4给老六；老六拿到后连同原先的桔子分1/3给老大”。结果大家手中的桔子正好一样多。问六兄弟原来手中各有多少桔子？
四、实验过程
（一）题目一：……
1.题目分析
由已知可得，运动会最后一天剩余的金牌数gold等于运动会举行的天数由此可倒推每一
天的金牌剩余数，且每天的金牌数应为6的倍数。
2.算法构造
设运动会举行了N天，
If(i==N)Gold[i]=N;
Else gold[i]=gold[i+1]*7/6+i;
3.算法实现
#include
using namespace std;
void main() //主函数
{
int i=0,count=0; //count表示运动会举办的天数
int gold[100]; //定义储存数组
do
{
count=count+6; // 运动会天数加六
gold[count]=count;
for (i=count-1; i>=1; i--)
{
if (gold[i+1]%6!=0 )
break; // 跳出for循环
else
gold[i]=gold[i+1]*7/6+i; //计算第i天剩余的金牌数
}
} while( i>=1 ); // 当i>=1 继续做do循环
cout <<"运动会开了"< cout<<"总共发了"< } 4.运行结果 （二）题目二：…… 1.题目分析 由已知可得，最后一个儿子得到的遗产份数即为王子数目，由此可得到每个儿子得到的遗产份数，在对遗产数目进行合理性判断可得到符合要求的结果。 2.算法构造 设皇帝有count个王子， property[count]=count; for (i=count-1; i>=1; i--) { if (property[i+1]%9!=0 ) break; // 数目不符跳出for循环 else property[i]=property[i+1]*10/9+i; //计算到第i个王子时剩余份数} 3.算法实现 #include using namespace std; void main() //主函数 { int i=0,count=0; //count表示国王的儿子数 int property[100]; //定义储存数组，表示分配到每个王子时剩余份数 do { count=count+9; //王子数目为9的倍数 property[count]=count; for (i=count-1; i>=1; i--) { if (property[i+1]%9!=0 ) break; // 数目不符跳出for循环 else property[i]=property[i+1]*10/9+i; //计算到第i个王子时剩余份数} } while( i>=1 ); // 当i>=1 继续做do循环 cout <<"皇帝有"< cout<<"遗产被分成"< 4.运行结果 （三）题目三：…… 1.题目分析 由最后一天的金鱼数目，可递推得到每天的金鱼数目，第一天的数目即为金鱼总数。 2.算法构造 fish[5]=11; for (i=4; i>=1; i--) fish[i]=(fish[i+1]*(i+1)+1)/i; //计算到第i天剩余金鱼条数 3.算法实现 #include using namespace std; void main() //主函数 { int i=0; int fish[6]; //定义储存数组各天剩余金鱼数 fish[5]=11; for (i=4; i>=1; i--) fish[i]=(fish[i+1]*(i+1)+1)/i; //计算到第i天剩余金鱼条数 c out<<"浴缸里原有金鱼"< } 4.运行结果 （四）题目四：…… 1.题目分析 有到终点站时车上的乘客数可求得到任意一站的乘客人数，到第二站时车上的乘客数目即为发车时车上的乘客数。 2.算法构造 n um[8]=6; //到终点站车上还有六人 f or(i=7; i>=2; i--) num[i]=2*(num[i+1]-8+i); //计算到第i站车上的人数 3.算法实现 #include using namespace std; void main() //主函数 { int i=0; i nt num[9]; //定义储存数组 n um[8]=6; //到终点站车上还有六人 f or(i=7; i>=2; i--) num[i]=2*(num[i+1]-8+i); //计算到第i站车上的人数 c out<<"发车时车上有"< } 4.运行结果 （五）题目五：…… 1.题目分析 可假设有第十天，则第十天剩余的桃子数目为0，由此递推可得每一天剩余的桃子数目。 第一天的桃子数目即为猴子摘桃子的总数。 2.算法构造 n um[10]=0; //第n天吃前的桃子数 f or(i=9; i>=1; i--) 3.算法实现 num[i]=2*(num[i+1]+1); //计算到第i天剩余的桃子数算法实现 #include using namespace std; void main() //主函数 { int i=0; i nt num[11]; //定义储存数组 n um[10]=0; //第n天吃前的桃子数 f or(i=9; i>=1; i--) num[i]=2*(num[i+1]+1); //计算到第i天剩余的桃子数 c out<<"猴子共摘来了"< } 4.运行结果 （六）题目六：…… 1.题目分析 由第六天剩余的页数可递推得到每天的剩余页数，第一天的页数即为全书的页数 2.算法构造 num[6]=3; //到第n天时剩余的页数 f or(i=5; i>=1; i--) num[i]=2*(num[i+1]+2); //计算到第i天剩余的页数 3.算法实现 #include using namespace std; void main() //主函数 { int i=0; i nt num[7]; //定义储存数组 n um[6]=3; //到第n天时剩余的页数 f or(i=5; i>=1; i--) num[i]=2*(num[i+1]+2); //计算到第i天剩余的页数 c out<<"全书共有"< } 4.运行结果 （七）题目七：…… 1.题目分析 由已知可得，第一个儿子得到的橘子数目为平均数的一半，由此可得到第一个儿子原先的橘子数目，而第i个儿子原先的橘子数目可由递推公式得到； 2.算法构造 if(i==0) { a[i]=(ave-ave/2)*(8-i)/(8-i-1); //第一个儿子的数目 left=a[i]-ave/2; } else { a[i]=ave*(8-i)/(8-i-1)-left; //由left求第i+1个儿子的橘子数目 left=ave/(8-i-1); //第i+1个儿子得到的橘子数目} 3.算法实现 #include using namespace std; void main() { i nt a[6]; //存放六个儿子原先手中的橘子数目 i nt left=0; //存放下一个儿子得到的橘子数目 i nt ave=420; f or(int i=0;i<6;i++) { if(i==0) { a[i]=(ave-ave/2)*(8-i)/(8-i-1); //第一个儿子的数目 left=a[i]-ave/2; } else { a[i]=ave*(8-i)/(8-i-1)-left; //由left求第i+1个儿子的橘子数目 left=ave/(8-i-1); //第i+1个儿子得到的橘子数目} } f or(i=0;i<6;i++) cout<<"第"< } 4.运行结果 应注意：已知一个力和它的另一个分力的方向，则另一个分力有无数个解，且有最小值（两分力方向垂直时）。 3. 分力方向的确定 分解的原则：根据力所产生的效果进行分解，一个力可以分解成无数对分力，但对于一个确定的物体所受到的力进行分解时，应考虑实际效果，即进行有意义分解。 4. 力的分解的解题思路 力分解问题的关键是根据力的实际作用效果，画出力的平行四边形，接着就转化为一个根据已知边角关系求解的几何问题，因此其解题基本思路可表示为 5. 力的分解的几种情况 已知一个力的大小和方向，求它的两个分力。 据平行四边形定则知，这种情况下可以作出无数个符合条件的平行四边形，即对一已知力分解，含有无数个解，但如果再加以下条件，情况就不一样了，下面讨论： （1）已知两个分力的方向时，有唯一解，如图所示。 （2）已知一个分力1 F 的大小和方向，力的分解有唯一解，如图所示，只能作出一个平行四边形。 （3）已知两个分力的大小，力的分解可能有两个解，如图所示，可作出两个平行四边形。 （4）已知一个分力1F 的方向与另一个分力2F 的大小，如图所示，则：当θsin F F 2=时，有唯一解，如图甲所示；当θsin F F 2<时，无解，如图乙所示；当 θsin F F F 2>>时，存在两个解，如图丙所示；当F F 2>时，存在一个解，如图丁所示。 总结：如图所示，已知力F 的一个分力1F 沿OA 方向，另一个分力大小为 2F 。我们可以以合力F 的末端为圆心，以分力2 F 的长度为半径作圆弧，各种情况均可由图表示出来。 6. 求分力的方法 （1）直角三角形法。 对物体进行受力分析，对其中的某力按效果或需要分解，能构成直角三角形的，可直接应用直角三角形边、角的三角函数关系求解，方便快捷。 （2）正交分解法。 ①以力的作用点为原点作直角坐标系，标出x 轴和y 轴，如果这时物体处于平衡状态，则两轴的方向可根据方便自己选择。 ②将与坐标轴不重合的力分解成x 轴方向和y 轴方向的两个分力，并在图上标明，用符号x F ，和 y F 表示。 ③在图上标出力与x 轴或力与y 轴的夹角，然后列出x F 、y F 的数学表达式，如：F 与x 轴夹角为θ，则θcos F F x =，θ sin F F y =与两轴重合的力就不需要分解了。 ④列出x 轴方向上的各分力的合力和y 轴方向上的各分力的合力的两个方程，然后再求解。 （3）相似三角形法。 对物体进行受力分析，根据题意对其中的某力分解，找出与力的矢量三角形相似的几何三角形，用相似三角形对应边的比例关系求解。 （4）动态矢量三角形（动态平衡）法。 所谓动态平衡问题是指通过控制某些物理量，使物体的状态发生缓慢变化，而在这个过程中物体又始终处于一系列的平衡状态，利用图解法解决此类问题方便快捷。 【典型例题】 贪心算法经典例题 发布日期：2009-1-8 浏览次数：1180 本资料需要注册并登录后才能下载！ ·用户名密码验证码找回密码·您还未注册？请注册 您的账户余额为元，余额已不足，请充值。 您的账户余额为元。此购买将从您的账户中扣除费用0.0元。 内容介绍>> 贪心算法经典例题 在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解，这种求解方法就是贪心算法。 从贪心算法的定义可以看出，贪心法并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法可以得到最优解。 我们看看下面的例子 例1 均分纸牌（NOIP2002tg） [问题描述] 有 N 堆纸牌，编号分别为 1，2，…, N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若干张纸牌，然后移动。移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。例如 N=4，4 堆纸牌数分别为： ①9 ②8 ③17 ④ 6 移动3次可达到目的： 从③取 4 张牌放到④（9 8 13 10） -> 从③取 3 张牌放到②（9 11 10 10）-> 从②取 1 张牌放到①（10 10 10 10）。 [输入]：键盘输入文件名。 文件格式：N（N 堆纸牌，1 <= N <= 100） A1 A2 … An （N 堆纸牌，每堆纸牌初始数，l<= Ai <=10000） [输出]：输出至屏幕。格式为：所有堆均达到相等时的最少移动次数。 [输入输出样例] a.in： 4 9 8 17 6 屏慕显示：3 算法分析：设a[i]为第i堆纸牌的张数（0<=i<=n），v为均分后每堆纸牌的张数，s为最小移到次数。 我们用贪心法，按照从左到右的顺序移动纸牌。如第i堆(0 银行家算法例题 系统中原有三类资源A、B、C和五个进程P1、P2、P3、P4、P5，A资源17，B资源5，C资源20。当前（T0时刻）系统资源分配和进程最大需求如下表。 1、现在系统T0时刻是否处于安全状态？ 2、是否可以允许以下请求？ (1)T1时刻：P2 Request2=(0,3,4) (2)T2时刻：P4 Request4=(2,0,1) (3)T3时刻：P1 Request1=(0,2,0) 注：T0 T1 T2 T3时刻是前后顺序，后一时刻是建立在前一时刻的基础上。 解：由题设可知Need=Max-Allocation AvailableA=17-(2+4+4+2+3)=2(原有-分配) 同理AvailableB=3,AvailableC=3 可得T0时刻资源分配表如下所示（表中数据顺序均为A B C）： 1、判断T0时刻是否安全，需要执行安全算法找安全序列，过程如下表： T0时刻能找到一个安全序列{P4,P3,P2,P5,P1},故T0时刻系统处于安全状态。 2、判断T1 T2 T3时刻是否满足进程请求进行资源分配。 （1）T1时刻，P2 Request2=(0,3,4) //第一步判断条件 ①满足Request2=(0,3,4)<=Need2(1,3,4) ②不满足Request2=(0,3,4)<=Available(2,3,3) 故系统不能将资源分配给它，此时P2必须等待。 （2）T2时刻，P4 Request4=(2,0,1) //第一步判断条件①满足Request4=(2,0,1)<=Need4(2,2,1) ②满足Request4=(2,0,1)<=Available(2,3,3) //第二步修改Need、Available、Allocation的值 Available=Available-Request4= (0,3,2) Allocation4=Allocation4+Request4=(4,0,5) Need4=Need4-Request4=(0,2,0) //第三步执行安全算法，找安全序列 (注解：先写上work，其初值是系统当前进行试分配后的Available(0,3,2) ，找五个进程中Need小于work的进程，比如Need4<=Work满足，则将P4写在第一行的最前面，同时写出P4的Need和Allocation，以此类推) 北京四中编稿老师：肖伟华审稿老师：肖伟华责编: 郭金娟 力的合成与分解 本节课我们需要掌握以下几个概念： 1、合力与分力； 2、力的合成、分解； 3、矢量与标量； 4、熟练掌握力的合成与分解的定则：平行四边形定则。 5、理解一种物理学处理问题的方法：等效替代法，并能用这种方法解决有关力学问题。 一、合力与分力： 在实际问题中，一个物体往往同时受到几个力的作用。如果一个力产生的效果与原来几个力产生的效果相同，这个力就叫那几个力的合力，而那几个力就叫这个力的分力。 二、力的合成与分解： 求几个力的合力的过程叫力的合成，求一个力的分力的过程叫力的分解。 合力与分力有等效性与可替代性。求力的合成的过程实际上就是寻找一个与几个力等效的力的过程；求力的分解的过程，实际上是寻找几个与这个力等效的力的过程。 三、力的平行四边形定则： 在中学阶段，我们主要处理平面力学中的共点力的合成与分解。 1、一条直线上的两个共点力的合成方法： 选定一定正方向，我们用“+”、“-”号代表力的方向，与正方向相同的力前面加“+”号，与正方向相反的力前面加“-”号。有了这种规定以后，一条直线上的力的合成就可以转化为代数加减了：当两个力的方向相同时，合力的大小等于两个分力数值相加，方向与分力的方向相同；当两个力的方向相反时，合力的大小等于两个分力数值上相减，方向与大的那个分力相同。 2、互成角度的共点力的合成、分解： 实验表明，两个互成角度的共点力的合力，可以用表示这两个力的有向线段为邻边作平行四边形，这两个邻边之间的对角线就表示合力的大小和方向，这就是力的平行四边形定则。 力的分解是合成的逆运算，即以表示合力的有向线段为对角线，作平行四边形，与合力作用点共点的两个邻边就表示两个分力的大小和方向。 在理解力的合成与分解时应注意的问题： 1）合力与分力在效果上是相同的，可以互相替代。在求力的合成时，合力只是分力的效果，实际并不存在；同样，在求力的分解时，分力只是合力产生的效果，实际并不存在。因此在进行受力分析时，不能同时把合力与分力都当作物体所受的力。 算法设计与分析试卷 一、填空题（20分，每空2分） 1、算法的性质包括输入、输出、确定性、有限性。 2、动态规划算法的基本思想就将待求问题分解成若干个子问题、先求解子问题，然后 从这些子问题的解得到原问题的解。 3、设计动态规划算法的4个步骤： （1）找出最优解的性质，并刻画其结构特征。 （2）递归地定义最优值。 （3）以自底向上的方式计算出最优值。 （4）根据计算最优值得到的信息，构造最优解。 4、流水作业调度问题的johnson算法： （1）令N1={i|ai 银行家算法例题 假定系统中有五个进程{P0，P1，P2，P3，P4} 和三类资源{A ，B,C},各种资源的数量分别为10、5、7，在T0 时刻的资源分配情况 （1）T0时刻的安全性 利用安全性算法对T0时刻的资源分配情况进行分析 （2）P1请求资源：P1发出请求向量Request1(1,0,2),系统按银行家算法进行检查 ①Request1（1，0，2）≤Need1（1，2，2） ②Request1（1，0，2）≤Available1（3,3,2) ③系统先假定可为P1分配资源，并修改Available ，Allocation1和Need1向量，由此形成 资源情况 进程 Max Allocation Need Available A B C A B C A B C A B C P0 7 5 3 0 1 0 7 4 3 3 3 2 P1 3 2 2 2 0 0 1 2 2 P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1 资源情况 进程 Work A B C Need A B C Allocation A B C Work+Allocatio n A B C Finish P1 3 3 2 1 2 2 2 0 0 5 3 2 TRUE P3 5 3 2 0 1 1 2 1 1 7 4 3 TRUE P4 7 4 3 4 3 1 0 0 2 7 4 5 TRUE P2 7 4 5 6 0 0 3 0 2 10 4 7 TRUE P0 10 4 7 7 4 3 0 1 0 10 5 7 TRUE 操作系统之调度算法和死锁中的银行家算法习 题答案 集团文件发布号：（9816-UATWW-MWUB-WUNN-INNUL-DQQTY- 1. 有三个批处理作业，第一个作业 10:00 到达，需要执行 2 小时；第二个作业在10:10到达，需要执行 1 小时；第三个作业在 10:25 到达，需要执行 25 分钟。分别采用先来先服 务，短作业优先和最高响应比优先三种调度算法，各自的平均周转时间是多少？解： 先来先服务： （结束时间=上一个作业的结束时间+执行时间 周转时间=结束时间-到达时间=等待时间+执行时间） 按到达先后，执行顺序：1->2->3 短作业优先： 1)初始只有作业1，所以先执行作业1，结束时间是12:00，此时有作业2和3； 2)作业3需要时间短，所以先执行； 3)最后执行作业2 最高响应比优先： 高响应比优先调度算法既考虑作业的执行时间也考虑作业的等待时间，综合了先来先服务和最短作业优先两种算法的特点。 1)10:00只有作业1到达，所以先执行作业1； 2)12:00时有作业2和3， 作业2：等待时间=12:00-10:10=110m;响应比=1+110/60=2.8； 作业3：等待时间=12:00-10:25=95m，响应比=1+95/25=4.8； 所以先执行作业3 3)执行作业2 2. 在一单道批处理系统中，一组作业的提交时刻和运行时间如下表所示。试计算一下三种 作业调度算法的平均周转时间 T 和平均带权周转时间 W。 （ 1）先来先服务；（ 2）短作业优先（ 3）高响应比优先 解： 先来先服务： 作业顺序：1,2,3,4 短作业优先： 作业顺序： 力的合成与分解 课题力的合成与分解计划课时 2 节 教学目标1、理解合力与分力的概念。 2、理解共点力的概念 3、掌握力的合成方法。 4、掌握力的分解方法。 教学重点力的合成与分解 教学难点对实际问题进行正确的力的分解 教学方法探究法、讨论法 教学内容及教学过程 一、引入课题 物体往往会受到多个力的作用，如何求解物体所受的合力呢？ 二、主要教学过程 知识点一、力的合成和分解 1．合力与分力 (1)定义：如果一个力产生的效果跟几个共点力共同作用产生的效果相同，这一个力就叫做那几个力的合力，原来的几个力叫做分力。 (2)关系：合力和分力是等效替代的关系。 2．共点力 作用在物体的同一点，或作用线的延长线交于一点的力。 3．力的合成 (1)定义：求几个力的合力的过程。 (2)运算法则 ①平行四边形定则：求两个互成角度的共点力的合力，可以用表示这两个力的线段为邻边作平行四边形，这两个邻边之间的对角线就表示合力的大小和方向。 ②三角形定则：把两个矢量首尾相接，从而求出合矢量的方法。 图1 4．力的分解 (1)定义：求一个已知力的分力的过程。 (2)遵循原则：平行四边形定则或三角形定则。 (3)分解方法：①按力产生的效果分解；②正交分解。 知识点二、矢量和标量 1．矢量：既有大小又有方向的量，相加时遵从平行四边形定则。 2．标量：只有大小没有方向的量，求和时按代数法则相加。 三、典型例题分析 【例1】(多选)两个共点力F1、F2大小不同，它们的合力大小为F，则( ) A．F1、F2同时增大一倍，F也增大一倍 B．F1、F2同时增加10 N，F也增加10 N C．F1增加10 N，F2减少10 N，F一定不变 D．若F1、F2中的一个增大，F不一定增大 解析F1、F2同时增大一倍，F也增大一倍，选项A正确；F1、F2同时增加10 N，F不一定增加10 N，选项B错误；F1增加10 N，F2减少10 N，F可能变化，选项C错误；若F1、F2中的一个增大，F不一定增大，选项D正确。 【例2】一物体受到三个共面共点力F1、F2、F3的作用，三力的矢量关系如图4所示(小方格边长相等)，则下列说法正确的是( ) 图4 A．三力的合力有最大值F1＋F2＋F3，方向不确定 B．三力的合力有唯一值3F3，方向与F3同向 C．三力的合力有唯一值2F3，方向与F3同向 D．由题给条件无法求合力大小 解析先以力F1和F2为邻边作平行四边形，其合力与F3共线，大小F12＝2F3如图所示，合力F12再与第三个力F3合成求合力F合。可见F合＝3F3。 答案 B 【例3】(多选)如图5所示，电灯的重力G＝10 N，AO绳与顶板间的夹角为45°，BO绳水平，AO 绳的拉力为F A，BO绳的拉力为F B，则(注意：要求按效果分解和正交分解两种方法求解)( ) 图5 A．F A＝10 2 N B．F A＝10 N C．F B＝10 2 N D．F B＝10 N 解析效果分解法在结点O，灯的重力产生了两个效果，一是沿AO向下的拉紧AO的分力F1，二是沿BO向左的拉紧BO绳的分力F2，分解示意图如图所示。 贪心算法概论 贪心算法一般来说是解决“最优问题”，具有编程简单、运行效率高、空间 复杂度低等特点。是信息学竞赛中的一个有为武器，受到广大同学们的青睐。本 讲就贪心算法的特点作些概念上的总结。 一、贪心算法与简单枚举和动态规划的运行方式比较 贪心算法一般是求“最优解”这类问题的。最优解问题可描述为：有n个输入，它的解是由这n 个输入的某个子集组成，并且这个子集必须满足事先给定的条 件。这个条件称为约束条件。而把满足约束条件的子集称为该问题的可行解。这 些可行解可能有多个。为了衡量可行解的优劣，事先给了一个关于可行解的函数，称为目标函数。目标函数最大（或最小）的可行解，称为最优解。 a)求“最优解”最原始的方法为搜索枚举方案法（一般为回溯法）。 除了极简单的问题，一般用深度优先搜索或宽度优先搜索。通常优化方法为利用约束条件进行可行性判断剪枝；或利用目标函数下界（或上界），根据当前最 优解进行分枝定界。 b)其次现今竞赛中用的比较普遍的动态规划（需要满足阶段无后效性原则）。 动态规划主要是利用最最优子问题的确定性，从后向前（即从小规模向大规模）得到当前最优策略，从而避免了重复的搜索。 举例说明：求多段图的最短路径。 在图（1）中，我们省略了各线段的长度。 如果用回溯法，搜索树大致如下： 显然，上面的搜索有大量重复性工作。比如节点8、9、10到11的最短路分别被调用了9次，从节点5、6、7到节点11也分别搜索了3次。 如果先算出节点8、9、10到11的最短路，由于它与前面的点无关，因此最优值确定下来，再用它们求定节点5、6、7 到节点11 的最短路径。同理，再用节 点5、6、7 的最优值，来求节点2、3、4 优值。最后从节点2、3、4 推出1 到 11的最优值。显然复杂度大为降低。 当然，如果本题把简单搜索改为搜索＋记忆化的方法，则就是得能动态规划的原理，本质上就是动态规划，只是实现的方法不同与传统的表格操作法。搜索＋记忆化算法有其特有的特点，以后再讨论。 c)贪心算法则不同，它不是建立在枚举方案的基础上的。它从前向后，根据当前情况，“贪心地”决定出下一步，从而一步一步直接走下去，最终得到解。 假如上面的例子中，我们定下这样的贪心策略：节点号k%3= =1。则有图3： 银行家算法流程 安全性算法流程图 银行家算法例题 1.假定系统中有4个进程1P ，2P ，3P ，4P ， 3种类型的资源1R ，2R ，3R ，数量分别为9,3,6， 0T 时刻的资源分配情况如表2-1所示。 表2-1 T 0时刻的资源分配情况 试问: (1) T 0时刻是否安全？ (2) T 0时刻以后，若进程P 2发出资源请求Request 2(1,0,1), 系统能否将资源分配给它？ (3) 在进程P 2申请资源后，若P1发出资源请求Request 1(1,0,1), 系统能否将资源分配 给它？ (4) 在进程P 1申请资源后，若P3发出资源请求Request 3(0,0,1), 系统能否将资源分配 给它？ 2. 在银行家算法中，出现以下资源分配情况（见表2-2） 系统剩余资源数量=(3,3,2) (1) 该状态是否安全（给出详细的检查过程） (2) 如果进程依次有如下资源请求： P1：资源请求request （1,0,2） P2：资源请求request （3,3,0） P3：资源请求request （0,1,0） 则系统该如何进行资源分配才能避免死锁？ 3.设系统中有3种类型的资源（A、B、C）和5个进程P1、P2、P3、P4、P5，A资源的数量为17，B资源的数量为5，C资源的数量为20。在T0时刻，系统状态见表2-3。系统采用银行家算法实现死锁避免。 (1)T0时刻是否为安全状态？若是，请给出安全序列 (2)在T0时刻，若进程P2请求资源（0,3,4），是否能实施资源分配？为什么？ (3)在（2）的基础上，若进程P4请求资源（2,0,1），是否能实施资源分配？ (4)在（3）的基础上，若进程P1请求资源（0,2,0），是否能实施资源分配？ 4．某系统有R1、R2、R3共三种资源，在T0时刻P1、P2、P3、P4这四个进程对资源的占用和需求情况见表2-24，此时系统的可用资源矢量为（2，1，2）。试问： 1）将系统中各种资源总数和此刻各进程对各资源的需求数目用矢量或矩阵表示出来。2）如果此时进程P1和进程P2均发出资源请求矢量Request（1，0，1），为了保证系统的安全性，应如何分配资源给这两个进程？说明所采用策略的原因。 3）如果2）中两个请求立即得到满足后，系统此刻是否处于死锁状态？ 5．考虑某个系统在表2-25时刻的状态 力的合成与分解 【典型例题】 类型一、求合力的取值范围 例1、物体同时受到同一平面内的三个共点力的作用,下列几组力的合力不可能为零的是( ) A.5 N,7 N,8 N B.5 N,2 N,3 N C.1 N,5 N,10 N D.10 N,10 N,10 N 【答案】C 【解析】分析A?B?C?D各组力中,前两力合力范围分别是:2 N≤F合≤12 N,第三力在其范围之内:3 N≤F合≤7 N,第三力在其合力范围之内;4 N≤F合≤6 N,第三力不在其合力范围之内;0≤F合≤20 N,第三力在其合力范围之内,故只有C中第三力不在前两力合力范围之内,C中的三力合力不可能为零. 【点评】共点的三个力的合力大小范围分析方法是:这三个力方向相同时合力最大,最大值等于这三个力大小之和;若这三个力中某一个力处在另外两个力的合力范围中,则这三个力的合力最小值是零. 举一反三 【变式】一个物体受三个共点力的作用，它们的大小分别为F1＝7 N、F2＝8 N、F3＝9 N．求它们的合力的取值范围？【答案】0≤F≤24 N 类型二、求合力的大小与方向 例2、如图所示，物体受到大小相等的两个拉力作用，每个拉力都是20 N，夹角是60°，求这两个力的合力． 【解析】本题给出的两个力大小相等，夹角为60°，所以可以通过作图和计算两种方法计算合力的大小． 解法1(作图法)：取5 mm长线段表示5 N，作出平行四边形如图甲所示，量得对角线长为35 mm.合力F大小为35 N，合力的方向沿F1、F2夹角的平分线． 解法2(计算法)：由于两个力大小相等，所以作出的平行四边形是菱形，可用计算法求得合力F，如图乙所示，【点评】力的合成方法有“作图法”和“计算法”，两种解法各有千秋.“作图法”形象直观，一目了然，但不够精确，误差大；“计算法”是先作图，再解三角形，似乎比较麻烦，但计算结果更准确. 【高清课程：力的合成与分解例2】 例3、如左图在正六边形顶点A分别施以F1～F55个共点力，其中F3=10N，A点所受合力为；如图，在A 点依次施以1N～6N，共6个共点力．且相邻两力之间夹角为600，则A点所合力为。 安徽大学2010-2011学年第1学期《算法分析与设计》 期末试题 押宝 （内部交流，非考试试题，学生自发交流创作，版权归作者testfudan@https://www.wendangku.net/doc/4e3910961.html, 所有） 一、选择题(单选)(10*2’=20’) 1. 选择正确的组合对于 2112n +=( ) ①2()o n ② 2()O n ③2()n θ ④2()n Ω ⑤ 2()n ω A. ①③④ B. ②③④ C.③④⑤ D. ①⑤ 2. ①21()()n i i O n O n ==∑ ②2()()n O n O n = ③(log )()O n O n ? ④ 2.99993 ()n O n = ⑤2/lo g ()n n n ω=其中正确的有（ ） A ．5组 B.4组 C.3组 D.没有正确的 3. 2/102n n +=（ ） A. 2()O n B.(2)n O C.2(2)n n O + D.2 ()o n 4. 211/n += ( )（我认为是比较不错的一道题，考试可能会出现相同的方法，用极限定义来做，最后一节课老师也讲过类似的方法） A. ()O n B.()o n C.()n Ω D.(1)O 5. 310lo g n = ( ) A.(log )O n n B. (log )O n C. 3()O n D. lo g ()n O n 6. 认真完成课后习题P5面的算法分析题1-6，里面也有我不会做的，可是有谁愿意讨论？ 如果能够把以上的题目都能做对，应该就是掌握了。给自己一个奖励吧！答案(如有问题，联系我吧)：1-5：BBBDB 6.做出来对对答案吧。 二、填空题 1.()2(/2)T n T n n =+????的一个渐进上界为 （答案：(log )O n n ，用迭代法） 2.()(/3)(2/3)()T n T n T n O n =++的一个渐进上界为 （答案：(log )O n n ，用递归树求解，不会的赶快看） 3.()9(/3)T n T n n =+的一个渐进紧致界为 （答案：2 ()n θ，采用迭代法或者采用主方法，不会的赶快看） 《银行家算法的模拟实现》 --实验报告 题目: 银行家算法的模拟实现 专业: 班级: 组员: 指导老师: 一、实验目的 死锁会引起计算机工作僵死，因此操作系统中必须防止。本实验的目的在于让学生独立的使用高级语言编写和调试一个系统动态分配资源的简单模拟程序，了解死锁产生的条件和原因，并采用银行家算法有效地防止死锁的发生，以加深对课堂上所讲授的知识的理解。 二、实验内容 模拟实现银行家算法实现死锁避免。要求：初始数据（如系统在T0时刻的资源分配情况、每一种资源的总数量）从文本文件读入，文件中给出最大需求矩阵Max、分配矩阵Allocation，在程序中求得需求矩阵Need和可利用资源向量Available。 三、实验分析过程 1、整个银行家算法的思路。 先对用户提出的请求进行合法性检查，再进行预分配，利用安全性检查算法进行安全性检查。 1)进程一开始向系统提出最大需求量. 2)进程每次提出新的需求(分期贷款)都统计是否超出它事先提出的最大需求量. 3)若正常,则判断该进程所需剩余剩余量(包括本次申请)是否超出系统所掌握的 剩余资源量,若不超出,则分配,否则等待 2、算法用到的主要数据结构和C语言说明。 （1）、可利用资源向量INT A V AILABLE[M] M为资源的类型。 （2）、最大需求矩阵INT MAX[N][M] N为进程的数量。 （3）、已分配矩阵INT ALLOCA TION[N][M] （4）、还需求矩阵INT NEED[N][N] （5）、申请各类资源数量int Request[x]; // （6）、工作向量int Work[x]; （7）、int Finish[y]; //表示系统是否有足够的资源分配给进程，0为否，非0为是 3、银行家算法（主程序） （1）、系统初始化。输入进程数量，资源种类，各进程已分配、还需求各资源数量，各资源可用数量等 （2）、输入用户的请求三元组（I，J，K），为进程I申请K个J类资源。 （3）、检查用户的请求是否小于还需求的数量，条件是K<=NEED[I,J]。如果条件不符则提示重新输入，即不允许索取大于需求量 （4）、检查用户的请求是否小于系统中的可利用资源数量，条件是K<=A V ALIABLE[I,J]。 如果条件不符则申请失败，阻塞该进程，重新进行进程动态资源申请（使用goto语句） （5）、进行资源的预分配，语句如下： A V ALIBLE[I][J]= A V ALIBLE[I][J]-K； ALLOCATION[I][J]= ALLOCATION[I][J]+K； NEED[I][J]=NEED[I][J]-K； 力的分解基本知识点与练习题 基本知识点 一、分力的概念 1、几个力，如果它们共同产生的效果跟作用在物体上的一个力产生的效果相同，则这几个力就叫做 那个力的分力(那个力就叫做这几个力的合力)。 2、分力与合力是等效替代关系，其相同之处是作用效果相同；不同之处是不能同时出现，在受力分 析或有关力的计算中不能重复考虑。 二、力的分解 1、力的分解的概念：求一个已知力的分力叫做力的分解。 2、力的分解是力的合成的逆运算。同样遵守力的平行四边形定则：如果把已知力F作为平行四边形的 对角线，那么，与力F共点的平行四边形的两个邻边就表示力F的两个分力F1和F2。 3、力的分解的特点是：同一个力，若没有其他限制，可以分解为无数对大小、方向不同的力(因为对于 同一条对角线．可以作出无数个不同的平行四边形)，通常根据力的作用效果分解力才有实际意义。 4、按力的效果分解力F的一般方法步骤： (1)根据物体(或结点)所处的状态分析力的作用效果 (2)根据力的作用效果，确定两个实际分力的方向； (3)根据两个分力的方向画出平行四边形； (4)根据平行四边形定则，利用学过的几何知识求两个分力的大小。也可根据数学知识用计算法。 三、对一个已知力进行分解的几种常见的情况和力的分解的定解问题 将一个力F分解为两个分力，根据力的平行四边形法则，是以这个力F为平行四边形的一条对角线作一个平行四边形。在无附加条件限制时可作无数个不同的平行四边形。这说明两个力的合力可唯一确定，一个力的两个分力不是唯一的。要确定一个力的两个分力，一定有定解条件。 假设合力F一定 1、当俩个分力F1已知，求另一个分力F2，如图F2有唯一解。 2、当俩个分力F 1, F2的方向已知，求这俩个力，如图F1，F2 有唯一解 3、当俩个分力F1, F2的大小已知，求解这俩个力。 从贪心算法的定义可以看出，贪心法并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法可以得到最优解。 我们看看下面的例子 例1 均分纸牌（NOIP2002tg） [问题描述] 有 N 堆纸牌，编号分别为 1，2，…, N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若干张纸牌，然后移动。移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。例如 N=4，4 堆纸牌数分别为： ①9 ②8 ③17 ④6 移动3次可达到目的： 从③取 4 张牌放到④（9 8 13 10） -> 从③取 3 张牌放到②（9 11 10 10）-> 从②取 1 张牌放到①（10 10 10 10）。 [输入]：键盘输入文件名。 文件格式：N（N 堆纸牌，1 <= N <= 100） A1 A2 … An （N 堆纸牌，每堆纸牌初始数，l<= Ai <=10000） [输出]：输出至屏幕。格式为：所有堆均达到相等时的最少移动次数。 [输入输出样例] ： 4 9 8 17 6 屏慕显示：3 算法分析：设a[i]为第i堆纸牌的张数（0<=i<=n），v为均分后每堆纸牌的张数，s为最小移到次数。 我们用贪心法，按照从左到右的顺序移动纸牌。如第i堆(0 银行家算法 xxx 711103xx 2012年5月21日一、实验目的 通过实验，加深对多实例资源分配系统中死锁避免方法——银行家算法的理解，掌握Windows环境下银行家算法的实现方法，同时巩固利用Windows API进行共享数据互斥访问和多线程编程的方法。 二、实验内容 1. 在Windows操作系统上，利用Win32 API编写多线程应用程序实现银行家算法。 2. 创建n个线程来申请或释放资源，只有保证系统安全，才会批准资源申请。 3. 通过Win32 API提供的信号量机制，实现共享数据的并发访问。 三、实验步骤（设计思路和流程图） 最主要的用以实现系统功能的应该有两个部分，一是用银行家算法来判断，二是用安全性算法来检测系统的安全性。 1、银行家算法 设Requesti是进程Pi的请求向量，如果Requesti［j］=K，表示进程Pi 需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查： (1) 如果Requesti［j］≤Need［i,j］，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。 (2) 如果Requesti［j］≤Available［j］，便转向步骤(3)；否则，表示尚无足够资源，Pi须等待。 (3) 系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：Available［j］∶=Available［j］-Requesti［j］; Allocation［i,j］∶=Allocation［i,j］+Requesti［j］; Need［i,j］∶=Need［i,j］-Requesti［j］; (4) 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。 2、安全性算法 (1) 设置两个向量：①Work∶=Available; ②Finish (2) 从进程集合中找到一个能满足下述条件的进程：①Finish［i］=false; ②Need［i,j］≤Work［j］；若找到，执行步骤(3)，否则，执行步骤(4)。(3) 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Work［j］∶=Work［i］+Allocation［i,j］; Finish［i］∶=true; go to step 2; (4) 如果所有进程的Finish［i］=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。 淮海工学院计算机工程学院实验报告书 课程名：《操作系统原理》 题目：银行家算法 班级： 学号： 姓名： 一、实验目的 银行家算法是操作系统中避免死锁的典型算法，本实验可以加深对银行家算法的步骤和相关数据结构用法的更好理解。 实验环境 Turbo C 2.0/3.0或VC++6.0 实验学时 4学时，必做实验。 二、实验内容 用C语言编写一个简单的银行家算法模拟程序，用银行家算法实现资源分配。程序能模拟多个进程共享多种资源的情形。进程可动态地申请资源，系统按各进程的申请动态地分配资源。要求程序具有显示和打印各进程的某一时刻的资源分配表和安全序列；显示和打印各进程依次要求申请的资源数量以及为某进程分配资源后的有关资源数据的情况。 三、实验说明 实验中进程的数量、资源的种类以及每种资源的总量Total[j]最好允许动态指定。初始时每个进程运行过程中的最大资源需求量Max[i,j]和系统已分配给该进程的资源量Allocation[i,j]均为已知（这些数值可以在程序运行时动态输入），而算法中其他数据结构的值（包括Need[i,j]、Available[j]）则需要由程序根据已知量的值计算产生。 四、实验步骤 1、理解本实验中关于两种调度算法的说明。 2、根据调度算法的说明，画出相应的程序流程图。 3、按照程序流程图，用C语言编程并实现。 五、分析与思考 1．要找出某一状态下所有可能的安全序列，程序该如何实现？ 答：要找出这个状态下的所有可能的安全序列，前提是要是使这个系统先处于安全状态，而系统的状态可通过以下来描述： 进程剩余申请数=最大申请数-占有数；可分配资源数=总数-占有数之和； 通过这个描述来算出系统是否安全，从而找出所有的安全序列。 2．银行家算法的局限性有哪些？ 动能和动能定理、重力势能·典型例题剖析例1一个物体从斜面上高h处由静止滑下并紧接着在水平面上滑行一段距离后停止，量得停止处对开始运动处的水平距离为S，如图8－27，不考虑物体滑至斜面底端的碰撞作用，并设斜面与水平面对物体的摩擦因数相同．求摩擦因数μ． [思路点拨]以物体为研究对象，它从静止开始运动，最后又静止在平面上，考查全过程中物体的动能没有变化，即ΔEK=0，因此可以根据全过程中各力的合功与物体动能的变化上找出联系． [解题过程]设该面倾角为α，斜坡长为l，则物体沿斜面下滑时， 物体在平面上滑行时仅有摩擦力做功，设平面上滑行距离为S2，则 对物体在全过程中应用动能定理：ΣW=ΔEk． mgl·sinα－μmgl·cosα－μmgS2=0 得h－μS1－μS2=0． 式中S1为斜面底端与物体初位置间的水平距离．故 [小结]本题中物体的滑行明显地可分为斜面与平面两个阶段，而且运动性质也显然分别为匀加速运动和匀减速运动．依据各阶段中动力学和运动学关系也可求解本题．比较上述两种研究问题的方法，不难显现动能定理解题的优越性．用动能定理解题，只需抓住始、末两状态动能变化，不必追究从始至末的过程中运动的细节，因此不仅适用于中间过程为匀变速的，同样适用于中间过程是变加速的．不仅适用于恒力作用下的问题，同样适用于变力作用的问题． 例2 质量为500t的机车以恒定的功率由静止出发，经5min行驶2.25km，速度达到最大值54km/h，设阻力恒定且取g=10m/s2．求：(1)机车的功率P=？(2)机车的速度为36km/h时机车的加速度a=？ [思路点拨]因为机车的功率恒定，由公式P=Fv可知随着速度的增加，机车的牵引力必定逐渐减小，机车做变加速运动，虽然牵引力是变力，但由W=P·t可求出牵引力做功，由动能定理结合P=f·vm，可 活动安排 public static int greedySelector(int [] s, int [] f, boolean a[]) { //s[]开始时间f[]结束时间 int n=s.length-1; a[1]=true; int j=1; int count=1; for (int i=2;i<=n;i++) { if (s[i]>=f[j]) { a[i]=true; j=i; count++; } else a[i]=false; } return count; } 背包问题 void Knapsack(int n,float M,float v[],float w[],float x[]) { Sort(n,v,w); //以每种物品单位重量的价值Vi/Wi从大到小排序 int i; for (i=1;i<=n;i++) x[i]=0; float c=M; for (i=1;i<=n;i++) { if (w[i]>c) break; x[i]=1; c-=w[i]; } if (i<=n) x[i]=c/w[i]; //允许放入一个物品的一部分 } 最优装载 void Loading(int x[], T ype w[], T ype c, int n) { int *t = new int [n+1]; //t[i]要存的是w[j]中重量从小到大的数组下标Sort(w, t, n); //按货箱重量排序 for (int i = 1; i <= n; i++) x[i] = 0; //O(n) for (int i = 1; i <= n && w[t[i]] <= c; i++) {x[t[i]] = 1; c -= w[t[i]];} //调整剩余空间 } 单源最短路径Dijiksra template人教版高中物理必修一高一同步练习第三章第五节力的分解
贪心算法经典例题
银行家算法例题——四步走解题
力的合成与分解经典知识总结
算法习题
银行家算法例题
操作系统之调度算法和死锁中的银行家算法习题答案
高三物理一轮复习力的合成与分解教案
贪心算法概论
银行家算法习题1
高中物理知识讲解 力的合成与分解
算法分析与设计期末模拟试题
《银行家算法的模拟实现》—实验报告
_力的分解知识点与习题及答案
贪心算法的应用
操作系统实验四-银行家算法
银行家算法-实验报告
动能及动能定理典型例题剖析
贪心算法经典问题：活动安排,背包问题,最优装载,单源最短路径 Dijiksra,找零钱问题,多机调度