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

实验三 分治与贪心


南华 大学

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

专业班级:本 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 美分的找完,最后得出找钱的硬币数。 此两程序,加深了对分治法、贪心算法的理解,并且加以运用


赞助商链接
相关文章:
贪心算法、分治算法、动态规划算法间的比较.doc
当问题满足第一、二、三条,而不满足第四条时,一般可以用动 态规划法解决,可以说,动态规划法的实质是: 分治算法思想+解决子问题冗余情况 2、贪心算法与动态规划...
算法设计与分析典型算法概述——分治法与贪心法
算法设计与分析典型算法概述 ▌ 分治与贪心法 ▌拾光工作室 算法设计与分析...它们的面值分别为二角五分、一角、五分和一分,现要找给顾客六角三分钱, 问...
1、算法分析复习题目及答案
( A、找出最优解的性质 3、最大效益优先是( A、分支界限法 A B、构造最...C、贪心法 D、回溯法 38、合并排序算法是利用( A、分治策略 B、动态规划法 ...
分治、贪心、动态规划算法要点复习
分治贪心、动态规划算法要点复习 - 分治法 1 分割成独立的子问题 2 递归解决子问题 3 合并求得初始问题的解 动态规划算法 1. 描述最优解的结构特征 2. ...
算法分析复习题目及答案
一。选择题 1、二分搜索算法是利用( A、分治策略 A )实现的算法。 C、贪心...( A、找出最优解的性质 3、最大效益优先是( A、分支界限法 A B、构造最...
算法设计与分析试卷(A)及答案
A、分治策略 B、动态规划法 C、贪心法 )。 正确的 考试课程: D、回溯法 2、下列不是基本计算模型的是( B A、RAM B、ROM C、RASP D、TM 3、下列算法中...
分治法解决合并排序问题及动态规划解决矩阵连乘和最长...
(2)最长公共子序列 3贪心法 (1)哈夫曼编码 三、概要设计 1、分治法 基本...以前对与计算 机算法的认识是模糊的, 概念上的, 现在通过自己动手做实验, 从...
算法分析样卷
0-1 背包问题用( A、分治策略 C、贪心法 2. ...2. 说明贪心算法与动态规划算法的的主要差别。 3....算法分析实验报告 暂无评价 5页 2下载券 算法分析...
...A.动态规划 B.贪心 C.回溯 D.分治_答案_百度高考
B.贪心 C.回溯 D.分治正确答案及相关解析 正确答案 B 解析 分治法:对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决;否则将其...
...A.归纳法 B.分治法 C.贪心法 D.回溯法_答案_百度高考...
归并排序采用的算法设计方法属于()。 A.归纳法 B.分治法 C.贪心法 D.回溯法_答案解析_2016年_一模/二模/三模/联考_图文_百度高考
更多相关标签: