球拍累加器列表功能

2024-02-22

我正在研究创建您可能玩过的 2048 游戏的具体步骤。它位于许多在线网站上。

基本上这个函数所做的就是: 1)所有空格移到后面 2)如果前两个数字相等,则加倍并检查每两个数字

这些是我所坚持的步骤的说明:

设计一个向左滑动的函数,使其运行single使用 APS(累加器传递样式)帮助器传递给定行。您将需要维护两个累加器。第一个累加器记住最后一个未合并的数字。最初,该值为false,这意味着我们还没有看到一个数字。第二个累加器是我们在遇到空格时堆积它们的地方(空格是“-”)。最简单的方法是使用列表来实现此目的,因此它的初始值为空。

一次完成:起初,您可能会认为使用累加器作为解决方案是个好主意。但接下来就出现了顺序问题。您可以使用类似(追加解决方案(列表编号))的方法将新元素添加到当前解决方案的末尾,但是该追加操作是递归的,并且所花费的时间与解决方案列表的长度成正比。如果可以的话,我们绝对希望在 APS 递归期间避免不平凡的操作。相反,您可以决定将新数字添加到当前解决方案的前面(使用 cons),目的是在最后反转解决方案。这肯定比附加方法更好。缺点是需要第二次传递数据才能进行反转。我们希望一次性完成此任务,而且我们可以。因此,最简单、最快的方法就是在退出递归时以正确的顺序构建解决方案。

我在这里添加了一堆检查期望,以便您可以看到它在做什么:

