Computing Fibonacci Numbers: Fib (N) 0, 1, Fib (n-2) + Fib (n-1), Ifn 0 Ifn 1 Ifn 1
Computing Fibonacci Numbers: Fib (N) 0, 1, Fib (n-2) + Fib (n-1), Ifn 0 Ifn 1 Ifn 1
Computing Fibonacci Numbers: Fib (N) 0, 1, Fib (n-2) + Fib (n-1), Ifn 0 Ifn 1 Ifn 1
fib(n) =
0,
if n = 0
1,
if n = 1
fib(n-2) + fib(n-1),
if n > 1
COMP 222
Module B Prolog
Chapter 7, Slide 1
Module B Prolog
Chapter 7, Slide 2
fib(4)
1 + fib(2)
0 +1
fib(2)
0 +1
+ fib(3)
1 + fib(2)
0 + 1
COMP 222
Module B Prolog
Chapter 7, Slide 3
COMP 222
X > 1,
X1 is X - 1,
fib(X1, Y2, Y3),
Y1 is Y2 + Y3.
Logic and Programming
Module B Prolog
Chapter 7, Slide 4
COMP 222
Module B Prolog
Chapter 7, Slide 5
COMP 222
Module B Prolog
Chapter 7, Slide 6
Module B Prolog
Chapter 7, Slide 7
COMP 222
Module B Prolog
Chapter 7, Slide 8
COMP 222
Module B Prolog
Chapter 7, Slide 9
0)).
1)).
1)).
2)).
3)).
5)).
8)).
13)).
testFail(fib(-1,_)).
COMP 222
Module B Prolog
Chapter 7, Slide 10
COMP 222
Module B Prolog
Chapter 7, Slide 11
Quick Sorting
quicksort([], []).
quicksort([X | Tail], Sorted) :split(X, Tail, Small, Big),
quicksort(Small, SSmall),
quicksort(Big, SBig),
append(SSmall, [X | SBig], Sorted).
COMP 222
Module B Prolog
Chapter 7, Slide 12
Quick Sorting
split(_X, [], [], []).
split(X, [Y|Tail], [Y|Small], Big) :X >= Y, split(X, Tail, Small, Big).
split(X, [Y|Tail], Small, [Y|Big]) :X < Y, split(X, Tail, Small, Big).
COMP 222
Module B Prolog
Chapter 7, Slide 13
Testing sort
Different ways of saying the same thing:
test(quicksort([3,1,2], [1,2,3])).
test(quicksort([3,1,2], S), [quicksort([3,1,2], [1,2,3])]).
test(quicksort([3,1,2], S), S, [[1,2,3]]).
COMP 222
Module B Prolog
Chapter 7, Slide 14
Testing sort
A handy way that shows you can write testing rules.
test(quicksort(L,X), X, [S]) :- test_sort(L, S).
test_sort([], []).
test_sort([1], [1]).
test_sort([2,1], [1,2]).
test_sort([1,2], [1,2]).
test_sort([3,1,2], [1,2,3]).
test_sort([5,6,1,3,4,7,2],
[1,2,3,4,5,6,7]).
COMP 222
Module B Prolog
Chapter 7, Slide 15
Testing split
test(split(X,L,Sn,Bn), [Sn,Bn], [[S,B]]) :test_split(X,L,S,B).
test_split(3, [3,2,1,4,5,1,7],
[3,2,1,1], [4,5,7]).
test_split(0, [3,2,1,4,5,1,7],
[], [3,2,1,4,5,1,7]).
test_split(1, [], [], []).
test_split(1, [1], [1], []).
test_split(0, [1], [], [1]).
COMP 222
Module B Prolog
Chapter 7, Slide 16
Implementing Test
COMP 222
Module B Prolog
Chapter 7, Slide 17
Implementing Test
soln(G, Ex, Res) :- sort(Ex, Exs),
(Res = Exs
-> (Ex = [] -> print('-') ; print('+'))
; error(G, Exs, Res))
).
failed(G, Ex) :(Ex = []
-> print('-')
; error(G, Ex, []))
).
COMP 222
Module B Prolog
Chapter 7, Slide 18
Implementing Test
testRun :- nl, print('starting testing'), nl, fail.
testRun :- test, fail.
testRun :- nl, print('end of testing'), nl.
test :- test(G, Re, Ex), check(G, Re, Ex).
test :- test(G, Ex), check(G, G, Ex).
test :- test(G), check(G, G, [G]).
test :- testFail(G), check(G, G, []).
COMP 222
Module B Prolog
Chapter 7, Slide 19
Testing sort
test :- test_sort(L, S),
check(quicksort(L,X), [S], X).
test_sort([], []).
test_sort([1], [1]).
test_sort([2,1], [1,2]).
test_sort([1,2], [1,2]).
test_sort([3,1,2], [1,2,3]).
test_sort([5,6,1,3,4,7,2],
[1,2,3,4,5,6,7]).
COMP 222
Module B Prolog
Chapter 7, Slide 20
Merge Sort
merge_pass([], []).
merge_pass([L], [L]).
merge_pass([L1, L2 | L], [M | Ln]) :- merge(L1, L2, M),
merge_pass(L, Ln).
COMP 222
Module B Prolog
Chapter 7, Slide 21