NOIP复赛辅导模拟法ppt课件.ppt

,NOIP复赛辅导-模拟法,2012-09,模拟法有些问题难以找到公式与规律来解决，只能依旧问题的叙述一步一步不停地做下去，才能最终得到结果。这样的问题用计算机来模拟解决是最有效的。所以计算机模拟算法，即使程序完整的按题目所叙述的方式运行，最终得出答案。其实，模拟算法也就是将整个过程完完整整的走一遍。题目怎么叙述的，程序就怎么运行。,在C语言中,rand()函数可以用来产生随机数，但是这不是真真意义上的随机数，是一个伪随机数，是根据一个数，我们称它为种子为基准以某个递推公式推算出来的一系数。(1) C语言的伪随机数函数 rand(x); rand()产生一个从0到32767之间的伪随机数。使用本函数应使用#include 。我们常常用(rand( )%N)这样的一个表达式来产生一个从0N-1之间的整数。（曾经说过%是求余运算符）(2)随机数初始化函数 randomize(); 用一个time不断变化的时间函数对随机数函数发生器进行初始化。因此使用本函数应使用#include 。,常用rand()%N这样的一个表达式来产生一个从0N-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的随机整数r r = rand() % 6 + 1; (2) 产生2000至2050的随机整数r r = 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)统计中奖的选号有多少。#include#include #include main() int a,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 ,第一题：欢乐同庆（文件名：hltq.c） 过年了，小明与邻居的小伙伴们共5个人相约一起放鞭炮：他们同时放响了第一个，随后5个人分别以A1、A2、A3、A4、A5秒的间隔继续放鞭炮，每人都放了b个。问：总共可听到多少声鞭炮响？输入：A1、A2、A3、A4、A5(每个数30)和B(b30，并满足An*b255)。输出一个整数，即听到的鞭炮响声数。输入输出示例：输入：1 2 3 4 5 （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号同学的接水量。1n10000，1m100且mn；1wi100。【输出格式】仅一行，1个整数，表示接水所需的总时间。【样例输入】5 34 4 1 2 1 【样例输出】4,【算法分析】这是一道典型的模拟题，设置ai为第i个水龙头已经输出的水量，那么每次某个人去接水量为的水时，就是在所有ai中最小的一个里面加上，由此，对于每个人都重复这一过程，最后输出所有ai里最大的一个就是结果。想一想，本题采用模拟法，于是有了加或者减的方法。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】6 7 210 0 0 0 0 0 00 0 0 0 13 0 00 0 0 0 0 0 70 15 0 0 0 0 00 0 0 9 0 0 00 0 0 0 0 0 0【样例输出1】37【样例输入2】6 7 200 0 0 0 0 0 00 0 0 0 13 0 00 0 0 0 0 0 70 15 0 0 0 0 00 0 0 9 0 0 00 0 0 0 0 0 0【样例输出2】28,【算法分析】乍一看此题，就会发现，穷举、搜索的方法对此题都不适用，因为题目中已明确给出了摘豆子的规则。其实，我们只需要根据题目给出的规则，编程序模拟摘豆子的过程就可以了。首先，定义一个整型的二维数组a存储每个格子中的豆子数目，然后进行摘豆子。设置一个二层循环求出含有最多豆子的格子的坐标，由数学知识可知，从(x1,y1)到(x2,y2)需要的单位时间为|x1-x2|+|y1-y2|，因此由当前位置（x，y）跳到含有最多豆子的格子（x1，y1）内摘下豆子并回到路边所需的时间为step=|x-x1|+|y-y1|+1+x1，接下来判断step与剩余的时间p的大小关系。若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号同学的接水量。1n10000，1m100且mn；1wi100。【输出格式】仅一行，1个整数，表示接水所需的总时间。【样例输入】5 34 4 1 2 1 【样例输出】4,【算法分析】这是一道典型的模拟题，设置ai为第i个水龙头已经输出的水量，那么每次某个人去接水量为的水时，就是在所有ai中最小的一个里面加上，由此，对于每个人都重复这一过程，最后输出所有ai里最大的一个就是结果。想一想，本题采用模拟法，于是有了加或者减的方法。1减法（纯粹模拟）2加法（更优模拟）注：减法时最好不要时间一点一点的模拟，找最小得数减。,