(check-expect (slide-row-left '(2 2 4 -))(list 4 4 '- '-))
(check-expect (slide-row-left '(2 2 - 4))(list 4 4 '- '-))
(check-expect (slide-row-left '(2 - 2 4))(list 4 4 '- '-))
(check-expect (slide-row-left '(- 2 2 4))(list 4 4 '- '-))

(check-expect (slide-row-left '(2 2 2 2))(list 4 4 '- '-))
(check-expect (slide-row-left '(4 2 2 2))(list 4 4 2 '-))
(check-expect (slide-row-left '(2 4 2 2))(list 2 4 4 '-))
(check-expect (slide-row-left '(2 2 4 2))(list 4 4 2 '-))
(check-expect (slide-row-left '(2 2 4 4))(list 4 8 '- '-))

好吧,这就是我所拥有的:

(define (blank? item) (equal? item '-))

(define (slide-row-left b)
  (blank-help (slide-row-left/help b false) '()))

(define (slide-row-left/help ls acc)
  (cond [(empty? ls) acc]
        [(not (equal? (first ls) (first (rest ls)))) 
         (slide-row-left/help (rest (rest ls)) 
           (cons (first (rest ls)) (cons (first ls) acc)))]
        [else (slide-row-left/help (rest (rest ls)) acc)]))

(define (blank-help ls acc)
  (cond [(empty? ls) acc]
        [(blank? (first ls)) (blank-help (rest ls) (cons (first ls) acc))]     
        [else (cons (first ls) (blank-help (rest ls) acc))]))

第一个累加器向左滑动行/帮助创建不会合并的数字列表。它检查第一个数字和第二个数字是否不相等并将它们添加到列表中。如果它们相等(这意味着它们合并为原始数量的两倍),那么它就会重复出现。第二个累加器空白帮助将所有空格 '- 推到列表末尾,因此所有数字都向左移动。

问题是我不知道如何使用这些来合并各个部分,尤其是在一次传递中。

我今晚就要出发了,希望你们明天能回复我。任何帮助都会非常好。这也是为了ISL+


我想我发现了你的问题。坦白说,你还没有完全做到这一点。作业明确指出您必须在从递归返回时建立结果。这是因为你不想reverse在你的程序结束时,或者做一个append在进行尾递归时。

以下是解释每种方法的几个示例:

;; Using an accumulator
(define (double ls acc)
  (if (empty? ls)
      acc
      (double (rest ls) (cons (* 2 (first ls)) acc))))

(double '(1 2 3) '())
;; = '(6 4 2)
;; So you could reverse the result: (reverse '(1 2 3) '()))
;; but this requires looping over the list again!

;; Using append
(define (double2 ls acc)
  (if (empty? ls)
      acc
      (double2 (rest ls) (append acc (list (* 2 (first ls)))))))

(double2 '(1 2 3) '())
;; = '(2 4 6)
;; But the append operation is very expensive and you don't want that!

(define (double3 ls)
  (if (empty? ls)
      '()
      (cons (* 2 (first ls)) (double3 (rest ls)))))

(double3 '(1 2 3))
;; Cons *after* the recursive call.
;; Requires more memory though, becuase you can not do tail call optimisation!
;; Info: http://c2.com/cgi/wiki?TailRecursion

所以对于函数的不同输入slide-row-left/help:

情况 1:前两个数字相等

Input: '(2 2 4 -)结果:'(4 4 '- '-)

您在这里想要做的是对两个第一个元素求和 (4)。然后你想要计算列表的其余部分。列表的其余部分现在还应该包含一个额外的空白,因为对两个元素求和会使列表缩短一个元素。所以你将一个新的空白传递给acc递归调用中的值。因此,您首先要做的是计算列表的其余部分。因此,递归调用(drop ls 2) and (cons '- acc)。这会删除列表中的前 2 个元素。一旦你得到结果(结果将是'(4 '- '-), 你刚才cons你前面的总和。这导致总结果为'(4 4 '- '-).

情况 2:前两个数字不同

Input: '(4 2 2 2)结果:'(4 4 2 '-)

如果前两个数字不同,我们就无能为力。我们从列表中取出第一个数字(4),这给你留下了'(2 2 2)。您不能删除前两个元素,因为第二个和第三个元素可能可以求和。您记住第一个元素并递归调用该函数来计算结果的其余部分。该函数返回并给你'(4 2 '-)。现在你需要做的就是cons第一个元素回到它前面,产生'(4 4 2 '-).

情况3:第一个元素是空白

Input: '(- 2 2 4)结果:'(4 4 '- '-)

如果第一个数字是空白,您将无法对其执行任何操作。你可能会认为在这种情况下case 2适用但不适用。应将空白放在解决方案的背面。但你怎么能这么做呢?简单,将空白放入蓄能器中。正如您很快看到的那样,累加器基本上是列表的末尾。因此,将空白从列表中移开,这使您感到'(2 2 4). Put '-在累加器前面,这使得累加器等于'('- <rest of acc>)并进行递归调用。所以你用列表来称呼它'(2 2 4)和累加器'('- <rest of acc>)。你的递归调用将产生'(4 4 '- '-)。因此,你不必cons它前面的任何东西都不再存在,这只是你的结果。

情况 4:第二个元素为空白

Input: '(2 - 2 4)结果:'(4 4 '- '-)

如果第二个数字是空白,情况就有点棘手了。您必须从列表中删除空白。所以你会想要(2 2 4)。要做到这一点,你可以这样做(cons (first ls) (rest (rest ls)))。空白再次不能被丢弃。您需要将其放在列表的末尾。列表的末尾在哪里?确实,累加器。那么你cons您想要在解决方案后面(空白)的元素acc像这样:(cons (second ls) acc)。同样,您已将空白放在末尾并进行递归调用。无需将任何元素放在递归调用的解决方案前面,以便调用可以给出完整的答案。

情况 5:输入为空

Input: '()结果:acc

如果您的输入为空,则需要返回acc价值。由于您的输入为空,因此您需要返回列表的末尾,我们知道这是acc value.

情况6:输入长度为1

Input: '(4)结果:(cons 4 acc)

如果输入只有一个元素,则无法对其应用任何总和或其他内容。你只有一个元素。所以,结果是该元素,consd 在前面acc.

Source

#lang racket

;; A shorthand for (first (rest ls))
(define (second ls) (first (rest ls)))

(define (blank? item) (equal? item '-))

(define (slide-row-left b)
  (blank-help (slide-row-left/help b '()) '()))

(define (slide-row-left/help ls acc)
  (cond [(empty? ls) acc]
        [(= (length ls) 1) (cons (first ls) acc)]
        ;; When the first element is blank (e.g., '(- 2 4))
        ;; -> Discard the blank
        ;; -> call the function on the rest of the list.
        [(blank? (first ls))
         (slide-row-left/help (rest ls) (cons (first ls) acc))]
        ;; When the second element is blank (e.g., '(2 - 2 4))
        ;; -> Discard the second element
        ;; -> Run the function again with the entire list (without the blank)
        [(blank? (second ls))
         (slide-row-left/help (cons (first ls) (drop ls 2)) (cons (second ls) acc))]        
        ;; If the first two elements are not equal:
        ;; -> drop 1 element from the list
        ;; -> cons this element to the result of the recursive call
        [(not (equal? (first ls) (second ls)))
         (let  ([fst (first ls)]
                [snd (second ls)]
                [rst (rest ls)]) 
           (cons fst (slide-row-left/help rst acc)))]

        ;; If the first two elements are the same:
        ;; -> drop 2 elements from the list
        ;; -> Sum them
        ;; -> cons the sum in front of the recursive call
        [else
         (let  ([fst (first ls)]
                [snd (second ls)]
                [rst (drop ls 2)]) 
           (cons (* 2 snd) (slide-row-left/help rst (cons '- acc))))]))


(define (blank-help ls acc)
  (cond [(empty? ls) acc]
        [(blank? (first ls)) (blank-help (rest ls) (cons (first ls) acc))]     
        [else (cons (first ls) (blank-help (rest ls) acc))]))

(define (check-expect x y)
  (display x)
  (display y)
  (equal? x y))

(check-expect (slide-row-left '(2 2 4 -))(list 4 4 '- '-))
(check-expect (slide-row-left '(2 2 - 4))(list 4 4 '- '-))
(check-expect (slide-row-left '(2 - 2 4))(list 4 4 '- '-))
(check-expect (slide-row-left '(- 2 2 4))(list 4 4 '- '-))

(check-expect (slide-row-left '(2 2 2 2))(list 4 4 '- '-))
(check-expect (slide-row-left '(4 2 2 2))(list 4 4 2 '-))
(check-expect (slide-row-left '(2 4 2 2))(list 2 4 4 '-))
(check-expect (slide-row-left '(2 2 4 2))(list 4 4 2 '-))
(check-expect (slide-row-left '(2 2 4 4))(list 4 8 '- '-))

Edit

The drop函数用于删除n列表的第一个元素。可以如下图实现。但是,您也可以使用(rest (rest ls))反而。为了简洁起见,我使用了它。

drop

(define (drop ls n)
  (cond [(empty? ls)
         ls]
        [(>= 0 n)
         ls]
        [else
         (drop (rest ls) (- n 1))]))
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

球拍累加器列表功能 的相关文章

  • 方案作业

    当我每次得到值 10 时评估以下表达式 lambda x lambda set x x 10 x 0 不过 我只是通过用名称抽象上述过程来进行修改 并在每次值增加 10 时调用 foo define foo lambda x lambda
  • 遍历 Racket 中的字母表中的字母

    我想编写一个程序 将字母表中的字母作为符号进行迭代 并用它们做一些事情 我希望它大致相当于以下 C 代码 for char letter a letter lt z letter printf The letter is c n lette
  • 对方案中的列表进行排序

    如何编写一个排序算法 以升序返回列表 ex 1 3 5 2 9 回报 1 2 3 5 9 大多数Scheme 实现都附带一个对列表进行排序的过程 如果您的实现没有提供这一功能 那么为您提供一个并不困难 下面是快速排序算法的实现 gt def
  • 方案单词列表 eq?

    我有一个问题 我需要查找列表是否等于第二个列表 例如 set eq 1 2 3 1 2 3 gt t set eq 1 2 3 2 3 4 gt f 这些例子在我的程序中是正确的 但这个例子不是 set eq quote quote one
  • 删除重复项并对列表进行排序

    我正在尝试编写一个过程 该过程采用一个可能包含或不包含重复项的列表 然后按排序顺序返回没有重复项的列表 到目前为止我想到的是 define remove duplicated list if null list if car list ca
  • 按方案中的第一个元素对列表列表进行排序

    例如 我正在研究按第一个元素对列表列表进行排序 排序 列表 2 1 6 7 4 3 1 2 4 5 1 1 预期输出 gt 1 1 2 1 6 7 4 3 1 2 4 5 我使用的算法是冒泡排序 我修改了它来处理列表 但是 该代码无法编译
  • 方案 - 列表之和

    我正在尝试实现一个计算 list 的函数 其名称是sum define sum elemList if null elemList car elemList sum cdr elemList 0 上面的实现给出了错误的结果 例如 gt su
  • 球拍、包含、要求和提供不起作用

    我有一个名为 functions rkt 的文件 其中有一些函数 我正在另一个文件中工作 我们将其命名为 working rkt 我在 working rkt 中尝试了以下操作 一一 来使用 functions rkt 中定义的函数 req
  • (Chez) 用于隐藏 lambda 的方案宏

    我想编写一个宏来创建速记语法来隐藏更详细的 lambda 表达式 但我很难理解如何编写宏 我意识到这是反对使用它们的一个论据 给出这个例子 define alist example x 1 2 3 y 4 5 6 z 7 8 9 defin
  • 传递给过程的列表转换为过程内列表的列表

    我正在 DrRacket 上调试这段代码 lang racket define last element on list lambda l cond null l null cdr l car l else last element on
  • 经验丰富的计划者的 get-first、get-next 和 waddle 函数

    define get first lambda l call with current continuation lambda here set leave here waddle l leave quote define get firs
  • 方案:为什么内部定义比外部定义快?

    我尝试运行下面的程序 define odd internal x define even x if zero x t odd internal sub1 x if zero x f even sub1 x define odd extern
  • 如何解释方案表达式 '(a 'b)

    a b 给出答案 a b 当 a 没有绑定 未加引号 时 这是如何工作的 这就是我们计算表达式时发生的情况 a b gt a b The quote 是简写quote http docs racket lang org guide quot
  • 如何获取 SICP、Scheme、练习 2.78 等中的 put 和 get 函数

    我正在尝试在 SICP 中做练习 2 78 但 put 和 get 函数未知 我尝试过多种语言 比如相当大 racket r5rs mit scheme mzscheme等 我什至下载了SICP支持 http www neilvandyke
  • 方案语言:合并两个数字

    如何将列表中的两个整数合并为一个 方案中 例子 11 223 gt 11223 假设列表恰好有两个元素 并且都是数字 define merge numbers lst let 1st number gt string first lst 2
  • Scheme 和 Racket 中嵌套引号的行为

    在 Racket 中编写函数时 我不小心在符号前面放了两个单引号而不是一个 即我不小心写了 a 并发现嵌套引号的一些行为看起来很奇怪 我正在使用 DrRacket 并使用 Racket lang 和 R5RS lang 对此进行了测试 wr
  • Letrec 和可重入延续

    有人告诉我 以下表达式的计算结果为 0 但许多方案的实现将其计算为 1 let cont f letrec x call with current continuation lambda c set cont c 0 y call with
  • Lisp 中的 (定义 (平均 ....))

    我只是在玩scheme lisp 并正在考虑如何纠正我自己的定义average 我不确定如何做一些我认为需要的事情 定义一个接受任意数量参数的过程 计算这些参数 将参数列表传递给 以将它们加在一起 有人有定义的例子吗average 我似乎对
  • 从when语句内的函数返回

    我想做的就是使用 when 语句返回一个值 我想要以下功能 if x return y 我正在尝试使用 when x y 但是when语句并没有以退出函数并返回y的方式进行计算 它只是愉快地继续下一行 有没有办法做到这一点而不需要制作一个看
  • 迭代函数可以调用自身吗?

    当观看下面的 MIT 6 001 课程视频时 讲师在 28 00 将此算法标记为迭代 但是 在 30 27 他说这个算法和实际的 递归 算法都是递归的 该函数正在使用基本情况调用自身 那么这次迭代情况如何 private int itera

随机推荐