程序设计实习第二讲.ppt

《程序设计实习第二讲.ppt》由会员分享，可在线阅读，更多相关《程序设计实习第二讲.ppt（43页珍藏版）》请在三一办公上搜索。

1、程序设计实习第二讲,内容提要,POJ简介例题1：Packets例题2：校门外的树例题3：生理周期例题4：确定进制例题5：日历问题,网址及功能 http:/建立帐号 提交作业 查看结果 出错类型,POJ系统说明,出错类型Runtime Error 运行时错Complie Error 编译错Wrong Answer 答案错Presentation Error 格式错Time Limit Exceed 超时,例题1：POJ 1017 Packets(课本P92),题意已知：有6*6 的大箱子和 1*1，2*2，3*3，4*4，5*5，6*6 的木块，箱子高度和木块一样问：给定各种木块的数目，求最少需

2、要多少个大箱子来装？例如：输入：0 0 4 0 0 1-输出 2输入：7 5 1 0 0 0-输出 1,解题思想：先放大的，后放小的,Packets,4*4，5*5，6*6的块单独占一个箱子,Packets,3*3的块，每4块占一个箱子,余下的再占一个箱子,Packets,如果箱子里放1个3*3木块，那么还能放5个2*2木块,以及7个1*1木块,Packets,如果箱子里放2个3*3木块，那么还能放3个2*2木块,以及6个1*1木块,Packets,如果箱子里放3个3*3木块，那么还能放1个2*2木块,以及5个1*1木块,Packets,解题思想：先放大的，后放小的6*6的木块每个占用一个新箱

3、子；5*5的木块每个占用一个新箱子，余下11个1*1的空格；4*4的木块每个占用一个新箱子，余下5个2*2的空格；3*3的木块每4个占用新一个箱子，不足4个也占一个新箱子，分情况余下不同数目的空格；2*2的木块先填空格，空格不足开新箱子，每9个2*2的木块占一个新箱子；1*1的木块先填空格，空格不足开新箱子，每36个占一个新箱子。,Packets,构造法 6*6，5*5，4*4，3*3，2*2，1*1个数 b6 b5 b4 b3 b2 b1nTotal-箱子数1）先放好所有 6*6,5*5,4*4 和3*3 的木块nTotal=b6+b5+b4+(b3+3)/4 4*4,5*5,6*6 单独开

4、箱子 3*3 每4个占一个箱子，余下的占一个箱子,Packets,2)再把2*2的塞到放有3*3木块的箱子里 设一个数组：int Contain24=0,5,3,1;Contain2i 表示当3*3木块的数目除以4的余数分别是0,1,2,3时，会产生多少个能放2*2木块的空格。用数组纪录某些事实，比写 if else 方便 放完2*2的木块后，再算一下有多少1*1的空格，能否把1*1的木块都填进去，如果不能，也容易算出还要加多少个箱子,#include using namespace std;int main()int b6,b5,b4,b3,b2,b1;/不同大小的木块个数int nTota

5、l=0;/最少需要的箱子数目int c1;/当前能放 1*1 木块的空格数目int c2;/当前能放 2*2 木块的空格数目int Contain24=0,5,3,1;while(1)cinb1b2b3b4b5b6;if(b1=0,Packets,3)计算放好6*6,5*5,4*4,3*3后留下多少空格能放2*2c2=5*b4+Contain2b3%4;4)在放好2*2的木块后，算留下多少空格能放1*1c1=36*nTotal-36*b6-25*b5-16*b4-9*b3-4*b2;,例题2：ai2808 校门外的树(P88),某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1

6、米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，L，都种有一棵树。由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。,校门外的树,【输入文件】输入的第一行有两个整数L（1=L=10000）和 M（1=M=100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一

7、个区域的起始点和终止点的坐标。【输出文件】输出包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。,校门外的树,【样例输入】500 3150 300100 200470 471【样例输出】298,校门外的树,思路1：开一个有L+1个元素的数组，每个元素对应一棵树，全部初始化为1，表示各个位置上都有树然后每读入一个区间，就将该区间对应的数组元素都变成0，表示该区间的树都被砍了最后算一下还有几个1，就是还剩几棵树了这种做法比较慢,校门外的树,思路2：将区间按起点排序，然后把所有区间遍历一遍，就把所有的树都砍了。不用开设L+1个元素的数组了，但是要开设数组将所有区间的起点，终点保存下来,例题3

8、：POJ1006 生理周期,人生来就有三个生理周期，分别为体力、感情和智力周期，它们的周期长度为23天、28天和33天。每一个周期中有一天是高峰。在高峰这天，人会在相应的方面表现出色。例如，智力周期的高峰，人会思维敏捷，精力容易高度集中。因为三个周期的长度不同，所以通常三个周期的高峰不会落在同一天。对于每个人，我们想知道何时三个高峰落在同一天。对每个周期，我们都给出了某一个高峰出现的日子（用高峰日是当年的第几天表示，1月1日算第0天)。现给定一个日子（也用当年的第几天表示），要求你输出从给定日子开始（不包括给定日子）下一次三个高峰落在同一天的时间（用距给定日子的天数来表示）。例如：给定日子为当

