《北京大学ACM国际大学生程序设计竞赛1ppt课件》由会员分享，可在线阅读，更多相关《北京大学ACM国际大学生程序设计竞赛1ppt课件（23页珍藏版）》请在金锄头文库上搜索。
1、问题求解与程序设计第七讲 内容提要搜索 讨论 1011 stick讨论 1054 the troublesome frog参考王知昆的冬令营报告作业搜索的普通概念在解空间中尝试一切能够，找出满足条件的取值回想填数游戏：1-9填在3*3的表格中，使得行、列、对角线的和均为15。方程组搜索 逐一尝试+剪枝标题讨论1011 stick标题讨论The Troublesome FrogIOI 2002 day 1 task 1问题稻田问题青蛙从外面跳入稻田，踩过一些禾苗，后，跳出稻田。问题蛙路：一个方向，等间距，大于等于3个点 不同蛙路：可以方向不同，间距不同问题许多青蛙跳过稻田，构成多条蛙路，不同蛙路
2、可以踩过同一作物。问题青蛙每天早上踩坏稻田，早上人们发现稻田有假设干株作物被踩坏，但不知多少青蛙来过。也有不在蛙路上的被踩坏的作物。问题问，给定一块被踩坏的稻田，求能够的最长的蛙路上被踩坏的作物的数目。输入第一行整数R和C，稻田的行数和列数第二行整数N，表示被踩坏的作物总数。后续N行，每行两个整数i,j为被踩坏的作物的行和列的位置:1=i=R,1，1=j=C。每个被踩坏的作物只出现一次。输出单个整数- 表示最长能够蛙路上踩坏的作物数目样例Figure- 4问题的解这道标题也就是说，在给出的n个点中找出一些点的序列来，使得每一个点相对于上一个点的坐标都是一个一样的向量，且第一个点减去这个向量和最
3、后一个点加上这个向量后均落在方格的外面。 问题的解我们先对这些点按照坐标排序。然后依次循环出要求的序列中的第一个和第二个点，这样我们就知道后一个点相对于前一个点的坐标是多少了。然后我们依次用第二个点加上这个坐标的出第三个点，第三个点加上这个坐标得出第四个点等等。当然，我们还需求判别一下这求出来的第三个、第四个点能否在给定的点内。 问题的解由于每个点的上一个点/下一个点最多只能有n种选择，故一个点最多属于n条不同的蛙路。这样，对于某个确定的点来说，它的一切能够的下一个需求判别的点至多有n个。这样由于判别一个点在不在给定的点内只需求O(1)的复杂度，所以我们只需求O(n2)的时间就可以得出问题的解
4、答。由于这个算法需求一个r*c的表来保管点在方格中的存在形状，故空间复杂度为O(n2)。 问题的解需求留意的是，蛙路中的点数少于3个的时候是不思索的。所以这个时候的蛙路中的点数应该按照0来算。 实现细节Frog vs frog 平面上点的表示Frog 2 0 有冗余代码Frog 2 1 去掉冗余Frog 2 2 compare 判别Frog 2 3改动表达式写法Frog 2 4添加剪枝Frog 2 5不太好的剪枝顺序Frog 2 6较好的剪枝顺序测试数据No. N, (R*C) Description Solution1 18, (6 * 7) Sample data in the task
5、description 42 10, (10 * 10) Manually designed 53 25, (50 * 50) Manually designed 134 50, (10 * 10) Several Lines + random points 105 100, (20 * 20) modified random point set 106 300, (30 * 30) modified random point set 157 500, (55 * 55) Several Lines + random points 288 500, (100 * 100) Special ca
6、se for no solution 09 1000, (100 * 100) Several Lines + random points 3410 1000, (1000 * 1000) Several Lines + random points 25011 2000, (50 * 50) Random (uniform) points 2512 2000, (100 * 200) Several Lines + random points 3313 2000, (1000 * 2000) Several Lines + random points 333测试数据14 3000, (60 *
7、 60) Uniformly random points 3115 3000, (500 * 500) X shapes and random points 50016 3000, (5000 * 1) Horizontal line 2017 3000, (5 * 1000) Several Lines + random points 1718 4000, (100 * 100) Random points (uniformly) 3419 4000, (200 * 20) Very dense points set 20020 4000, (1000 * 1000) Several Lin
8、es + random points 50021 4000, (5000 * 5000) Several Lines + random points 31122 5000, (100 * 100) Chess board style 10023 5000, (1000 * 1000) Several Lines + random points 33424 5000, (3000 * 3000) Irregular linear points 100025 5000, (5000 * 5000) Modified random points 72参考资料王知昆的冬令营报告作业10111054 选做
