×

Loading...

给坛子里自己在搞软件,孩子在学或者想学CS的朋友分享一道滑大 CS145 的期末考试题。看看他们都在学些什么。

原题是用 RACKET 教学语言, 这里转成了Python, 应无漏题嫌疑。 用Java 9 以上带 Functional Programming 的语言也可编出来。

题:

严格按照以下要求,编一个小程序或者一个Function, 输入为一个单链表(Single Linked List), 输出为一个反转(Reversed) 后的同一单链表。

要求:
1. 不能用任何循环 (No LOOP)
2. 不能用递归 (No Recursive)
3. 可以定义help functions 和 variables, 但只能用以下 Python关键字: def, is None,if, next_node(). (这个条件太苛刻, 如果用Java可以忽略它。)

我孩子考完回来说别的题都简单, 就这个题足足做了一个多小时才做出来。然后就用它来考老爸。于是我的头就开始疼了。

有兴趣的朋友闲的时候可以试试看。
Report

Replies, comments and Discussions:

  • 工作学习 / 学科技术 / 给坛子里自己在搞软件,孩子在学或者想学CS的朋友分享一道滑大 CS145 的期末考试题。看看他们都在学些什么。 +2
    原题是用 RACKET 教学语言, 这里转成了Python, 应无漏题嫌疑。 用Java 9 以上带 Functional Programming 的语言也可编出来。

    题:

    严格按照以下要求,编一个小程序或者一个Function, 输入为一个单链表(Single Linked List), 输出为一个反转(Reversed) 后的同一单链表。

    要求:
    1. 不能用任何循环 (No LOOP)
    2. 不能用递归 (No Recursive)
    3. 可以定义help functions 和 variables, 但只能用以下 Python关键字: def, is None,if, next_node(). (这个条件太苛刻, 如果用Java可以忽略它。)

    我孩子考完回来说别的题都简单, 就这个题足足做了一个多小时才做出来。然后就用它来考老爸。于是我的头就开始疼了。

    有兴趣的朋友闲的时候可以试试看。
    • 长度未知的情况下不用循环和递归?没想出来。
      • 是难。 提示一下, 这门课叫 CS 145: Designing Functional Programs (Advanced Version)。 一定要用 FP 才做得出来。 +2
        • 觉得Dp才难,只要多做题才能领悟
    • 滑铁卢读CS出来的都是牛人啊。当年我读CS读不下去了才转精算, +4
      毕业后花了8,9年才达到肉联平均工资水平。感谢滑铁卢给我这个普通学生普通智商一个平台(自己在国内应该中山大学都考不到的水平),也深深羡慕着那些CS大拿毕业一两年就可以赚大钱的校友们,也觉得确实他们大多数都有那水平!
      • 是给龙潭提供一个思路吗 -- 考不上或者念不下去CS就转精算,88%的人一辈子也到不了肉坦平均水平。
      • 好奇问一下。肉联平均工资水平的都哪毕业的? 滑大毕业的普通生要毕业8-9年才能达到这平均水平。
        • 蓝翔
    • Functional Progarmming is new to me. Very interesting!
      • 1, Recursion can replace loop. 2, In FP, functions can be arguments and results of other functions. This serves the purpose of recursion.
        • javascript 的promise竟是些那个东东
          • Promise is about asynchronization, is that right?
        • u can define a func and use it as argument but i feel in this case, that func still needs to call itself? In a way it's still recursive? no?
          • Defining a function which calls itself inside the body is recursive. But,
            actually it's another hint, assume we define a function f, which return a function g, and g behaves like f(f(f(..... with has indefinite layers.

            Then this is not recursive.

            Now the problem gets simplified - only need to figure out how to define this function g.
            • tail recursive function?
              • key point 是不是用 recursive lambda 实现 tail call 不造成 stack overflow?
                • need to think about the language features to avoid overflow.
                  • ok my bad - 我原以为 compiler 能用类似优化 tail call 的方法来优化 recursive lambda... 不是 cs 科班出身总有些缺课的感觉...
            • If A -> B, B->A, this is still recursion.
    • 这种题要做一个钟头。俸劝改专业吧 +4
      • 人家还只是个一年级的孩子。
    • 这题估计考的是FUNCTIONAL PROGRAMMING 特性。国内大学计算机课程里没学过。 +2
      • 是的,用了FP这道题真不算什么了。