wc2008-II
2008/1/25
上午, 吴文虎, 搜索.
主要讲DFS和BFS. 吴老师讲课时从不会拿很难的东西吓我们. 很基础的DFS, 非常详细的展示了一道用DFS解决的题目的思想过程, 以及如何剪枝. 又一次引入了与结点和或结点, 感觉或节点就是if语句, 与结点就是顺序的语句. 按吴老师的话, 这是用图示的直观性帮助思维. 印象最深的一句话: 问题要从简单到复杂, 从特例到一般, 我好像就是少这样一种思考问题的方法. BFS讲了USACO上那道亚瑟王, 最终得出这样一个结论, 这是一类这样的题目: 正确的作法显而易见, 却又很难证明. 吴老师在学生间走动时, 忽然把话筒递给了我, 我首次, 第一次, 史无前例的一次, 在国家级比赛活动的站起来发言, 尽管是被人点起来的, 但毕竟是起来了, 写下纪念. 至于我的发言, 自然是像我本人一样没有水平, 好像就是把前前一位同学的发言重复了一遍( 但, 这道题我就是这么做的, 我也不明白为什么这样就对 ). 然后讲了递归, 强调递归在计算机算法中的重要性, 提了两道题, 一道是著名的青蛙过河, 另一道是同样著名的汉诺塔问题. 汉诺塔问题的一般情况我明白. 但是又提出如果有N个盘子, M个柱子( M >= 3 )时, 怎么解决汉诺塔问题. 解法是DP+递归. 方程 f[ i ][ j ] = f[ i – k ][ j ] + f[ k ][ j – 1 ] + f[ i – k ][ j ], 其中f[ i ][ j ]表示有i个盘子j个柱子时至少需要多少次移动才可以将所有盘子从A盘移动到B盘. More »
Tags: noi, 冬令营, 吴文虎, 生日, 礼物