A Box is a structure consisting of
   - width as number
   - length as number
   - height as number

struct Box
{
   double width;
   double length;
   double height;
}

Box box1 = { 3, 5, 9 };
Box box2 = { 0, -2, 3 };
Box box3 = { 1, 2, 3 };
Box box4 = { 1, 12, 3 };

... (F b)
{
 ... b.width ...
 ... b.length ...
 ... b.height ...
}

//----------------------------------------------------------------------------
// @description check whether the box is a valid box
// @param b a box
// @return true if the box is valid, false otherwise
// @contract isValidBox : Box -> boolean
// @example isValidBox( {3, 5, 9 } ) = true
// @example isValidBox( {0, -2, 3 } ) = false
// @example isValidBox( {1, 2, 3 } ) = true
//----------------------------------------------------------------------------
bool isValidBox(Box b)
{
    return (b.width > 0) &&
           (b.length > 0) &&
           (b.height > 0);
}

//----------------------------------------------------------------------------
// @description calculate the area of the outside surface of a box
// @param b a box
// @return the area of the outside surface of a box
// @contract surface : Box -> double
// @example surface( {3, 5, 9 } ) = 15*2 + 45*2 + 27*2 = 174
// @example surface( {1, 12, 3 } ) = 12*2 + 36*2 + 3*2 = 82
// @example surface( {1, 2, 3 } ) = 2*2 + 6*2 + 3*2 = 22
//----------------------------------------------------------------------------
double surface(Box b)
{
    return ( (b.width * b.height) +
             (b.height * b.length) +
             (b.width * b.length) ) * 2;
}

//--------------------------------------------------------------------------
// Data Definition
// A binary tree is either
//  - an empty tree
// or a structure consisting of
//  - data as number
//  - left a binary tree
//  - right as as binary tree
//--------------------------------------------------------------------------
struct BTree
{
    int      data;
    BTree    *left;
    BTree    *right;
};

//--------------------------------------------------------------------------
// Data Example
//--------------------------------------------------------------------------
BTree *empty = 0;
BTree tree1 = { 1, empty, empty };
BTree tree2 = { 2, empty, empty };
BTree tree3 = { 3, &tree1, &tree2 };
BTree tree4 = { 4, empty, empty };
BTree tree5 = { 5, empty, empty };
BTree tree6 = { 6, &tree4, &tree5 };
BTree tree7 = { 7, &tree3, &tree6 };
BTree tree8 = { 8, empty, empty };
BTree tree9 = { 9, &tree8, &tree7 };

//----------------------------------------------------------------------------
// @description determine the larger of two numbers
// @param x the first number
// @param y the second number
// @return the larger of the two numbers
// @contract max2 : int int -> int
// @example max2( 2, 3 ) == 3
// @example max2( 5, 3 ) == 5
// @example max2( 2, -3 ) == 2
//----------------------------------------------------------------------------
int max2(int x, int y)
{
    if (x > y)
    {
        return x;
    }
    else
    {
        return y;
    }
}

//----------------------------------------------------------------------------
// @description determine the height of a binary tree
// @param T a binary tree
// @return the height of a binary tree
// @contract height : Box -> int
// @example height( empty ) == 0
// @example height( tree1 ) == 1
// @example height( tree2 ) == 1
// @example height( tree3 ) == 2
// @example height( tree4 ) == 1
// @example height( tree5 ) == 1
// @example height( tree6 ) == 2
// @example height( tree7 ) == 3
// @example height( tree8 ) == 1
// @example height( tree9 ) == 4
//----------------------------------------------------------------------------
int height(BTree * T)
{
    if (T == 0)
    {
        return 0;
    }
    else
    {
        return 1 + max2( height(T->left), height(T->right) );
    }
}

//----------------------------------------------------------------------------
// @description determine whether a binary tree is balanced
// @param T a binary tree
// @return true if every node in T has the difference between the height of
//         the left subtree and the height of the right subtree is not more
//         than 1
// @contract isBalanced : Box -> bool
// @example isBalanced( empty ) == true
// @example isBalanced( tree1 ) == true
// @example isBalanced( tree2 ) == true
// @example isBalanced( tree3 ) == true
// @example isBalanced( tree4 ) == true
// @example isBalanced( tree5 ) == true
// @example isBalanced( tree6 ) == true
// @example isBalanced( tree7 ) == true
// @example isBalanced( tree8 ) == true
// @example isBalanced( tree9 ) == false
//----------------------------------------------------------------------------
bool isBalanced(BTree * T)
{
    if (T == 0)
    {
        return true;
    }
    else
    {
        return (abs(height(T->left) - height(T->right)) <= 1) &&
                isBalanced(T->left) &&
                isBalanced(T->right);
    }
}

;----------------------------------------------------------------------------
; @description concatenate a list of numbers with another list of numbers
; @param L1 a list of numbers
; @param L2 a list of numbers
; @return a new list of numbers
; @contract concatenate : LON LON -> LON
; @example (concatenate empty (cons 1 empty)) = (cons 1 empty)
; @example (concatenate (cons 1 empty) (cons 2 empty)) = (cons 1 (cons 2 empty))
; @example (concatenate (cons 1 (cons 2 empty)) (cons 3 empty)) = (cons 1 (cons 2 (cons 3 empty)))
; @example (concatenate empty (cons 1 (cons 2 empty))) = (cons 1 (cons 2 empty))
;----------------------------------------------------------------------------
(define (concatenate L1 L2)
  (cond
    [(empty? L1) L2]
    [else (cons (first L1) (concatenate (rest L1) L2))]))

