V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
lcj2class
V2EX  ›  程序员

这种题如何编程解决?

  •  
  •   lcj2class · 2014-08-16 19:03:57 +08:00 · 4852 次点击
    这是一个创建于 3737 天前的主题,其中的信息可能已经有所发展或是发生改变。
    题目要求是这样的:
    假设有一个池塘,里面有无穷多的水。现有2个空水壶,容积分别为5升和6升。如何只用这2个水壶从池塘里取得3升的水**(最后,这三升水,在其中一个壶里)


    我这里尝试进行了总结,
    http://liujiacai.net/blog/2014/08/16/two-pot-question/

    大家谁还有这种题目,可以分享出来,我觉得这种题很能锻炼思维,谢谢。
    34 条回复    2014-08-17 14:35:50 +08:00
    yangkeao
        1
    yangkeao  
       2014-08-16 20:02:51 +08:00
    wikioi上参见博弈,,很能锻炼思维。//这好像已经不是一个东西啦~~不过如果要求是锻炼思维也还是可以
    exoticknight
        2
    exoticknight  
       2014-08-16 20:03:06 +08:00
    文章写得很好,算法渣渣表示也看得懂!
    kmvan
        3
    kmvan  
       2014-08-16 20:30:11 +08:00 via Android
    gcd是什么函数我已经看不懂了
    lcj2class
        4
    lcj2class  
    OP
       2014-08-16 20:49:52 +08:00
    @yangkeao 谢谢分享,以前还真不知道这个平台
    lcj2class
        5
    lcj2class  
    OP
       2014-08-16 20:50:23 +08:00
    @exoticknight 好不敢当,只希望对大家多少有些启发
    jok3r
        6
    jok3r  
       2014-08-16 20:51:45 +08:00
    我感觉在OJ上刷题时遇见过类似的,
    fishleen
        7
    fishleen  
       2014-08-16 20:53:33 +08:00 via iPhone
    推荐MIT的教程Mathematics for Computer Science里的Number Theory,其中有详细证明为什么能得到X升的线性组合。只要有高中数学基础都能看懂(小学做过类似奥数题目也能看懂)。
    CS学到后面都是算法了,没有离散数学基础很难学下去。
    ruoyu0088
        8
    ruoyu0088  
       2014-08-16 20:55:14 +08:00
    接下来可以试试三个水桶互相倒水。
    Exin
        9
    Exin  
       2014-08-16 21:07:31 +08:00
    总结里面的代码用的是什么字体?
    lcj2class
        10
    lcj2class  
    OP
       2014-08-16 21:08:25 +08:00
    @jok3r 我在校期间没怎么玩过OJ,发现浪费了4年的大好光阴呀
    lcj2class
        11
    lcj2class  
    OP
       2014-08-16 21:11:39 +08:00
    @fishleen 赞,天天coding是真码农了,记得当年学离散时的群论那部分最爽了,有空再复习下。
    lcj2class
        12
    lcj2class  
    OP
       2014-08-16 21:13:30 +08:00
    @ruoyu0088 你说的是三桶水平分的哪个吗
    lcj2class
        13
    lcj2class  
    OP
       2014-08-16 21:14:49 +08:00
    @Exin 你用firebug看下就知道了
    yangff
        14
    yangff  
       2014-08-16 21:16:01 +08:00 via Android
    dp[i][j]分别表示第一个桶iL水,第二个桶jL水这个状态能否达到。
    然后转移就可以了。
    yangff
        15
    yangff  
       2014-08-16 21:17:20 +08:00 via Android
    然后这个转移的过程就是欧几里德算法求gdc啦。。
    GtDzx
        16
    GtDzx  
       2014-08-16 21:25:37 +08:00
    http://hihocoder.com 有一个活动叫"hiho一下",会按照一定的知识体系每周详细讲解一道算法题目,并且要求你写出正确的程序。你可以从第一周的题目开始跟着做。每周的题目结束之后,还会公布所有通过的用户的代码供你学习参考。
    另外hihocoder明天刚好有一场模拟赛,是给参加google校招的同学准备的。题目难度接近google去年校招的水平,并且都不是那种需要特定算法/数据结构知识才能做的竞赛题,可以尝试一下。
    lcj2class
        17
    lcj2class  
    OP
       2014-08-16 21:33:47 +08:00
    @yangff 用gcd这个是毫无疑问了,你说的数组怎么用我还不清楚,能否赐教
    lcj2class
        18
    lcj2class  
    OP
       2014-08-16 21:34:42 +08:00
    @GtDzx 谢谢分享,有空可以玩玩
    Exin
        19
    Exin  
       2014-08-16 21:41:32 +08:00
    @lcj2class 不好意思没有安装,你能直接告诉我吗?
    lcj2class
        20
    lcj2class  
    OP
       2014-08-16 21:46:18 +08:00   ❤️ 1
    @Exin font-family="Monaco,​Menlo,​Consolas,​Courier New,​monospace"
    pljhonglu
        21
    pljhonglu  
       2014-08-16 21:55:11 +08:00
    见到校友~赞一个~
    yangff
        22
    yangff  
       2014-08-16 21:57:00 +08:00 via Android   ❤️ 1
    @lcj2class 你这样考虑,最开始的时候两个桶都是空的显然是可以的为1,
    每个时刻有4种操作可以做,把某个桶装满,把一个桶的水倒进另一个桶。
    直接搜索的话当然可以,但是你会发现,如果你已经知道ij这个状态的结果,就不用再去计算了,用数组记一下某个状态是否到达过就可以了,最后可以发现这个转移的过程其实就是在mod x意义下做扩展欧几里德。
    lcj2class
        23
    lcj2class  
    OP
       2014-08-16 22:25:04 +08:00
    @yangff 我大概知道你的意思了,那这个数组应该怎么构造呢?
    asmore
        24
    asmore  
       2014-08-16 22:31:55 +08:00
    算法表述非常清晰~~
    bengol
        25
    bengol  
       2014-08-16 22:47:05 +08:00
    @jok3r hackerrank 出过
    yhf
        26
    yhf  
       2014-08-16 23:06:34 +08:00 via iPhone
    acm里一般都会有这种题吧,描述题。
    yangff
        27
    yangff  
       2014-08-16 23:39:56 +08:00 via Android
    @lcj2class 搜索的时候记录一下当前的ij是否被算过,如果算过了就直接return这样最后得到的就是这个数组了。。
    yangff
        28
    yangff  
       2014-08-16 23:42:27 +08:00 via Android
    http://codeforces.com/problemset/problem/343/A
    这题和你这题做法差不多。。
    heganj
        29
    heganj  
       2014-08-17 00:09:49 +08:00
    core.logic
    bombless
        30
    bombless  
       2014-08-17 00:15:09 +08:00
    也许可以参考一下张景中的书…他研究的一个方向就是用程序证明几何命题。
    monkeylyf
        31
    monkeylyf  
       2014-08-17 00:46:34 +08:00
    gcd
    lcj2class
        32
    lcj2class  
    OP
       2014-08-17 10:06:57 +08:00
    @yangff 你这不就是动态规划嘛,不过lisp中一般都是直接用递归或迭代解决问题的,怎么保存中间状态我还不清楚
    yangff
        33
    yangff  
       2014-08-17 10:13:40 +08:00 via Android
    @lcj2class 囧我写的就是dp啊
    tushiner
        34
    tushiner  
       2014-08-17 14:35:50 +08:00
    弱弱的说,ACM里面不是有很多这种东东么。。。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2835 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 02:16 · PVG 10:16 · LAX 18:16 · JFK 21:16
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.