计算机作业代写需求解析｜Racket程序设计、Quicksort与生成递归—UKThesis

留学生程序设计作业真正难的地方，往往不是把代码“跑通”，而是严格按照课程指定的方法完成设计过程。本文整理的是一份Racket语言Programming assignment要求，涉及Design Recipe、helper functions、lambda、quicksort、struct数据定义以及generative recursion。作业以clue和t-map为核心数据结构，要求学生完成线索排序与按地点分组等函数，同时遵守文件命名、测试和代码风格规范。

对于正在搜索计算机作业代写、程序代写、Racket作业代写、计算机代写、计算机硕士论文代写或Computer Science Assignment辅导的留学生来说，这类题目不能只看最终输出是否正确。老师通常还会检查purpose、contract、examples、tests、helper function位置及递归方式是否符合限制。优客网UKThesis创立于1999年，可围绕程序设计作业提供题目讲解、思路梳理、代码调试、错误定位和学习辅导。本文保留原作业要求，仅清理乱码、分页符和排版问题，不提供可直接提交的完整答案。

Instructions

留学生Racket程序设计作业要求

对于本次及后续Assignment，学生需要使用课程规定的Design Recipe设计所编写的函数，包括所有辅助函数。

不要直接从Assignment Description中复制函数的purpose。Purpose应当使用自己的语言表述，并明确提及函数使用的参数名称。

1. General Requirements

For this and all subsequent assignments, you are expected to use the design recipe for every function you write, including helper functions.

Do not copy the purpose directly from the assignment description. The purpose statement should be written in your own words and should refer explicitly to the parameter names used by your function.

The solutions you submit must be entirely your own work. Do not search for full or partial solutions on the Internet or in printed sources.

Do not send code files to instructors or tutors by email. Course staff will not accept emailed code as an assignment submission and will not debug code sent by email.

Test data used for each question will satisfy the assumptions stated for the values consumed by the function.

Read the course webpage for further information about how to organise and submit your work.

Download the required interface file from the course webpage.

Follow the instructions contained in the course style guide.

Place your solutions in files named a4qY.rkt, where Y is a value from 1 to 4.

A correct final program alone is not sufficient for full marks. You must complete every relevant step of the design recipe, including the definition of constants and helper functions where appropriate.

Read every question carefully and observe all stated restrictions.

2. Recursion and Helper-Function Requirements

If a question requires generative recursion, the submitted solution must contain a genuinely generative recursive element.

Structural recursion, accumulative recursion and abstract list functions may also be used when permitted by the question.

All helper functions should be defined locally inside the main function definition or written using lambda.

Use lambda for small functions that are required only once.

中文说明

这一部分是整份作业最容易丢分的地方。很多同学看到题目要求generative recursion，却提交了一个普通的structural recursion。虽然程序可能也能产生正确结果，但没有按照指定方法完成，仍然可能失分。

同样，题目明确要求辅助函数应当：

定义在主要函数内部；或者

使用lambda表达。

如果把所有helper functions都写成全局函数，即使程序结果正确，也可能不符合Assignment restrictions。

Language Level

Intermediate Student with Lambda

Coverage

Module 4

中文说明

这意味着作业需要在DrRacket指定的Intermediate Student with Lambda语言级别下运行。学生不能随意使用课程尚未讲授的高级语言功能，也不能因为完整Racket更加方便，就擅自修改Language Level。

Useful Structure and Data Definitions

本次Assignment需要使用以下结构和数据定义。请把这些定义包含在对应的solution files中。

(define-struct clue (current points next))

Clue Data Definition

;; A Clue is a structure:
;; (make-clue cur pts nxt)
;;
;; where:
;; cur is a lowercase string representing
;;     the location of the current clue;
;;
;; pts is a natural number representing
;;     the number of points assigned to the clue;
;;
;; nxt is a lowercase string representing
;;     the location of the next clue.

中文说明

clue结构包含三个字段：

current：当前线索所在位置；

points：该线索对应的分值；

next：下一条线索所在的位置。

例如：

(make-clue "hay loft" 10 "shed")

表示当前线索位于"hay loft"，分值为10，下一条线索位于"shed"。

T-Map Data Definition

;; A T-Map is a list of Clue structures representing
;; paths between locations.
;;
;; Two locations A and B are linked in a T-Map when
;; there is a clue in the list whose current location
;; is A and whose next location is B.
;;
;; No clue has the same value for current and next.
;;
;; No two clues have both the same current location
;; and the same number of points.
;;
;; A T-Map may describe multiple paths.
;;
;; No path contains a loop. A loop would occur if
;; the same location were encountered more than once
;; along a path in the T-Map.

