📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 2398| 回复: 9
跳转到指定楼层
上一主题 下一主题
收起左侧

求助Scheme编程题

全局:

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

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

上一篇:帮忙找bug.....多谢,matrix旋转90度那题
下一篇:CC150 1.7把矩阵元素为0的行和列清空
推荐
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))
我忘记考虑最后一个和第一个相连的问题了,不过改一下就能解决的样子。
回复

使用道具 举报

🔗
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行左右代码。。。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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