资源描述：
《北京大学acm国际大学生程序设计竞赛2ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、问题求解与程序设计 第二讲 对局问题李文新2004.2–2004.6内容提要上周作业总结放硬币问题取火柴问题取石子问题-n堆取石子问题–1堆作业–装箱问题1005题弗雷德先生想在路易斯安娜州买一块地造房子。在调查中他了解到由于密西西比河的侵蚀，路易斯安娜州正在以每年50平方英里的速度变小。因为弗雷德先生希望在他的新房子里生活直至终老，所以他想知道他的房子是否会被侵蚀掉。1005题经过进一步研究，弗雷德发现将要被侵蚀得陆地呈半圆形。半圆是一个以（0，0）点为中心的圆的一半，半圆的直边是X轴。X轴以下的部分在水中。在第一年的开始，圆的面积是0。（半圆如下
2、图所示）。1005–问题1005–问题分析1）分析问题寻求算法因为河水呈半圆形扩散，每年扩散50平方英里，所以当给定一点的坐标时，可以用它与原点的距离作为半径，计算以此为半径的半圆的面积，在用这一面积除以50，向上取整，得到的就是要求的年数。即使用如下公式计算：1005–源代码#include //将输入输出的库函数包含#include //将用到的库函数包含进来void main(){//程序开始float x,y;//用来存放读入的坐标值int year;//用于保存计算出来的年数scanf(“%f %f”,&x
3、,&y);//从键盘读入坐标值year = (int)ceil((x*x+y*y)*3.1415926/2/50);//套用公式计算年数printf(“第%d年年末”, year);//将算出来的年数输出到屏幕上}//程序结束1006题人生来就有三个生理周期，分别为体力、感情和智力周期，它们的周期长度为23天、28天和33天。每一个周期中有一天是高峰。在高峰这天，人会在相应的方面表现出色。例如，智力周期的高峰，人会思维敏捷，精力容易高度集中。因为三个周期的周长不同，所以通常三个周期的高峰不会落在同一天。对于每个人，我们想知道何时三个高峰落在同一
4、天。对于每个周期，我们会给出从当前年份的第一天开始，到出现高峰的天数（不一定是第一次高峰出现的时间）。你的任务是给定一个从当年第一天开始数的天数，输出从给定时间开始（不包括给定时间）下一次三个高峰落在同一天的时间（距给定时间的天数）。例如：给定时间为10，下次出现三个高峰同天的时间是12，则输出2（注意这里不是3）。1006题输入输入四个整数：p,e,i和d。p,e,i分别表示体力、情感和智力高峰出现的时间（时间从当年的第一天开始计算）。d是给定的时间，可能小于p,e,或i。所有给定时间是非负的并且小于365,所求的时间小于21252。输出从给定时间
5、起，下一次三个高峰同天的时间（距离给定时间的天数）。1006题问题分析令所求的时间为当年的第x天，则x具有如下性质：1)21252=>x>d2)(x-p)%23=03)(x-e)%28=04)(x-i)%33=01006题一个最简单直观的做法就是枚举从d+1到21252之间所有的数字，寻找第一个满足条件2）3）4）的数字，注意输出时间减去d.。1006题可以做的进一步改进是从d+1开始逐一枚举寻找满足条件2）的数字a，从a开始每步加23寻找满足条件2）3）的数字b，从b开始每步加23*28寻找满足条件2）3）4）的数字x。x就是我们要找的数字，输出时
6、输出x-d。1006题程序设计//读入p,e,i,d//j从d+1循环到21252，如果(j-p)%23==0，跳出循环//j从上次跳出循环的值循环到21252，如果(j-e)%28==0，跳出循环//j从上次跳出循环的值循环到21252，如果(j-i)%33==0，跳出循环//输出j-d1006题#include#includevoidmain(){intp,e,i,d,j,no=1;scanf("%d%d%d%d",&p,&e,&i,&d);while(p!=-1&&e!=-1&&i!=-1&&d!=-1){
7、for(j=d+1;j<=21252;j++)if((j-p)%23==0)break;for(;j<=21252;j=j+23)if((j-e)%28==0)break;for(;j<=21252;j=j+23*28)if((j-i)%33==0)break;printf("Case%d:thenexttriplepeakoccursin%ddays.",no,j-d);scanf("%d%d%d%d",&p,&e,&i,&d);no++;}}放硬币问题在一个圆形桌面上，甲、乙轮流放5分硬币，不许重叠，甲先放，首先放不下硬币的一方为负。甲如
8、何取胜呢？放硬币问题事实上，甲只要先在圆桌中心放下一枚硬币，此后无论乙怎么放，甲总在其关于中心对称处放一枚，