中文说明

t-map并不是一个单独的新结构，而是由多个clue结构组成的列表。列表中的线索可以连接成一条或多条路径。

一个合法的t-map需要满足：

current和next不能是同一个地点；

不能有两个clue同时拥有相同的current和points；

一张t-map可以描述多条路径；

任意一条路径都不能出现loop；

同一个地点不能在同一条路径中重复出现。

Example 1: A Valid T-Map

(list
 (make-clue "hay loft" 10 "shed")
 (make-clue "shed" 20 "pool")
 (make-clue "shed" 30 "apple tree")
 (make-clue "barn" 20 "shed"))

这个t-map包含以下四条路径：

"hay loft" → "shed" → "pool"

"hay loft" → "shed" → "apple tree"

"barn" → "shed" → "pool"

"barn" → "shed" → "apple tree"

这些路径都没有包含loop，因为没有任何地点在同一条路径中出现两次。

当路径到达一个没有作为任何clue的current出现的地点时，路径便会终止。在这个例子中，"pool"和"apple tree"都是终点。

Example 2: An Invalid T-Map

(list
 (make-clue "hay loft" 10 "shed")
 (make-clue "shed" 20 "pool")
 (make-clue "pool" 10 "hay loft"))

这个列表包含以下路径：

"hay loft" → "shed" → "pool" → "hay loft"

因为"hay loft"在同一条路径中被重复访问，所以该路径形成了一个loop。这个列表不符合t-map的数据定义，因此不是合法的t-map。

Question 1: Function sort-tm

Write a function named sort-tm that consumes a t-map and produces a new t-map containing the clues from the consumed t-map, sorted alphabetically in increasing order according to the current location of each clue.

If two clues have the same current location, they should be ordered from the highest number of points to the lowest number of points.

Use the built-in quicksort function to implement sort-tm.

Do not use explicit recursion in your solution.

中文要求

编写函数sort-tm。该函数：

消耗一个t-map；

产生一个重新排序后的t-map；

首先按照clue的current地点进行字母升序排列；

如果两个clue的current相同，则按照points从高到低排列；

必须使用内置的quicksort函数；

不允许使用显式递归。

这一题主要考什么？

这一题主要考查学生能否为quicksort编写正确的比较函数。

比较逻辑需要处理两种情况：

两个clue的current不同；

两个clue的current相同。

如果地点不同，应比较地点字符串的字母顺序；如果地点相同，则需要比较points，并让分值较高的clue排在前面。

因为题目明确规定不能使用explicit recursion，所以学生应通过quicksort和适当的比较函数完成排序。

排序规则示例

假设输入为：

(list
 (make-clue "shed" 20 "pool")
 (make-clue "hay loft" 10 "shed")
 (make-clue "shed" 30 "apple tree")
 (make-clue "barn" 20 "shed"))

排序后，current地点的顺序应为：

"barn"
"hay loft"
"shed"
"shed"

两个"shed"位置的clue还需要根据points排序，因此30分的clue应排在20分的clue之前。

注意：以上只用于解释预期顺序，不是可直接提交的完整函数答案。

Question 2: Function group-by-location

Use generative recursion to write a function named group-by-location.

The function consumes a t-map and produces another t-map in which clues sharing the same current location are grouped together.

The groups should appear in the order in which each current location first appears in the consumed list.

Within each group, clues should remain in the same order in which they appeared in the consumed list.

The resulting order is not necessarily alphabetical. Therefore, the output produced by group-by-location may differ from the result produced by sort-tm in Question 1.

中文要求

编写函数group-by-location。该函数：

消耗一个t-map；

产生一个按照current地点分组的新t-map；

current相同的clue必须出现在一起；

各地点组的顺序，按照该地点第一次在输入列表中出现的顺序决定；

每一组内部的clue顺序必须保持不变；

必须使用generative recursion。

Example

输入：

(list
 (make-clue "hay loft" 10 "shed")
 (make-clue "shed" 20 "pool")
 (make-clue "apple tree" 30 "hay loft")
 (make-clue "hay loft" 50 "front steps")
 (make-clue "apple tree" 20 "tree house"))

输出顺序应为：

(list
 (make-clue "hay loft" 10 "shed")
 (make-clue "hay loft" 50 "front steps")
 (make-clue "shed" 20 "pool")
 (make-clue "apple tree" 30 "hay loft")
 (make-clue "apple tree" 20 "tree house"))

为什么是这个顺序？

输入列表中第一次出现的current是：

"hay loft"

