《贪心算法解决搬桌子问题.doc》由会员分享，可在线阅读，更多相关《贪心算法解决搬桌子问题.doc（3页珍藏版）》请在金锄头文库上搜索。
1、贪心算法解决搬桌子问题实验目的：理解贪心算法的基本思想。掌握贪心算法思想分析问题的一般方法，对较简单的问题能正确分析，设计出贪心算法，并能快速编程实现。实验内容：编程实现讲过的例题：活动安排问题，背包问题。本实验中的问题，设计出算法并编程实现。1. 搬桌子问题某教学大楼一层有n个教室，从左到右依次编号为1、2、n。现在要把一些课桌从某些教室搬到另外一些教室，每张桌子都是从编号较小的教室搬到编号较大的教室，每一趟，都是从左到右走，搬完一张课桌后，可以继续从当前位置或往右走搬另一张桌子。输入数据：先输入n、m，然后紧接着m行输入这m张要搬课桌的起始教室和目标教室。输出数据：最少需要跑几趟。Samp
2、le Input10 51 33 94 66 107 8Sample Output3分析：贪心算法，把课桌按起点从小到大排序，每次都是搬离当前位置最近的课桌。程序如下：#includeint main()structint start;int end;a100;int i,j;int n,m,min,num,temp,used100=0;scanf(%d%d,&m,&n);for(i=0;in;i+)scanf(%d%d,&ai.start,&ai.end);/sort(a,n); /按start从小到大对数组a排序min=0;num=0;while(numn)temp=0;for(i=0;i=temp)temp=ai.end;usedi=1;num+;min+;printf(%d,min);
