一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 750|回复: 9
收起左侧

[编程题] 求助Scheme编程题

[复制链接] |试试Instant~ |关注本帖
zt7584 发表于 2014-8-24 22:07:35 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
求助一道Scheme编程题,地里有没有同学对Scheme比较熟悉呢?

只能用Scheme语言,或者如果用Scala也可以。小弟初学scheme,感觉很是不开窍啊,求点醒,求解题思路。

1st part:
input: an integer, n
output: a list of pair

for example:
input : n = 2
output: ((2 . 2) (2 . 0) (2 . 1) (1 . 1) (1 . 0) (0 . 0))

2nd part:
find all permutations of the list above
wweerr 发表于 2014-8-26 06:53:59 | 显示全部楼层
本帖最后由 wweerr 于 2014-8-26 07:05 编辑
zt7584 发表于 2014-8-26 06:06
恩啊,多谢,你写的感觉超级简洁,给力。

我自己写了一个version,但是有三个sub function,不过总算 ...

(define (check-link list)
(if (check-if-link)
list
'()))

(define (check-if-link list)
(if ((length list) 1)
#T
(let ((ff (first (first list)))
       (sf (if (eq? 2 (length (first list))) (second (first list)) #F))
       (fs (first (second list)))
       (ss (second (second))))
(if (eq? sf #F)
  (if (eq? ff fs)
       (check-if-link (append (list ss) (rest (rest list))))
       (if (eq? ff ss)
            (check-if-link (append (list fs) (rest (rest list))))
            #f)))
(or (check-if-link (append (list ff) (rest list))))
(check-if-link (append (list sf) (rest list))))))
基本思路就是如果pair里的一个元素已经与之前相连了的话,就把它删掉之后recursive,也就是说input是((1) (2 1) (3 2))这种的,在开始的时候第一个pair里的两个可能都会与后面link上,所以拆成两个做就好了。((1 . 0) (1 . 0) (2 . 1) (0 . 2)) =》 ((1) (1 . 0) (2 . 1) (0 . 2))  or ((0) (1 . 0) (2 . 1) (0 . 2))
我忘记考虑最后一个和第一个相连的问题了,不过改一下就能解决的样子。
回复 支持 1 反对 0

使用道具 举报

Linzertorte 发表于 2014-8-25 00:38:06 | 显示全部楼层
这是找规律吗?我智商低,看不出input与ouput的关系
回复 支持 反对

使用道具 举报

 楼主| zt7584 发表于 2014-8-25 01:20:52 来自手机 | 显示全部楼层
Linzertorte 发表于 2014-8-24 11:38
这是找规律吗?我智商低,看不出input与ouput的关系

哦。。。不好意思,我确实没描述的太清楚,其实就是给一个数n,然后输出一个list,每一个元素是一个pair。
例子就是,如果n=1,就是((1,1)(1,0)(0,0)),如果n是2,就等于说在上面这个list基础上加三个,(2,2)(2,1)(2,0)。就是这么个规律哈,具体这个叫什么问题,我也不知道。。。如果是一般语言,一个循环嵌套就能解决,不过scheme就不知道怎么解决了
回复 支持 反对

使用道具 举报

wweerr 发表于 2014-8-25 01:42:23 | 显示全部楼层
本帖最后由 wweerr 于 2014-8-25 03:01 编辑

写个recrusive的就行了吧,
(define recursive(n)
(if (equal? n 0)
(list (list 0 0))
(else
(append  (map-n (lambda (x) (list n x)) n) (recursive (- n 1))))))

随便写了一下,你大概参考一下。
不知道你了解不了解map-n,我这里的意思是 (map function (list 1 2 ...n)).
回复 支持 反对

使用道具 举报

 楼主| zt7584 发表于 2014-8-25 10:49:21 | 显示全部楼层
wweerr 发表于 2014-8-24 12:42
写个recrusive的就行了吧,
(define recursive(n)
(if (equal? n 0)

谢谢大神指点,我根据你的代码,终于写出了第一部分。

现在开始试着弄一下permutation这个部分~
回复 支持 反对

使用道具 举报

wweerr 发表于 2014-8-25 22:33:58 | 显示全部楼层
zt7584 发表于 2014-8-25 10:49
谢谢大神指点,我根据你的代码,终于写出了第一部分。

现在开始试着弄一下permutation这个部分~

permutation也可以用recursion做

(define (permutation list)
(if (equal? (length permutation) 1)
(list list)
(let ((l (length list))
  (reduce (lambda (a b) (append a b)) (map-n (lambda (n) (map (lambda (x) (append (nth list n) x)) (permutation (remove-nth list n)))) l) '() ))))

但是需要两个subfunction, remove-nth和nth,scheme里有buildin的,但是跟我这里写的可能输出和输入格式不同,你要自己想下。我也不知道我这个到底对不对。
回复 支持 反对

使用道具 举报

 楼主| zt7584 发表于 2014-8-26 06:06:48 | 显示全部楼层
wweerr 发表于 2014-8-25 09:33
permutation也可以用recursion做

(define (permutation list)

恩啊,多谢,你写的感觉超级简洁,给力。

我自己写了一个version,但是有三个sub function,不过总算是原创笨方法哈。我用了一个insert的,没有用remove。

最后还有个problem 3,是判断是否是头尾相连,如果是,返回list,否则返回空list

例如((0 . 0) (0 . 1) (1 . 2) (2 . 0)),就是头尾相连。
((0 . 0) (1 . 0) (2 . 1) (0 . 2)),这个也算是,因为每个pair里面的两个数顺序可以改变。

这个感觉也是递归。。。每次比当前A和后面list的第一个B,A pair的第一个值是不是等于B pair的第一个值或第二个值;还有就是A pair的第二个值是不是等于B pair的第一个值或第二个值;如果有一个等于,就算是能连上了,但是也有可能先决定的会影响后面的决定。。。就有点迷茫了。。。
回复 支持 反对

使用道具 举报

 楼主| zt7584 发表于 2014-8-27 00:43:07 | 显示全部楼层
本帖最后由 zt7584 于 2014-8-26 11:47 编辑
wweerr 发表于 2014-8-25 17:53
(define (check-link list)
(if (check-if-link)
list

嗯啊,我现在在根据你的代码学习摸索中。

最后一个和第一个相连,我想的是就是在list最后加上一个第一个pair就行了。

我还觉得,按你设计的,(0 . 1) (1 . 0)这种是不是处理过后,就是不仅仅是第一个删去一个,而且后面就要删去另一个,因为既然前面选择了0和后面接,后面第一个就是0,然后第二个就必然是1的感觉。有点混乱,也可能我没太研究透你的代码,我再研究一下。
回复 支持 反对

使用道具 举报

 楼主| zt7584 发表于 2014-8-27 03:16:29 | 显示全部楼层
终于搞出来了,一共100行左右代码。。。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 03:01

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表