实验3__ 分治与贪心.doc

实验三 分治与贪心 一、 实验目的 熟悉C/C++语言的集成开发环境； 通过本实验加深对分治法、贪心算法的理解。 二、 实验内容 掌握分治法、贪心算法的概念和基本思想，并结合具体的问题学习如何用相应策略 进行求解的方法。 三、 实验要求 1.【循环赛日程安排问题】计算机学院准备举办一次男生羽毛球单打比赛，现在总共有16名选手报名，首轮比赛准备采取循环赛的形式进行角逐，要求必须在15天内比完，且每个选手每天只能安排一场比赛，请你帮助学生会安排首轮循环赛的比赛日程表。 2.【找零钱问题】一个小孩买了价值为33美分的糖，并将1美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供了数目有限的面值为25美分、10美分、5美分、及1美分的硬币。给出一种找零钱的贪心算法。 四、 实验步骤 理解算法思想和问题要求； 编程实现题目要求； 上机输入和调试自己所编的程序； 验证分析实验结果； 整理出实验报告。 五、 实验程序 1. #includeiostream #includeSTDIO.H void Table(int k) { int a[20][20]; int q,n=1; for(int i=1;i=k;i++) n*=2; q=n; for(int i=1;i=n;i++) a[1][i]=i; int m=1; for(int s=1;s=k;s++) { n/=2; for(int t=1;t=n;t++) for(int i=m+1;i=2*m;i++) for(int j=m+1;j=2*m;j++) { a[i][j+(t-1)*m*2]=a[i-m][j+(t-1)*m*2-m]; a[i][j+(t-1)*m*2-m]=a[i-m][j+(t-1)*m*2]; } m*=2; } for(int i=1;i=q;i++) { for(int j=1;j=q;j++) printf(%d ,a[i][j]); printf(\n); } } void main() { int k=4; Table(k); system(pause); } 2. #includeiostream using std::cout; using std::endl; int main() { int s=100-33; int a=25; int b=10; int c=5; int d=1; int cout1=0; int cout2=0; int cout3=0; int cout4=0; for(s;s=a;cout1++) s=s-a; for(s;s=b;cout2++) s=s-b; for(s;s=c;cout3++) s=s-c; for(s;s=d;cout4++) s=s-d; { if(s==0) cout找cout1个25美分的硬币endl cout2个10美分的硬币endl cout3个5美分的硬币endl cout4个1美分的硬币endl; } system(pause); return 0; } 实验结果 1. 2. 实验分析 分