9、年第10天，如果下次出现三个高峰同日的时间是当年第12天，则输出2（注意这里不是3）。,生理周期,输入输入四个整数：p,e,i和d。p,e,i分别表示体力、情感和智力高峰出现的日子（即第p天，第e天和第d天）。d 是给定的日子（第d天)，可能小于p,e,或 i。d 是非负的并且小于365,数据保证所求的日子会在第21252 天前。数据以一行4个-1结束 输出从给定日子起，下一次三个高峰同天的日子距离给定日子的天数。,生理周期,问题分析令所求的时间为第x天，则x具有如下性质：1)D x=212522)(x-p)%23=03)(x-e)%28=04)(x-i)%33=0,生理周期,一个最简单直观的

10、做法就是枚举从d+1 到 21252 之间所有的数字，寻找第一个满足条件2）3）4）的数字，注意输出时间减去d.。,生理周期,可以做的进一步改进是从d+1开始逐一枚举寻找满足条件2 的数字a，从a开始每步加23寻找满足条件 3的数字b（这样的b自然也满足条件2)，然后再从b开始每步加23*28寻找满足条件 4 的数字x(这样的x同时满足条件2,3)。x就是我们要找的数字，输出时输出x-d。,生理周期,程序设计/读入p,e,i,d/j从d+1 循环到21252，如果(j-p)%23=0，跳出循环/j从上次跳出循环的值循环到21252，如果(j-e)%28=0，跳出循环/j从上次跳出循环的值循环到

11、21252，如果(j-i)%33=0，跳出循环/输出j-d,#include/生理周期using namespace std;int main()int p,e,i,d,j,no=1;cin p e i d;while(p!=-1,6*9=42 对于十进制来说是错误的，但是对于13进制来说是正确的。即,6(13)*9(13)=42(13)，而 42(13)=4*13+2=54(10)。你的任务是写一段程序读入三个整数p,q和 r，然后确定一个进制 B(2=B=16)使得 p*q=r.如果 B有很多选择,输出最小的一个。例如：p=11,q=11,r=121.则有 11(3)*11(3)=121(

12、3)因为 11(3)=1*31+1*30=4(10)和 121(3)=1*32+2*31+1*30=16(10)。对于进制 10,有 11(10)*11(10)=121(10)。这种情况下，应该输出 3。如果没有合适的进制，则输出 0。,例题4：poj1331确定进制(P98),输入输入有 T组测试样例。T在第一行给出。每一组测试样例占一行，包含三个整数p,q,r。p,q,r 的所有位都是数字，并且1=p,q,r=1,000,000。输出对于每个测试样例输出一行。该行包含一个整数-即使得p*q=r成立的最小的B。如果没有合适的B，则输出 0。,确定进制,输入样例3 6 9 42 11 11 1

13、21 2 2 2 输出样例13 30,确定进制,此题没难度，逐一试探法，注意一些实现的细节。,确定进制,程序设计练习 例2,#include#include int b2ten(int x,int b);int main()int p,q,r,n,b;scanf(%d,程序设计练习 例2,int b2ten(int x,int b)char tmp100;int ret=0;sprintf(tmp,%d,x);int len=strlen(tmp);for(int i=0;i=b)return-1;ret*=b;ret+=tmpi-0;return ret;,问题描述：在我们现在使用的日历中,

14、闰年被定义为能被4整除的年份，但是能被100整除而不能被400整除的年是例外，它们不是闰年。例如：1700,1800,1900 和 2100 不是闰年，而 1600,2000 和 2400是闰年。给定从公元2000年1月1日开始逝去得天数，你的任务是给出这一天是哪年哪月哪日星期几。,例题5：poj2080日历问题（P130),输入：输入包含若干行，每行包含一个正整数，表示从2000年1月1日开始逝去的天数。输入最后一行是1,不必处理。可以假设结果的年份不会超过9999。输出：对每个测试样例，输出一行，该行包含对应的日期和星期几。格式为“YYYY-MM-DD DayOfWeek”,其中“DayO

15、fWeek”必须是下面中的一个：Sunday,Monday,Tuesday,Wednesday,Thursday,Friday and Saturday“。,日历问题,样例输入1730 1740 1750 1751-1 样例输出2004-09-26 Sunday 2004-10-06 Wednesday 2004-10-16 Saturday 2004-10-17 Sunday,日历问题,问题解答 此题为典型的日期处理程序，没有难度,只是编程需要特别细心,日期处理的程序非常容易出错。基本思路：确定星期几；确定年；闰年366天，否则365天 确定月；每个月长短不同 确定日。,#include i

16、nt type(int);char week710=Saturday,Sunday,Monday,Tuesday,Wednesday,Thursday,Friday;int year2=365,366;/year0表示非闰年的天数，year1表示闰年的天数。int month212=31,28,31,30,31,30,31,31,30,31,30,31,31,29,31,30,31,30,31,31,30,31,30,31;/month0表示非闰年里每个月的天数，month1表示闰年里每个月的天数。,int main()int days,dayofweek;/days 表示输入的天数，dayo

17、fweek表示星期几。int i=0,j=0;while(scanf(%d,int type(int m)/判断第m年是否是闰年，是则返回1，否则返回0。if(m%4!=0|(m%100=0/是闰年,VC便于调试测试数据的办法,将测试数据拷贝，存到某.txt文件中，比如1661.txt选 Project|Settings菜单选debug页在Program arguments里输入存放测试数据的文件名 1661.txt5.在VC中点击感叹号图标运行程序,VC便于调试测试数据的办法,另一种方法：程序里加：freopen(“data.in”,”r”,stdin);则此后所有scanf,cin 语句都是从 data.in里读取数据了交题前注意将此句去掉,