计算机网络——T-MAP的路径树结构的作业要求
12-28, 2012
不要使用任何内置的排序功能，在您的解决方案。使用生成的递归创建一个函数，产生一个T-MAP，所有的在T-MAP的路径树结构。写的函数，创建T-MAP，即消耗一个字符串列表，loclist，没有重复的字符串和自然数，并且产生的t-结合到一个列表中的地图由以下产生的线索算法。使用所提供的功能定义在这个问题产生的firsthalf的的列表和secondhalf的一个列表。
Do not use any built-in sorting function in your solution.
Use generative recursion to create a function that produces a t-map where all the
paths in the t-map follow a tree structure. Write the function, create-t-map, that
consumes a list of strings, loclist, with no duplicate strings, and a natural number,
v, and produces a t-map by combining into a list the clues produced by the following
algorithm. Use the provided functions defined at the end of this question to produce
the firsthalf of a list and the secondhalf of a list.
a. If the length of loclist is 0 or 1, produce the empty list.
b. Otherwise,http://www.ukthesis.org/jsjwl/
i. Define part1 to be the firsthalf of the rest of loclist.
ii. Define part2 to be the secondhalf of the rest of loclist.
iii. Create a clue where the current location is the first location in
loclist and the next location is the first location in part1.
Assign this clue the points v.
iv. If part2 is not empty, create a clue where the current location is the
first location in loclist and the next location is the first location
in part2. Assign this clue the points v+1.
v. Apply create-t-map to part1 and the number 2v.
vi. Apply create-t-map to part2 and the number 3v.
例子
Examples:
(create-t-map
(list "hay loft" "pool" "shed" "apple tree" "old box") 10)
=>
(list
(make-clue "hay loft" 10 "pool")
(make-clue "hay loft" 11 "apple tree")
(make-clue "pool" 20 "shed")
(make-clue "apple tree" 30 "old box")))
(create-t-map
(list "hay loft" "pool" "shed" "apple tree" "old box" "bike") 5)
=>
(list
(make-clue "hay loft" 5 "pool")
(make-clue "hay loft" 6 "old box")
(make-clue "pool" 10 "shed")
(make-clue "pool" 11 "apple tree")
(make-clue "old box" 15 "bike")))
使用下面的功能解决方案中的问题3。包含此代码在您的的解决方案。不要使用直接在你的函数的子列表的功能。它是包括因为它是需要为firsthalf和secondhalf。这些功能应该你的函数内部定义。
Use the following functions in your solution to Question 3. Include this code in your
solution. Do not use the function sublist directly in your function. It is included
because it is needed for firsthalf and secondhalf. These functions should
NOT be included as local definitions within your function.
;; sublist: (listof X) nat nat -> (listof X)
;; Produces the sublist of lst starting at position
;; p1 and ending at position p2-1, using 0-based
;; indexing of positions in the list
;; (It is similar to the function substring for strings.)
;; Examples:
;; (sublist (list 1 2 3) 1 1 ) => empty
;; (sublist (list 1 2 3 4) 0 2) => (list 1 2)
;; (sublist (list 1 2) 0 4) => (list 1 2)
;; (sublist (list 1 2) 2 4) => empty
(define (sublist lst p1 p2)
(cond [(empty? lst) empty]
[(= p1 p2) empty]
[(= p1 0) (cons (first lst) (sublist (rest lst) p1 (sub1 p2)))]
[else (sublist (rest lst) (sub1 p1) (sub1 p2) )]))
;; firsthalf: (listof X) -> (listof X)
;; Produces the first half of the elements of the
;; consumed list lst
;; Examples:
;; (firsthalf empty) => empty
;; (firsthalf (list 1)) => (list 1)
;; (firsthalf (list 1 2)) => (list 1)
;; (firsthalf (list 1 2 3)) => (list 1 2)
;; (firsthalf (list 1 2 3 4)) => (list 1 2)
(define (firsthalf lst)
(local
[(define len (length lst))
;; add 1 if the length is odd
(define odd (cond [(even? len) 0][else 1]))]
(sublist lst 0 (+ (quotient (length lst) 2) odd))))
;; secondhalf: (listof X) -> (listof X)
;; Produces the second half of the elements of the
;; consumed list lst
;; Examples:
;; (secondhalf empty) => empty
;; (secondhalf (list 1)) => empty
;; (secondhalf (list 1 2)) => (list 2)
;; (secondhalf (list 1 2 3)) => (list 3)
(define (secondhalf lst)
(local
[(define len (length lst))
;; add 1 if the length is odd
(define odd (cond [(even? len) 0][else 1]))]
(sublist lst (+ (quotient (length lst) 2) odd) (length lst))))
Note that lst = append (firsthalf lst) (secondhalf lst) always.
4. Use generative recursion to implement the following greedy algorithm for traversing
a path in a t-map and summing the points accumulated on this path. Write a function,
sum-points-on-path,that consumes a t-map and a current location. It should
consider all the clues in the current location and use the one with the highest number
of points to choose a next location. It should recursively consider all clues in this
new location and again follow the one with the highest number of points. The
process terminates when the location reached is not the value for current location in
any clues in the t-map. The function produces the number of points accumulated
along the path.
To test this function, ensure that it consumes a t-map, which is a list of clues with no
loops. Also, no two clues in the list should have the same number of points. Paths
produced by Question 3 satisfy these criteria.
Get expert help on all your writing
立即预定