;----------------------------------------------------------------------------
; @description convert a binary tree to a list of numbers in an in-order
;              fashion
; @param T a binary tree
; @return a list of numbers
; @contract BT->list : BT -> LON
; @example (BT->list empty) = empty
; @example (BT->list tree1) = (cons 1 empty)
; @example (BT->list tree3) = (cons 1 (cons 3 (cons 2 empty)))
;----------------------------------------------------------------------------
(define (BT->list T)
  (cond
    [(empty? T) empty]
    [else (concatenate (concatenate (BT->list (BT-left T))
                                    (cons (BT-data T) empty))
                       (BT->list (BT-right T)))]))
;----------------------------------------------------------------------------
; @description convert a binary tree to a list of numbers in an pre-order
;              fashion
; @param T a binary tree
; @return a list of numbers
; @contract BT->list : BT -> LON
; @example (BT->list_2 empty) = empty
; @example (BT->list_2 tree1) = (cons 1 empty)
; @example (BT->list_2 tree3) = (cons 1 (cons 3 (cons 2 empty)))
;----------------------------------------------------------------------------
(define (BT->list_2 T)
  (cond
    [(empty? T) empty]
    [else (concatenate (concatenate (cons (BT-data T) empty)
                                    (BT->list_2 (BT-left T)))
                       (BT->list_2 (BT-right T)))]))

;----------------------------------------------------------------------------
; @description convert a binary tree to a list of numbers in an post-order
;              fashion
; @param T a binary tree
; @return a list of numbers
; @contract BT->list : BT -> LON
; @example (BT->list_3 empty) = empty
; @example (BT->list_3 tree1) = (cons 1 empty)
; @example (BT->list_3 tree3) = (cons 1 (cons 2 (cons 3 empty)))
;----------------------------------------------------------------------------
(define (BT->list_3 T)
  (cond
    [(empty? T) empty]
    [else (concatenate (concatenate (BT->list_3 (BT-left T))
                                    (BT->list_3 (BT-right T)))
                       (cons (BT-data T) empty))]))

;----------------------------------------------------------------------------
; @description check whether a list of numbers contains a specific number
; @param L a list of numbers
; @param num a number
; @return true if L contains num, false otherwise
; @contract contain : LON number -> boolean
; @example (contain empty 1) = false
; @example (contain (cons 1 empty) 1) = true
; @example (contain (cons 1 (cons 2 empty)) 2) = true
;----------------------------------------------------------------------------
(define (contain L num)
  (cond
    [(empty? L) false]
    [(eq? (first L) num) true]
    [else (contain (rest L) num)]))

;----------------------------------------------------------------------------
; @description check whether a list of numbers contains duplicate elements
; @param L a list of numbers
; @return true if a list of numbers contains duplicate elements,
;         false otherwise
; @contract hasDuplicate? : BT -> boolean
; @example (hasDuplicate? empty) = false
; @example (hasDuplicate? (cons 1 (cons 2 (cons 1 empty)))) = true
; @example (hasDuplicate? (cons 1 (cons 2 (cons 3 empty)))) = false
;----------------------------------------------------------------------------
(define (hasDuplicate? L)
  (cond
    [(empty? L) false]
    [(contain (rest L) (first L)) true]
    [else (hasDuplicate? (rest L))]))

;----------------------------------------------------------------------------
; @description check whether a binary tree contains duplicate elements
; @param T a binary tree
; @return true if a binary tree contains duplicate elements, false otherwise
; @contract containDuplicate? : BT -> boolean
; @example (containDuplicate? empty) = false
; @example (containDuplicate? tree9) = false
; @example (containDuplicate? (make-BT 1 (make-BT 2 empty empty) (make-BT 1 empty empty))) =  true
;----------------------------------------------------------------------------
(define (containDuplicate? T)
  (hasDuplicate? (BT->list T)))

;----------------------------------------------------------------------------
; @description generate a list of numbers from 1 to a specific number
; @param num a positive number
; @return a list of numbers from 1 to num
; @contract genLON : number -> LON
; @example (genLON_A 0 empty) = empty
; @example (genLON_A 1 empty) = (cons 1 empty)
; @example (genLON_A 2 (cons 3 empty)) = (cons 1 (cons 2 (cons 3 empty)))
;----------------------------------------------------------------------------
(define (genLON_A num acc)
  (cond
    [(<= num 0) acc]
    [else (genLON_A (- num 1) (cons num acc))]))

;----------------------------------------------------------------------------
; @description generate a list of numbers from 1 to a specific number
; @param num a positive number
; @return a list of numbers from 1 to num
; @contract genLON : number -> LON
; @example (genLON 0) = empty
; @example (genLON 1) = (cons 1 empty)
; @example (genLON 3) = (cons 1 (cons 2 (cons 3 empty)))
;----------------------------------------------------------------------------
(define (genLON num)
  (genLON_A num empty))

Last update 19 September 2005, 21:09
Copyright © 2005 Suradet Jitprapaikulsarn
สงวนลิขสิทธิ์ 2548 สุรเดช จิตประไพกุลศาล