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盘. 方程是很容易理解, 但我想到这么一个问题: 这个方程显然是先将(i-k)个盘借助所有柱子移到C柱, 再将剩下k个盘子移到B盘, 最后再把(i-k)个盘移到B盘上. 但会不会如果我们不把(i-k)个盘子全部都移到C盘, 就是分散到C盘, D盘, E盘甚至F盘什么的, 可以得到更少的移动的次数呢? 但是想想, 这只是分到C盘的盘子不到(i-k)罢了, 剩下的盘子参与k个盘子移动到了B盘, 也就是这是f[ i ][ j ] = f[ i – k’ ][ j ] * 2 + f[ k’ ][ j – 1 ] ( k’的情况.. 接着又讲了一会儿DP, 印象比较深的一句话, 写下:
贪心和动态规划的区别: 贪心仅仅是作出局部最优选择, 而动态规划是保证全局最优的情况下作出局部最优选择.
我还是觉得, 动态规划就是记忆化搜索, 就是避免重复的搜索. 我做题很少, 要是您实在看不下去我这句很**的话(**自填), 感谢指出!!
下午, 王宏, 回顾2007试题. 我看到, 当初不会的题, 现在我还是不会. 非算法方面两个收获: 多做题, 多参加网上的比赛; 有时, 有些看似没有解决方法的问题, 可以用恶搞的方法解决, 有时真的能拿蛮多的点. 不可以轻易放弃看似不会的题目, 在USACO的月赛上一定实践. 月赛不恶搞看来是拿不上多少分的, 我又不是cdq.. ( yz要乱想, 拖出去斩了!!! )
在今后的计划中, 我想应该在搞懂经典算法的基础上, 应该看一些随机搜索, 模拟退火之类的算法, 开放式题目在Noi, Wc上MS已经是每届一道的频率了.
我不喜欢南方湿冷的冬天, 潮湿的空气中, 我总觉得呼吸着绝望, 难受 的, 明年终于到北京了, 美好的北方, 美好的北京, 美好的暖气.. 如果, 我还在的话.
收到你的短信, 是今天最值得一提的惊喜. 终于找到一台可以上网的机器, 却发现没有新邮件. 郁闷.. 还真是首发倒计时, 连预售都没有吗? “对不起, 您拨打的电话已停机”, 我有跳海的冲动, 绍兴附近有海吗?
下午, 强忍住没看柯南, 搞学习.
晚上, 一直听孙燕姿. 我是一个超级博爱的歌迷: 我是Andy饭(Myself, hehe), Twins饭, Jay饭, Stefanie饭, Lp饭…
