教育学论文 旅游管理 社会学论文 广告学论文 MBA论文 会计学论文 媒体学 物流学论文 国际商务管理 金融学论文计算机网络
返回首页

计算机网络——T-MAP的路径树结构的作业要求


不要使用任何内置的排序功能,在您的解决方案。使用生成的递归创建一个函数,产生一个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://ukthesiss.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。包含此代码在您的的解决方案。不要使用直接在你的函数的子列表的功能。它是包括因为它是需要为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.
 


------分隔线----------------------------
UK Thesis Base Contacts

24小时在线客服

QQ:77276002

Email:77276002@qq.com

推荐内容