## Saturday, December 19, 2009

### Order a list as per list using scheme

(define (nth lst1 lst2 n)

(if (= n (car lst2)) (car lst1) (nth (cdr lst1) (cdr lst2) n)))

(define (order lst1 lst2)

(define (order-help n)

(if (> n (length lst1)) '() (cons (nth lst1 lst2 n) (order-help (+ n 1)))))

(order-help 1))

(order '(a b c d e) '(1 2 3 4 5))

; Value 1: (a b c d e)

(order '(a b c d e) '(4 1 2 3 5))

; Value 2: (b c d a e)

(order '(a b c d e) '(5 4 3 2 1))

; Value 3: (e d c b a)

(order '(a b c d e) '(1 5 2 4 3))

; Value 4: (a c e d b)

## Friday, December 18, 2009

### My maximum and minimum procedure in scheme

(max x ...+) → real?

x : real?

Returns the largest of the xs, or +nan.0 if any x is +nan.0. If any x is inexact, the result is coerced to inexact.

Examples:

> (max 1 3 2)

3

> (max 1 3 2.0)

3.0

(min x ...+) → real?

x : real?

Returns the smallest of the xs, or +nan.0 if any x is +nan.0. If any x is inexact, the result is coerced to inexact.

Examples:

> (min 1 3 2)

1

> (min 1 3 2.0)

1.0

My own implementations of max and min also work in the same way, including that fact that (max 1) will return 1 instead of an error that only one number is given. The code for max and min are the same except for the signs.

(define (mymin x . lst)

(define (myleast lst6 last)

(if (null? (cdr (if (pair? lst6) lst6 (list lst6)))) last

(if (<> last (car(cdr lst6))) (myleast (cdr lst6) last) (myleast (cdr lst6) (car (cdr lst6))))))

(myleast lst x))

(mymax 2 3 4 5 6 1)

These procedure demonstrate the simple concept of sending 1 or more arguments to a scheme procedure. The arguments come into the procedure in the form of a list. The operator "." does the trick.

## Wednesday, December 16, 2009

### Scheme program for accumulate - n

(define (accumulate op init lst)

(if (null? lst)

init

(op (car lst)

(accumulate op init

(cdr lst)))))

Implementation 1:

(define (accumulate-n op init seqs)

(if (null? (car seqs))

'()

(cons (accumulate op init (car seqs))

(accumulate-n op init (if (pair? (cdr seqs)) (cdr seqs) (list(cdr seqs)))))))

(accumulate-n + 0 (list (list 1) (list 4 5 6)))

Implementation 2:

(define (accumulate-n op init lst)

(define (accumulate-help lst)

(accumulate op init lst))

(map accumulate-help lst))

(accumulate-n + 0 (list (list 1 2 3) (list 4 5 6) (list 7 8 9)))

## Saturday, December 12, 2009

### 3 Missionaries and 3 cannibals - crossing the river

the same riverbank a boat, that can maximally take 2 persons (minimally 1), lies. The 6 people are

facing a problem: how to optimally transport (minimal number of moves) ourselves from

the current riverbank (the left one) to the opposite bank of the river (the right one) in a way

that guarantees that at any time the number of cannibals never outnumber the number of

missionaries (they will then be eaten)?

The missionaries and cannibal problem is a popular problem used in Artificial intelligence to understand and experiment with search methods. Here is a list of the possible optimal solutions for the various cases

1 cannibal and 1 missionary

Step1:(left 1 1 0 0)

Step2:(right 0 0 1 1)

2 cannibals and 2 missionaries

Solution1:

((left 2 2 0 0) (right 2 0 0 2) (left 2 1 0 1) (right 0 1 2 1) (left 1 1 1 1) (right 0 0 2 2))

Solution2:

((left 2 2 0 0) (right 1 1 1 1) (left 2 1 0 1) (right 0 1 2 1) (left 0 2 2 0) (right 0 0 2 2))

3 cannibals and 3 missionaries

Solution1:

((left 3 3 0 0)

(right 3 1 0 2)

(left 3 2 0 1)

(right 3 0 0 3)

(left 3 1 0 2)

(right 1 1 2 2)

(left 2 2 1 1)

(right 0 2 3 1)

(left 0 3 3 0)

(right 0 1 3 2)

(left 1 1 2 2)

(right 0 0 3 3))

Solution2:

((left 3 3 0 0)

(right 2 2 1 1)

(left 3 2 0 1)

(right 3 0 0 3)

(left 3 1 0 2)

(right 1 1 2 2)

(left 2 2 1 1)

(right 0 2 3 1)

(left 0 3 3 0)

(right 0 1 3 2)

(left 0 2 3 1)

(right 0 0 3 3))

2 cannibals and 3 missionaries

Solution1:

((left 3 2 0 0)

(right 2 1 1 1)

(left 2 2 1 0)

(right 1 1 2 1)

(left 2 1 1 1)

(right 1 0 2 2)

(left 1 1 2 1)

(right 0 0 3 2))

Solution2:

((left 3 2 0 0)

(right 3 0 0 2)

(left 3 1 0 1)

(right 1 1 2 1)

(left 2 1 1 1)

(right 0 1 3 1)

(left 1 1 2 1)

(right 0 0 3 2))

1 cannibal and 2 missionaries

Solution1:

((left 2 1 0 0) (right 0 1 2 0) (left 1 1 1 0) (right 0 0 2 1))

Solution2:

((left 2 1 0 0) (right 0 1 2 0) (left 1 1 1 0) (right 1 0 1 1) (left 2 0 0 1) (right 0 0 2 1))

0 cannibal and 1 missionaries

((left 1 0 0 0) (right 0 0 1 0))

Solutions are not possible for numbers greater than 3 or cases in which cannibals outnumber missionaries.

## Tuesday, December 8, 2009

### Prime number or not program - scheme

test if a number is a prime is to find the number's divisors. If a number *n *is prime then

*n *equals the smallest integral divisor of *n*.

**Below procedure tests if a number is a prime based on the above method.**

**(define (is-prime-help n count) (if (= count 1) #t (if(= (modulo n count) 0) #f (is-prime-help n (- count 1)))))**

**(define (is-prime n) (if(<>**

Another method is related to Fermat’s little theorem:

*If *n *is a prime number and *a *is any positive integer less than *n*, then *a *raised to the*

n*th power is congruent to *a *modulo *n*.*

Two numbers are said to be congruent modulo *n *if they both have the same remainder

when divided by *n*. Trying a random number *a <>**, one can be sure that n is not prime*

if the remainder of *a**n *modulo *n *is not equal to *a*. However, the opposite does not

always hold, i.e. a number *n *is not always prime if the remainder of *a**n *modulo *n *is

equal to *a*. By trying more and more random *a <>**, one can get more confident that n*

is prime. This algorithm is known as the Fermat test.

**Below implements a Fermat test procedure.**

(define a 0)

(define (ftp n k) (cond((= k 0) #t) ((= n 2) #t) ((<>

*
*
## Sunday, December 6, 2009

### How many pins?

In bowling one often uses ten pins positioned on four rows. How many pins are needed for five rows, six rows, or n rows (where n is a positive integer)?

The below procedure calculates the number of pins needed for n rows recurssively.

(define (number-of-pins-rec n)(if(= n 1) n (+ n (number-of-pins-rec(- n 1)))))> (number-of-pins-rec 2)

3

> (number-of-pins-rec 4)

10

> (number-of-pins-rec 5)

15

> (number-of-pins-rec 6)

21

The procedure in a iterative process.

(define (number-of-pins-it-help n sum count)(if (> count n)

sum

(number-of-pins-it-help n

(+ sum count)

(+ count 1))))

(define (number-of-pins-it n)

(number-of-pins-it-help n 0 1))

> (number-of-pins-it 3)

6

> (number-of-pins-it 4)

10

> (number-of-pins-it 5)

15

> (number-of-pins-it 6)

21

> (number-of-pins-it 7)

28

*
Subscribe to:
Posts (Atom)
*

*
*

*
*

*
*