当前位置:首页 >> 工学 >>

实验三 分治与贪心


南华 大学

实验名称:分治与贪心 学 院:计 算 机 学 院

专业班级:本 2010 电气信息类 03 班 学 姓 号:20104030342 名: 谢志兴 余颖

指导教师:

日期:

2012 年

4 月

10 日

实验三 分治与贪心
一、 实验目的与要求
熟悉 C/C++语言的集成开发环境; 通过本实验加深对分治法、贪心算法的理解。

二、

实验内容: 实验内容

掌握分治法、 贪心算法的概念和基本思想, 并结合具体的问题学习如何用相应策略进行 求解的方法。

三、

实验题

1. 【循环赛日程安排问题】计算机学院准备举办一次男生羽毛球单打比赛,现在总共 有 16 名选手报名, 首轮比赛准备采取循环赛的形式进行角逐, 要求必须在 15 天内比完, 且每个选手每天只能安排一场比赛,请你帮助学生会安排首轮循环赛的比赛日程表。 2.【找零钱问题】一个小孩买了价值为 33 美分的糖,并将 1 美元的钱交给售货员。售 货员希望用数目最少的硬币找给小孩。 假设提供了数目有限的面值为 25 美分、 美分、 10 5 美分、及 1 美分的硬币。给出一种找零钱的贪心算法。

四、

实验步骤

理解算法思想和问题要求; 编程实现题目要求; 上机输入和调试自己所编的程序; 验证分析实验结果; 整理出实验报告。

五、 实验程序 /*题目一代码*/
#include<iostream> using namespace std; const int n=16; int a[n][n],b[n]; bool odd(int n)//当分割中遇到 n 为奇数时 { return n&1; } void copy(int n) { int m=n/2;//对 n 进行分割 for(int i=1;i<=m;i++)//对 m 进行执行循环 for(int j=1;j<=m;j++) { a[i][j+m]=a[i][j]+m; a[i+m][j]=a[i][j+m]; a[i+m][j+m]=a[i][j]; } } void copyodd(int n) {

int m=n/2; for(int i=1;i<=m;i++) { b[i]=m+i; b[m+i]=b[i]; } for( i=1;i<=m;i++) { for(int j=1;j<=m+1;j++) { if(a[i][j]>m) { a[i][j]=b[i]; a[m+i][j]=(b[i]+m)%n; } else a[m+i][j]=a[i][j]+m; } for( j=2;j<=m;j++) { a[i][m+j]=b[i+j-1]; a[b[i+j-1]][m+j]=i; } } } void makecopy(int n)//对 n 进行判断函数,调用哪个函数 { if(n/2>1&&odd(n/2)) copyodd(n);//调用函数 copyodd() else copy(n);//调用函数 copy() } void tournament(int n) { if(n==1) { a[1][1]=1; return; } if(odd(n)) { tournament(n+1); return; }

tournament(n/2); makecopy(n); } int main() { cout<<"比赛日程为"<<endl; int n,i,j; n=16; tournament(n); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { if(a[i][j]>9) cout<<" "<<a[i][j]; else cout<<" } cout<<endl; } return 0; } /*题目二代码*/ #include<iostream> using namespace std; int main() { int money,value,returns; int twenty_five,ten,five,one; int i=0,j=0,k=0,l=0; money=100; value=33; returns=money-value; cout<<"应该找给孩子的钱是(美分) :"<<returns<<endl; cout<<"请输入现有的 25 美分,10 美分,5 美分,1 美分硬币的个数"<<endl; cin>>twenty_five>>ten>>five>>one; i=returns/25; if(i<=twenty_five) returns-=25*i; else { returns-=twenty_five*25; i=twenty_five; } if(returns>0) { "<<a[i][j];

j=returns/10; if(j<=ten) returns-=10*j; else { returns-=ten*10; j=ten; } } if(returns>0) { k=returns/5; if(k<=five) returns-=5*k; else { returns-=five*5; k=five; } } if(returns>0) { l=returns; if(l<=one) returns-=l; else { returns-=one; l=one; } } returns=money-value-(i*25+j*10+k*5+l); if(returns>0) cout<<"不好意思,现在没有足够的硬币! "<<endl; else { cout<<"应找 25 美分的个数是:"<<i<<endl; cout<<"应找 10 美分的个数是:"<<j<<endl; cout<<"应找 5 美分的个数是:"<<k<<endl; cout<<"应找 1 美分的个数是:"<<l<<endl; } return 0; }

六、

实验结果

题目一结果:

题目二结果:

七、

实验分析

(1) 采用循环赛方式进行比赛, 则用分治法进行, 其中用到递归, 解决方法按分治策略, 将所有的选手分为两半, 个选手的比赛日程表就可以通过为 8 个选手设计的比赛 16 日程表来决定。递归地对选手进行分割,直到只剩下两个选手时,比赛日程表的制 定就变得简单了。这时只要让两个选手进行比赛就可以了。 (2) 此找钱问题,运用贪心法,将 25 美分的找完,然后将 10 美分的找完,然后将 5 美 分的找完,再将 1 美分的找完,最后得出找钱的硬币数。 此两程序,加深了对分治法、贪心算法的理解,并且加以运用


赞助商链接
相关文章:
实验三 分治与贪心
实验三 分治与贪心_工学_高等教育_教育专区。', 南华 大学 实验名称:分治与贪心 学院:计算机学院 专业班级:本 2010 电气信息类 03 班学姓号:20104030342 名: ...
分治与贪心
二、 实验内容: 实验内容 掌握分治法、 贪心算法的概念基本思想, 并结合具体的问题学习如何用相应策略进行 求解的方法。 三、 实验题 1. 【循环赛日程安排...
实验三 贪心算法
实验一 分治与递归 实验二 动态规划算法棋盘... 实验四 回溯算法和分支限界.....实验三 贪心算法多机调度问题一、实验目的 : 1、熟悉多机调度问题的算法; 2、...
实验三 贪心算法设计与实现实验报告
实验一 递归与分治策略算... 实验三 查询实验报告 实验四 单纯形算法设计与....刘景超 实验三 贪心算法的设计与实现 实验三 贪心算法的设计与实现实验目的: 一...
实验三.归并排序的分治策略设计
关键词:算法实验 同系列文档 实验四.哈夫曼编码的贪心算... 实验五.Kruskal算法...归并排序的分治策略设计( 学时) 实验三 归并排序的分治策略设计(4 学时) [...
实验三(分治算法)
实验三(分治算法)_工学_高等教育_教育专区。算法与设计 华东师范大学计算机科学技术系学生上机实践报告 华东师范大学计算机科学技术系上机实践报告课程名称 课程名称: ...
分治法实验报告
使用分治法求解: 把原问题划分成子问题:把原问题分成两个子问题 求解子问题:问题...运行得到正确结果 三、实验环境实验中主要使用的仪器、设备:计算机 实验材料:...
分治算法实验报告
算法分析与设计实验报告 第 1 次实验姓名 时间 实验名称 10.17 上午 学号 地点 四合院 102 班级 分治算法实验(用分治法查找数组元素的最大值和最小值) 。 ...
分治法实验报告
掌握分治算法的时间复杂度,并能利用 c 语言实现算法。 三、实验内容及要求 1. 大整数乘法。 要求: (1) 求解两个 n 位的二进制整数的乘法,设 n=2k; (2)...
算法设计与分析实验报告:分治算法实验
算法设计与分析实验报告:分治算法实验_计算机软件及应用_IT/计算机_专业资料。...②将问题分解,如果数组的元素大于等于 3 个,将数组分为两个小的数组。 ③...
更多相关标签: