校门外的树P88.PPT

int main() { int days, dayofweek; //days 表示输入的天数，dayofweek表示星期几。 int i = 0, j = 0; while (scanf(%d, days) days != -1) { dayofweek = days % 7; for(i = 2000; days = year[type(i)]; i++) days -= year[type(i)]; for(j = 0; days = month[ type(i) ][ j ]; j++) days -= month[ type(i) ][ j ]; printf(%d-%02d-%02d %s\n, i, j + 1, days + 1, week[dayofweek]); } return 0; } int type(int m){ //判断第m年是否是闰年，是则返回1，否则返回0。 if(m % 4 != 0 || (m % 100 == 0 m % 400 != 0)) return 0; //不是闰年 else return 1; // 是闰年 } 程序设计II第二讲 内容提要 POJ简介 例题1：Packets 例题2：校门外的树 例题3：生理周期 例题4：确定进制 例题5：日历问题 出错类型 Complie Error – 编译错 Runtime 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 的木块，箱子高度和木块一样 问：给定各种木块的数目，求最少需要多少个大箱子来装？ 例如： 输入：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的木块每个占用一个新箱子； 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 b1 nTotal - 箱子数 1） 先放好所有 6 * 6, 5 * 5, 4 * 4 和3 * 3 的木块 nTotal = b6 + b5 + b4 + (b3+3)/4 4*4, 5*5, 6*6 单独开箱子 3*3 每4个占一个箱子，余下的占一个箱子 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的木块都填进去，如果不能，也容易算出还要加多少个箱子 #include iostream using namespace std; int main() { int b6,b5,b4,b3,b2,b1; //不同大小的木块个数 int nTotal = 0; //最少需要的箱子数目 int c1; //当前能放 1*1 木块的空格数目 int c2; //当前能放 2*2 木块的空格数目