因此，所有current为"hay loft"的clue被放在第一组，并且组内仍然保持原来的先后顺序。

第二个第一次出现的地点是：

"shed"

所以"shed"组出现在第二位。

第三个第一次出现的地点是：

"apple tree"

因此，所有"apple tree"的clue被放在最后一组。

最终地点组顺序为：

"hay loft" → "shed" → "apple tree"

这不是字母排序，所以group-by-location的结果不一定与sort-tm相同。

Design Recipe应该包含什么？

题目明确要求所有函数都遵循Design Recipe。对于这类Racket作业，一个较完整的函数设计过程通常包括：

1. Contract

说明函数消耗什么类型的数据，并产生什么类型的数据。

示意格式：

;; function-name: T-Map -> T-Map

2. Purpose

使用自己的语言说明函数完成什么任务，同时提及函数参数的名称。

不能直接复制题目中的句子，也不要只写：

;; sorts a t-map

这样的purpose过于简单，没有说明参数，也没有说明具体排序规则。

3. Examples

提供具有代表性的输入和预期输出。示例应覆盖：

空列表；

只有一个clue的列表；

多个不同地点；

多个相同current地点；

相同地点但points不同的情况。

4. Function Definition

按照题目要求实现函数，并遵守：

Language Level限制；

Recursion限制；

Helper function限制；

Lambda使用要求；

Style Guide要求。

5. Tests

使用check-expect或课程指定的测试方式验证函数。

测试不应只复制题目提供的example，还应增加自己设计的边界情况。

两道题最容易出现的错误

1. 把两种排序要求混在一起

sort-tm要求按照字母顺序排序；group-by-location要求按照地点第一次出现的顺序分组。两者不是同一个问题。

2. 相同地点没有比较points

在sort-tm中，如果两个clue的current相同，必须按照points从高到低排列。

3. 使用了题目禁止的显式递归

Question 1明确要求使用quicksort，不允许explicit recursion。

4. Question 2没有使用生成递归

如果只是对列表进行普通结构递归，即使结果正确，也可能不符合题目规定。

5. 分组后改变了组内顺序

group-by-location要求同一地点组内的clue保持原输入顺序。

6. Helper Functions写在全局作用域

题目要求学生自己创建的辅助函数定义在主函数内部，或者使用lambda。

7. 使用了超出Language Level的功能

完整Racket中可用的函数，不一定能在Intermediate Student with Lambda环境下使用。

8. 只写代码，没有Design Recipe

代码运行正确不等于能够获得满分。缺少contract、purpose、examples和tests通常都会影响成绩。

如何测试自己的程序？

建议至少考虑以下几类测试数据：

Empty t-map；

A t-map containing one clue；

Clues with different current locations；

Clues sharing the same current location；

Clues sharing the same current location but having different points；

A t-map in which the same location appears in several separated positions；

An input list that is already correctly sorted or grouped；

An input list arranged in reverse alphabetical order。

测试的目的不是简单证明函数“能运行”，而是检查每一项题目限制是否都得到了满足。

提交前检查清单

提交之前，可以逐项确认：

文件是否命名为a4qY.rkt；

Language Level是否为Intermediate Student with Lambda；

是否包含题目指定的structure和data definitions；

每个函数是否具有contract；

Purpose是否使用自己的语言编写；

Purpose是否提到对应参数名称；

是否提供examples和tests；

sort-tm是否使用内置quicksort；

Question 1是否避免显式递归；

group-by-location是否包含生成递归元素；

Helper functions是否定义在本地或使用lambda；

是否测试了空列表和重复地点；

是否遵守课程Style Guide；

是否删除了调试过程中遗留的无关代码。

结语

这份程序设计作业表面上只要求完成两个t-map处理函数，实际上同时考查数据定义、函数设计、排序比较、生成递归、局部辅助函数、lambda和测试设计。最容易丢分的情况，不是程序完全不能运行，而是结果虽然正确，却没有遵守题目规定的Design Recipe或递归方法。

对于搜索计算机作业代写、程序代写、Racket作业代写、计算机代写或Computer Science Assignment辅导的留学生来说，真正有价值的帮助应当是讲清楚数据结构、递归思路、错误原因和测试方法，而不是直接提供一份无法解释的提交代码。原题也明确要求提交内容必须由学生独立完成。

优客网UKThesis创立于1999年，可围绕计算机课程作业提供题目翻译、需求分析、程序思路讲解、代码调试、错误定位和写作规范辅导。学生应根据讲解独立完成代码，并确保最终提交内容符合学校关于学术诚信和Assignment submission的要求。