程序设计实习第二讲课件.ppt

内容提要 POJ简介 例题1：Packets 例题2：校门外的树 例题3：生理周期 例题4：确定进制 例题5：日历问题 例题1：POJ 1017 Packets (课本P92) 题意 已知：有6*6 的大箱子和 1*1，2*2，3*3，4*4，5*5，6*6 的木块，箱子高度和木块一样 问：给定各种木块的数目，求最少需要多少个大箱子来装？ 例如： 输入：0 0 4 0 0 1 -〉 输出 2 输入：7 5 1 0 0 0 -〉 输出 1 Packets Packets Packets Packets Packets Packets 2) 再把2 * 2的塞到放有3*3木块的箱子里 设一个数组： int Contain2[4] = { 0, 5, 3, 1 }; Contain2[i] 表示当3*3木块的数目除以4的余数分别是0,1,2,3时，会产生多少个能放2*2木块的空格。 用数组纪录某些事实，比写 if else 方便 放完2*2的木块后，再算一下有多少1*1的空格，能否把1*1的木块都填进去，如果不能，也容易算出还要加多少个箱子 Packets 3) 计算放好6*6,5*5,4*4,3*3后留下多少空格能放2*2 c2 = 5 * b4 + Contain2[b3 % 4]; 4) 在放好2*2的木块后，算留下多少空格能放1*1 c1 = 36 * nTotal - 36 * b6 - 25 * b5 - 16 * b4 - 9 * b3 - 4 * b2; 例题2： ai2808 校门外的树(P88) 某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。 由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。 ? 校门外的树 【输入文件】 ?输入的第一行有两个整数L（1 = L = 10000）和 M（1 = M = 100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。 ?【输出文件】 ?输出包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。 ? 校门外的树 【样例输入】 500 3 150 300 100 200 470 471 【样例输出】 298 例题3：POJ1006 生理周期 人生来就有三个生理周期，分别为体力、感情和智力周期，它们的周期长度为23天、28天和33天。每一个周期中有一天是高峰。在高峰这天，人会在相应的方面表现出色。例如，智力周期的高峰，人会思维敏捷，精力容易高度集中。因为三个周期的长度不同，所以通常三个周期的高峰不会落在同一天。对于每个人，我们想知道何时三个高峰落在同一天。对每个周期，我们都给出了某一个高峰出现的日子（用高峰日是当年的第几天表示，1月1日算第0天)。现给定一个日子（也用当年的第几天表示），要求你输出从给定日子开始（不包括给定日子）下一次三个高峰落在同一天的时间（用距给定日子的天数来表示）。例如：给定日子为当年第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 = 21252 2) (x-p)%23=0 3) (x-e)%28=0 4) (x-i)%33=0 生理周期 一个最简单直观的做法就是枚举从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-