武汉理工大学暑期基础强化训练课程设计poj测评1017附完整源代码Word下载.docx
- 文档编号:8095408
- 上传时间:2023-05-10
- 格式:DOCX
- 页数:11
- 大小:82.80KB
武汉理工大学暑期基础强化训练课程设计poj测评1017附完整源代码Word下载.docx
《武汉理工大学暑期基础强化训练课程设计poj测评1017附完整源代码Word下载.docx》由会员分享,可在线阅读,更多相关《武汉理工大学暑期基础强化训练课程设计poj测评1017附完整源代码Word下载.docx(11页珍藏版)》请在冰点文库上搜索。
指导教师:
工作单位:
计算机科学与技术学院
题目:
Packets
初始条件:
输入:
输入内容由若干行组成。
每一行是一份订单,所有的订单都由6个整数组成,分别对应1*1产品到6*6产品的需求量。
输入内容的最后一行由6个0组成;
输出:
输出内容的每一行对应输入内容的每一行,它表示所需要的最少箱子数量(输入内容最后一行对应的输出内容为空)。
要求完成的主要任务:
(包括课程设计工作量及其技术要求,以及说明书撰写等具体要求)
1、完成算法分析;
2、给出对应的程序流程图;
3、给出能正确实现的程序源码;
5、给出试算截屏图;
6、课程设计工作的分析与总结;
7、给出不少于5篇参考文献。
时间安排:
2014-7-7到2014-7-11
消化资料、系统调查、形式描述1天
系统分析、总体设计、实施计划3天
撰写课程设计报告书1天
指导教师签名:
年月日
系主任(或责任教师)签名:
目录
1注册资料2
2选题描述2
3算法分析3
3.1思路分析3
3.2算法描述3
4程序流程图5
4.1主流程图5
4.2fill_2部分流程图6
4.3fill_1部分流程图6
5程序源码7
6试算截屏图9
6.1程序运行截图9
6.2POJ系统评测结果截图9
7分析与总结10
参考文献10
Packets
1注册资料
用户名:
密码:
选题题号:
1017
2选题描述
【问题】
工厂生产一种产品,它们的高度都是h,长宽有六个型号,分别为1*1、2*2、3*3、4*4、5*5、6*6。
这些产品通常使用6*6*h的长方体箱子包装后邮寄给客户。
由于费用问题,工厂希望使用最少的箱子寄送给订购货物的客户。
一个好的程序能根据客户的订单找到所需要的最少箱子数量。
你需要写出这样一个程序。
【输入】
每一行代表一份订单,每份订单包括六个整数,中间用空格隔开,分别为1*1至6*6这六种产品的数量;
输入内容以6个0组成的一行结尾。
【输出】
输出内容的每一行对应输入内容的每一行,它表示对应的订单所需的最小箱子数(输入内容最后一行对应的输出内容为空)。
【输入示例】
0
4
1
7
5
0
0
【输出示例】
2
3算法分析
3.1思路分析
由于产品和箱子的高均为h,所以只需考虑它们底面积的空间。
可以用到贪心思想,从型号较大的产品开始放置到箱子,然后用型号较小的填充。
分情况考虑贪心(问题的关键是3*3的产品怎么放置):
1.如果一个箱子中放置了一个6*6的产品,则此箱子中无法放置其它产品;
2.若放置5*5的产品,则此箱子中还可放置11个1*1的产品;
3.若放置4*4的产品,则此箱子中还可放置5个2*2的产品;
4.若放置3*3的产品,其总个数模4后,就是最后一个箱子放几个3*3的
a)如果是1,这个箱子还可放5个2*2和7个1*1;
b)如果是2,这个箱子可以放3个2*2和6个1*1;
c)如果是3,这个箱子可以放1个2*2和5个1*1的。
5.2*2的产品和1*1的产品主要用于填充其他箱子的剩余空间,填充后的多余部分用新箱子包装。
3.2算法描述
sum为需要的箱子数,a[i]表示每种类型产品的数量,“fill_1”表示用来填充的1*1产品个数,“fill_2”表示用来填充的2*2产品个数。
S1:
输入客户订单a[6](底面积为1*1到6*6的产品需求量)
代码如下:
intsum=0;
for(inti=1;
i<
=6;
i++){
scanf("
%d"
&
a[i]);
sum+=a[i];
}
S2:
若sum=0,则终止运行,否则令sum=0;
if(sum==0)
break;
sum=0;
//初始化
S3:
计算包装底面积为3*3、4*4、5*5、6*6的产品需要的箱子数
代码如下:
sum=a[4]+a[5]+a[6]+a[3]/4;
if(a[3]%4!
=0)
sum++;
S4:
计算用于填充其它箱子剩余空间的2*2产品数,进而得出所需箱子数;
intfill_2=a[4]*5+p[a[3]%4];
if(fill_2<
a[2]){
sum+=(a[2]-fill_2)/9;
if((a[2]-fill_2)%9!
sum++;
S5:
计算用于填充其它箱子剩余空间的1*1产品数,进而得出所需箱子数;
intfill_1=sum*36-a[2]*4-a[3]*9-a[4]*16-a[5]*25-a[6]*36;
if(fill_1<
a[1]){
sum+=(a[1]-fill_1)/36;
if((a[1]-fill_1)%36!
sum++;
S6:
输出所需的最少箱子数量sum,终止。
4程序流程图
4.1主流程图
4.2fill_2部分流程图
4.3fill_1部分流程图
5程序源码
#include<
iostream>
usingnamespacestd;
intmain()
{
inta[6];
intp[4]={0,5,3,1};
//表示底面积为3*3的产品放完后,余下的放入新箱子中,还可以放几个2*2的产品(下标对应余数)
while
(1)
{
intsum=0;
for(inti=1;
i++)
scanf("
//输入一份订单,即底面积为1*1到6*6的产品的需求量
sum+=a[i];
//输入均为0时,终止运行
//包装底面积为3*3、4*4、5*5、6*6的产品需要的箱子数
intfill_2=a[4]*5+p[a[3]%4];
//“fill_2”表示用于填充其它箱子剩余空间的2*2产品个数
a[2])
sum+=(a[2]-fill_2)/9;
intfill_1=sum*36-a[2]*4-a[3]*9-a[4]*16-a[5]*25-a[6]*36;
//“fill_1”表示用于填充其它箱子剩余空间的1*1产品个数,即所有箱子的底面总面积减去后5种产品的总面积
a[1])
cout<
<
sum<
endl;
//输出所需的最少箱子数量
return0;
}
6试算截屏图
6.1程序运行截图
6.2POJ系统评测结果截图
7分析与总结
本题中,输入几份订单,需要找出包装产品所需的最少箱子数。
这题用到贪心策略,我们可以从型号较大的产品开始放置到箱子,然后用型号较小的产品填充。
该算法实现较简单,但是分析过程需考虑多种情况,需要细心。
通过这次强化训练,我受益匪浅,学会了综合运用所学知识,提高了分析和解决实际问题的能力;
能比较全面而辩证地分析和处理问题,逐步树立起了正确的软件开发设计思想。
另外,我知道了,编程不仅仅要得出结果而且必须在空间和时间上具有优越性,既尽可能降低时间复杂性和空间复杂性。
而这两者一般相互矛盾,所以我们需要结合实际问题,找出最好的契合点。
参考文献
[1]刘任任.算法设计与分析[M].武汉:
武汉理工大学出版社,2003.12
[2]谭浩强.C程序设计[M].北京:
清华大学出版社,2005
[3]张蕊,吕涛.C程序设计教程[M].武汉:
华中科技大学出版社,2012.9
[4]谭浩强.C++面向对象程序设计[M].北京:
清华大学出版社,2006.1
[5]严蔚敏,吴伟民.数据结构[M].北京:
清华大学出版社,1996
[6]李文新、郭炜、余华山.程序设计导引及在线实践[M].北京:
清华大学出版社
本科生课程设计成绩评定表
班级:
姓名:
学号:
序号
评分项目
满分
实得分
1
学习态度认真、遵守纪律
2
设计分析合理性
3
设计方案正确性、可行性、创造性
20
4
设计结果正确性
40
5
设计报告的规范性
6
设计验收
总得分/等级
评语:
注:
最终成绩以五级分制记。
优(90-100分)、良(80-89分)、中(70-79分)、
及格(60-69分)、60分以下为不及格
指导教师签名:
2014年月日
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 武汉理工大学 暑期 基础 强化 训练 课程设计 poj 测评 1017 完整 源代码
![提示](https://static.bingdoc.com/images/bang_tan.gif)