第4章-贪心算法-习题.ppt
- 文档编号:18627864
- 上传时间:2023-08-21
- 格式:PPT
- 页数:38
- 大小:474KB
第4章-贪心算法-习题.ppt
《第4章-贪心算法-习题.ppt》由会员分享,可在线阅读,更多相关《第4章-贪心算法-习题.ppt(38页珍藏版)》请在冰点文库上搜索。
1,第4章贪心算法,2,课程安排,3,第4章贪心算法,会场安排问题最优合并问题磁带最优存储问题磁盘文件最优存储问题程序存储问题最优服务次序问题多处最优服务次序问题d森林问题汽车加油问题区间覆盖问题硬币找钱问题删数问题数列极差问题,嵌套箱问题套汇问题信号增强装置问题磁带最大利用率问题非单位时间任务安排问题多元Huffman编码问题多元Huffman编码变形区间相交问题任务时间表问题最优分解问题可重复最优分解问题可重复最优组合分解问题旅行规划问题登山机器人问题,4,算法实现题4-1会场安排问题,问题描述:
假设要在足够多的会场里安排一批活动,并希望使用尽可能少的会场。
设计一个有效的贪心算法进行安排。
(这个问题实际上是著名的图着色问题。
若将每一个活动作为图的一个顶点,不相容活动间用边相连。
使相邻顶点着有不同颜色的最小着色数,相应于要找的最小会场数。
)编程任务:
对于给定的k个待安排的活动,编程计算使用最少会场的时间表(必须都安排完成)。
5,算法实现题4-1会场安排问题,数据输入:
第一行有1个正整数k,表示有k个待安排的活动。
接下来的k行中,每行有2个正整数,分别表示k个待安排的活动开始时间和结束时间。
时间以0点开始的分钟计。
结果输出:
最少会场数。
输入文件51231228253527803650输出示例3,6,算法实现题4-5程序存储问题,问题描述:
设有n个程序1,2,n要存放在长度为L的磁带上。
程序i存放在磁带上的长度是li,1in。
程序存储问题要求确定这n个程序在磁带上的一个存储方案,使得能够在磁带上存储尽可能多的程序。
编程任务:
对于给定的n个程序存放在磁带上的长度,编程计算磁带上最多可以存储的程序数。
7,算法实现题4-5程序存储问题,数据输入:
第一行是2个正整数,分别表示文件个数n和磁带的长度L。
接下来的1行中,有n个正整数,表示程序存放在磁带上的长度。
结果输出:
最多可以存储的程序数。
输入示例650231388020输出示例5,8,intgreedy(vectorx,intm)inti=0,sum=0,n=x.size();sort(x.begin(),x.end();while(in)sum+=xi;if(sum=m)i+;elsereturni;returnn;/所有的程序都没有磁带长,算法实现题4-5程序存储问题,贪心策略:
最短程序优先排序后的数据,9,算法实现题4-6最优服务次序问题,问题描述:
设有n个顾客同时等待一项服务。
顾客i需要的服务时间为ti,1=i=n。
应如何安排n个顾客的服务次序才能使平均等待时间达到最小?
平均等待时间是n个顾客等待服务时间的总和除以n。
编程任务:
对于给定的n个顾客需要的服务时间,编程计算最优服务次序。
10,算法实现题4-6最优服务次序问题,数据输入:
第一行是正整数n,表示有n个顾客。
接下来的1行中,有n个正整数,表示n个顾客需要的服务时间。
结果输出:
计算出的最小平均等待时间。
输入示例1056121991000234335599812输出示例532.00,11,算法实现题4-6最优服务次序问题,doublegreedy(vectorx)inti,n=x.size();sort(x.begin(),x.end();for(i=1;in;+i)xi+=xi-1;doublet=0;for(i=0;in;+i)t+=xi;t/=n;returnt;,定义:
vectorx;读取数据:
intn;scanf(“%d”,12,算法实现题4-7多处最优服务次序问题,问题描述:
设有n个顾客同时等待一项服务。
顾客i需要的服务时间为ti,1=i=n。
共有s处可以提供此项服务。
应如何安排n个顾客的服务次序才能使平均等待时间达到最小?
平均等待时间是n个顾客等待服务时间的总和除以n。
编程任务:
对于给定的n个顾客需要的服务时间和s的值,编程计算最优服务次序。
13,算法实现题4-7多处最优服务次序问题,数据输入:
第一行有2个正整数n和s,表示有n个顾客且有s处可以提供顾客需要的服务。
接下来的1行中,有n个正整数,表示n个顾客需要的服务时间。
结果输出:
最小平均等待时间。
输入示例10256121991000234335599812输出示例336,14,算法实现题4-7多处最优服务次序问题,doublegreed(vectorx,ints)vectorst(s+1,0);vectorsu(s+1,0);intn=x.size();sort(x.begin(),x.end();inti=0,j=0;while(in)stj+=xi;suj+=stj;+i,+j;if(j=s)j=0;doublet=0;for(i=0;is;+i)t+=sui;t/=n;returnt;,排序后的数据,15,算法实现题4-9汽车加油问题,问题描述一辆汽车加满油后可行驶nkm。
旅途中有若干个加油站。
设计一个有效算法,指出应在哪些加油站停靠加油,使沿途加油次数最少。
编程任务对于给定的n和k个加油站位置,编程计算最少加油次数。
16,算法实现题4-9汽车加油问题,数据输入第1行有2个正整数n和k,表示汽车加满油后可行驶nkm,且旅途有k个加油站。
接下来的一行中,有k+1个整数,表示第k个加油站与第k-1个加油站之间的距离。
第0个加油站表示出发地,汽车已加满油。
第k+1个加油站表示目的地。
结果输出计算出的最少加油次数。
如果无法到达目的地,则输出”NoSolution”。
输入示例7712345166,输出示例4,17,算法实现题4-9汽车加油问题,intgreedy(vectorx,intn)intj,i,s,sum=0,k=x.size();for(j=0;jn)coutn)sum+,s=xi;returnsum;,i=310i=49i=612i=712,18,算法实现题4-9汽车加油问题,读取数据:
intt,n,k;scanf(%d%d,19,算法实现题4-10区间覆盖问题,问题描述:
设x1,x2,.,xn是实直线上的n个点。
用固定长度的闭区间覆盖这n个点,至少需要多少个这样的固定长度闭区间?
设计解此问题的有效算法。
编程任务:
对于给定的实直线上的n个点和闭区间的长度k,编程计算覆盖点集的最少区间数。
20,算法实现题4-10区间覆盖问题,数据输入:
第一行有2个正整数n和k,表示有n个点,且固定长度闭区间的长度为k。
接下来的1行中,有n个整数,表示n个点在实直线上的坐标(可能相同)。
结果输出:
最少区间数。
输入示例7312345-26输出文件示例3,21,算法实现题4-10区间覆盖问题,intgreedy(vectorx,intk)inti,sum=1,n=x.size();sort(x.begin(),x.end();inttemp=x0;/区间的起始位置for(i=1;ik)sum+,temp=xi;returnsum;,22,算法实现题4-12删数问题,问题描述:
给定n位正整数a,去掉其中任意kn个数字后,剩下的数字按原次序排列组成一个新的正整数。
对于给定的n位正整数a和正整数k,设计一个算法找出剩下数字组成的新数最小的删数方案。
编程任务:
对于给定的正整数a,编程计算删去k个数字后得到的最小数。
23,算法实现题4-12删数问题,数据输入:
文件的第1行是1个正整数a。
第2行是正整数k。
结果输出:
计算出的最小数。
输入示例1785434输出文件示例13,24,算法实现题4-12删数问题,voiddelek(stringa,intk)/在整数a中删除k个数字intm=a.size();if(k=m)a.erase();return;/全部删除while(k0)/寻找最近下降点inti;for(i=0;(i1/删除前导0,能使用m吗?
25,算法实现题4-15套汇问题,问题描述:
套汇是指利用货币汇兑率的差异将一个单位的某种货币转换为大于一个单位的同种货币。
例如,假定1美元可以买0.7英镑,1英镑可以买9.5法郎,且1法郎可以买到0.16美元。
通过货币兑换,一个商人可以从1美元开始买入,得到0.79.50.16=1.064美元,从而获得6.4%的利润。
编程任务:
给定n种货币c1,c2,c3,.,cn的有关兑换率,试设计一个有效算法,用以确定是否存在套汇的可能性。
26,输入示例3USDollarBritishPoundFrenchFranc3USDollar0.5BritishPoundBritishPound10.0FrenchFrancFrenchFranc0.21USDollar0输出示例Case1yes,算法实现题4-15套汇问题,数据输入:
本题有多个测试数据项。
每个测试数据项的第一行中只有1个整数n(1n30),表示货币总数。
其后n行给出n种货币的名称。
接下来的一行中有1个整数m,表示有m种不同的货币兑换率。
其后m行给出m种不同的货币兑换率,每行有3个数据项ci,rij和cj,表示货币ci和cj的兑换率为rij。
文件最后以数字0结束。
结果输出:
对每个测试数据项j,如果存在套汇的可能性则输出“Casejyes”,否则输出“Casejno”。
27,算法实现题4-15套汇问题,while
(1)cinn;if(n=0)break;/输入结束for(i=0;inamei;/读取货币名称for(i=0;iedges;/兑换率数目for(i=0;iaxb;for(j=0;strcmp(a,namej);j+);/确定a的下标for(k=0;strcmp(b,namek);k+);/确定b的下标rjk=x;,28,算法实现题4-15套汇问题,while
(1)for(i=0;i1.0)break;/搜索赢利情况if(in)coutcase(cases)yesendl;elsecoutcase(cases)noendl;,只要搜到一个赢利就行,29,算法实现题4-15套汇问题,3USDollarBritishPoundFrenchFranc6USDollar0.5BritishPoundUSDollar4.9FrenchFrancBritishPound10.0FrenchFrancBritishPound1.99USDollarFrenchFranc0.09BritishPoundFrenchFranc0.19USDollarAnswer:
no,30,算法实现题4-21区间相交问题,问题描述:
给定x轴上n个闭区间。
去掉尽可能少的闭区间,使剩下的闭区间都不相交。
编程任务:
给定n个闭区间,编程计算去掉的最少闭区间数。
数据输入:
第一行是正整数n,表示闭区间数。
接下来的n行中,每行有2个整数,分别表示闭区间的2个端点。
结果输出:
计算出的去掉的最少闭区间数。
输入示例3102010152015输出文件示例2/与活动安排类似if(ab)swap(a,b);按右端点从小到大排序;依左端点超过右端点进行选择.,31,算法实现题4-21区间相交问题,数据结构:
structintervalintstart;intend;比较函数:
boolcmp(intervala,intervalb)if(a.endb.end)returntrue;elsereturnfalse;,32,算法实现题4-21区间相交问题,在intmain()中:
intn;inta,b;cinn;intervalinte100;for(inti=0;iab;if(ab)swap(a,b);intei.start=a;intei.end=b;sort(inte,inte+n,cmp);coutn-GreedySelector(n,inte)endl;,33,算法实现题4-21区间相交问题,贪心选择:
intGreedySelector(intn,intervalinte)intcount=1;intj=0;/区间的起点for(inti=1;iintej.end)count+;j=i;returncount;,34,算法实现题4-23最优分解问题,问题描述:
设n是一个正整数。
现在要求将n分解为若干个互不相同的自然数的和,且使这些自然数的乘积最大。
编程任务:
对于给定的正整数n,编程计算最优分解方案。
数据输入:
第1行是正整数n。
结果输出:
计算出的最大乘积。
输入示例10输出示例30,35,算法实现题4-23最优分解问题,voiddicomp()k=1;if(nak)k+;ak=ak-1+1;n-=ak;if(n=ak)ak+;-n;for(inti=0;in;+i)ak-i+;,大数运算,36,算法实现题4-24可重复最优分解问题,问题描述:
设n是一个正整数。
现在要求将n分解为若干个自然数的和,且使这些自然数的乘积最大。
编程任务:
对于给定的正整数n,编程计算最优分解方案。
数据输入:
文件的第1行是正整数n。
结果输出:
计算出的最大乘积。
输入示例10输出示例36,37,算法实现题4-24可重复最优分解问题,若a+b=const,则|a-b|越小,ab越大。
贪心策略:
38,算法实现题4-24可重复最优分解问题,voidcompute(intn)intr=n%3;t1=1;intk=n/3;length=1;/大数的长度,是全局变量if(r=1)t1=4;k=(n-4)/3;if(r=2)t1=2;k=(n-2)/3;for(inti=1;i0;-i)coutti;coutendl;,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 贪心 算法 习题