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

实验三 分治与贪心


南华 大学

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

专业班级:本 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. 【循环赛日程安排...
基于分治和贪心相结合的排课算法研究
例如,可将教室划分为:普通教室、多媒体教室、语音室、物理实验室、机房等。 ...3 算法分析及测试基于分治贪心相结合的排课算法主要分为3 个阶段:即分配上课...
算法设计与分析-实验1-递归与分治算法-
算法设计与分析-实验3-贪心... 算法设计与分析-实验4-回溯...1...《 算法分析与设计》实验报告 -1- 实验 1 实验目的和要求 递归与分治算法 (...
贪心、分治
分治 江苏省连云港市赣榆高级中学 仲晨 A 3 -贪心分治 学习小结江苏省连云港...笔者做了随机试验(写了一个程序多次随机处理1000个问 题),大概有20%解出的是...
分治、贪心、动态规划算法要点复习
分治贪心、动态规划算法要点复习 隐藏>> 分治法 1 分割成独立的子问题 2 递归解决子问题 3 合并求得初始问题的解 动态规划算法 1. 描述最优解的结构特征 2...
贪心算法、分治算法、动态规划算法间的比较.doc
当问题满足第一、二、三条,而不满足第四条时,一般可以用动 态规划法解决,可以说,动态规划法的实质是: 分治算法思想+解决子问题冗余情况 2、贪心算法与动态规划...
分治法解决合并排序问题及动态规划解决矩阵连乘和最长...
(2)最长公共子序列 3贪心法 (1)哈夫曼编码 三、概要设计 1、分治法 基本...以前对与计算 机算法的认识是模糊的, 概念上的, 现在通过自己动手做实验, 从...
实验三 分治算法设计与应用
实验三 分治算法设计与应用一.实验目的和要求 1.加深对分治算法的基本思想、 基本步骤和一般形式的理解, 掌握分治算法设计的基本 方法。 2.用分治法设计 L 型...
更多相关标签: