NOIP复赛辅导-模拟法

NOIP复赛辅导-模拟法2012-09模拟法有些问题难以找到公式与规律来解决，只能依旧问题的叙述一步一步不停地做下去，才能最终得到结果。这样的问题用计算机来模拟解决是最有效的。所以计算机模拟算法，即使程序完整的按题目所叙述的方式运行，最终得出答案。其实，模拟算法也就是将整个过程完完整整的走一遍。题目怎么叙述的，程序就怎么运行。在C语言中,rand()函数可以用来产生随机数，但是这不是真真意义上的随机数，是一个伪随机数，是根据一个数，我们称它为种子为基准以某个递推公式推算出来的一系数。(1)C语言的伪随机数函数rand(x);rand()产生一个从0到32767之间的伪随机数。使用本函数应使用#includestdlib.h。我们常常用(rand()%N)这样的一个表达式来产生一个从0~N-1之间的整数。（曾经说过%是求余运算符）(2)随机数初始化函数randomize();用一个time不断变化的时间函数对随机数函数发生器进行初始化。因此使用本函数应使用#includetime.h。常用rand()%N这样的一个表达式来产生一个从0~N-1之间的整数。假设我们希望产生一个在A到B之间的随机数(AB)，则我们可以这样写随机数生成的式子：x=rand()%(B-A+1)+A;x=rand()%B+1产生的随机数x是在0到B之间的整数;x=rand()%(B-A+1)+A产生的随机数x是在A到B之间的整数。随机数生成举例:(1)产生1至6的随机整数rr=rand()%6+1;(2)产生2000至2050的随机整数rr=rand()%51+2000[探索]请依据下面给出的条件写出随机数生成的式子。(1)产生100至999的随机整数r_____________________________(2)产生10以内的随机奇数r_____________________________(3)产生100以内被5整除的随机整数r___________________________________例题1:模拟七选三的彩票中奖机率(1)先随机产生三个从1到7的数a,b,c为彩票中奖号码。(2)再随机产生1000组选号x,y,z(3)统计中奖的选号有多少。#includestdio.h#includestdlib.h#includetime.hmain(){inta,b,c,x,y,z,j,p=0;clrscr();randomize();a=random(7)+1;b=random(7)+1;c=random(7)+1;for(j=1;j=1000;j++){x=random(7)+1;y=random(7)+1;z=random(7)+1;if(x==a&&y==b&&z==c){p++;printf(“(%d)%d%d%d\n”,p,x,y,z);}}}第一题：欢乐同庆（文件名：hltq.c）过年了，小明与邻居的小伙伴们共5个人相约一起放鞭炮：他们同时放响了第一个，随后5个人分别以A1、A2、A3、A4、A5秒的间隔继续放鞭炮，每人都放了b个。问：总共可听到多少声鞭炮响？输入：A1、A2、A3、A4、A5(每个数≤30)和B(b≤30，并满足An*b≤255)。输出一个整数，即听到的鞭炮响声数。输入输出示例：输入：12345（5个人放鞭炮的间隔）4（每人放鞭炮数b）输出：12第二题：接水问题(water.c)【问题描述】学校里有一个水房，水房里一共装有m个龙头可供同学们打开水，每个龙头每秒钟的供水量相等，均为1。现在有n名同学准备接水，他们的初始接水顺序已经确定。将这些同学按接水顺序从1到n编号，i号同学的接水量为wi。接水开始时，1到m号同学各占一个水龙头，并同时打开水龙头接水。当其中某名同学j完成其接水量要求Wj后，下一名排队等候接水的同学k马上接替j同学的位置开始接水。这个换人的过程是瞬间完成的，且没有任何水的浪费。即j同学第x秒结束时完成接水，则k同学第x+1秒立刻开始接水。若当前接水人数n不足m，则只有n个龙头供水，其它m-n个龙头关闭。现在给出n名同学的接水量，按照上述接水规则，问所有同学都接完水需要多少秒。【输入格式】第1行2个整数n和m，用一个空格隔开，分别表示接水人数和龙头个数。第2行n个整数w1、w2、……、wn，每两个整数之间用一个空格隔开，wi表示i号同学的接水量。1≤n≤10000，1≤m≤100且m≤n；1≤wi≤100。【输出格式】仅一行，1个整数，表示接水所需的总时间。【样例输入】5344121【样例输出】4【算法分析】这是一道典型的模拟题，设置a[i]为第i个水龙头已经输出的水量，那么每次某个人去接水量为ｗ的水时，就是在所有a[i]中最小的一个里面加上ｗ，由此，对于每个人都重复这一过程，最后输出所有a[i]里最大的一个就是结果。想一想，本题采用模拟法，于是有了加或者减的方法。1．减法（纯粹模拟）2．加法（更优模拟）注：减法时最好不要时间一点一点的模拟，找最小得数减。第三题：花生采摘(peanuts.pas/dpr/c/cpp)【问题描述】鲁宾逊先生有一只宠物猴，名叫多多。这天，他们两个正沿着乡间小路散步，突然发现路边的告示牌上贴着一张小小的纸条：“欢迎免费品尝我种的花生！—熊字”。鲁宾逊先生和多多都很开心，因为花生正是他们的最爱。在告示牌背后，路边真的有一块花生田，花生植株整齐地排列成矩形网格（如图1）。有经验的多多一眼就能看出，每棵花生植株下的花生有多少。为了训练多多的算术，鲁宾逊先生说：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此类推，不过你一定要在我限定的时间内回到路边。”我们假定多多在每个单位时间内，可以做下列四件事情中的一件：1)从路边跳到最靠近路边（即第一行）的某棵花生植株；2)从一棵植株跳到前后左右与之相邻的另一棵植株；3)采摘一棵植株下的花生；4)从最靠近路边（即第一行）的某棵花生植株跳回路边。现在给定一块花生田的大小和花生的分布，请问在限定时间内，多多最多可以采到多少个花生？注意可能只有部分植株下面长有花生，假设这些植株下的花生个数各不相同。例如在图2所示的花生田里，只有位于(2,5),(3,7),(4,2),(5,4)的植株下长有花生，个数分别为13,7,15,9。沿着图示的路线，多多在21个单位时间内，最多可以采到37个花生。【输入文件】输入文件peanuts.in的第一行包括三个整数，M,N和K，用空格隔开；表示花生田的大小为M*N（1=M,N=20），多多采花生的限定时间为K（0=K=1000）个单位时间。接下来的M行，每行包括N个非负整数，也用空格隔开；第i+1行的第j个整数Pij（0=Pij=500）表示花生田里植株(i,j)下花生的数目，0表示该植株下没有花生。【输出文件】输出文件peanuts.out包括一行，这一行只包含一个整数，即在限定时间内，多多最多可以采到花生的个数。【样例输入1】672100000000000130000000070150000000090000000000【样例输出1】37【样例输入2】672000000000000130000000070150000000090000000000【样例输出2】28【算法分析】乍一看此题，就会发现，穷举、搜索的方法对此题都不适用，因为题目中已明确给出了摘豆子的规则。其实，我们只需要根据题目给出的规则，编程序模拟摘豆子的过程就可以了。首先，定义一个整型的二维数组a存储每个格子中的豆子数目，然后进行摘豆子。设置一个二层循环求出含有最多豆子的格子的坐标，由数学知识可知，从(x1,y1)到(x2,y2)需要的单位时间为|x1-x2|+|y1-y2|，因此由当前位置（x，y）跳到含有最多豆子的格子（x1，y1）内摘下豆子并回到路边所需的时间为step=|x-x1|+|y-y1|+1+x1，接下来判断step与剩余的时间p的大小关系。若step=p则说明有足够的时间去摘豆子，则去摘：具体步骤（剩余时间p：=p-|x-x1|+|y-y1|-1；当前点的坐标跳入（x1，y1）；摘下的总豆子数sum：=sum+a[x，y]，a[x，y]：=0；表示此格子内的豆子已被摘没）；若stepp，说明没有足够多的时间跳过去摘下豆子再回到路边，因此只能回到路边而不能去摘豆子了。重复此摘法即可得出最后结果。第二题：接水问题(water.c)【问题描述】学校里有一个水房，水房里一共装有m个龙头可供同学们打开水，每个龙头每秒钟的供水量相等，均为1。现在有n名同学准备接水，他们的初始接水顺序已经确定。将这些同学按接水顺序从1到n编号，i号同学的接水量为wi。接水开始时，1到m号同学各占一个水龙头，并同时打开水龙头接水。当其中某名同学j完成其接水量要求wj后，下一名排队等候接水的同学k马上接替j同学的位置开始接水。这个换人的过程是瞬间完成的，且没有任何水的浪费。即j同学第x秒结束时完成接水，则k同学第x+1秒立刻开始接水。若当前接水人数n不足m，则只有n个龙头供水，其它m?n个龙头关闭。现在给出n名同学的接水量，按照上述接水规则，问所有同学都接完水需要多少秒。【输入格式】第1行2个整数n和m，用一个空格隔开，分别表示接水人数和龙头个数。第2行n个整数w1、w2、……、wn，每两个整数之间用一个空格隔开，wi表示i号同学的接水量。1≤n≤10000，1≤m≤100且m≤n；1≤wi≤100。【输出格式】仅一行，1个整数，表示接水所需的总时间。【样例输入】5344121【样例输出】4【算法分析】这是一道典型的模拟题，设置a[i]为第i个水龙头已经输出的水量，那么每次某个人去接水量为ｗ的水时，就是在所有a[i]中最小的一个里面加上ｗ，由此，对于每个人都重复这一过程，最后输出所有a[i]里最大的一个就是结果。想一想，本题采用模拟法，于是有了加或者减的方法。1．减法（纯粹模拟）2．加法（更优模拟）注：减法时最好不要时间一点一点的模拟，找最小得数减。