Copyright ©
2005 Suradet Jitprapaikulsarn
สงวนลิขสิทธิ์ 2548 สุรเดช จิตประไพกุลศาล
Mid-term Examination
30 กรกฎาคม 2548 เวลา 09:00 - 12:00 น.
1. (400
คะแนน)
Structure. Solution
File
1.1. (30
คะแนน) เขียน a data
definition ของนาฬิกาแบบ 24 ชั่วโมง
เราจะเรียกมันว่า Clock
A clock is a structure consisting of
- hour as number
- minute as number
- second as number
1.2. (20
คะแนน) เขียนคำสั่งภาษา Scheme สำหรับ data definition ในข้อ 1.1
(define-struct
clock (hour
minute second))
1.3. (30
คะแนน) เขียนตัวอย่างข้อมูล (data
example) ของ data
definition ในข้อ 1.2
(define clock1 (make-clock 12 5 7))
(define clock2 (make-clock 13 7 29))
(define clock3 (make-clock 7 58 34))
1.4. (20
คะแนน) เขียน code
pattern สำหรับ data definition ในข้อ 1.1
(define
(F c)
... (clock-hour c) ...
... (clock-minute c) ...
... (clock-second c) ...)
1.5. (100
คะแนน) เขียนฟังก์ชัน validTime?
เพื่อตรวจดูว่านาฬิกาบอกเวลาที่ถูกต้องหรือไม่ ตัวอย่างเช่น 17:05:48
เป็นเวลาที่ถูกต้อง
แต่ 29:86:74 เป็นเวลาที่ผิด
;----------------------------------------------------------------------------
; @description check whether the clock shows valid time
; @param C a clock
; @return true if the time is valid, false otherwise
; @contract validTime? : clock -> boolean
; @example (validTime? (make-clock 12 5 7)) = true
; @example (validTime? (make-clock 29 79 3)) = false
; @example (validTime? (make-clock 0 0 0)) = true
;----------------------------------------------------------------------------
(define
(validTime? c)
(and (>= (clock-hour c) 0) (< (clock-hour c)
24)
(>= (clock-minute c) 0) (< (clock-minute c) 60)
(>= (clock-second c) 0) (< (clock-second c) 60)))
1.6. (100
คะแนน) เขียนฟังก์ชัน toSeconds
เพื่อแปลงเวลาให้เป็นวินาที ตัวอย่างเช่น
06:25:17 จะเท่ากับ 23117
วินาที
;----------------------------------------------------------------------------
; @description convert the clock time to seconds
; @param c a clock
; @return clock time in seconds
; @contract toSeconds : clock -> number
; @example (toSeconds (make-clock 12 5 7)) = 43507
; @example (toSeconds (make-clock 19 29 3)) = 70143
; @example (toSeconds (make-clock 0 0 0)) = 0
;----------------------------------------------------------------------------
(define
(toSeconds c)
(+ (* (clock-hour c) 3600)
(* (clock-minute c) 60)
(clock-second c)))
1.7. (100
คะแนน) เขียนฟังก์ชัน greaterTime?
เพื่อเปรียบเทียบว่าเวลาของนาฬิกาที่
1 มากกว่าเวลาของนาฬิกาที่ 2 หรือไม่
;----------------------------------------------------------------------------
; @description check if the time in the first clock is greater than the
time
;
in the second clock
; @param C1 the 1st clock
; @param C2 the second clock
; @return true if C1 > C2, false otherwise
; @contract greaterTime? : clock clock -> boolean
; @example (greaterTime? (make-clock 12 5 7) (make-clock 22 4 5)) =
false
; @example (greaterTime? (make-clock 22 5 7) (make-clock 22 4 5)) = true
; @example (greaterTime? (make-clock 12 5 7) (make-clock 3 5 5)) = true
;----------------------------------------------------------------------------
(define
(greaterTime? C1 C2)
(> (toSeconds C1)
(toSeconds C2)))
2. (400
คะแนน) เราสามารถใช้ประยุกต์ใช้หลักการของ list-of-number
ในการสร้างเซ็ตของตัวเลข
เราจะเรียกข้อมูลชนิดนี้ว่า set-of-number. Solution
File
2.1. (30 คะแนน) เขียน a data definition ของ
set-of-number (ใช้ตัวย่อว่า SON)
A set-of-number (SON) is either
- an empty set
or a structure consisting of
- first as number
- rest as set-of-number
2.2. (20 คะแนน) เขียนคำสั่งภาษา Scheme สำหรับ data definition ในข้อ 2.1
(define-struct
SON (first rest))
2.3. (30
คะแนน) เขียนตัวอย่างข้อมูล data example) ของ data
definition ในข้อ 2.2 โดยใช้แต่ตัวเลขในแต่ละหลักจากเลขประจำตัวนิสิต
หมายเหตุ
เช็ตจะมีสมาชิกซ้ำกันไม่ได้
สมมุติว่า
เลขประจำตัวนิสิตคือ 47360365
(define set1 empty)
(define set2 (make-SON 4 empty))
(define set3 (make-SON 7 (make-SON 4 empty)))
(define set4 (make-SON 6 (make-SON 3 (make-SON 7 (make-SON 4 empty)))))
(define set5 (make-SON 0 (make-SON 6 (make-SON 3 (make-SON 7 (make-SON
4 empty))))))
(define set6 (make-SON 5 (make-SON 0 (make-SON 6 (make-SON 3 (make-SON
7 (make-SON 4 empty)))))))
2.4. (20
คะแนน) เขียน code pattern สำหรับ data definition ในข้อ 2.1
(define (F s)
(cond
[(empty? s) ... ]
[else ... (SON-first s) ...
...
(F (SON-rest s)) ...]))
2.5. (100 คะแนน) เขียนฟังก์ชัน isMember?
เพื่อตรวจดูว่าเซ็ตของตัวเลขมีตัวเลขเป็นสมาชิกหรือไม่
;----------------------------------------------------------------------------
; @description check whether a digit is a member of a set of number
; @param N a number to check
; @param S a set of number
; @return true if N is a member of S, false otherwise
; @contract isMember? : number SON -> boolean
; @example (isMember? 5 empty) = false
; @example (isMember? 4 (make-SON 3 (make-SON 4 (make-SON 5 empty)))) =
true
; @example (isMember? 2 (make-SON 7 (make-SON 8 (make-SON 9 empty)))) =
false
;----------------------------------------------------------------------------
(define (isMember? N S)
(cond
[(empty? S) false]
[(eq? N (SON-first S)) true]
[else (isMember? N (SON-rest S))]))
2.6. (100 คะแนน) เขียนฟังก์ชัน isSubset?
เพื่อตรวจดูว่าเซ็ตที่ 1 เป็น subset ของเซ็ตที่ 2
หรือไม่ หมายเหตุ
เช็ตที่ 1 เป็น subset ของเซ็ตที่
2 ก็ต่อเมื่อสมาชิกทุกตัวของเซ็ตที่ 1 เป็นสมาชิกของเซ็ตที่ 2
;----------------------------------------------------------------------------
; @description check if the first set is a subset of the second set
; @param S1 the first set
; @param S2 the second set
; @return true if S1 is a subset of S2, false otherwise
; @contract iSubset? : SON SON -> boolean
; @example (isSubset? empty empty) = true
; @example (isSubset? empty (make-SON 1 (make-SON 2 empty))) = true
; @example (isSubset? (make-SON 1 (make-SON 2 empty)) empty) = false
; @example (isSubset? (make-SON 1 (make-SON 2 empty)) (make-SON 1
(make-SON 2 empty))) = true
; @example (isSubset? (make-SON 2 (make-SON 1 empty)) (make-SON 1
(make-SON 2 empty))) = true
; @example (isSubset? (make-SON 2 (make-SON 3 empty)) (make-SON 1
(make-SON 2 empty))) = false
;----------------------------------------------------------------------------
(define (isSubset? S1 S2)
(cond
[(empty? S1) true]
[else (and (isMember? (SON-first S1) S2)
(isSubset? (SON-rest S1) S2))]))
2.7. (100 คะแนน) เขียนฟังก์ชัน isEquivalent?
เพื่อตรวจดูว่าเซ็ตที่
1 เท่ากับ เซ็ตที่ 2 หรือไม่ หมายเหตุ เช็ตที่ 1
เท่ากับเซ็ตที่ 2
ก็ต่อเมื่อ เซ็ตที่ 1 เป็น subset ของเซ็ตที่
2 และ เซ็ตที่
2 ก็เป็น subset ของเซ็ตที่ 1
;----------------------------------------------------------------------------
; @description check if the first set is equal to the second set
; @param S1 the first set
; @param S2 the second set
; @return true if S1 is equivalent to S2, false otherwise
; @contract iSubset? : SON SON -> boolean
; @example (isEquivalent? empty empty) = true
; @example (isEquivalent? empty (make-SON 1 (make-SON 2 empty))) = true
; @example (isEquivalent? (make-SON 1 (make-SON 2 empty)) empty) = false
; @example (isEquivalent? (make-SON 1 (make-SON 2 empty)) (make-SON 1 (make-SON 2 empty))) = true
; @example (isEquivalent? (make-SON 2 (make-SON 1 empty)) (make-SON 1 (make-SON 2 empty))) = true
; @example (isEquivalent? (make-SON 2 (make-SON 3 empty)) (make-SON 1 (make-SON 2 empty))) = false
;----------------------------------------------------------------------------
(define (isEquivalent? S1 S2)
(and (isSubset? S1 S2)
(isSubset? S2 S1)))