計(jì)算機(jī)網(wǎng)絡(luò)——T-MAP的路徑樹結(jié)構(gòu)的作業(yè)要求
12-28, 2012
不要使用任何內(nèi)置的排序功能，在您的解決方案。使用生成的遞歸創(chuàng)建一個(gè)函數(shù)，產(chǎn)生一個(gè)T-MAP，所有的在T-MAP的路徑樹結(jié)構(gòu)。寫的函數(shù)，創(chuàng)建T-MAP，即消耗一個(gè)字符串列表，loclist，沒有重復(fù)的字符串和自然數(shù)，并且產(chǎn)生的t-結(jié)合到一個(gè)列表中的地圖由以下產(chǎn)生的線索算法。使用所提供的功能定義在這個(gè)問題產(chǎn)生的firsthalf的的列表和secondhalf的一個(gè)列表。
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.mythingswp7.com/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。包含此代碼在您的的解決方案。不要使用直接在你的函數(shù)的子列表的功能。它是包括因?yàn)樗切枰獮閒irsthalf和secondhalf。這些功能應(yīng)該你的函數(shù)內(nèi)部定義。
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
立即預(yù)定